nach oben

EURO Journal on Transportation and Logistics

Erschienen in:

10.01.2015 | Research Paper

Vehicle routing problems for city logistics

verfasst von: Diego Cattaruzza, Nabil Absi, Dominique Feillet, Jesús González-Feliu

Erschienen in: EURO Journal on Transportation and Logistics | Ausgabe 1/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper surveys the vehicle routing problems met in cities for good distribution. It applies the following methodology. First, it gives an overview of the literature devoted to vehicle route optimization in cities. Then, it classifies and analyses urban logistic flows. As a result, it identifies the principal scientific challenges that need to be addressed: time-dependency, multi-level and multi-trip organization of the distribution, dynamic information. Finally, it focuses on each one of these challenges, analyses the main difficulties they imply and how they are treated in the literature.

Vorheriger Artikel An extended demand responsive connector

Nächster Artikel Optimization of a city logistics transportation system with mixed passengers and goods

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Ahn BH, Shinm JY (1991) Vehicle-routing with time windows and time-varying congestion. J Oper Res Soc 42(5):393–400CrossRef

Ambrosini C, Routhier JL (2004) Objectives, methods and results of surveys carried out in the field of urban freight transport: an international comparison. Transp Rev 24(1):57–77CrossRef

Anderson S, Allen J, Browne M (2005) Urban logistics—how can it meet policy makers’ sustainability objectives? J Transp Geogr 13(1):71–81CrossRef

Ando N, Taniguchi E (2006) Travel time reliability in vehicle routing and scheduling with time windows. Netw Spat Econ 6(3):293–311CrossRef

Azi N, Gendreau M, Potvin J-Y (2010) An exact algorithm for a vehicle routing problem with time windows and multiple routes. Eur J Oper Res 202(3):756–763CrossRef

Barkaoui M, Gendreau M (2013) An adaptive evolutionary approach for the real-time vehicle routing and dispatching. Comput Oper Res 40(7):1766–1776CrossRef

Bent R, Van Hentenryck P (2007) Waiting and relocation strategies in online stochastic vehicle routing. In: Proceedings of the 20th international joint conference on Artificial intelligence. pp 3041–3050

Berbeglia G, Cordeau JF, Laporte G (2010) Dynamic pickup and delivery problems. Eur J Oper Res 202(1):8–15CrossRef

Bonnafous A (2001) Les marchandises en ville: le problème méthodologique de l’apréhension statistique. L’intégration des marchandises dans le système des déplacements urbains., Etudes & RecherchesLaboratoire d’economie des transports. Lyon, France, pp 86–91

Boschetti M, Maniezzo V (2014) A set covering based matheuristic for a real-world city logistics problem. Int Trans Oper Res. doi:10.1111/itor.12110

Branke J, Middendorf M, Noeth G, Dessouky M (2005) Waiting strategies for dynamic vehicle routing. Transp Sci 39(3):298–312CrossRef

Browne M, Allen J, Leonardi J (2011) Evaluating the use of an urban consolidation centre and electric vehicles in central london. IATSS Res 35(1):1–6CrossRef

Cattaruzza D, Absi N, Feillet D (2014) The multi-trip vehicle routing problem: a survey. Technical Report 2014–03, Ecole des Mines de Saint-Etienne

Cattaruzza D, Absi N, Feillet D (2014) The multi-trip vehicle routing problem with time windows and release dates. Technical Report 2014–01, Ecole des Mines de Saint-Etienne

Cattaruzza D, Absi N, Feillet D, Vidal T (2014) A memetic algorithm for the multi trip vehicle routing problem. Eur J Oper Res 236(6):833–848CrossRef

Chang TS, Yen HM (2012) City-courier routing and scheduling problems. Eur J Oper Res 223(2):489–498CrossRef

Chen Z-L, Xu H (2006) Dynamic column generation for dynamic vehicle routing with time windows. Transp Sci 40(1):74–88CrossRef

Crainic TG (2008) City Logistics, pages 181–212. Tutorials in Operations Research 2008—state-of-the-Art Decision Making Tools in the Information-Intensive Age. INFORMS

Crainic TG, Gajapl Y, Gendreau M (2012) Multi-zone multi-trip vehicle routing problem with time windows. Technical Report 2012–36, Centre interuniversitaire de recherche sur les réseaux d’enterprise, la logistique et le transport, Université de Montréal, Montréal, QC, Canada

