IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v46y2012i3p297-316.html
   My bibliography  Save this article

Synchronization in Vehicle Routing---A Survey of VRPs with Multiple Synchronization Constraints

Author

Listed:
  • Michael Drexl

    (Chair of Logistics Management, Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, 55128 Mainz, Germany and Fraunhofer Centre for Applied Research on Supply Chain Services SCS, 90411 Nuremberg, Germany)

Abstract

This paper presents a survey of vehicle routing problems with multiple synchronization constraints. These problems exhibit, in addition to the usual task covering constraints, further synchronization requirements between the vehicles, concerning spatial, temporal, and load aspects. They constitute an emerging field in vehicle routing research and are becoming a “hot” topic. The contribution of the paper is threefold: (i) It presents a classification of different types of synchronization. (ii) It discusses the central issues related to the exact and heuristic solution of such problems. (iii) It comprehensively reviews pertinent literature with respect to applications as well as successful solution approaches, and it identifies promising algorithmic avenues.

Suggested Citation

  • Michael Drexl, 2012. "Synchronization in Vehicle Routing---A Survey of VRPs with Multiple Synchronization Constraints," Transportation Science, INFORMS, vol. 46(3), pages 297-316, August.
    • Handle: RePEc:inm:ortrsc:v:46:y:2012:i:3:p:297-316
    DOI: 10.1287/trsc.1110.0400
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1110.0400
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1110.0400?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Gendreau, Michel & Laporte, Gilbert & Seguin, Rene, 1996. "Stochastic vehicle routing," European Journal of Operational Research, Elsevier, vol. 88(1), pages 3-12, January.
    2. Christos D. Tarantilis & Emmanouil E. Zachariadis & Chris T. Kiranoudis, 2008. "A Hybrid Guided Local Search for the Vehicle-Routing Problem with Intermediate Replenishment Facilities," INFORMS Journal on Computing, INFORMS, vol. 20(1), pages 154-168, February.
    3. Nagy, Gabor & Salhi, Said, 2007. "Location-routing: Issues, models and methods," European Journal of Operational Research, Elsevier, vol. 177(2), pages 649-672, March.
    4. Diego Klabjan, 2005. "Large-Scale Models in the Airline Industry," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 163-195, Springer.
    5. Jacobsen, S. K. & Madsen, O. B. G., 1980. "A comparative study of heuristics for a two-level routing-location problem," European Journal of Operational Research, Elsevier, vol. 5(6), pages 378-387, December.
    6. Sam Thangiah & Adel Fergany & Salman Awan, 2007. "Real-time split-delivery pickup and delivery time window problems with transfers," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 15(4), pages 329-349, November.
    7. Hollis, B.L. & Forbes, M.A. & Douglas, B.E., 2006. "Vehicle routing and crew scheduling for metropolitan mail distribution at Australia Post," European Journal of Operational Research, Elsevier, vol. 173(1), pages 133-150, August.
    8. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    9. Andersen, Jardar & Crainic, Teodor Gabriel & Christiansen, Marielle, 2009. "Service network design with management and coordination of multiple fleets," European Journal of Operational Research, Elsevier, vol. 193(2), pages 377-389, March.
    10. Ebben, M. J. R. & van der Heijden, M. C. & van Harten, A., 2005. "Dynamic transport scheduling under multiple resource constraints," European Journal of Operational Research, Elsevier, vol. 167(2), pages 320-335, December.
    11. Imai, Akio & Nishimura, Etsuko & Current, John, 2007. "A Lagrangian relaxation-based heuristic for the vehicle routing with full container load," European Journal of Operational Research, Elsevier, vol. 176(1), pages 87-105, January.
    12. N H Moin & S Salhi, 2007. "Inventory routing problems: a logistical overview," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(9), pages 1185-1194, September.
    13. Yanzhi Li & Andrew Lim & Brian Rodrigues, 2005. "Manpower allocation with time windows and job‐teaming constraints," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(4), pages 302-311, June.
    14. Alain Hertz & Michel Mittaz, 2001. "A Variable Neighborhood Descent Algorithm for the Undirected Capacitated Arc Routing Problem," Transportation Science, INFORMS, vol. 35(4), pages 425-434, November.
    15. Angelelli, Enrico & Grazia Speranza, Maria, 2002. "The periodic vehicle routing problem with intermediate facilities," European Journal of Operational Research, Elsevier, vol. 137(2), pages 233-247, March.
    16. Cortés, Cristián E. & Matamala, Martín & Contardo, Claudio, 2010. "The pickup and delivery problem with transfers: Formulation and a branch-and-cut solution method," European Journal of Operational Research, Elsevier, vol. 200(3), pages 711-724, February.
    17. Cheung, Raymond K. & Shi, Ning & Powell, Warren B. & Simao, Hugo P., 2008. "An attribute-decision model for cross-border drayage problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 44(2), pages 217-234, March.
    18. M Wen & J Larsen & J Clausen & J-F Cordeau & G Laporte, 2009. "Vehicle routing with cross-docking," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(12), pages 1708-1718, December.
    19. Grunert, Tore & Sebastian, Hans-Jurgen, 2000. "Planning models for long-haul operations of postal and express shipment companies," European Journal of Operational Research, Elsevier, vol. 122(2), pages 289-309, April.
    20. Guy Desaulniers, 2010. "Branch-and-Price-and-Cut for the Split-Delivery Vehicle Routing Problem with Time Windows," Operations Research, INFORMS, vol. 58(1), pages 179-192, February.
    21. U Derigs & B Li & U Vogel, 2010. "Local search-based metaheuristics for the split delivery vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(9), pages 1356-1364, September.
    22. Gerdessen, Johanna C., 1996. "Vehicle routing problem with trailers," European Journal of Operational Research, Elsevier, vol. 93(1), pages 135-147, August.
    23. Park, Junhyuk & Kim, Byung-In, 2010. "The school bus routing problem: A review," European Journal of Operational Research, Elsevier, vol. 202(2), pages 311-319, April.
    24. Freling, R. & Huisman, D. & Wagelmans, A.P.M., 2000. "Models and algorithms for Integration of Vehicle and Crew Scheduling," ERIM Report Series Research in Management ERS-2000-14-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    25. Villeneuve, Daniel & Desaulniers, Guy, 2005. "The shortest path problem with forbidden paths," European Journal of Operational Research, Elsevier, vol. 165(1), pages 97-107, August.
    26. Barbara De Rosa & Gennaro Improta & Gianpaolo Ghiani & Roberto Musmanno, 2002. "The Arc Routing and Scheduling Problem with Transshipment," Transportation Science, INFORMS, vol. 36(3), pages 301-313, August.
    27. Jesus Gonzalez-Feliu, 2009. "The N-echelon Location routing problem: concepts and methods for tactical and operational planning," Working Papers halshs-00422492, HAL.
    28. A Lim & B Rodrigues & L Song, 2004. "Manpower allocation with time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(11), pages 1178-1186, November.
    29. Chris Groër & Bruce Golden & Edward Wasil, 2009. "The Consistent Vehicle Routing Problem," Manufacturing & Service Operations Management, INFORMS, vol. 11(4), pages 630-643, February.
    30. Recker, W. W., 1995. "The household activity pattern problem: General formulation and solution," Transportation Research Part B: Methodological, Elsevier, vol. 29(1), pages 61-77, February.
    31. J Clossey & G Laporte & P Soriano, 2001. "Solving arc routing problems with turn penalties," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 52(4), pages 433-439, April.
    32. Teodor Gabriel Crainic & Nicoletta Ricciardi & Giovanni Storchi, 2009. "Models for Evaluating and Planning City Logistics Systems," Transportation Science, INFORMS, vol. 43(4), pages 432-454, November.
    33. Bock, Stefan, 2010. "Real-time control of freight forwarder transportation networks by integrating multimodal transport chains," European Journal of Operational Research, Elsevier, vol. 200(3), pages 733-746, February.
    34. Baker, Hope M. & Franz, Lori S. & Sweigart, James R., 1993. "Coordinated transportation systems: An alternative approach to traditional independent systems," European Journal of Operational Research, Elsevier, vol. 66(3), pages 341-352, May.
    35. Maciek Nowak & Özlem Ergun & Chelsea C. White, 2008. "Pickup and Delivery with Split Loads," Transportation Science, INFORMS, vol. 42(1), pages 32-43, February.
    36. A N Letchford & J Lysgaard & R W Eglese, 2007. "A branch-and-cut algorithm for the capacitated open vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(12), pages 1642-1651, December.
    37. Belanger, Nicolas & Desaulniers, Guy & Soumis, Francois & Desrosiers, Jacques, 2006. "Periodic airline fleet assignment with time windows, spacing constraints, and time dependent revenues," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1754-1766, December.
    38. Jesus Gonzalez-Feliu & Guido Perboli & Roberto Tadei & Daniele Vigo, 2008. "The two-echelon capacitated vehicle routing problem," Working Papers halshs-00879447, HAL.
    39. J-F Cordeau & G Laporte & A Mercier, 2001. "A unified tabu search heuristic for vehicle routing problems with time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 52(8), pages 928-936, August.
    40. Macharis, C. & Bontekoning, Y. M., 2004. "Opportunities for OR in intermodal freight transport research: A review," European Journal of Operational Research, Elsevier, vol. 153(2), pages 400-416, March.
    41. Ambrosino, Daniela & Grazia Scutella, Maria, 2005. "Distribution network design: New problems and related models," European Journal of Operational Research, Elsevier, vol. 165(3), pages 610-624, September.
    42. Xiang, Zhihai & Chu, Chengbin & Chen, Haoxun, 2006. "A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints," European Journal of Operational Research, Elsevier, vol. 174(2), pages 1117-1139, October.
    43. S. Irnich, 2008. "A Unified Modeling and Solution Framework for Vehicle Routing and Local Search-Based Metaheuristics," INFORMS Journal on Computing, INFORMS, vol. 20(2), pages 270-287, May.
    44. Robert A. Russell & Reece B. Morrel, 1986. "Routing Special-Education School Buses," Interfaces, INFORMS, vol. 16(5), pages 56-64, October.
    45. C-A Amaya & A Langevin & M Trépanier, 2010. "A heuristic method for the capacitated arc routing problem with refill points and multiple loads," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(7), pages 1095-1103, July.
    46. Ioachim, Irina & Desrosiers, Jacques & Soumis, Francois & Belanger, Nicolas, 1999. "Fleet assignment and routing with schedule synchronization constraints," European Journal of Operational Research, Elsevier, vol. 119(1), pages 75-90, November.
    47. Stefan Irnich & Guy Desaulniers, 2005. "Shortest Path Problems with Resource Constraints," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 33-65, Springer.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Jesus Gonzalez-Feliu, 2013. "Multi-stage LTL transport systems in supply chain management," Post-Print halshs-00796714, HAL.
    2. Drexl, Michael, 2013. "Applications of the vehicle routing problem with trailers and transshipments," European Journal of Operational Research, Elsevier, vol. 227(2), pages 275-283.
    3. Lahyani, Rahma & Khemakhem, Mahdi & Semet, Frédéric, 2015. "Rich vehicle routing problems: From a taxonomy to a definition," European Journal of Operational Research, Elsevier, vol. 241(1), pages 1-14.
    4. Liu, Chuanju & Zhang, Junlong & Lin, Shaochong & Shen, Zuo-Jun Max, 2023. "Service network design with consistent multiple trips," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 171(C).
    5. repec:hal:wpaper:halshs-00796714 is not listed on IDEAS
    6. Michael Drexl, 2014. "A Generic Heuristic for Vehicle Routing Problems with Multiple Synchronization Constraints," Working Papers 1412, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz, revised 04 Nov 2014.
    7. Ann-Kathrin Rothenbächer & Michael Drexl & Stefan Irnich, 2018. "Branch-and-Price-and-Cut for the Truck-and-Trailer Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 52(5), pages 1174-1190, October.
    8. David Wolfinger & Fabien Tricoire & Karl F. Doerner, 2019. "A matheuristic for a multimodal long haul routing problem," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(4), pages 397-433, December.
    9. Reinhardt, Line Blander & Clausen, Tommy & Pisinger, David, 2013. "Synchronized dial-a-ride transportation of disabled passengers at airports," European Journal of Operational Research, Elsevier, vol. 225(1), pages 106-117.
    10. Li, Jiliu & Qin, Hu & Baldacci, Roberto & Zhu, Wenbin, 2020. "Branch-and-price-and-cut for the synchronized vehicle routing problem with split delivery, proportional service time and multiple time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 140(C).
    11. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    12. Maximilian Schiffer & Michael Schneider & Grit Walther & Gilbert Laporte, 2019. "Vehicle Routing and Location Routing with Intermediate Stops: A Review," Transportation Science, INFORMS, vol. 53(2), pages 319-343, March.
    13. Fink, Martin & Desaulniers, Guy & Frey, Markus & Kiermaier, Ferdinand & Kolisch, Rainer & Soumis, François, 2019. "Column generation for vehicle routing problems with multiple synchronization constraints," European Journal of Operational Research, Elsevier, vol. 272(2), pages 699-711.
    14. Drexl, Michael & Schneider, Michael, 2015. "A survey of variants and extensions of the location-routing problem," European Journal of Operational Research, Elsevier, vol. 241(2), pages 283-308.
    15. Masson, Renaud & Ropke, Stefan & Lehuédé, Fabien & Péton, Olivier, 2014. "A branch-and-cut-and-price approach for the pickup and delivery problem with shuttle routes," European Journal of Operational Research, Elsevier, vol. 236(3), pages 849-862.
    16. Tilk, Christian & Drexl, Michael & Irnich, Stefan, 2019. "Nested branch-and-price-and-cut for vehicle routing problems with multiple resource interdependencies," European Journal of Operational Research, Elsevier, vol. 276(2), pages 549-565.
    17. Janjevic, Milena & Winkenbach, Matthias & Merchán, Daniel, 2019. "Integrating collection-and-delivery points in the strategic design of urban last-mile e-commerce distribution networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 131(C), pages 37-67.
    18. Ann-Kathrin Rothenbächer & Michael Drexl & Stefan Irnich, 2016. "Branch-and-Price-and-Cut for the Truck-andTrailer Routing Problem with Time Windows," Working Papers 1617, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    19. Maximilian Schiffer & Grit Walther, 2018. "An Adaptive Large Neighborhood Search for the Location-routing Problem with Intra-route Facilities," Transportation Science, INFORMS, vol. 52(2), pages 331-352, March.
    20. Qie He & Stefan Irnich & Yongjia Song, 2019. "Branch-and-Cut-and-Price for the Vehicle Routing Problem with Time Windows and Convex Node Costs," Transportation Science, INFORMS, vol. 53(5), pages 1409-1426, September.
    21. Gschwind, Timo, 2015. "A comparison of column-generation approaches to the Synchronized Pickup and Delivery Problem," European Journal of Operational Research, Elsevier, vol. 247(1), pages 60-71.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ortrsc:v:46:y:2012:i:3:p:297-316. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.