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

Formulations and Branch-and-Cut Algorithms for the Generalized Vehicle Routing Problem

Author

Listed:
  • Tolga Bektaş

    (School of Management and Centre for Operational Research, Management Science and Information Systems (CORMSIS), University of Southampton, Highfield, Southampton SO17 1BJ, United Kingdom)

  • Güneş Erdoğan

    (Industrial Engineering Department, Ozyegin University, Üsküdar, 34662 Istanbul, Turkey)

  • Stefan Røpke

    (Department of Transport, Technical University of Denmark, 2800 Kgs. Lyngby, Denmark)

Abstract

The generalized vehicle routing problem (GVRP) consists of finding a set of routes for a number of capacitated vehicles on a graph where the vertices are partitioned into clusters with given demands, such that the total cost of travel is minimized and all demands are met. This paper describes and compares four new integer linear programming formulations for the GVRP, two based on multicommodity flow and the other two based on exponential-size sets of inequalities. Branch-and-cut algorithms are proposed for the latter two. Computational results on a large set of instances are presented.

Suggested Citation

  • Tolga Bektaş & Güneş Erdoğan & Stefan Røpke, 2011. "Formulations and Branch-and-Cut Algorithms for the Generalized Vehicle Routing Problem," Transportation Science, INFORMS, vol. 45(3), pages 299-316, August.
    • Handle: RePEc:inm:ortrsc:v:45:y:2011:i:3:p:299-316
    DOI: 10.1287/trsc.1100.0352
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1100.0352
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1100.0352?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. Gouveia, Luis, 1995. "A result on projection for the vehicle routing ptoblem," European Journal of Operational Research, Elsevier, vol. 85(3), pages 610-624, September.
    2. R Baldacci & E Bartolini & G Laporte, 2010. "Some applications of the generalized vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(7), pages 1072-1077, July.
    3. Stefan Ropke & David Pisinger, 2006. "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 40(4), pages 455-472, November.
    4. Asef-Vaziri, Ardavan & Laporte, Gilbert, 2005. "Loop based facility planning and material handling," European Journal of Operational Research, Elsevier, vol. 164(1), pages 1-11, July.
    5. Ghiani, Gianpaolo & Improta, Gennaro, 2000. "An efficient transformation of the generalized vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 122(1), pages 11-17, April.
    6. Dominique Feillet & Pierre Dejax & Michel Gendreau, 2005. "Traveling Salesman Problems with Profits," Transportation Science, INFORMS, vol. 39(2), pages 188-205, May.
    7. Matteo Fischetti & Juan José Salazar González & Paolo Toth, 1997. "A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem," Operations Research, INFORMS, vol. 45(3), pages 378-394, June.
    8. Jean-Francois Cordeau & Gilbert Laporte, 2006. "Modeling and Optimization of Vehicle Routing and Arc Routing Problems," International Series in Operations Research & Management Science, in: Gautam Appa & Leonidas Pitsoulis & H. Paul Williams (ed.), Handbook on Modelling for Discrete Optimization, chapter 0, pages 151-191, Springer.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Elfe Buluc & Meltem Peker & Bahar Y. Kara & Manoj Dora, 2022. "Covering vehicle routing problem: application for mobile child friendly spaces for refugees," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(2), pages 461-484, June.
    2. Ozbaygin, Gizem & Ekin Karasan, Oya & Savelsbergh, Martin & Yaman, Hande, 2017. "A branch-and-price algorithm for the vehicle routing problem with roaming delivery locations," Transportation Research Part B: Methodological, Elsevier, vol. 100(C), pages 115-137.
    3. Miranda, Pablo A. & Blazquez, Carola A. & Obreque, Carlos & Maturana-Ross, Javier & Gutierrez-Jarpa, Gabriel, 2018. "The bi-objective insular traveling salesman problem with maritime and ground transportation costs," European Journal of Operational Research, Elsevier, vol. 271(3), pages 1014-1036.
    4. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2014. "A unified solution framework for multi-attribute vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 234(3), pages 658-673.
    5. Timo Hintsch & Stefan Irnich, 2017. "Large Multiple Neighborhood Search for the Clustered Vehicle-Routing Problem," Working Papers 1701, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    6. Zhou, Lin & Baldacci, Roberto & Vigo, Daniele & Wang, Xu, 2018. "A Multi-Depot Two-Echelon Vehicle Routing Problem with Delivery Options Arising in the Last Mile Distribution," European Journal of Operational Research, Elsevier, vol. 265(2), pages 765-778.
    7. Timo Hintsch & Stefan Irnich, 2018. "Exact Solution of the Soft-Clustered Vehicle Routing Problem," Working Papers 1813, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    8. Hintsch, Timo & Irnich, Stefan, 2018. "Large multiple neighborhood search for the clustered vehicle-routing problem," European Journal of Operational Research, Elsevier, vol. 270(1), pages 118-131.
    9. Glock, Katharina & Meyer, Anne, 2023. "Spatial coverage in routing and path planning problems," European Journal of Operational Research, Elsevier, vol. 305(1), pages 1-20.
    10. Katrin Heßler & Stefan Irnich, 2020. "A Branch-and-Cut Algorithm for the Soft-Clustered Vehicle-Routing Problem," Working Papers 2001, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    11. Perugia, Alessandro & Moccia, Luigi & Cordeau, Jean-François & Laporte, Gilbert, 2011. "Designing a home-to-work bus service in a metropolitan area," Transportation Research Part B: Methodological, Elsevier, vol. 45(10), pages 1710-1726.
    12. Frey, Christian M.M. & Jungwirth, Alexander & Frey, Markus & Kolisch, Rainer, 2023. "The vehicle routing problem with time windows and flexible delivery locations," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1142-1159.
    13. Wang, Mengtong & Zhang, Canrong & Bell, Michael G.H. & Miao, Lixin, 2022. "A branch-and-price algorithm for location-routing problems with pick-up stations in the last-mile distribution system," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1258-1276.
    14. Bulhões, Teobaldo & Hà, Minh Hoàng & Martinelli, Rafael & Vidal, Thibaut, 2018. "The vehicle routing problem with service level constraints," European Journal of Operational Research, Elsevier, vol. 265(2), pages 544-558.
    15. Timo Hintsch, 2019. "Large Multiple Neighborhood Search for the Soft-Clustered Vehicle-Routing Problem," Working Papers 1904, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    16. Liu, Dan & Kaisar, Evangelos I. & Yang, Yang & Yan, Pengyu, 2022. "Physical Internet-enabled E-grocery delivery Network:A load-dependent two-echelon vehicle routing problem with mixed vehicles," International Journal of Production Economics, Elsevier, vol. 254(C).
    17. Yuan, Yuan & Cattaruzza, Diego & Ogier, Maxime & Semet, Frédéric & Vigo, Daniele, 2021. "A column generation based heuristic for the generalized vehicle routing problem with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    18. Balcik, Burcu, 2017. "Site selection and vehicle routing for post-disaster rapid needs assessment," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 101(C), pages 30-58.
    19. Maria Battarra & Güneş Erdoğan & Daniele Vigo, 2014. "Exact Algorithms for the Clustered Vehicle Routing Problem," Operations Research, INFORMS, vol. 62(1), pages 58-71, February.

    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. Yuan, Yuan & Cattaruzza, Diego & Ogier, Maxime & Semet, Frédéric & Vigo, Daniele, 2021. "A column generation based heuristic for the generalized vehicle routing problem with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    2. Frey, Christian M.M. & Jungwirth, Alexander & Frey, Markus & Kolisch, Rainer, 2023. "The vehicle routing problem with time windows and flexible delivery locations," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1142-1159.
    3. Balcik, Burcu, 2017. "Site selection and vehicle routing for post-disaster rapid needs assessment," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 101(C), pages 30-58.
    4. R Baldacci & E Bartolini & G Laporte, 2010. "Some applications of the generalized vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(7), pages 1072-1077, July.
    5. Elfe Buluc & Meltem Peker & Bahar Y. Kara & Manoj Dora, 2022. "Covering vehicle routing problem: application for mobile child friendly spaces for refugees," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(2), pages 461-484, June.
    6. Álvarez-Miranda, Eduardo & Luipersbeck, Martin & Sinnl, Markus, 2018. "Gotta (efficiently) catch them all: Pokémon GO meets Orienteering Problems," European Journal of Operational Research, Elsevier, vol. 265(2), pages 779-794.
    7. Ido Orenstein & Tal Raviv & Elad Sadan, 2019. "Flexible parcel delivery to automated parcel lockers: models, solution methods and analysis," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(5), pages 683-711, December.
    8. Li, Yuan & Chen, Haoxun & Prins, Christian, 2016. "Adaptive large neighborhood search for the pickup and delivery problem with time windows, profits, and reserved requests," European Journal of Operational Research, Elsevier, vol. 252(1), pages 27-38.
    9. Timo Hintsch, 2019. "Large Multiple Neighborhood Search for the Soft-Clustered Vehicle-Routing Problem," Working Papers 1904, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    10. Pop, Petrică C., 2020. "The generalized minimum spanning tree problem: An overview of formulations, solution procedures and latest advances," European Journal of Operational Research, Elsevier, vol. 283(1), pages 1-15.
    11. Amira Saker & Amr Eltawil & Islam Ali, 2023. "Adaptive Large Neighborhood Search Metaheuristic for the Capacitated Vehicle Routing Problem with Parcel Lockers," Logistics, MDPI, vol. 7(4), pages 1-27, October.
    12. Dumez, Dorian & Lehuédé, Fabien & Péton, Olivier, 2021. "A large neighborhood search approach to the vehicle routing problem with delivery options," Transportation Research Part B: Methodological, Elsevier, vol. 144(C), pages 103-132.
    13. Pop, Petrică C. & Cosma, Ovidiu & Sabo, Cosmin & Sitar, Corina Pop, 2024. "A comprehensive survey on the generalized traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 314(3), pages 819-835.
    14. Dominique Feillet & Pierre Dejax & Michel Gendreau, 2005. "Traveling Salesman Problems with Profits," Transportation Science, INFORMS, vol. 39(2), pages 188-205, May.
    15. Cosmin Sabo & Petrică C. Pop & Andrei Horvat-Marc, 2020. "On the Selective Vehicle Routing Problem," Mathematics, MDPI, vol. 8(5), pages 1-11, May.
    16. Daniel Negrotto & Irene Loiseau, 2021. "A Branch & Cut algorithm for the prize-collecting capacitated location routing problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(1), pages 34-57, April.
    17. Leticia Vargas & Nicolas Jozefowiez & Sandra Ulrich Ngueveu, 2017. "A dynamic programming operator for tour location problems applied to the covering tour problem," Journal of Heuristics, Springer, vol. 23(1), pages 53-80, February.
    18. Pěnička, Robert & Faigl, Jan & Saska, Martin, 2019. "Variable Neighborhood Search for the Set Orienteering Problem and its application to other Orienteering Problem variants," European Journal of Operational Research, Elsevier, vol. 276(3), pages 816-825.
    19. Martinelli, Rafael & Pecin, Diego & Poggi, Marcus, 2014. "Efficient elementary and restricted non-elementary route pricing," European Journal of Operational Research, Elsevier, vol. 239(1), pages 102-111.
    20. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.

    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:45:y:2011:i:3:p:299-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.