Crainic TG, Mancini S, Perboli G, Tadei R (2008) Clustering-based heuristic for the two-echelon vehicle routing problem. Technical Report 2008–46, Centre interuniversitaire de recherche sur les réseaux d’enterprise, la logistique et le transport, Université de Montréal, Montréal, QC, Canada

Crainic TG, Mancini S, Perboli G, Tadei R (2011) Heuristics for the two-echelon vehicle routing problem: A multi-start approach. Technical Report 2011–16, Centre interuniversitaire de recherche sur les réseaux d’enterprise, la logistique et le transport, Université de Montréal, Montréal, QC, Canada

Crainic TG, Perboli G, Mancini S, Tadei R (2010) Two-echelon vehicle routing problem: a satellite location analysis. Procedia Soc Behav Sci 2(3):5944–5955CrossRef

Crainic TG, Ricciardi N, Storchi G (2004) Advanced freight transportation systems for congested urban areas. Transp Res Part C 12(2):119–137CrossRef

Crainic TG, Ricciardi N, Storchi G (2009) Models for evaluating and planning city logistics systems. Transp Sci 43(4):432–454CrossRef

Cuda R, Guastaroba G, Speranza MG (2014) A survey on two-echelon routing problems. Comput Oper Res. doi:10.1016/j.cor.2014.06.008

Del Pia A, Filippi C (2006) A variable neighborhood descent algorithm for a real waste collection problem with mobile depots. Int Trans Oper Res 13(2):125–141CrossRef

Delaître L, De Barbeyrac C (2012) Improving an urban distribution centre, the french case of samada monoprix. Procedia Soc Behav Sci 39:753–769CrossRef

Donati AV, Montemanni R, Casagrande N, Rizzoli AE, Gambardella LM (2008) Time dependent vehicle routing problem with a multi ant colony system. Eur J Oper Res 185(3):1174–1191CrossRef

Drexl M (2012) Synchronization in vehicle routing—a survey of vrps with multiple synchronization constraints. Transp Sci 46(3):297–316CrossRef

Durand B, Gonzalez-Feliu J (2012) Urban logistics and e-grocery: have proximity delivery services a positive impact on shopping trips? Procedia Soc Behav Sci 39:510–520CrossRef

Egger D, Ruesch M (2002) Best practice handbook year 3—road pricing and urban freight transport urban freight platforms. Technical report, BESTUFS

Ehmke JF (2012) Provision of distance matrices. In: Integration of Information and Optimization Models for Routing in City Logistics, International Series in Operations Research & Management Science. Springer, pp 83–104

Ehmke JF, Mattfeld DC (2010) Data allocation and application for time-dependent vehicle routing in city logistics. Eur Transp 46:24–35

Ehmke JF, Mattfeld DC (2011) Integration of information and optimization models for vehicle routing in urban areas. Procedia Soc Behav Sci 20:110–119CrossRef

Ehmke JF, Meisel S, Mattfeld DC (2012) Floating car based travel times for city logistics. Transp Res Part C 21(1):338–352CrossRef

Ehmke JF, Steinert A, Mattfeld DC (2012) Advanced routing for city logistics service providers based on time-dependent travel times. J Comput Sci 3(4):193–205CrossRef

Figliozzi MA (2012) The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics. Transp ResPart E 48(3):616–636CrossRef

Fleischmann B (1990) The vehicle routing problem with multiple use of vehicles. Technical report, Fachbereich Wirtschaftswissenschaften, Universität Hamburg

Fleischmann B, Gietz M, Gnutzmann S (2004) Time-varying travel times in vehicle routing. Transp Sci 38(2):160–173CrossRef

Fleischmann B, Gnutzmann S, Sandvoß E (2004) Dynamic vehicle routing based on online traffic information. Transp Sci 38(4):420–433CrossRef

Ghiani G, Guerriero F, Laporte G, Musmanno R (2003) Real-time vehicle routing: Solutions concepts, algorithms and parallel computing strategies. Eur J Oper Res 151(1):1–11CrossRef

Gonzalez-Feliu J (2008) Models and methods for the City Logistic. The Two-Echelon Capacitated Vehicle Routing Problem. Ph.D. thesis, Politecnico di Torino

Gonzalez-Feliu J (2013) Vehicle routing in multi-echelon distribution systems with cross-docking: a systematic lexical-metanarrative analysis. Comput Inf Sci 6(3):28–47

