×

Vehicle routing with compartments: applications, modelling and heuristics. (English) Zbl 1229.90021

Summary: Despite the vast amount of literature about vehicle routing problems, only very little attention has been paid to vehicles with compartments that allow transportation of inhomogeneous products on the same vehicle, but in different compartments. We motivate a general vehicle routing problem with compartments that is essential for several industries, like the distribution of food or petrol. We introduce a formal model, an integer program formulation and a benchmark suite of 200 instances. A solver suite of heuristic components is presented, which covers a broad range of alternative approaches for construction, local search, large neighbourhood search and meta-heuristics. The empirical results for the benchmark instances identify effective algorithmic setups as well as essential components for achieving high solution quality. In a comparison on 23 specific and combinatorially less complex instances taken from literature, our algorithm showed to be competitive.

MSC:

90B06 Transportation, logistics and supply chain management
90B20 Traffic problems in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Archetti C, Speranza M, Hertz A (2006) A tabu search algorithm for the split delivery vehicle routing problem. Transp Sci 40(1): 64–73 · doi:10.1287/trsc.1040.0103
[2] Avella P, Boccia M, Sforza A (2004) Solving a fuel delivery problem by heuristic and exact approaches. Eur J Oper Res 152(1): 170–179 · Zbl 1045.90012 · doi:10.1016/S0377-2217(02)00676-8
[3] Bartodziej P, Derigs U, Malcherek D, Vogel U (2009) Models and algorithms for solving combined vehicle and crew scheduling problems with rest constraints: an application to road feeder service planning in air cargo transportation. OR Spectr 31(2): 405–429 · Zbl 1160.90469 · doi:10.1007/s00291-007-0110-7
[4] Brown G, Graves G (1981) Real-time dispatch of petroleum tank trucks. Manag Sci 27(1): 19–32 · doi:10.1287/mnsc.27.1.19
[5] Chajakis E, Guignard M (2003) Scheduling deliveries in vehicles with multiple compartments. J Glob Optim 26(1): 43–78 · Zbl 1053.90006 · doi:10.1023/A:1023067016014
[6] 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
[7] Clarke G, Wright J (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
[8] Cordeau J-F, Gendreau M, Laporte G, Potvin J-Y, Semet F (2002) A guide to vehicle routing heuristics. J Oper Res Soc 53: 512–522 · Zbl 1099.90506 · doi:10.1057/palgrave.jors.2601319
[9] Cordeau J-F, Gendreau M, Hertz A, Laporte G, Sormany J (2005) New heuristics for the vehicle routing problem. In: Langevin A, Riopel D (eds) Logistic systems: design and optimization. Wiley, Chichester, pp 279–298 · Zbl 1130.90416
[10] Cornillier F, Boctor F, Laporte G, Renaud J (2008) A heuristic for the multi-period petrol station replenishment problem. Eur J Oper Res 191(2): 295–305 · Zbl 1149.90071 · doi:10.1016/j.ejor.2007.08.016
[11] Derigs U, Kaiser R (2007) Applying the attribute based hill climber heuristic to the vehicle routing problem. Eur J Oper Res 177(2): 719–732 · Zbl 1109.90011 · doi:10.1016/j.ejor.2005.11.038
[12] Derigs U, Li B, Vogel U (2009) Local search-based metaheuristics for the split delivery vehicle routing problem. J Oper Res Soc. doi: 10.1057/jors.2009.100
[13] Derigs U, Reuter K (2009) A simple and efficient tabu search heuristic for solving the open vehicle routing problem. J Oper Res Soc 60: 1658–1669 · Zbl 1196.90022 · doi:10.1057/jors.2008.107
[14] Derigs U, Vogel U (2009) A computational study on neighborhood search heuristics for the open vehicle routing problem with time windows. In: MIC 2009: the VIII metaheuristics international conference
[15] Dror M, Trudeau P (1989) Savings by split delivery routing. Transp Sci 23(2): 141–145 · Zbl 0668.90044 · doi:10.1287/trsc.23.2.141
[16] Dueck G (1993) New optimization heuristics. J Comput Phys 104(1): 86–92 · Zbl 0773.65042 · doi:10.1006/jcph.1993.1010
[17] Eilon S, Watson-Gandy C, Christofides N (1971) Distribution management: mathematical modelling and practical analysis. Griffin, London
[18] El Fallahi A, Prins C, Wolfler Calvo R (2008) A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem. Comput Oper Res 35(5): 1725–1741 · Zbl 1211.90031 · doi:10.1016/j.cor.2006.10.006
[19] Fagerholt K, Christiansen M (2000) A combined ship scheduling and allocation problem. J Oper Res Soc 51(7): 834–842 · Zbl 1055.90549
[20] Gillett BE, Miller LR (1974) A heuristic algorithm for the vehicle-dispatch problem. Oper Res 22(2): 340–349 · Zbl 0274.90013 · doi:10.1287/opre.22.2.340
[21] Glover F (1989) Tabu search–part I. ORSA J Comput 1(3): 190–206 · Zbl 0753.90054 · doi:10.1287/ijoc.1.3.190
[22] Glover F (1990) Tabu search–part II. ORSA J Comput 2(1): 4–32 · Zbl 0771.90084 · doi:10.1287/ijoc.2.1.4
[23] Glover F, Laguna M, Marti R (2000) Fundamentals of scatter search and path relinking. Control Cybern 39(3): 653–684 · Zbl 0983.90077
[24] Hoos HH, Stützle T (2004) Stochastic local search. Foundations and applications. Elsevier/Morgan Kaufmann, San Francisco
[25] Jetlund AS, Karimi IA (2004) Improving the logistics of multi-compartment chemical tankers. Comput Chem Eng 28: 1267–1283 · doi:10.1016/j.compchemeng.2003.08.009
[26] Kalkoff J (2006) Generierung von Benchmarks und empirische Analyse von Metaheuristiken für Tourenplanungsprobleme mit teilbaren Frachträumen. Diplomarbeit, Lehrstuhl für Wirtschaftsinformatik I, Universität Mannheim
[27] Kirkpatrick S, Gelatt CD Jr, Vecchi MP (1983) Optimization by simulated annealing. Science 220: 671–680 · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[28] Lin S, Kernighan B (1973) An effective heuristic algorithm for the traveling-salesman problem. Oper Res 21(2): 498–516 · Zbl 0256.90038 · doi:10.1287/opre.21.2.498
[29] Lourenço H, Martin O, Stützle T (2002) Iterated local search. In: Glover F, Kochenberger G (eds) Handbook of metaheuristics. Kluwer, Norwell, pp 321–353 · Zbl 1116.90412
[30] Michalewicz Z (1996) Genetic algorithms + data structures = evolution programs, 3rd edn. Springer, Berlin · Zbl 0841.68047
[31] Mladenović N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24(11): 1097–1100 · Zbl 0889.90119 · doi:10.1016/S0305-0548(97)00031-2
[32] Moscato P (1999) Memetic algorithms: a short introduction. In: Corne D, Dorigo M, Glover F (eds) New ideas in optimization. McGraw-Hill, London, pp 219–234
[33] Muyldermans L, Pang G (2007) On the benefits of co-collection: experiments with a multi-compartment vehicle routing algorithm (submitted) · Zbl 1188.90036
[34] Or I (1976) Traveling salesman-type combinatorial problems and their relation to the logistics of blood banking. Ph.D. thesis, Department of Industrial Engineering and Management Sciences, Northwestern University
[35] Piesche M (2007) Entwicklung und Praxistest leistungsfähiger Meta-Heuristiken für das Vehicle Routing Problem mit teilbaren Frachträumen. Diplomarbeit, Seminar für Wirtschaftsinformatik und Operations Research, Universität zu Köln
[36] Pisinger D, Ropke S (2007) A general heuristic for vehicle routing problems. Comput Oper Res 34(8): 2403–2435 · Zbl 1144.90318 · doi:10.1016/j.cor.2005.09.012
[37] Potvin J-Y, Rousseau J-M (1995) An exchange heuristic for routing problems with time windows. J Oper Res Soc 46(12): 1433–1446 · Zbl 0843.90043
[38] Ropke S, Pisinger D (2006) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp Sci 40(4): 455–472 · doi:10.1287/trsc.1050.0135
[39] Schrimpf G, Schneider J, Stamm-Wilbrandt H, Dueck G (2000) Record breaking optimization results using the ruin and recreate principle. J Comput Phys 159: 139–171 · Zbl 0997.90105 · doi:10.1006/jcph.1999.6413
[40] Shaw P (1998a) A new local search algorithm providing high quality solutions to vehicle routing problems. Technical report, APES group
[41] Shaw P (1998b) Using constraint programming and local search methods to solve vehicle routing problems. In: Proceedings CP-98 fourth international conference on principles and practice of constraint programming
[42] Toth P, Vigo D (2002) The vehicle routing problem. SIAM · Zbl 0979.00026
[43] 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(3): 460–473 · doi:10.1016/0377-2217(94)00189-J
[44] Whittley I, Smith G (2004) The attribute based hill climber. J Math Model Algorithm 3(2): 167–178 · Zbl 1092.93035 · doi:10.1023/B:JMMA.0000036583.17284.02
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.