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

The Generalized Consistent Vehicle Routing Problem

Author

Listed:
  • Attila A. Kovacs

    (Department of Business Administration, University of Vienna, A-1090 Vienna, Austria)

  • Bruce L. Golden

    (Robert H. Smith School of Business, University of Maryland, College Park, Maryland 20742)

  • Richard F. Hartl

    (Department of Business Administration, University of Vienna, A-1090 Vienna, Austria)

  • Sophie N. Parragh

    (Department of Business Administration, University of Vienna, A-1090 Vienna, Austria)

Abstract

The consistent vehicle routing problem (ConVRP) takes customer satisfaction into account by assigning one driver to a customer and by bounding the variation in the arrival times over a given planning horizon. These requirements may be too restrictive in some applications. In the generalized ConVRP (GenConVRP), each customer is visited by a limited number of drivers and the variation in the arrival times is penalized in the objective function. The vehicle departure times may be adjusted to obtain stable arrival times. Additionally, customers are associated with AM/PM time windows. In contrast to previous work on the ConVRP, we do not use the template concept to generate routing plans. Our approach is based on a flexible large neighborhood search that is applied to the entire solution. Several destroy and repair heuristics have been designed to remove customers from the routes and to reinsert them at better positions. Arrival time consistency is improved by a simple 2-opt operator that reverses parts of particular routes.A computational study is performed on ConVRP benchmark instances and on new instances generated for the generalized problem. The proposed algorithm performs well on different variants of the ConVRP. It outperforms template-based approaches in terms of travel cost and time consistency. For the GenConVRP, we experiment with different input parameters and examine the trade-off between travel cost and customer satisfaction. Remarkable cost savings can be obtained by allowing more than one driver per customer.

