Multi Echelon Single and Multi Source Routing Problems
by Ms. Amalia Nikolopoulou, Doctoral Candidate
The increasing market competition and customer-oriented service requirements have forced transportation service providers to explore alternative shipping strategies and redesign their distribution networks. Multi-echelon distribution is an alternative strategy to direct shipping, where shipping and storage of goods downstream from suppliers to demand points takes place via capacitated transshipment facilities, such as warehouses and distribution centers. In this way, lower transportation costs and faster response times are achieved, at the expense of higher inventory costs which increase substantially in a distribution network with multiple echelons. In addition, cross docking has recently appeared as an innovative strategy among multi-echelon networks. Cross docking attempts to minimize inventory costs by reducing warehouses and distribution centers to purely transshipment facilities (cross docks) which do not hold inventory.
Multi-echelon systems have been widely adopted in real-world distribution systems often coupled with hybrid strategies combining direct shipping, warehousing and cross-docking. Examples of multi-echelon distribution schemes can be found in the press (newspaper and magazine), postal, and grocery distribution. Furthermore, this concept is strongly connected to the design of city logistics systems for large cities. The importance of reducing logistics costs has motivated both companies and academic researchers to improve the efficiency of multi-echelon networks. In the literature, most of the studies have addressed facility location problems, where vehicle routing is not explicitly considered at all echelons. Recently, research interest has focused on the optimization of the physical flow of goods involving vehicle routing at all echelons and consolidation decisions at transshipment facilities.
A large category in this field addresses Multi-Echelon Location Routing Problems (NE-LRPs), considering strategic and tactical decisions (Crainic et al. 2011; Nguyen et al. 2012a). In this class of problems, the structure of the distribution system has to be defined by optimizing the number and location of facilities, the vehicle fleet size and the material flow distribution for each echelon. Consolidation decisions at the intermediate facilities and time constraints are not considered. Another broad family of problems is the Multi-Echelon Single and Multi-Source Vehicle Routing Problems (NE-VRPs). In this category, delivery from one or more depots to customers is managed by shipping through intermediate facilities which can be capacitated (Gonzalez-Feliu et al. 2008; Perboli et al. 2008). Time window constraints are usually considered while split deliveries or direct shipping to customers can be handled as well. A closely related problem is the Multi-Source Two-Echelon Vehicle Routing Problems with One Cross Dock (VRPCD). The VRPCD is the problem of delivering products from a set of suppliers to a set of customers via a single cross-dock, using a fleet of homogeneous vehicles (Tarantilis, 2012; Wen et al. 2009). Goods are stored in the cross-dock for a short time, or are directly dispatched to the customers through a consolidation process which allows products to be classified and loaded to the delivery vehicles.
Several solution methods have been proposed for dealing with the complexity associated with multi-echelon and multi-source VRPs. Emphasis so far, has been put on mathematical programming techniques and metaheuristics which capture critical aspects of the problems described above. Given the computational complexity and the combinatorial nature of these problems, hybridization of metaheuristics has recently appeared as a promising area for future research.
Crainic, T. G., Sforza , A., Sterle,C. 2011. Tabu Search Heuristic for a Two-Echelon Location-Routing Problem, Notes in CIRELT
Nguyen, V. P., Prins, C., & Prodhon, C. 2012(a). Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking. European Journal of Operational Research, 216(1), 113-126.
Gonzalez-Feliu, J., Perboli, G. Tadei, R. & Vigo, D. 2008. The two-echelon capacitated vehicle routing problem. Technical Report, OR/02/08, Politecnico di Torino.
Perboli, G., Tadei, R. and Vigo D. 2008. The two-echelon capacitated vehicle routing problem. Publication cirrelt-2008-55, CIRRELT Montreal, Canada; and Transportation Science
Tarantilis, C. D. 2012. Adaptive multi-restart Tabu Search algorithm for the vehicle routing problem with cross-docking. Optimization letters, p.1-14.
Wen, M., Larsen, J., Clausen, J., Cordeau, J.F., and Laporte, G., 2009. Vehicle routing with cross-docking. Journal of the Operational Research Society. Vol. 60, pp. 1708-1718.