Routing problems with loading constraints. (English) Zbl 1279.90146
Summary: We consider difficult combinatorial optimization problems arising in transportation logistics when one is interested in optimizing both the routing of vehicles and the loading of goods into them. The separate problems (routing and loading) are already \(\mathcal{NP}\)-hard, and very difficult to solve in practice. A fortiori their combination is extremely challenging and stimulating. Although the specific literature is still quite limited, a first attempt to a systematic view of this field can be useful both to academic researchers and to practitioners. We review vehicle routing problems with two- and three-dimensional loading constraints. Other combinations of routing and special loading constraints arising from industrial applications are also considered.
Keywords:
vehicle routing; loading; two-dimensional packing; three-dimensional packing; traveling salesman; pickup and deliveryReferences:
| [1] | Applegate D, Bixby RE, Chvátal V, Cook W (2007) The traveling salesman: a computational study. Princeton University Press, Princeton · Zbl 1130.90036 |
| [2] | Avella P, Boccia M, Sforza A (2004) Solving a fuel delivery problem by heuristic and exact approaches. Eur J Oper Res 151:170–179 · Zbl 1045.90012 · doi:10.1016/S0377-2217(02)00676-8 |
| [3] | Baker BS, Coffman EG Jr, Rivest RL (1980) Orthogonal packing in two dimensions. SIAM J Comput 9:846–855 · Zbl 0447.68080 · doi:10.1137/0209064 |
| [4] | Baldacci R, Mingozzi A (2009) A unified exact method for solving different classes of vehicle routing problems. Math Program 120:347–380 · Zbl 1180.90260 · doi:10.1007/s10107-008-0218-9 |
| [5] | Baldacci R, Toth P, Vigo D (2007) Recent advances in vehicle routing exact algorithms. 4OR, Q J Oper Res 5:269–298 · Zbl 1160.90312 · doi:10.1007/s10288-007-0063-3 |
| [6] | Baldacci R, Christofides N, Mingozzi A (2008) An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math Program 115:351–385 · Zbl 1279.90139 · doi:10.1007/s10107-007-0178-5 |
| [7] | Baldacci R, Toth P, Vigo D (2010) Exact algorithms for routing problems under vehicle capacity constraints. In: Bouyssou D, Martello S, Plastria F (eds) Operations research II, invited surveys from 4OR, 2006–2008. Annals of operations research, vol 175. Springer, Berlin, pp 213–245 |
| [8] | Battarra M, Erdogan G, Laporte G, Vigo D (2010) The travelling salesman problem with pickups, deliveries and handling costs. Transp Sci. doi: 10.1287/trsc.1100.0316 |
| [9] | Berbeglia G, Cordeau J-F, Gribkovskaia I, Laporte G (2007) Static pickup and delivery problems: a classification scheme and survey. TOP 15:1–31 · Zbl 1121.90001 · doi:10.1007/s11750-007-0009-0 |
| [10] | Bortfeldt A, Mack D (2007) A heuristic for the three-dimensional strip packing problem. Eur J Oper Res 183:1267–1279 · Zbl 1136.90413 · doi:10.1016/j.ejor.2005.07.031 |
| [11] | Boschetti MA (2004) New lower bounds for the three-dimensional finite bin packing problem. Discrete Appl Math 140(1–3):241–258 · Zbl 1069.90085 · doi:10.1016/j.dam.2003.08.004 |
| [12] | Boschetti MA, Mingozzi A (2003a) The two-dimensional finite bin packing problem. Part I: new lower bounds for the oriented case. 4OR 1:27–42 · Zbl 1062.90051 |
| [13] | Boschetti MA, Mingozzi A (2003b) The two-dimensional finite bin packing problem. Part II: new lower and upper bounds. 4OR 1:135–147 · Zbl 1097.90033 |
| [14] | Brown GG, Graves GW (1981) Real-time dispatching of petroleum tank trucks. Manag Sci 27:19–32 · doi:10.1287/mnsc.27.1.19 |
| [15] | Brown GG, Ellis CJ, Graves GW, Ronen D (1987) Realtime, wide area dispatch of Mobil tank trucks. Interfaces 17:107–120 · doi:10.1287/inte.17.1.107 |
| [16] | Brown GG, Goodman CE, Wood RK (1990) Annual scheduling of Atlantic fleet naval combatants. Oper Res 38:249–259 · doi:10.1287/opre.38.2.249 |
| [17] | Caprara A, Monaci M (2009) Bidimensional packing by bilinear programming. Math Program 118:75–108 · Zbl 1169.90428 · doi:10.1007/s10107-007-0184-7 |
| [18] | Carrabs F, Cerulli R, Cordeau J-F (2007a) An additive branch-and-bound algorithm for the pickup and delivery traveling salesman problem with LIFO or FIFO loading. INFOR 45:223–238 |
| [19] | Carrabs F, Cordeau J-F, Laporte G (2007b) Variable neighbourhood search for the pickup and delivery traveling salesman problem with LIFO loading. INFORMS J Comput 19:618–623 · Zbl 1241.90103 · doi:10.1287/ijoc.1060.0202 |
| [20] | Christensen SG, Rousøe DM (2010) Container loading with multi-drop constraints. Int Trans Oper Res 16:727–743 · Zbl 1179.90278 · doi:10.1111/j.1475-3995.2009.00714.x |
| [21] | Christofides N, Mingozzi A, Toth P (1979) The vehicle routing problem. In: Christofides N, Mingozzi A, Toth P, Sandi C (eds) Combinatorial optimization. Wiley, Chichester, pp 315–338 · Zbl 0413.90075 |
| [22] | Clarke G, Wright JV (1964) Scheduling of vehicles from a central depot to a number of delivery points. Oper Res 12:568–581 · doi:10.1287/opre.12.4.568 |
| [23] | Clautiaux F, Jouglet A, Carlier J, Moukrim A (2008) A new constraint programming approach for the orthogonal packing problem. Comput Oper Res 35:944–959 · Zbl 1278.90147 · doi:10.1016/j.cor.2006.05.012 |
| [24] | Coffman EG Jr, Garey MR, Johnson DS (1997) Approximation algorithms for bin packing: a survey. PWS, Boston, pp 46–93 |
| [25] | Coffman EG Jr, Galambos G, Martello S, Vigo D (1999) Bin packing approximation algorithms: Combinatorial analysis. In: Du D-Z, Pardalos PM (eds) Handbook of combinatorial optimization. Kluwer Academic, Dordrecht, pp 151–208 · Zbl 1253.90191 |
| [26] | Cordeau J-F, Gendreau M, Hertz A, Laporte G, Sormany J-S (2005) New heuristics for the vehicle routing problem. In: Langevin A, Riopel D (eds) Logistics systems: design and optimization. Springer, New York, pp 279–297 · Zbl 1130.90416 |
| [27] | Cordeau J-F, Dell’Amico D, Iori M (2010a) Branch-and-cut for the pickup and delivery traveling salesman problem with FIFO loading. Comput Oper Res 37:970–980 · Zbl 1177.90336 · doi:10.1016/j.cor.2009.08.003 |
| [28] | Cordeau J-F, Iori M, Laporte G, Salazar González JJ (2010b) Branch-and-cut for the pickup and delivery traveling salesman problem with LIFO loading. Networks 55:46–59 · Zbl 1206.90137 · doi:10.1002/net.20312 |
| [29] | Cordeau J-F, Laporte G (2004) Tabu search heuristics for the vehicle routing problem. In: Rego C, Alidaee B (eds) Metaheuristic optimization via memory and evolution: tabu search and scatter search. Kluwer Academic, Boston, pp 145–163 |
| [30] | Cordeau J-F, Laporte G, Savelsbergh MWP, Vigo D (1999) Vehicle routing. In: Barnhart C, Laporte G (eds) Transportation. Handbooks in operations research and management science, vol 14. Elsevier, Amsterdam, pp 367–428 |
| [31] | Cornillier F, Boctor FF, Laporte G, Renaud J (2008a) An exact algorithm for the petrol station replenishment problem. J Oper Res Soc 59:607–615 · Zbl 1153.90490 · doi:10.1057/palgrave.jors.2602374 |
| [32] | Cornillier F, Boctor FF, Laporte G, Renaud J (2008b) A heuristic for the multi-period petrol station replenishment problem. Eur J Oper Res 191:295–305 · Zbl 1149.90071 · doi:10.1016/j.ejor.2007.08.016 |
| [33] | Cornillier F, Boctor FF, Laporte G, Renaud J (2009) The petrol station replenishment problem with time windows. Comput Oper Res 36:919–935 · Zbl 1157.90410 · doi:10.1016/j.cor.2007.11.007 |
| [34] | Crainic TG, Perboli G, Tadei R (2008) Extreme point-based heuristics for three-dimensional bin packing. INFORMS J Comput 20:368–384 · Zbl 1243.90088 · doi:10.1287/ijoc.1070.0250 |
| [35] | D’Ambrosio C, Lodi A, Martello S (2010) Combinatorial traveling salesman problem algorithms. In: Cochran JJ (ed) Wiley encyclopedia of operations research and management science. Wiley, Chichester (to appear) |
| [36] | Dantzig GB, Ramser JH (1959) The truck dispatching problem. Manag Sci 6:80 · Zbl 0995.90560 · doi:10.1287/mnsc.6.1.80 |
| [37] | Dell’Amico M, Martello S (1995) Optimal scheduling of tasks on identical parallel processors. ORSA J Comput 7:191–200 · Zbl 0859.90081 |
| [38] | den Boef E, Korst J, Martello S, Pisinger D, Vigo D (2005) Erratum to ”the three-dimensional bin packing problem”: Robot-packable and orthogonal variants of packing problems. Oper Res 53:735–736 · Zbl 1165.90603 · doi:10.1287/opre.1050.0210 |
| [39] | Doerner K, Fuellerer G, Gronalt M, Hartl R, Iori M (2007) Metaheuristics for vehicle routing problems with loading constraints. Networks 49:294–307 · Zbl 1141.90336 · doi:10.1002/net.20179 |
| [40] | Dumitrescu I, Ropke S, Cordeau J-F, Laporte G (2010) The traveling salesman problem with pickup and delivery: polyhedral results and a branch-and-cut algorithm. Math Program, Ser A 121:269–305 · Zbl 1184.90108 · doi:10.1007/s10107-008-0234-9 |
| [41] | Dyckhoff H, Finke U (1992) Cutting and packing in production and distribution. Physica-Verlag, Heidelberg |
| [42] | Erdogan G, Cordeau J-F, Laporte G (1800–1808) The pickup and delivery traveling salesman problem with first-in-first-out loading. Comput Oper Res 36:2009 · Zbl 1179.90280 |
| [43] | Fagerholt K, Christiansen M (2000) A combined ship scheduling and allocation problem. J Oper Res Soc 51:834–842 · Zbl 1055.90549 |
| [44] | Faroe O, Pisinger D, Zachariasen M (2003) Guided local search for the three-dimensional bin packing problem. INFORMS J Comput 15:267–283 · Zbl 1238.90112 · doi:10.1287/ijoc.15.3.267.16080 |
| [45] | Fekete SP, Schepers J, van der Veen JC (2007) An exact algorithm for higher-dimensional orthogonal packing. Oper Res 55:569–587 · Zbl 1167.90483 · doi:10.1287/opre.1060.0369 |
| [46] | Felipe A, Ortuño MT, Tirado G (2009) New neighborhood structures for the double traveling salesman problem with multiple stacks. TOP 17:190–213 · Zbl 1170.90464 · doi:10.1007/s11750-009-0080-9 |
| [47] | Fuellerer G, Doerner K, Hartl R, Iori M (2009) Ant colony optimization for the two-dimensional loading vehicle routing problem. Comput Oper Res 36:655–673 · Zbl 1157.90335 · doi:10.1016/j.cor.2007.10.021 |
| [48] | Fuellerer G, Doerner K, Hartl R, Iori M (2010) Metaheuristics for vehicle routing problems with three-dimensional loading constraints. Eur J Oper Res 201:751 · Zbl 1173.90511 · doi:10.1016/j.ejor.2009.03.046 |
| [49] | Fukasawa R, Longo H, Lysgaard J, Poggi de Aragao M, Reis M, Uchoa E, Werneck RF (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math Program 106:491–511 · Zbl 1094.90050 · doi:10.1007/s10107-005-0644-x |
| [50] | Gendreau M, Hertz A, Laporte G (1994) A tabu search heuristic for the vehicle routing problem. Manag Sci 40:1276–1290 · Zbl 0822.90053 · doi:10.1287/mnsc.40.10.1276 |
| [51] | Gendreau M, Iori M, Laporte G, Martello S (2006) A tabu search algorithm for a routing and container loading problem. Transp Sci 40:342–350 · doi:10.1287/trsc.1050.0145 |
| [52] | Gendreau M, Iori M, Laporte G, Martello S (2007a) Erratum: A tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints. Networks 51:153–153 · Zbl 1180.90021 · doi:10.1002/net.20245 |
| [53] | Gendreau M, Iori M, Laporte G, Martello S (2007b) A tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints. Networks 51:4–18 · Zbl 1146.90012 · doi:10.1002/net.20192 |
| [54] | Golden B, Raghavan S, Wasil E (eds) (2008) The vehicle routing problem: latest advances and new challenges. Operations research/computer science interfaces series, vol 43. Springer, Berlin · Zbl 1142.90004 |
| [55] | Gutin G, Punnen AP (eds) (2002) The traveling salesman and its variations. Kluwer Academic, Dordrecht · Zbl 0996.00026 |
| [56] | Hochbaum DS, Shmoys DB (1987) Using dual approximation algorithms for scheduling problems: practical and theoretical results. J ACM 34:144–162 · doi:10.1145/7531.7535 |
| [57] | Iori M (2005) Metaheuristic algorithms for combinatorial optimization problems. 4OR 3:163–166 · Zbl 1134.90300 · doi:10.1007/s10288-005-0052-3 |
| [58] | Iori M, Martello S, Monaci M (2003) Metaheuristic algorithms for the strip packing problem. In: Pardalos P, Korotkich V (eds) Optimization and industry: new frontiers. Kluwer Academic, Boston, pp 159–179 · Zbl 1051.90030 |
| [59] | Iori M, Salazar González JJ, Vigo D (2007) An exact approach for the vehicle routing problem with two-dimensional loading constraints. Transp Sci 41:253–264 · doi:10.1287/trsc.1060.0165 |
| [60] | Kenmochi M, Imamichi T, Nonobe K, Yagiura M, Nagamochi H (2009) Exact algorithms for the two-dimensional strip packing problem with and without rotations. Eur J Oper Res 198:73–83 · Zbl 1163.90803 · doi:10.1016/j.ejor.2008.08.020 |
| [61] | Ladany SP, Mehrez A (1984) Optimal routing of a single vehicle with loading constraints. Transp Plan Technol 8:301–306 · doi:10.1080/03081068408717261 |
| [62] | Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys D (eds) (1985) The traveling salesman problem. Wiley, Chichester |
| [63] | Letchford AN, Lodi A (2010) Mathematical programming approaches to the traveling salesman problem. In: Cochran JJ (ed) Wiley encyclopedia of operations research and management science. Wiley, Chichester (to appear) |
| [64] | Lodi A, Martello S, Vigo D (1999) Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems. INFORMS J Comput 11:345–357 · Zbl 1034.90500 · doi:10.1287/ijoc.11.4.345 |
| [65] | Lusby R, Larsen J, Ehrgott M, Ryan D (2010) An exact method for the double TSP with multiple stacks. Int Trans Oper Res. doi: 10.1111/j.1475-3995.2009.00748.x · Zbl 1220.90109 |
| [66] | Lysgaard J, Letchford AN, Eglese RW (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math Program 100:423–445 · Zbl 1073.90068 · doi:10.1007/s10107-003-0481-8 |
| [67] | Malapert A, Guerét C, Jussien N, Langevin A, Rousseau L-M (2008) 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 |
| [68] | Martello S, Toth P (1990) Knapsack problems: algorithms and computer implementations. Wiley, Chichester. Available on line at http://www.or.deis.unibo.it/knapsack.html · Zbl 0708.68002 |
| [69] | Martello S, Vigo D (1998) Exact solution of the two-dimensional finite bin packing problem. Manag Sci 44:388–399 · Zbl 0989.90114 · doi:10.1287/mnsc.44.3.388 |
| [70] | Martello S, Pisinger D, Vigo D (2000) The three-dimensional bin packing problem. Oper Res 48:256–267 · Zbl 1106.90371 · doi:10.1287/opre.48.2.256.12386 |
| [71] | Martello S, Pisinger D, Vigo D, Den Boef E, Korst J (2007) Algorithm 864: General and robot-packable variants of the three-dimensional bin packing problem. ACM Trans Math Softw 33:7 · doi:10.1145/1206040.1206047 |
| [72] | Moura A (2008) A multi-objective genetic algorithm for the vehicle routing with time windows and loading. In: Bortfeldt A, Homberger J, Kopfer H, Pankratz G, Strangmeier R (eds) Intelligent decision support. Gabler, Germany, pp 87–201 |
| [73] | Moura A, Oliveira JF (2009) An integrated approach to vehicle routing and container loading problems. OR Spectr 31:775–800 · Zbl 1175.90045 · doi:10.1007/s00291-008-0129-4 |
| [74] | Pacheco J (1997) Heuristico para los problemas de ruta con carga y descarga en sistemas LIFO. SORT, Stat Oper Res Trans 21:153–175 |
| [75] | Parragh SN, Doerner KF, Hartl RF (2008a) A survey on pickup and delivery models. Part I: transportation between customers and depot. J Betriebswirtsch 58:21–51 · doi:10.1007/s11301-008-0033-7 |
| [76] | Parragh SN, Doerner KF, Hartl RF (2008b) A survey on pickup and delivery models. Part II: transportation between pickup and delivery locations. J Betriebswirtsch 58:81–117 · doi:10.1007/s11301-008-0036-4 |
| [77] | Petersen HL, Madsen OBG (2009) The double travelling salesman problem with multiple stacks - formulation and heuristic solution approaches. Eur J Oper Res 198:139–147 · Zbl 1163.90816 · doi:10.1016/j.ejor.2008.08.009 |
| [78] | Petersen H, Archetti C, Speranza MG (2010) Exact solution approaches to the double travelling salesman problem with multiple stacks. Networks. doi: 10.1002/net.20375 |
| [79] | Pisinger D, Sigurd M (2007) Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem. INFORMS J Comput 19:36–51 · Zbl 1241.90118 · doi:10.1287/ijoc.1060.0181 |
| [80] | Reimann M, Doerner K, Hartl RF (2004) D-ants: Savings based ants divide and conquer the vehicle routing problem. Comput Oper Res 31:563–591 · Zbl 1061.90024 · doi:10.1016/S0305-0548(03)00014-5 |
| [81] | Reinelt G (1994) The traveling salesman: computational solutions for TSP applications. Lecture notes in computer science, vol 840. Springer, Berlin · Zbl 0825.90720 |
| [82] | Riff MC, Bonnaire X, Neveu B (2009) A revision of recent approaches for two-dimensional strip-packing problems. Eng Appl Artif Intell 198:823–827 · doi:10.1016/j.engappai.2008.10.025 |
| [83] | Ronen D (1995) Dispatching petroleum products. Oper Res 43:379–387 · Zbl 0839.90076 · doi:10.1287/opre.43.3.379 |
| [84] | Tadei R, Perboli G, della Croce F (2002) A heuristic algorithm for the auto-carrier transportation problem. Transp Sci 36:55–62 · Zbl 1065.90504 · doi:10.1287/trsc.36.1.55.567 |
| [85] | Taillard E, Badeau P, Gendreau M, Guertin F, Potvin J-Y (1997) A tabu search heuristic for the vehicle routing problem with soft time windows. Transp Sci 31:170–186 · Zbl 0886.90070 · doi:10.1287/trsc.31.2.170 |
| [86] | Tarantilis CD, Zachariadis EE, Kiranoudis CT (2009) A hybrid metaheuristic algorithm for the integrated vehicle routing and three-dimensional container-loading problem. IEEE Trans Intell Transp Syst 10:255–271 · doi:10.1109/TITS.2009.2020187 |
| [87] | Toth P, Vigo D (2002) The vehicle routing problem. SIAM monographs on discrete mathematics and applications. SIAM, Philadelphia · Zbl 1060.90065 |
| [88] | Tricoire F, Doerner K, Hartl R, Iori M (2010) Heuristic and exact algorithms for the multi-pile vehicle routing problem. OR Spectrum. doi: 10.1007/s00291-009-0179-2 · Zbl 1229.90039 |
| [89] | van der Bruggen L, Gruson R, Salomon M (1995) Reconsidering the distribution structure of gasoline products for a large oil company. Eur J Oper Res 81:460–473 · doi:10.1016/0377-2217(94)00189-J |
| [90] | Wang F, Tao Y, Shi N (2009) A survey on vehicle routing problem with loading constraints. Int Jt Conf Comput Sci Optim 2:602–606 |
| [91] | Wäscher G, Haußner H, Schumann H (2007) An improved typology of cutting and packing problems. Eur J Oper Res 183:1109–1130 · Zbl 1278.90347 · doi:10.1016/j.ejor.2005.12.047 |
| [92] | Xu H, Chen Z-L, Rajagopal S, Arunapuram S (2003) Solving a practical pickup and delivery problem. Transp Sci 37:347–364 · doi:10.1287/trsc.37.3.347.16044 |
| [93] | Zachariadis EE, Tarantilis CD, Kiranoudis CT (2009) A guided tabu search for the vehicle routing problem with two-dimensional loading constraints. Eur J Oper Res 195:729–743 · Zbl 1155.90331 · doi:10.1016/j.ejor.2007.05.058 |
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.