Gonzalez-Feliu J, Ambrosini C, Pluvinet P, Toilier F, Routhier JL (2012) A simulation framework for evaluating the impacts of urban goods transport in terms of road occupancy. J Comput Sci 6(4):206–215CrossRef

Gonzalez-Feliu J, Toilier F, Ambrosini C, Routhier JL (2014) Estimated data production for urban goods transport diagnosis. The freturb methodology. Sustainable urban logistics: concepts., methods and information systems. Springer, Berlin, pp 113–143

Grangier P, Gendreau M, Lehuédé F, Rousseau L-M (2014) An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization. Technical Report 2014–33, Centre interuniversitaire de recherche sur les réseaux d’enterprise, la logistique et le transport, Université de Montréal, Montréal, QC, Canada

Grzybowska H, Barceló J (2012) Decision support system for real-time urban freight management. Procedia Soc Behav Sci 39:712–725CrossRef

Güner AR, Murat A, Chinnam RB (2012) Dynamic routing under recurrent and non-recurrent congestion using real-time its information. Comput Oper Res 39(2):358–373CrossRef

Hashimoto H, Yagiura M, Ibaraki T (2008) An iterated local search algorithm for time-dependent vehicle routing problem with time windows. Discrete Optim 5(2):434–456CrossRef

Hasle G, Kloster O (2007) Geometric modelling, numerical simulation, and optimization. In: Operations Research Computer Science Interfaces. Springer, pp 397–436

Hemmelmayr VC, Cordeau JF, Crainic TG (2012) An adaptive large neighbourhood search heuristic for two-echelon vehicle routing problems arising in city logistics. Comput Oper Res 39(12):3215–3228CrossRef

Hernandez F, Feillet D, Giroudeau R, Naud O (2013) A new exact algorithm to solve the multi-trip vehicle routing problem with time windows and limited duration. 4OR. doi:10.1007/s10288-013-0238-z

Hill AV, Benton WC (1992) Modelling intra-city time-dependent travel speeds for vehicle scheduling problems. J Oper Res Soc 43(4):343–351CrossRef

Hitchcock FL (1941) The distribution of a product from several sources to numerous facilities. J Math Phys 20(2):224–230CrossRef

Ichoua S, Gendreau M, Potvin J-Y (2000) Diversion issues in real-time vehicle dispatching. Transp Sci 34(4):426–438CrossRef

Ichoua S, Gendreau M, Potvin J-Y (2003) Vehicle dispatching with time-dependent travel times. Eur J Oper Res 144(2):379–396CrossRef

Ichoua S, Gendreau M, Potvin J-Y (2006) Exploiting knowledge about future demands for real-time vehicle dispatching. Transp Sci 40(2):211–225CrossRef

Ichoua S, Gendreau M, Potvin J-Y (2007) Planned Route Optimization for Real-Time Vehicle Routing. Springer, pp 1–18

Jepsen M, Spoorendonk S, Ropke S (2013) A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem. Transp Sci 4(1):23–37CrossRef

Kim S, Lewis M, White C (2005) Optimal vehicle routing with real-time traffic information. Intell Transp Syst IEEE Trans 6(2):178–188CrossRef

Kok AL, Hans EW, Shutten JMJ (2009) Vehicle routing under time-dependent travel times: the impact of congestion avoidance. In: Technical Report 267, Beta Research School for Operations Management and Logistics, University of Twente

Kok AL, Hans EW, Shutten JMJ, Zijm WHM (2010) A dynamic programming heuristic for a vehicle routing with time-dependent travel times and required breaks. Flex Serv Manuf J 22(1–2):83–108CrossRef

Kritzinger S, Doerner KF, Hartl RF, Kiechle G, Stadler H, Manohar SS (2011) Using traffic information for time-dependent vehicle routing. Procedia Soc Behav Sci 39:217–229CrossRef

Kuo Y (2010) Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem. Comput Ind Eng 59(1):157–165CrossRef

Kuo Y, Wang CC, Chuang PY (2009) Optimizing goods assignment and the vehicle routing problem with time-dependent travel speeds. Comput Ind Eng 57(4):1385–1392CrossRef

Larsen A, Madsen OBG, Solomon MM (2008) Recent Developments in Dynamic Vehicle Routing Systems. In: The vehicle routing problem—latest advances and new challenges, number 43 in Operations Research Computer Science Interface. Springer, pp 199–218

Lee Y, Jung J, Lee K (2006) Vehicle routing scheduling for cross-docking in the supply chain. Comput Ind Eng 51(2):247–256CrossRef