Suggested Citation

  • Attila A. Kovacs & Bruce L. Golden & Richard F. Hartl & Sophie N. Parragh, 2015. "The Generalized Consistent Vehicle Routing Problem," Transportation Science, INFORMS, vol. 49(4), pages 796-816, November.
    • Handle: RePEc:inm:ortrsc:v:49:y:2015:i:4:p:796-816
    DOI: 10.1287/trsc.2014.0529
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.2014.0529
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.2014.0529?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. Karen Smilowitz & Maciek Nowak & Tingting Jiang, 2013. "Workforce Management in Periodic Delivery Operations," Transportation Science, INFORMS, vol. 47(2), pages 214-230, May.
    2. Peter Francis & Karen Smilowitz & Michal Tzur, 2006. "The Period Vehicle Routing Problem with Service Choice," Transportation Science, INFORMS, vol. 40(4), pages 439-454, November.
    3. Ilgaz Sungur & Yingtao Ren & Fernando Ordóñez & Maged Dessouky & Hongsheng Zhong, 2010. "A Model and Algorithm for the Courier Delivery Problem with Uncertainty," Transportation Science, INFORMS, vol. 44(2), pages 193-205, May.
    4. Julie Paquette & François Bellavance & Jean-François Cordeau & Gilbert Laporte, 2012. "Measuring quality of service in dial-a-ride operations: the case of a Canadian city," Transportation, Springer, vol. 39(3), pages 539-564, May.
    5. 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.
    6. Peter Francis & Karen Smilowitz & Michal Tzur, 2007. "Flexibility and complexity in periodic distribution problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(2), pages 136-150, March.
    7. Francis, Peter & Smilowitz, Karen, 2006. "Modeling techniques for periodic vehicle routing problems," Transportation Research Part B: Methodological, Elsevier, vol. 40(10), pages 872-884, December.
    8. Woodward, Christel A. & Abelson, Julia & Tedford, Sara & Hutchison, Brian, 2004. "What is important to continuity in home care?: Perspectives of key stakeholders," Social Science & Medicine, Elsevier, vol. 58(1), pages 177-192, January.
    9. Spliet, R. & Gabor, A.F., 2012. "The Time Window Assignment Vehicle Routing Problem," Econometric Institute Research Papers EI 2012-07, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    10. Potvin, Jean-Yves & Rousseau, Jean-Marc, 1993. "A parallel route building algorithm for the vehicle routing and scheduling problem with time windows," European Journal of Operational Research, Elsevier, vol. 66(3), pages 331-340, May.
    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. Zhen, Lu & Gao, Jiajing & Tan, Zheyi & Laporte, Gilbert & Baldacci, Roberto, 2023. "Territorial design for customers with demand frequency," European Journal of Operational Research, Elsevier, vol. 309(1), pages 82-101.
    2. Yang, Meng & Ni, Yaodong & Song, Qinyu, 2022. "Optimizing driver consistency in the vehicle routing problem under uncertain environment," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    3. Anirudh Subramanyam & Chrysanthos E. Gounaris, 2018. "A Decomposition Algorithm for the Consistent Traveling Salesman Problem with Vehicle Idling," Transportation Science, INFORMS, vol. 52(2), pages 386-401, March.
    4. Rodríguez-Martín, Inmaculada & Yaman, Hande, 2022. "Periodic Vehicle Routing Problem with Driver Consistency and service time optimization," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 468-484.
    5. Meyer, Anne & Amberg, Boris, 2018. "Transport concept selection considering supplier milk runs – An integrated model and a case study from the automotive industry," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 113(C), pages 147-169.
    6. Mike Hewitt & Maciek Nowak & Nisha Nataraj, 2016. "Planning Strategies for Home Health Care Delivery," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(05), pages 1-26, October.
    7. Hewitt, Mike & Nowak, Maciek & Gala, Leo, 2015. "Consolidating home meal delivery with limited operational disruption," European Journal of Operational Research, Elsevier, vol. 243(1), pages 281-291.
    8. Braekers, Kris & Kovacs, Attila A., 2016. "A multi-period dial-a-ride problem with driver consistency," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 355-377.
    9. Karen Smilowitz & Maciek Nowak & Tingting Jiang, 2013. "Workforce Management in Periodic Delivery Operations," Transportation Science, INFORMS, vol. 47(2), pages 214-230, May.
    10. Ulmer, Marlin & Nowak, Maciek & Mattfeld, Dirk & Kaminski, Bogumił, 2020. "Binary driver-customer familiarity in service routing," European Journal of Operational Research, Elsevier, vol. 286(2), pages 477-493.
    11. Jost, Christian & Jungwirth, Alexander & Kolisch, Rainer & Schiffels, Sebastian, 2022. "Consistent vehicle routing with pickup decisions - Insights from sport academy training transfers," European Journal of Operational Research, Elsevier, vol. 298(1), pages 337-350.
    12. Vidal, Thibaut & Laporte, Gilbert & Matl, Piotr, 2020. "A concise guide to existing and emerging vehicle routing problem variants," European Journal of Operational Research, Elsevier, vol. 286(2), pages 401-416.
    13. Zhou, Lin & Zhen, Lu & Baldacci, Roberto & Boschetti, Marco & Dai, Ying & Lim, Andrew, 2021. "A Heuristic Algorithm for solving a large-scale real-world territory design problem," Omega, Elsevier, vol. 103(C).
    14. Michael Schneider & Andreas Stenger & Fabian Schwahn & Daniele Vigo, 2015. "Territory-Based Vehicle Routing in the Presence of Time-Window Constraints," Transportation Science, INFORMS, vol. 49(4), pages 732-751, November.
    15. Martins, Sara & Ostermeier, Manuel & Amorim, Pedro & Hübner, Alexander & Almada-Lobo, Bernardo, 2019. "Product-oriented time window assignment for a multi-compartment vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 276(3), pages 893-909.
    16. repec:dar:wpaper:62383 is not listed on IDEAS
    17. Benavent, Enrique & Corberán, Ángel & Laganà, Demetrio & Vocaturo, Francesca, 2019. "The periodic rural postman problem with irregular services on mixed graphs," European Journal of Operational Research, Elsevier, vol. 276(3), pages 826-839.
    18. Jeffrey W. Ohlmann & Michael J. Fry & Barrett W. Thomas, 2008. "Route Design for Lean Production Systems," Transportation Science, INFORMS, vol. 42(3), pages 352-370, August.
    19. Vera C. Hemmelmayr & Karl F. Doerner & Richard F. Hartl & Daniele Vigo, 2014. "Models and Algorithms for the Integrated Planning of Bin Allocation and Vehicle Routing in Solid Waste Management," Transportation Science, INFORMS, vol. 48(1), pages 103-120, February.
    20. Liu, Chuanju & Lin, Shaochong & Shen, Zuo-Jun Max & Zhang, Junlong, 2023. "Stochastic service network design: The value of fixed routes," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 174(C).
    21. Nasr Al-Hinai & Chefi Triki, 2020. "A two-level evolutionary algorithm for solving the petrol station replenishment problem with periodicity constraints and service choice," Annals of Operations Research, Springer, vol. 286(1), pages 325-350, March.

    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:49:y:2015:i:4:p:796-816. 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.