Vehicle routing with compartments: applications, modelling and heuristics | OR Spectrum Skip to main content
Springer Nature Link
Log in

Vehicle routing with compartments: applications, modelling and heuristics

  • Regular Article
  • Published:
OR Spectrum Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Archetti C, Speranza M, Hertz A (2006) A tabu search algorithm for the split delivery vehicle routing problem. Transp Sci 40(1): 64–73

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Brown G, Graves G (1981) Real-time dispatch of petroleum tank trucks. Manag Sci 27(1): 19–32

    Article  Google Scholar 

  • Chajakis E, Guignard M (2003) Scheduling deliveries in vehicles with multiple compartments. J Glob Optim 26(1): 43–78

    Article  Google Scholar 

  • 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

    Google Scholar 

  • Clarke G, Wright J (1964) Scheduling of vehicles from a central depot to a number of delivery points. Oper Res 12: 568–581

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Chapter  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

  • 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

    Article  Google Scholar 

  • 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

  • Dror M, Trudeau P (1989) Savings by split delivery routing. Transp Sci 23(2): 141–145

    Article  Google Scholar 

  • Dueck G (1993) New optimization heuristics. J Comput Phys 104(1): 86–92

    Article  Google Scholar 

  • Eilon S, Watson-Gandy C, Christofides N (1971) Distribution management: mathematical modelling and practical analysis. Griffin, London

    Google Scholar 

  • 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

    Article  Google Scholar 

  • Fagerholt K, Christiansen M (2000) A combined ship scheduling and allocation problem. J Oper Res Soc 51(7): 834–842

    Google Scholar 

  • Gillett BE, Miller LR (1974) A heuristic algorithm for the vehicle-dispatch problem. Oper Res 22(2): 340–349

    Article  Google Scholar 

  • Glover F (1989) Tabu search—part I. ORSA J Comput 1(3): 190–206

    Google Scholar 

  • Glover F (1990) Tabu search—part II. ORSA J Comput 2(1): 4–32

    Google Scholar 

  • Glover F, Laguna M, Marti R (2000) Fundamentals of scatter search and path relinking. Control Cybern 39(3): 653–684

    Google Scholar 

  • Hoos HH, Stützle T (2004) Stochastic local search. Foundations and applications. Elsevier/Morgan Kaufmann, San Francisco

    Google Scholar 

  • Jetlund AS, Karimi IA (2004) Improving the logistics of multi-compartment chemical tankers. Comput Chem Eng 28: 1267–1283

    Google Scholar 

  • 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

  • Kirkpatrick S, Gelatt CD Jr, Vecchi MP (1983) Optimization by simulated annealing. Science 220: 671–680

    Article  Google Scholar 

  • Lin S, Kernighan B (1973) An effective heuristic algorithm for the traveling-salesman problem. Oper Res 21(2): 498–516

    Article  Google Scholar 

  • 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

    Google Scholar 

  • Michalewicz Z (1996) Genetic algorithms + data structures = evolution programs, 3rd edn. Springer, Berlin

    Google Scholar 

  • Mladenović N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24(11): 1097–1100

    Article  Google Scholar 

  • 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

    Google Scholar 

  • Muyldermans L, Pang G (2007) On the benefits of co-collection: experiments with a multi-compartment vehicle routing algorithm (submitted)

  • 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

  • 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

  • Pisinger D, Ropke S (2007) A general heuristic for vehicle routing problems. Comput Oper Res 34(8): 2403–2435

    Article  Google Scholar 

  • Potvin J-Y, Rousseau J-M (1995) An exchange heuristic for routing problems with time windows. J Oper Res Soc 46(12): 1433–1446

    Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Shaw P (1998a) A new local search algorithm providing high quality solutions to vehicle routing problems. Technical report, APES group

  • 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

  • Toth P, Vigo D (2002) The vehicle routing problem. SIAM

  • 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

    Article  Google Scholar 

  • Whittley I, Smith G (2004) The attribute based hill climber. J Math Model Algorithm 3(2): 167–178

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Universität zu Köln, Pohligstr. 1, 50969, Köln, Germany

    Ulrich Derigs, Michael Piesche & Ulrich Vogel

  2. SAP AG, Dietmar-Hopp-Allee 16, 69190, Walldorf, Germany

    Jens Gottlieb

  3. SAP Deutschland AG & Co. KG, Hasso-Plattner-Ring 7, 69190, Walldorf, Germany

    Jochen Kalkoff

  4. Universität Mainz, Jakob-Welder-Weg 9, 55128, Mainz, Germany

    Franz Rothlauf

Authors
  1. Ulrich Derigs
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jens Gottlieb
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jochen Kalkoff
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Michael Piesche
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Franz Rothlauf
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Ulrich Vogel
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ulrich Derigs.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Derigs, U., Gottlieb, J., Kalkoff, J. et al. Vehicle routing with compartments: applications, modelling and heuristics. OR Spectrum 33, 885–914 (2011). https://doi.org/10.1007/s00291-010-0194-3

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00291-010-0194-3

Keywords

Search

Navigation