Macedo R, Alves C, Valério deCarvalho JM, Clautiaux F, Hanafi S (2011) Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model. Eur J Oper Res 214(3):536–545CrossRef

Maden W, Eglese R, Black D (2010) Vehicle routing and scheduling with time-varying data: a case study. J Oper Res Soc 61:515–522CrossRef

Makhloufi R, Cattaruzza D, Meunier F, Absi N, Feillet D (2014) Simulation of a mutualized urban logistics system with real-time management,International Symposium of Transport Simulation

Malandraki C, Daskin MS (1992) Time dependent vehicle routing problems: formulations, properties and heuristic algorithms. Transp Sci 26(3):185–200CrossRef

Masson R, Trentini A, Lehuédé F, Malhéné N, Péton O, Tlahig H (2013) Optimization of a city logistics transportation system with mixed passenger and goods. Technical Report ENM Working Paper 13/1/AUTO, Ecole des Mines de Nantes

Mitrović-Minić S, Laporte G (2004) Waiting strategies for the dynamic pickup and delivery problem with time windows. Transp Res Part B 38(7):635–655CrossRef

Muñuzuri J, Cortés P, Guadix J, Onieva L (2012) City logistics in spain: Why it might never work. Cities 29(2):133–141CrossRef

Muñuzuri J, Grosso R, Cortés P, Guadix J (2013) Estimating the extra costs imposed on delivery vehicles using access time windows in a city. Comput Environ Urban Syst 41:262–275CrossRef

Nguyen PK, Crainic TG, Toulouse M (2013) A tabu search for time-dependent multi-zone multi-trip vehicle routing problem with time windows. Eur J Oper Res 231(1):43–56CrossRef

Nguyen PK, Crainic TG, Toulouse M (2014) Multi-zone multi-trip pickup and delivery problem with time windows and synchronization. Technical Report 2014–18, Centre interuniversitaire de recherche sur les réseaux d’enterprise, la logistique et le transport, Université de Montréal, Montréal, QC, Canada

Nguyen V-P, Prins C, Prodhon C (2012) Solving the two-echelon location routing problem by a grasp reinforced by a learning process and path relinking. Eur J Oper Res 216(1):113–126CrossRef

Noveas AGN, Frazzon EM, Burin PJ (2011) Dynamic vehicle routing in over congested areas. Dyn Logist Second Int Conf LDIC 2009:49–58

Commission of the European Communities (2009) Action plan on urban mobility. Technical Report COM (2009) 490. http://ec.europa.eu

Commission of the European Communities (2009) Full evaluation report - satellite based traffic management for smes. Technical report. http://www.civitas.eu/index.php?id=79&sel\_menu=23&measure\_id=250

Commission of the European Communities (2009) A sustainable future for transport: Towards an integrated, technology-led and user friendly system. Technical Report COM, pp 279. http://ec.europa.eu

Commission of the European Communities (2011) Roadmap to a single european transport area - towards a competitive and resource efficient transport system. Technical Report COM (2011) 144. http://ec.europa.eu

Olivera A, Viera O (2007) Adaptive memory programming for the vehicle routing problem with multiple trips. Comput Oper Res 34(1):28–47CrossRef

Ortúzar JD, Willumsen LG (2011) Modelling transport, 4th edn. Wiley

Patier D, Routhier JL (2009) How to Improve the Capture of Urban Goods Movement Data. In: Transport survey methods. Keeping up with a changing world. Emerald, Bingley, pp 251–287

Perboli G, Tadei R, Vigo D (2011) The two-echelon capacitated vehicle routing problem: models and math-based heuristic. Transp Sci 45(3):364–380CrossRef

Perrier Nathalie, Langevin André, Amaya Ciro-Alberto (2008) Vehicle routing for urban snow plowing operations. Transp Sci 42(1):44–56CrossRef

Perrier N, Langevin A, Campbell JF (2007) A survey of models and algorithms for winter road maintenance. part III: vehicle routing and depot location for spreading. Comput OR 34(1):211–257CrossRef

Perrier N, Langevin A, Campbell JF (2007) A survey of models and algorithms for winter road maintenance. part IV: vehicle routing and fleet sizing for plowing and snow disposal. Comput OR 34(1):258–294CrossRef

Petch RJ, Salhi S (2004) A multi-phase constructive heuristic for the vehicle routing problem with multi trips. Discrete Appl Math 133(1–3):69–92

