IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v275y2019i1p93-107.html
   My bibliography  Save this article

Vehicle routing with arrival time diversification

Author

Listed:
  • Hoogeboom, Maaike
  • Dullaert, Wout

Abstract

Unpredictable routes may be generated by varying the arrival time at each customer over successive visits. Inspired by a real-life case in cash distribution, this study presents an efficient solution approach for the vehicle routing problem with arrival time diversification by formulating it as a vehicle routing problem with multiple time windows in a rolling horizon framework. Because waiting times are not allowed, a novel algorithm is developed to efficiently determine whether routes or local search operations are time window feasible. To allow infeasible solutions during the heuristic search, four different penalty methods are proposed. The proposed algorithm and penalty methods are evaluated in a simple iterated granular tabu search that obtains new best-known solutions for all benchmark instances from the literature, decreasing average distance by 29% and reducing computation time by 93%. A case study is conducted to illustrate the practical relevance of the proposed model and to examine the trade-off between arrival time diversification and transportation cost.

Suggested Citation

  • Hoogeboom, Maaike & Dullaert, Wout, 2019. "Vehicle routing with arrival time diversification," European Journal of Operational Research, Elsevier, vol. 275(1), pages 93-107.
    • Handle: RePEc:eee:ejores:v:275:y:2019:i:1:p:93-107
    DOI: 10.1016/j.ejor.2018.11.020
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221718309457
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2018.11.020?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. Michel Gendreau & Alain Hertz & Gilbert Laporte, 1994. "A Tabu Search Heuristic for the Vehicle Routing Problem," Management Science, INFORMS, vol. 40(10), pages 1276-1290, October.
    2. 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.
    3. Schneider, Michael & Schwahn, Fabian & Vigo, Daniele, 2017. "Designing granular solution methods for routing problems with time windows," European Journal of Operational Research, Elsevier, vol. 263(2), pages 493-509.
    4. Talarico, Luca & Sörensen, Kenneth & Springael, Johan, 2015. "Metaheuristics for the risk-constrained cash-in-transit vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 244(2), pages 457-470.
    5. Dell'Olmo, Paolo & Gentili, Monica & Scozzari, Andrea, 2005. "On finding dissimilar Pareto-optimal paths," European Journal of Operational Research, Elsevier, vol. 162(1), pages 70-82, April.
    6. Talarico, L. & Sörensen, K. & Springael, J., 2015. "The k-dissimilar vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 244(1), pages 129-140.
    7. Paolo Toth & Daniele Vigo, 2003. "The Granular Tabu Search and Its Application to the Vehicle-Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 15(4), pages 333-346, November.
    8. Z Fu & R Eglese & L Y O Li, 2008. "A unified tabu search algorithm for vehicle routing problems with soft time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(5), pages 663-673, May.
    9. 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.
    10. Akgun, Vedat & Erkut, Erhan & Batta, Rajan, 2000. "On finding dissimilar paths," European Journal of Operational Research, Elsevier, vol. 121(2), pages 232-246, March.
    11. Andrew Lim & Xingwen Zhang, 2007. "A Two-Stage Heuristic with Ejection Pools and Generalized Ejection Chains for the Vehicle Routing Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 19(3), pages 443-457, August.
    12. 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.
    13. Martin W. P. Savelsbergh, 1992. "The Vehicle Routing Problem with Time Windows: Minimizing Route Duration," INFORMS Journal on Computing, INFORMS, vol. 4(2), pages 146-154, May.
    14. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    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. Tikani, Hamid & Setak, Mostafa & Demir, Emrah, 2021. "A risk-constrained time-dependent cash-in-transit routing problem in multigraph under uncertainty," European Journal of Operational Research, Elsevier, vol. 293(2), pages 703-730.
    2. Soriano, Adria & Vidal, Thibaut & Gansterer, Margaretha & Doerner, Karl, 2020. "The vehicle routing problem with arrival time diversification on a multigraph," European Journal of Operational Research, Elsevier, vol. 286(2), pages 564-575.
    3. 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.
    4. 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.
    5. Maaike Hoogeboom & Wout Dullaert & David Lai & Daniele Vigo, 2020. "Efficient Neighborhood Evaluations for the Vehicle Routing Problem with Multiple Time Windows," Transportation Science, INFORMS, vol. 54(2), pages 400-416, March.
    6. Belhaiza, Slim & M’Hallah, Rym & Al-Qarni, Munirah, 2023. "A data-driven game theoretic multi-objective hybrid algorithm for the Dial-A-Ride Problem with multiple time windows," Transportation Research Part A: Policy and Practice, Elsevier, vol. 178(C).
    7. Allahyari, Somayeh & Yaghoubi, Saeed & Van Woensel, Tom, 2021. "A novel risk perspective on location-routing planning: An application in cash transportation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 150(C).
    8. Chen, Yi-Ting & Sun, Edward W. & Chang, Ming-Feng & Lin, Yi-Bing, 2021. "Pragmatic real-time logistics management with traffic IoT infrastructure: Big data predictive analytics of freight travel time for Logistics 4.0," International Journal of Production Economics, Elsevier, vol. 238(C).
    9. Zandieh, Fatemeh & Ghannadpour, Seyed Farid & Mazdeh, Mohammad Mahdavi, 2024. "New integrated routing and surveillance model with drones and charging station considerations," European Journal of Operational Research, Elsevier, vol. 313(2), pages 527-547.

    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. Schneider, M., 2016. "The vehicle-routing problem with time windows and driver-specific times," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 65941, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    2. Schneider, Michael, 2016. "The vehicle-routing problem with time windows and driver-specific times," European Journal of Operational Research, Elsevier, vol. 250(1), pages 101-119.
    3. Schneider, Michael & Schwahn, Fabian & Vigo, Daniele, 2017. "Designing granular solution methods for routing problems with time windows," European Journal of Operational Research, Elsevier, vol. 263(2), pages 493-509.
    4. Goeke, Dominik & Schneider, Michael, 2015. "Routing a mixed fleet of electric and conventional vehicles," European Journal of Operational Research, Elsevier, vol. 245(1), pages 81-99.
    5. 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.
    6. Goeke, D. & Schneider, M., 2015. "Routing a Mixed Fleet of Electric and Conventional Vehicles," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 65939, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    7. Soriano, Adria & Vidal, Thibaut & Gansterer, Margaretha & Doerner, Karl, 2020. "The vehicle routing problem with arrival time diversification on a multigraph," European Journal of Operational Research, Elsevier, vol. 286(2), pages 564-575.
    8. Michael Schneider & Andreas Stenger & Dominik Goeke, 2014. "The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations," Transportation Science, INFORMS, vol. 48(4), pages 500-520, November.
    9. Sandra Zajac, 2018. "On a two-phase solution approach for the bi-objective k-dissimilar vehicle routing problem," Journal of Heuristics, Springer, vol. 24(3), pages 515-550, June.
    10. Goeke, Dominik, 2019. "Granular tabu search for the pickup and delivery problem with time windows and electric vehicles," European Journal of Operational Research, Elsevier, vol. 278(3), pages 821-836.
    11. 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.
    12. 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.
    13. Asvin Goel & Thibaut Vidal, 2014. "Hours of Service Regulations in Road Freight Transport: An Optimization-Based International Assessment," Transportation Science, INFORMS, vol. 48(3), pages 391-412, August.
    14. Maaike Hoogeboom & Wout Dullaert & David Lai & Daniele Vigo, 2020. "Efficient Neighborhood Evaluations for the Vehicle Routing Problem with Multiple Time Windows," Transportation Science, INFORMS, vol. 54(2), pages 400-416, March.
    15. Mohamed Cissé & Semih Yalçindag & Yannick Kergosien & Evren Sahin & Christophe Lenté & Andrea Matta, 2017. "OR problems related to Home Health Care: A review of relevant routing and scheduling problems," Post-Print hal-01736714, HAL.
    16. Allahyari, Somayeh & Yaghoubi, Saeed & Van Woensel, Tom, 2021. "A novel risk perspective on location-routing planning: An application in cash transportation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 150(C).
    17. Jian Li & Yang Li & Panos M. Pardalos, 2016. "Multi-depot vehicle routing problem with time windows under shared depot resources," Journal of Combinatorial Optimization, Springer, vol. 31(2), pages 515-532, February.
    18. Liu, Ran & Xie, Xiaolan & Augusto, Vincent & Rodriguez, Carlos, 2013. "Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care," European Journal of Operational Research, Elsevier, vol. 230(3), pages 475-486.
    19. Schmid, Verena & Doerner, Karl F. & Laporte, Gilbert, 2013. "Rich routing problems arising in supply chain management," European Journal of Operational Research, Elsevier, vol. 224(3), pages 435-448.
    20. Derigs, U. & Kaiser, R., 2007. "Applying the attribute based hill climber heuristic to the vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 177(2), pages 719-732, 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:eee:ejores:v:275:y:2019:i:1:p:93-107. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.