An annotated bibliography of combined routing and loading problems
DOI:
https://doi.org/10.2298/YJOR130315032IKeywords:
vehicle routing, loading, two-dimensional packing, three-dimensional packing, traveling salesman, pickup and deliveryAbstract
Transportation problems involving routing and loading at the same time are currently a hot topic in combinatorial optimization. The interest of researchers and practitioners is motivated by the intrinsic difficulty of this research area, which combines two computationally hard problems, and by its practical relevance in important real world applications. This annotated bibliography aims at collecting, in a systematic way, the most relevant results obtained in the area of vehicle routing with loading constraints, with the objective of stimulating further research in this promising area.References
M. Iori and S. Martello. Routing problems with loading constraints. TOP 18:4-27, 2010.
C. D'Ambrosio, A. Lodi, and S. Martello. Combinatorial traveling salesman problem algorithms. In J.J. Cochran, editor, Wiley Encyclopedia of Operations Research and Management Science, pages 738-747. Wiley, Chichester, 2011.
A.N. Letchford and A. Lodi. Mathematical programming approaches to the traveling salesman problem. In J.J. Cochran, editor, Wiley Encyclopedia of Operations Research and Management Science, pages 3239-3248. Wiley, Chichester, 2011.
P. Toth and D. Vigo (eds.). The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002.
B. Golden, S. Raghavan, and E. Wasil (eds.). The Vehicle Routing Problem: Latest Advances and New Challenges, volume 43 of Operations Research/Computer Science Interfaces Series. Springer, Berlin, 2008.
R. Baldacci, P. Toth, and D. Vigo. Exact algorithms for routing problems under vehicle capacity constraints. In D. Bouyssou, S. Martello, and F. Plastria, editors, Surveys in Operations Research II (Invited Surveys from 4OR, 2006-2008), volume 175 of Annals of Operations Research, pages 213-245. Springer US, 2010.
V. Schmid, K.F. Doerner, and G. Laporte. Rich routing problems arising in supply chain management. European Journal of Operational Research, 224:435-448, 2013.
A. Lodi, S. Martello, and M. Monaci. Two-dimensional packing problems: A survey. European Journal of Operational Research, 141:3-13, 2002. A. Lodi, S. Martello, M. Monaci, and D. Vigo. Two-dimensional bin packing problems. In V.Th. Paschos (ed.), Paradigms of Combinatorial Optimization: Problems and New Approaches, ISTE and John Wiley & Sons, pages 107-129, 2010.
G. Wäscher, H. Hauβner, and H. Schumann. An improved typology of cutting and packing problems. European Journal of Operational Research, 183:1109-1130, 2007.
E.G. Coffman, Jr, J. Csirik, G. Galambos, S. Martello, and D. Vigo. Bin Packing Approximation Algorithms: Survey and Classification. In D.-Z. Du, P.M. Pardalos, and R.L. Graham (eds.), Handbook of Combinatorial Optimization, 2nd Edition, Springer, 2013.
L. Junqueira, R. Morabito, and D. SatoYamashita. MIP-based approaches for the container loading problem with multi-drop constraints. Annals of Operations Research, 199:51-75, 2012.
J.L.M. da Silveira, F.K. Miyazawa, and E.C. Xavier. Heuristics for the strip packing problem with unloading constraints. Computers & Operations Research, 40:991-1003, 2013.
S. Ceschia and A. Schaerf. Local search for a multi-drop multi-container loading problem. Journal of Heuristics, 19: 275-294, 2013
M. Iori. Metaheuristic algorithms for combinatorial optimization problems. 4OR, 3:163166, 2005.
M. Iori, J.J. Salazar Gonzalez, and D. Vigo. An exact approach for the vehicle routing problem with two-dimensional loading constraints. Transportation Science, 41:253-264, 2007.
M. Gendreau, M. Iori, G. Laporte, and S. Martello. A tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints. Networks, 51:4-18, 2007.
G. Fuellerer, K.F. Doerner, R. Hartl, and M. Iori. Ant colony optimization for the twodimensional loading vehicle routing problem. Computers & Operations Research, 36:655-673, 2009.
E.E. Zachariadis, C.D. Tarantilis, and C.T. Kiranoudis. A guided tabu search for the vehicle routing problem with two-dimensional loading constraints. European Journal of Operational Research, 195:729-743, 2009
J. Strodl, K.F. Doerner, F. Tricoire, and R.F. Hartl. On index structures in hybrid metaheuristics for routing problems with hard feasibility checks: An application to the 2dimensional loading vehicle routing problem
M.J. Blesa, C. Blum, G. Raidl, A. Roli, and M. Sampels, editors, Hybrid Metaheuristics, volume 6373 of Lecture Notes in Computer Science, pages 160-173. Springer Berlin Heidelberg, 2010.
S.C.H. Leung, J. Zheng, D. Zhang, and X. Zhou. Simulated annealing for the vehicle routing problem with two-dimensional loading constraints. Flexible Services and Manufacturing Journal, 22:61-82, 2010.
S.C.H. Leung, X. Zhou, D. Zhang, and J. Zheng. Extended guided tabu search and a new packing algorithm for the two-dimensional loading vehicle routing problem. Computers & Operations Research, 38:205-215, 2011.
C. Duhamel, P. Lacomme, A. Quilliot, and H. Toussaint. A multi-start evolutionary local search for the two-dimensional loading capacitated vehicle routing problem. Computers & Operations Research, 38:617-640, 2011.
Y. Shen and T. Murata. Pick-up scheduling of two-dimensional loading in vehicle routing problem by using GA. In Proceedings of the International MultiConference of Engineers and Computer Scientists, IMECS 2012, Vol. II, pages 1532-1537, Hong Kong, 2012
S. Khebbache-Hadji, C. Prins, A. Yalaoui, and M. Reghioui. Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows. Central European Journal of Operations Research, 21:307-336, 2013.
S.C.H. Leung, Z. Zhang, D. Zhang, X. Hua, and M.K. Lim. A meta-heuristic algorithm for heterogeneous fleet vehicle routing problems with two-dimensional loading constraints. European Journal of Operational Research, 225:199-210, 2013.
K. Hamdi-Dhaoui, N. Labadie, and A. Yalaoui. Memetic algorithm with population management for the two-dimensional loading vehicle routing problem with partial conflicts. In A.C. Rosa, A.D. Correia, K. Madani, J. Filipe, and J. Kacprzyk, editors, IJCCI 2012 - Proceedings of the 4th International Joint Conference on Computational Intelligence, SciTePress, pages 189-195, 2012.
L. Martínez and C.A. Amaya. A vehicle routing problem with multi-trips and time windows for circular items. Journal of the Operational Research Society, 2013.
M. Gendreau, M. Iori, G. Laporte, and S. Martello. A tabu search algorithm for a routing and container loading problem. Transportation Science, 40:342-350, 2006.
C.D. Tarantilis, E.E. Zachariadis, and C.T. Kiranoudis. A hybrid metaheuristic algorithm for the integrated vehicle routing and three-dimensional container-loading problem. IEEE Transactions on Intelligent Transportation Systems, 10:255-271, 2009.
G. Fuellerer, K.F. Doerner, R. Hartl, and M. Iori. Metaheuristics for vehicle routing problems with three-dimensional loading constraints. European Journal of Operational Research, 201:751-759, 2010.
Y. Tao and F. Wang. A new packing heuristic based algorithm for vehicle routing problem with three-dimensional loading constraints. In 2010 IEEE International Conference on Automation Science and Engineering, CASE 2010, pages 972-977, 2010.
A. Bortfeldt. A hybrid algorithm for the capacitated vehicle routing problem with threedimensional loading constraints. Computers & Operations Research, 39:2248-2257, 2012.
Q. Ruan, Z. Zhang, L. Miao, and H. Shen. A hybrid approach for the vehicle routing problem with three-dimensional loading constraints. Computers & Operations Research, 40:1579-1589, 2013.
L. Miao, Q. Ruan, K. Woghiren, and Q. Ruo. A hybrid genetic algorithm for the vehicle routing problem with three-dimensional loading constraints. RAIRO - Operations Research, 46:63-82, 2012.
W. Zhu, H. Qin, A. Lim, and L. Wang. A two-stage tabu search algorithm with enhanced packing heuristics for the 3L-CVRP and M3L-CVRP. Computers & Operations Research, 39:2178-2195, 2012.
A. Attanasio, A. Fuduli, G. Ghiani, and C. Triki. Integrated shipment dispatching and packing problems: a case study. Journal of Mathematical Modelling and Algorithms, 6:77-85, 2007.
A. Moura and J.F. Oliveira. An integrated approach to vehicle routing and container loading problems. OR Spectrum, 31:775-800, 2009.
A. Moura. A multi-objective genetic algorithm for the vehicle routing with time windows and loading. In A. Bortfeldt, J. Homberger, H. Kopfer, G. Pankratz, and R. Strangmeier, editors, Intelligent Decision Support, pages 187-201. Gabler, Germany, 2008.
G. Koloch and B. Kaminski. Nested vs. joint optimization of vehicle routing problems with three-dimensional loading constraints. Engineering Letters, 18:193-198, 2010.
A. Bortfeldt and J. Homberger. Packing first, routing second - a heuristic for the vehicle routing and loading problem. Computers & Operations Research, 40:873-885, 2013.
K.F. Doerner, G. Fuellerer, M. Gronalt, R. Hartl, and M. Iori. Metaheuristics for vehicle routing problems with loading constraints. Networks, 49:294-307, 2007.
F. Tricoire, K.F. Doerner, R. Hartl, and M. Iori. Heuristic and exact algorithms for the multi-pile vehicle routing problem. OR Spectrum, 33:931-959, 2011.
F. Massen, Y. Deville, and P. Hentenryck. Pheromone-based heuristic column generation for vehicle routing problems with black box feasibility.
N. Beldiceanu, N. Jussien, and E. Pinson, editors, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, volume 7298 of Lecture Notes in Computer Science, pages 260-274. Springer Berlin Heidelberg, 2012.
R. Tadei, G. Perboli, and F. Della Croce. A heuristic algorithm for the auto-carrier transportation problem. Transportation Science, 36:55-62, 2002.
B.M. Miller. Auto Carrier Transporter Loading and Unloading Improvement. PhD thesis, Air Force Institute of Technology, Wright-Patterson Air Force Base, Ohio, 2003.
B.O. Øystebø, L.M. Hvattum, and K. Fagerholt. Routing and scheduling of RoRo ships with stowage constraints. Transportation Research Part C: Emerging Technologies, 19:1225-1242, 2011.
G. Berbeglia, J.-F. Cordeau, I. Gribkovskaia, and G. Laporte. Static pickup and delivery problems: A classiffication scheme and survey. TOP, 15:1-31, 2007.
S.N. Parragh, K.F. Doerner, and R.F. Hartl. A survey on pickup and delivery models. Part I: transportation between customers and depot. Journal für Betriebswirtschaft, 58:21-51, 2008.
S.N. Parragh, K.F. Doerner, and R.F. Hartl. A survey on pickup and delivery models. Part II: transportation between pickup and delivery locations. Journal für Betriebswirtschaft, 58:81-117, 2008.
A. Malapert, C. Guerét, N. Jussien, A. Langevin, and L.-M. Rousseau. Two-dimensional pickup and delivery routing problem with loading constraints. In Proceedings of the First CPAIOR Workshop on Bin Packing and Placement Constraints (BPPC'08), Paris, France, 2008.
T. Bartók and C. Imreh. Pickup and delivery vehicle routing with multidimensional loading constraints. Acta Cybernetica, 20:17-33, 2011.
E.E. Zachariadis, C.D. Tarantilis, and C.T. Kiranoudis. The pallet-packing vehicle routing problem. Transportation Science, 46:341-358, 2012.
S.P. Ladany and A. Mehrez. Optimal routing of a single vehicle with loading constraints. Transportation Planning and Technology, 8:301-306, 1984.
J. Pacheco. Heuristico para los problemas de ruta con carga y descarga en sistemas LIFO. SORT, Statistics and Operations Research Transactions, 21:153-175, 1997.
K. Levitin and R. Abezgaouz. Optimal routing of multiple-load AGV subject to LIFO loading constraints. Computers & Operations Research, 30:397-410, 2003.
H. Xu, Z.-L. Chen, S. Rajagopal, and S. Arunapuram. Solving a practical pickup and delivery problem. Transportation Science, 37:347-364, 2003.
F. Carrabs, J.-F. Cordeau, and G. Laporte. Variable neighbourhood search for the pickup and delivery traveling salesman problem with LIFO loading. INFORMS Journal on Computing, 19:618-623, 2007.
F. Carrabs, R. Cerulli, and J.-F. Cordeau. An additive branch-and-bound algorithm for the pickup and delivery traveling salesman problem with LIFO or FIFO loading. INFOR, 45:223-238, 2007.
J.-F. Cordeau, M. Iori, G. Laporte, and J.J. Salazar González. Branch-and-cut for the pickup and delivery traveling salesman problem with LIFO loading. Networks, 55:46-59, 2010.
Y. Li, A. Lim, W.-C. Oon, H. Qin, and D. Tu. The tree representation for the pickup and delivery traveling salesman problem with LIFO loading. European Journal of Operational Research, 212:482-496, 2011.
G. Erdoğan, J.-F. Cordeau, and G. Laporte. The pickup and delivery traveling salesman problem with first-in-first-out loading. Computers & Operations Research, 36:18001808, 2009.
J.-F. Cordeau, M. Dell'Amico, and M. Iori. Branch-and-cut for the pickup and delivery traveling salesman problem with FIFO loading. Computers & Operations Research, 37:970-980, 2010.
H.L. Petersen and O.B.G. Madsen. The double travelling salesman problem with multiple stacks - Formulation and heuristic solution approaches. European Journal of Operational Research, 198:139-147, 2009.
A. Felipe, M.T. Ortuño, and G. Tirado. The double traveling salesman problem with multiple stacks: A variable neighborhood search approach. Computers & Operations Research, 36:2983-2993, 2009.
A. Felipe, M.T. Ortuño, and G. Tirado. New neighborhood structures for the double traveling salesman problem with multiple stacks. TOP, 17:190-213, 2009.
S. Toulouse and R. Wolfer Calvo. On the complexity of the multiple stack TSP, kSTSP. Lecture Notes in Computer Science, Theory and Applications of Models of Computation, 5532:360-369, 2009.
R.M. Lusby, J. Larsen, M. Ehrgott, and D. Ryan. An exact method for the double TSP with multiple stacks. International Transactions on Operations Research, 17:637-652, 2010.
H.L. Petersen, C. Archetti, and M.G. Speranza. Exact solutions to the double travelling salesman problem with multiple stacks. Networks, 56:229-243, 2010. R.M. Lusby and J. Larsen. Improved exact method for the double TSP with multiple stacks. Networks, 58:290-300, 2011.
A. Felipe, M.T. Ortuño, and G. Tirado. Using intermediate non-feasible solutions to approach vehicle routing problems with precedence and loading constraints. European Journal of Operational Research, 211:66-75, 2011.
F. Bonomo, S. Mattia, and G. Oriolo. Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem. Theoretical Computer Science, 412:6261-6268, 2011.
M. Casazza, A. Ceselli, and M. Nunkesser. Efficient algorithms for the double travelling salesman problem with multiple stacks. Computers & Operations Research, 39:10441053, 2012.
F. Carrabs, R. Cerulli, and M.G. Speranza. A branch-and-bound algorithm for the double travelling salesman problem with two stacks. Networks, 61:58-75, 2013.
M.A. Alba Martínez, J.-F. Cordeau, M. Iori, and M. Dell'Amico. A branch-and-cut algorithm for the double traveling salesman problem with multiple stacks. INFORMS Journal on Computing, 25: 41-55, 2013.
J.-F. Côté, M. Gendreau, and J.-Y. Potvin. Large neighborhood search for the single vehicle pickup and delivery problem with multiple loading stacks. Networks, 60:19-30, 2012.
J.-F. Côté, C. Archetti, M.G. Speranza, M. Gendreau, and J.-Y. Potvin. A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks. Networks, 60:212-226, 2012.
M. Battarra, G. Erdoğan, G. Laporte, and D. Vigo. The traveling salesman problem with pickups, deliveries, and handling costs. Transportation Science, 44:383-399, 2010.
G. Erdoğan, M. Battarra, G. Laporte, and D. Vigo. Metaheuristics for the traveling salesman problem with pickups, deliveries and handling costs. Computers & Operations Research, 39:1074-1086, 2012.
Downloads
Published
Issue
Section
License
Copyright (c) 2013 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