Pillac V, Gendreau M, Guéret C, Medaglia AL (2013) A review of dynamic vehicle routing problems. European Journal of Operational Research 225(1):1–11CrossRef

Potvin J-Y, Xu Y, Benyahia I (2006) Vehicle routing and scheduling with dynamic travel times. Comput Oper Res 33(4):1129–1137CrossRef

Psaraftis HN (1995) Dynamic vehicle routing: status and prospects. Ann Oper Res 61(1):143–164CrossRef

Quak HJ (2012) Improving urban freight transport sustainability by carriers—best practices from the netherlands and the eu project citylog. Procedia Soc Behav Sci 39:158–171CrossRef

Quak HJ, de Koster MBM (2009) Delivering goods in urban areas: how to deal with urban policy restrictions and the environment. Transp Sci 43(2):211–227CrossRef

Qureshi AG, Hanaoka S (2005) Analysis of the effects of a cooperative delivery system in bangkok. In: Recent adavances in city logistics. Langkawi

Qureshi AG, Taniguchi E, Yamada T (2011) A microsimulation based analysis of exact solution of dynamic vehicle routing with soft time windows. Procedia Soc Behav Sci 39:205–216CrossRef

Rodrigue JP (2013) The geography of transportation systems. Routledge, Taylor & Francis Group. http://people.hofstra.edu/geotrans/index.html

Rushton A, Croucher P, Baker P (2006) The handbook of Logistic and Distribution Management, 3rd edn. Kogan Page

Segalou E, Ambrosini C, Routhier JL (2004) The environmental assessment of urban goods movement. In: Logistics systems for sustainable cities—proceedings of the 3rd International Conference on City Logistics. Elsevier, pp 207–220

Soler D, Albiach J, Martínez E (2009) A way to optimally solve a time-dependent vehicle routing problem with time windows. Oper Res Lett 37(1):37–42CrossRef

Taillard ÉD, Laporte G, Gendreau M (1996) Vehicle routeing with multiple use of vehicles. J Oper Res Soc 47(8):1065–1070CrossRef

Taniguchi E, Shimamoto H (2004) Intelligent transportation sustem based dynamic vehicle routing and scheduling with variable travel times. Transp Res Part C 12(3–4):235–250CrossRef

Taniguchi E, Thompson RG, Yamada T, van Duin R (2001) City logistic—network modelling and intelligent transport systems. Pergamon, Amsterdam

Taniguchi E, Van Der Heijden RECM (2000) An evaluation methodology for the city logistics. Transp Rev 20(1):65–90CrossRef

Tarantilis CD, Kiranoudis CT (2001) Using the vehicle routing problem for the transportation of hazardous materials. Oper Res 1(1):67–78

Thompson RG, Hassall KP (2012) A collaborative urban distribution network. Procedia Soc Behav Sci 39:230–240CrossRef

Toth P, Vigo D (2002) The vehicle routing problem. Monographs on discrete mathematics and applications, Siam

Van Woensel T, Kerbache L, Peremans H, Vandaele N (2008) Vehicle routing with dynamic travel times: a queueing approach. Eur J Oper Res 186(3):990–1007CrossRef

Wen M, Larsen J, Clausen J, Cordeau J-F, Laporte G (2009) Vehicle routing with cross-docking. J Oper Res Soc 60:1708–1718CrossRef

Yang J, Jaillet P, Mahmassani H (2004) Real-time multivehicle truckload pickup and delivery problems. Transp Sci 38(2):135–148CrossRef

Zeimpekis V, Giaglis GM (2005) A dynamic real-time management system for incident handling in city logistics. In: Vehicular Technology Conference, 2005. VTC 2005-Spring. 2005 IEEE 61st, vol. 5. pp 2900–2904

Titel: Vehicle routing problems for city logistics
verfasst von: Diego Cattaruzza
Nabil Absi
Dominique Feillet
Jesús González-Feliu
Publikationsdatum: 10.01.2015
Verlag: Springer Berlin Heidelberg
Erschienen in: EURO Journal on Transportation and Logistics / Ausgabe 1/2017
Print ISSN: 2192-4376
Elektronische ISSN: 2192-4384
DOI: https://doi.org/10.1007/s13676-014-0074-0

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 1/2017

Introduction to the special issue on City Logistics

An extended demand responsive connector

Optimization of a city logistics transportation system with mixed passengers and goods

The multi-path Traveling Salesman Problem with stochastic travel costs