IDEAS home Printed from https://ideas.repec.org/p/ems/eureir/17350.html

The Vehicle Rescheduling Problem

Author

Listed:
  • Spliet, R.
  • Gabor, A.F.
  • Dekker, R.

Abstract

The capacitated vehicle routing problem is to find a routing schedule describing the order in which geographically dispersed customers are visited to satisfy demand by supplying goods stored at the depot, such that the traveling costs are minimized. In many practical applications, a long term routing schedule has to be made for operational purposes, often based on average demand estimates. When demand substantially differs, constructing a new schedule is beneficial. The vehicle rescheduling problem is to find a new schedule that not only minimizes the total traveling costs but also minimizes the costs of deviating from the original schedule. In this paper two mathematical programming formulations of the rescheduling problem are presented as well as two heuristic methods, a two-phase heuristic and a modified savings heuristic. Computational and analytical results show that for sufficiently high deviation costs, the two-phase heuristic generates a schedule that is on average close to optimal or even guaranteed optimal, for all considered problem instances. The modified savings heuristic generates schedules of constant quality, however the two-phase heuristic produces schedules that are on average closer to the optimum.

Suggested Citation

  • Spliet, R. & Gabor, A.F. & Dekker, R., 2009. "The Vehicle Rescheduling Problem," Econometric Institute Research Papers EI 2009-43, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    • Handle: RePEc:ems:eureir:17350
    as

    Download full text from publisher

    File URL: https://repub.eur.nl/pub/17350/EI2009-43.pdf
    Download Restriction: no
    ---><---

    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. Haughton, Michael A., 1998. "The performance of route modification and demand stabilization strategies in stochastic vehicle routing," Transportation Research Part B: Methodological, Elsevier, vol. 32(8), pages 551-566, November.
    3. Li, Jing-Quan & Mirchandani, Pitu B. & Borenstein, Denis, 2009. "A Lagrangian heuristic for the real-time vehicle rescheduling problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 45(3), pages 419-433, May.
    4. Tan, K.C. & Cheong, C.Y. & Goh, C.K., 2007. "Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation," European Journal of Operational Research, Elsevier, vol. 177(2), pages 813-839, March.
    5. R. Baldacci & E. Hadjiconstantinou & A. Mingozzi, 2004. "An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation," Operations Research, INFORMS, vol. 52(5), pages 723-738, October.
    6. Laporte, Gilbert, 1992. "The vehicle routing problem: An overview of exact and approximate algorithms," European Journal of Operational Research, Elsevier, vol. 59(3), pages 345-358, June.
    7. Dimitris J. Bertsimas & David Simchi-Levi, 1996. "A New Generation of Vehicle Routing Research: Robust Algorithms, Addressing Uncertainty," Operations Research, INFORMS, vol. 44(2), pages 286-304, April.
    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. Pillac, Victor & Gendreau, Michel & Guéret, Christelle & Medaglia, Andrés L., 2013. "A review of dynamic vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 225(1), pages 1-11.
    2. Van Woensel, T. & Kerbache, L. & Peremans, H. & Vandaele, N., 2008. "Vehicle routing with dynamic travel times: A queueing approach," European Journal of Operational Research, Elsevier, vol. 186(3), pages 990-1007, May.
    3. Chrysanthos E. Gounaris & Wolfram Wiesemann & Christodoulos A. Floudas, 2013. "The Robust Capacitated Vehicle Routing Problem Under Demand Uncertainty," Operations Research, INFORMS, vol. 61(3), pages 677-693, June.
    4. Bertazzi, Luca & Secomandi, Nicola, 2018. "Faster rollout search for the vehicle routing problem with stochastic demands and restocking," European Journal of Operational Research, Elsevier, vol. 270(2), pages 487-497.
    5. Papadakos, Nikolaos & Tzallas-Regas, George & Rustem, Berç & Thoms, Joanne, 2011. "Risky traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 212(1), pages 69-73, July.
    6. Nicola Secomandi, 2001. "A Rollout Policy for the Vehicle Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 49(5), pages 796-802, October.
    7. Hongsheng Zhong & Randolph W. Hall & Maged Dessouky, 2007. "Territory Planning and Vehicle Dispatching with Driver Learning," Transportation Science, INFORMS, vol. 41(1), pages 74-89, February.
    8. Chiang, Wen-Chyuan & Russell, Robert & Xu, Xiaojing & Zepeda, David, 2009. "A simulation/metaheuristic approach to newspaper production and distribution supply chain problems," International Journal of Production Economics, Elsevier, vol. 121(2), pages 752-767, October.
    9. Novoa, Clara & Storer, Robert, 2009. "An approximate dynamic programming approach for the vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 196(2), pages 509-515, July.
    10. Fouad Ben Abdelaziz & Hatem Masri & Houda Alaya, 2017. "A recourse goal programming approach for airport bus routing problem," Annals of Operations Research, Springer, vol. 251(1), pages 383-396, April.
    11. Jinil Han & Chungmok Lee & Sungsoo Park, 2014. "A Robust Scenario Approach for the Vehicle Routing Problem with Uncertain Travel Times," Transportation Science, INFORMS, vol. 48(3), pages 373-390, August.
    12. Ann Melissa Campbell & Martin W. P. Savelsbergh, 2005. "Decision Support for Consumer Direct Grocery Initiatives," Transportation Science, INFORMS, vol. 39(3), pages 313-327, August.
    13. Bhoopalam, Anirudh Kishore & Agatz, Niels & Zuidwijk, Rob, 2018. "Planning of truck platoons: A literature review and directions for future research," Transportation Research Part B: Methodological, Elsevier, vol. 107(C), pages 212-228.
    14. Barrett W. Thomas & Chelsea C. White, 2004. "Anticipatory Route Selection," Transportation Science, INFORMS, vol. 38(4), pages 473-487, November.
    15. 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.
    16. E. Angelelli & R. Mansini & M. Vindigni, 2016. "The Stochastic and Dynamic Traveling Purchaser Problem," Transportation Science, INFORMS, vol. 50(2), pages 642-658, May.
    17. Shubhechyya Ghosal & Wolfram Wiesemann, 2020. "The Distributionally Robust Chance-Constrained Vehicle Routing Problem," Operations Research, INFORMS, vol. 68(3), pages 716-732, May.
    18. Ann M. Campbell & Barrett W. Thomas, 2008. "Probabilistic Traveling Salesman Problem with Deadlines," Transportation Science, INFORMS, vol. 42(1), pages 1-21, February.
    19. Celikoglu, Hilmi Berk, 2013. "Reconstructing freeway travel times with a simplified network flow model alternating the adopted fundamental diagram," European Journal of Operational Research, Elsevier, vol. 228(2), pages 457-466.
    20. Allahviranloo, Mahdieh & Chow, Joseph Y.J. & Recker, Will W., 2014. "Selective vehicle routing problems under uncertainty without recourse," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 62(C), pages 68-88.

    More about this item

    Keywords

    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:ems:eureir:17350. 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: RePub The email address of this maintainer does not seem to be valid anymore. Please ask RePub to update the entry or send us the correct address (email available below). General contact details of provider: https://edirc.repec.org/data/feeurnl.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.