IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v61y2010i7d10.1057_jors.2009.51.html
   My bibliography  Save this article

Some applications of the generalized vehicle routing problem

Author

Listed:
  • R Baldacci

    (University of Bologna)

  • E Bartolini

    (University of Bologna)

  • G Laporte

    (HEC Montréal)

Abstract

The Generalized Vehicle Routing Problem (GVRP) is an extension of the classical Vehicle Routing Problem (VRP) in which the vertex set is partitioned into clusters and vehicles must visit exactly one (or at least one) vertex per cluster. The GVRP provides a useful modelling framework for a wide variety of applications. The purpose of this paper is to provide such examples of applications and models. These include the Travelling Salesman with Profits, several VRP extensions, the Windy Routing Problem, and the design of tandem configurations for automated guided vehicles.

Suggested Citation

  • 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.
    • Handle: RePEc:pal:jorsoc:v:61:y:2010:i:7:d:10.1057_jors.2009.51
    DOI: 10.1057/jors.2009.51
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/jors.2009.51
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/jors.2009.51?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. 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.
    2. 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.
    3. Ropke, Stefan & Pisinger, David, 2006. "A unified heuristic for a large class of Vehicle Routing Problems with Backhauls," European Journal of Operational Research, Elsevier, vol. 171(3), pages 750-775, June.
    4. Nagy, Gabor & Salhi, Said, 2007. "Location-routing: Issues, models and methods," European Journal of Operational Research, Elsevier, vol. 177(2), pages 649-672, March.
    5. Bruce L. Golden & Larry Levy & Rakesh Vohra, 1987. "The orienteering problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 34(3), pages 307-318, June.
    6. 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.
    7. Michel Gendreau & Gilbert Laporte & Frédéric Semet, 1997. "The Covering Tour Problem," Operations Research, INFORMS, vol. 45(4), pages 568-576, August.
    8. Bruce L. Golden & Edward A. Wasil, 1987. "OR Practice—Computerized Vehicle Routing in the Soft Drink Industry," Operations Research, INFORMS, vol. 35(1), pages 6-17, February.
    9. Dominique Feillet & Pierre Dejax & Michel Gendreau, 2005. "Traveling Salesman Problems with Profits," Transportation Science, INFORMS, vol. 39(2), pages 188-205, May.
    10. Edward Minieka, 1979. "The Chinese Postman Problem for Mixed Networks," Management Science, INFORMS, vol. 25(7), pages 643-648, July.
    11. Benavent, Enrique & Carrotta, Alessandro & Corberan, Angel & Sanchis, Jose M. & Vigo, Daniele, 2007. "Lower bounds and heuristics for the Windy Rural Postman Problem," European Journal of Operational Research, Elsevier, vol. 176(2), pages 855-869, January.
    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. Qin, Hu & Moriakin, Anton & Xu, Gangyan & Li, Jiliu, 2024. "The generator distribution problem for base stations during emergency power outage: A branch-and-price-and-cut approach," European Journal of Operational Research, Elsevier, vol. 318(3), pages 752-767.
    2. 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.
    3. Kenneth Stoop & Mario Pickavet & Didier Colle & Pieter Audenaert, 2024. "Selective Backhauls in Truck Transport with Risk Mitigation: Large Belgian Retailer Case Study," Networks and Spatial Economics, Springer, vol. 24(1), pages 99-130, March.
    4. 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.
    5. Mehmet Fatih Yuce & Erhan Musaoglu & Ali Gunes, 2016. "Enhancing heuristic bubble algorithm with simulated annealing," Cogent Business & Management, Taylor & Francis Journals, vol. 3(1), pages 1220662-122, December.
    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. 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.
    8. 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.
    9. Çetinkaya, Cihan & Karaoglan, Ismail & Gökçen, Hadi, 2013. "Two-stage vehicle routing problem with arc time windows: A mixed integer programming formulation and a heuristic approach," European Journal of Operational Research, Elsevier, vol. 230(3), pages 539-550.
    10. Lv, Chang & Zhang, Chaoyong & Lian, Kunlei & Ren, Yaping & Meng, Leilei, 2020. "A hybrid algorithm for the static bike-sharing re-positioning problem based on an effective clustering strategy," Transportation Research Part B: Methodological, Elsevier, vol. 140(C), pages 1-21.
    11. 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.
    12. 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.
    13. 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.
    14. Bakker, Steffen J. & Wang, Akang & Gounaris, Chrysanthos E., 2021. "Vehicle routing with endogenous learning: Application to offshore plug and abandonment campaign planning," European Journal of Operational Research, Elsevier, vol. 289(1), pages 93-106.
    15. Santos, Maria João & Curcio, Eduardo & Mulati, Mauro Henrique & Amorim, Pedro & Miyazawa, Flávio Keidi, 2020. "A robust optimization approach for the vehicle routing problem with selective backhauls," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 136(C).
    16. Maria João Santos & Pedro Amorim & Alexandra Marques & Ana Carvalho & Ana Póvoa, 2020. "The vehicle routing problem with backhauls towards a sustainability perspective: a review," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(2), pages 358-401, July.
    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. Forma, Iris A. & Raviv, Tal & Tzur, Michal, 2015. "A 3-step math heuristic for the static repositioning problem in bike-sharing systems," Transportation Research Part B: Methodological, Elsevier, vol. 71(C), pages 230-247.

    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. 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.
    2. 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.
    3. Dominique Feillet & Pierre Dejax & Michel Gendreau, 2005. "Traveling Salesman Problems with Profits," Transportation Science, INFORMS, vol. 39(2), pages 188-205, May.
    4. Lei, Chao & Lin, Wei-Hua & Miao, Lixin, 2014. "A multicut L-shaped based algorithm to solve a stochastic programming model for the mobile facility routing and scheduling problem," European Journal of Operational Research, Elsevier, vol. 238(3), pages 699-710.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. Erdogan, Günes & Cordeau, Jean-François & Laporte, Gilbert, 2010. "The Attractive Traveling Salesman Problem," European Journal of Operational Research, Elsevier, vol. 203(1), pages 59-69, May.
    10. Kobeaga, Gorka & Rojas-Delgado, Jairo & Merino, María & Lozano, Jose A., 2024. "A revisited branch-and-cut algorithm for large-scale orienteering problems," European Journal of Operational Research, Elsevier, vol. 313(1), pages 44-68.
    11. Fatih Rahim & Canan Sepil, 2014. "A location-routing problem in glass recycling," Annals of Operations Research, Springer, vol. 223(1), pages 329-353, December.
    12. Elena Fernández & Gilbert Laporte & Jessica Rodríguez-Pereira, 2019. "Exact Solution of Several Families of Location-Arc Routing Problems," Transportation Science, INFORMS, vol. 53(5), pages 1313-1333, September.
    13. 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.
    14. 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.
    15. Michael D. Moskal & Erdi Dasdemir & Rajan Batta, 2023. "Unmanned Aerial Vehicle Information Collection Missions with Uncertain Characteristics," INFORMS Journal on Computing, INFORMS, vol. 35(1), pages 120-137, January.
    16. Bergmann, Felix M. & Wagner, Stephan M. & Winkenbach, Matthias, 2020. "Integrating first-mile pickup and last-mile delivery on shared vehicle routes for efficient urban e-commerce distribution," Transportation Research Part B: Methodological, Elsevier, vol. 131(C), pages 26-62.
    17. Fischer, Vera & Pacheco Paneque, Meritxell & Legrain, Antoine & Bürgy, Reinhard, 2024. "A capacitated multi-vehicle covering tour problem on a road network and its application to waste collection," European Journal of Operational Research, Elsevier, vol. 315(1), pages 338-353.
    18. 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.
    19. 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.
    20. 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.

    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:pal:jorsoc:v:61:y:2010:i:7:d:10.1057_jors.2009.51. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.palgrave-journals.com/ .

    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.