A survey on two-echelon routing problems. (English) Zbl 1348.90078
Summary: The delivery of freight from its origin to its destination is often managed through one or more intermediate facilities where storing, merging and consolidation activities are performed. This type of distribution systems is commonly called multi-echelon, where each echelon refers to one level of the distribution network. Multi-echelon distribution systems are often considered by public administrations when implementing their transportation and traffic planning strategies as well as by private companies in their distribution networks. City logistics and multi-modal transportation systems are the most cited examples of multi-echelon distribution systems. Two-echelon distribution systems are a special case of multi-echelon systems where the distribution network comprises two levels. This latter type of distribution systems has inspired an ever growing body of literature in the last few years. This paper provides an overview of two-echelon distribution systems where routes are present at both levels. We consider three classes of problems: the two-echelon location routing problem, the two-echelon vehicle routing problem, and the truck and trailer routing problem. For each class we provide an introduction and survey the foremost related papers that have appeared in the operations research literature.
MSC:
| 90B06 | Transportation, logistics and supply chain management |
| 90-02 | Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming |
| 90B80 | Discrete location and assignment |
Keywords:
literature review; two-echelon distribution systems; two-echelon location routing problems; two-echelon vehicle routing problems; truck and trailer routing problemsReferences:
| [1] | Ambrosino, D.; Scutellá, M. G., Distribution network designnew problems and related models, Eur J Oper Res, 165, 610-624 (2005) · Zbl 1062.90008 |
| [2] | Archetti, C.; Speranza, M. G., The split delivery vehicle routing problem: a survey, (Golden, B. L.; Raghavan, R.; Wasil, E., The vehicle routing problem (2008), Springer), 103-122 · Zbl 1187.90037 |
| [3] | Baldacci, R.; Mingozzi, A.; Roberti, R.; Wolfler Calvo, R., An exact algorithm for the two-echelon capacitated vehicle routing problem, Oper Res, 2, 298-314 (2013) · Zbl 1267.90015 |
| [4] | Belenguer, J.; Benavent, E.; Prins, C.; Prodhon, C.; Wolfler Calvo, R., A branch-and-cut method for the capacitated location-routing problem, Comput Oper Res, 38, 931-941 (2011) · Zbl 1205.90172 |
| [6] | Caramia, M.; Guerriero, F., A heuristic approach for the truck and trailer routing problem, J Oper Res Soc, 61, 1168-1180 (2010) · Zbl 1193.90037 |
| [7] | Caramia, M.; Guerriero, F., A milk collection problem with incompatibility constraints, Interfaces, 40, 130-143 (2010) |
| [8] | Chao, I.-M., A tabu search method for the truck and trailer routing problem, Comput Oper Res, 29, 33-51 (2002) · Zbl 1026.90102 |
| [9] | Chopra, S.; Meindl, P., Supply chain management: strategy, planning, and operation (2009), Prentice Hall |
| [10] | Contardo, C.; Cordeau, J. F.; Gendron, B., A computational comparison of flow formulations for the capacitated location-routing problem, Discret Optim, 10, 263-295 (2013) · Zbl 1474.90373 |
| [11] | Contardo, C.; Crainic, T. G.; Hemmelmayr, V., Lower and upper bounds for the two-echelon capacitated location routing problem, Comput Oper Res, 39, 3215-3228 (2012) · Zbl 1349.90858 |
| [13] | Crainic, T. G.; Mancini, S.; Perboli, G.; Tadei, R., The two-echelon capacitated vehicle routing problema satellite location analysis, Procedia—Social Behav Sci, 2, 5944-5955 (2010) |
| [15] | Crainic, T. G.; Mancini, S.; Perboli, G.; Tadei, R., Impact of generalized travel costs on satellite location in the two-echelon vehicle routing problem, Procedia—Social Behav Sci, 39, 195-204 (2012) |
| [17] | Crainic, T. G.; Ricciardi, N.; Storchi, G., Advanced freight transportation systems for congested urban areas, Transp Res C: Emerging Technol, 12, 119-137 (2004) |
| [18] | Crainic, T. G.; Ricciardi, N.; Storchi, G., Models for evaluating and planning city logistics systems, Transp Sci, 43, 432-454 (2009) |
| [20] | Dalfard, V. M.; Kaveh, M.; Nosratian, N. E., Two meta-heuristic algorithms for two-echelon location-routing problem with vehicle fleet capacity and maximum route length constraints, Neural Comput Appl, 23, 2341-2349 (2013) |
| [21] | Derigs, U.; Pullmann, M.; Vogel, U., Truck and trailer routing—problems, heuristics and computational experience, Comput Oper Res, 40, 536-546 (2013) · Zbl 1349.90083 |
| [22] | Drexl, M., Branch-and-price and heuristic column generation for the generalized truck-and-trailer routing problem, Rev Métodos Cuantitativos para la Economía y la Empresa, 12, 5-38 (2011) |
| [23] | González Feliu, J., Two-echelon freight transport optimizationunifying concepts via a systematic review, Working papers on operations management, 2, 18-30 (2011) |
| [25] | Hamidi, M.; Farahmand, K.; Sajjadi, S. R., Modeling a four-layer location-routing problem, Int J Ind Eng Comput, 3, 43-52 (2012) |
| [26] | Hemmelmayr, V. C.; Cordeau, J. F.; Crainic, T. G., An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics, Comput Oper Res, 39, 3215-3228 (2012) · Zbl 1349.90858 |
| [27] | Infante, D.; Paletta, G.; Vocaturo, F., A ship-truck intermodal transportation problem, Marit Econ Logist, 11, 247-259 (2009) |
| [29] | Jacobsen, S. K.; Madsen, O. B.G., A comparative study of heuristics for a two-level routing-location problem, Eur J Oper Res, 5, 378-387 (1980) · Zbl 0441.90028 |
| [30] | Jepsen, M.; Røpke, S.; Spoorendonk, S., A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem, Transp Sci, 47, 23-37 (2013) |
| [33] | Laporte, G., Fifty years of vehicle routing, Transp Sci, 43, 408-416 (2009) |
| [34] | Lin, S.; Yu, V. F.; Chou, S., Solving the truck and trailer routing problem based on a simulated annealing heuristic, Comput Oper Res, 36, 1683-1692 (2009) · Zbl 1177.90079 |
| [35] | Lin, S.; Yu, V. F.; Chou, S., A note on the truck and trailer routing problem, Expert Syst Appl, 37, 899-903 (2010) |
| [36] | Lin, S.; Yu, V. F.; Lu, C., A simulated annealing heuristic for the truck and trailer routing problem with time windows, Expert Syst Appl, 38, 15244-15252 (2011) |
| [37] | Madsen, O. B.G., Methods for solving combined two level location-routing problems of realistic dimensions, Eur J Oper Res, 12, 295-301 (1983) |
| [38] | Marín, A.; Pelegrín, B., Applying lagrangian relaxation to the resolution of two-stage location problems, Ann Oper Res, 86, 179-198 (1999) · Zbl 0921.90104 |
| [39] | Nagy, G.; Salhi, S., Nested heuristics methods for the location-routing problem, J Oper Res Soc, 47, 1166-1174 (1996) · Zbl 0869.90019 |
| [40] | Nagy, G.; Salhi, S., Location-routingissues, models and methods, Eur J Oper Res, 177, 649-672 (2007) · Zbl 1109.90056 |
| [41] | Nguyen, V.-P.; Prins, C.; Prodhon, C., Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking, Eur J Oper Res, 216, 113-126 (2012) · Zbl 1237.90047 |
| [42] | Nguyen, V.-P.; Prins, C.; Prodhon, C., A multi-start iterated local search with tabu list and path relinking for the two-echelon location-routing problem, Eng Appl Artif Intell, 25, 56-71 (2012) |
| [43] | Nikbakhsh, E.; Zegordi, S. H., A heuristic algorithm and a lower bound for the two-echelon location-routing problem with soft time window constraints, Sci Iran Trans E: Ind Eng, 17, 36-47 (2010) |
| [44] | Perboli, G.; Masoero, F.; Tadei, R., New families of valid inequalities for the two-echelon vehicle routing problem, Electron Notes Discret Math, 36, 639-646 (2010) · Zbl 1237.90023 |
| [45] | Perboli, G.; Tadei, R.; Vigo, D., The two-echelon capacitated vehicle routing problemmodels and math-based heuristics, Transp Sci, 45, 364-380 (2011) |
| [46] | Pirkul, H.; Jayaraman, V., Production, transportation, and distribution planning in a multi-commodity tri-echelon system, Transp Sci, 30, 291-302 (1996) · Zbl 0879.90129 |
| [49] | Semet, F., A two-phase algorithm for the partial accessibility constrained vehicle routing problem, Ann Oper Res, 61, 45-65 (1995) · Zbl 0845.90045 |
| [50] | Semet, F.; Taillard, E., Solving real-life vehicle routing problems efficiently using tabu search, Ann Oper Res, 41, 469-488 (1993) · Zbl 0775.90156 |
| [51] | Scheuerer, S., A tabu search heuristic for the truck and trailer routing problem, Comput Oper Res, 33, 894-909 (2006) · Zbl 1079.90116 |
| [53] | Tragantalerngsak, S.; Holt, J.; Rönnqvist, M., Lagrangian heuristics for the two-echelon, single-source, capacitated facility location problem, Eur J Oper Res, 102, 611-625 (1997) · Zbl 0951.90561 |
| [54] | Tuzun, D.; Burke, L. I., A two-phase tabu search approach for the location routing problem, Eur J Oper Res, 116, 87-99 (1999) · Zbl 1009.90056 |
| [55] | Villegas, J. G.; Prins, C.; Prodhon, C.; Medaglia, A.; Velasco, N., GRASP/VND and multi-start evolutionary local search for the single truck and trailer routing problem with satellite depots, Eng Appl Artif Intell, 23, 780-794 (2010) |
| [56] | Villegas, J. G.; Prins, C.; Prodhon, C.; Medaglia, A.; Velasco, N., A GRASP with evolutionary path relinking for the truck and trailer routing problem, Comput Oper Res, 38, 1319-1334 (2011) · Zbl 1208.90024 |
| [57] | Villegas, J. G.; Prins, C.; Prodhon, C.; Medaglia, A.; Velasco, N., A matheuristic for the truck and trailer routing problem, Eur J Oper Res, 230, 231-244 (2013) · Zbl 1317.90057 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
