IDEAS home Printed from https://ideas.repec.org/p/ems/eureir/32175.html
   My bibliography  Save this paper

The Time Window Assignment Vehicle Routing Problem

Author

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

Abstract

In many distribution networks, it is vital that time windows in which deliveries are made are assigned to customers for the long term. However, at the moment of assigning time windows demand is not known. In this paper we introduce the time window assignment vehicle routing problem, the TWAVRP. In this problem time windows have to be assigned before demand is known. Next the realization of demand is revealed and an optimal vehicle routing schedule has to be made that satisfies the time window constraints. We assume that different scenarios of demand realizations are known, as well as their probability distribution. The TWAVRP is the problem of assigning time windows such that the expected traveling costs are minimized. We propose a formulation of the TWAVRP and develop two variants of a column generation algorithm to solve the LP relaxation of this formulation. Numerical experiments show that these algorithms provide us with very tight LP-bounds to instances of moderate size in reasonable computation time. We incorporate the column generation algorithm in a branch and price algorithm and find optimal integer solutions to small instances of the TWAVRP. In our numerical experiments, the branch and price algorithm typically finds the optimal solution very early in the branching procedure and spends most time on proving optimality.

Suggested Citation

  • 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.
    • Handle: RePEc:ems:eureir:32175
    as

    Download full text from publisher

    File URL: https://repub.eur.nl/pub/32175/EI2012-07.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. 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.
    2. Martin Desrochers & Jacques Desrosiers & Marius Solomon, 1992. "A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows," Operations Research, INFORMS, vol. 40(2), pages 342-354, April.
    3. Desrochers, Martin & Soumis, Francois, 1988. "A reoptimization algorithm for the shortest path problem with time windows," European Journal of Operational Research, Elsevier, vol. 35(2), pages 242-254, May.
    4. Niklas Kohl & Jacques Desrosiers & Oli B. G. Madsen & Marius M. Solomon & François Soumis, 1999. "2-Path Cuts for the Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 33(1), pages 101-116, February.
    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. Bach, Lukas & Gendreau, Michel & Wøhlk, Sanne, 2015. "Freight railway operator timetabling and engine scheduling," European Journal of Operational Research, Elsevier, vol. 241(2), pages 309-319.
    2. 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.

    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. Spliet, Remy & Desaulniers, Guy, 2015. "The discrete time window assignment vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 244(2), pages 379-391.
    2. Timo Gschwind & Stefan Irnich, 2012. "Effective Handling of Dynamic Time Windows and Synchronization with Precedences for Exact Vehicle Routing," Working Papers 1211, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    3. Stefan Irnich & Daniel Villeneuve, 2006. "The Shortest-Path Problem with Resource Constraints and k -Cycle Elimination for k (ge) 3," INFORMS Journal on Computing, INFORMS, vol. 18(3), pages 391-406, August.
    4. Hang Xu & Zhi-Long Chen & Srinivas Rajagopal & Sundar Arunapuram, 2003. "Solving a Practical Pickup and Delivery Problem," Transportation Science, INFORMS, vol. 37(3), pages 347-364, August.
    5. Stefan Irnich & Guy Desaulniers & Jacques Desrosiers & Ahmed Hadjar, 2010. "Path-Reduced Costs for Eliminating Arcs in Routing and Scheduling," INFORMS Journal on Computing, INFORMS, vol. 22(2), pages 297-313, May.
    6. 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.
    7. Keng Hoo Chuah & Jon C. Yingling, 2005. "Routing for a Just-in-Time Supply Pickup and Delivery System," Transportation Science, INFORMS, vol. 39(3), pages 328-339, August.
    8. Dayarian, Iman & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2015. "A column generation approach for a multi-attribute vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 241(3), pages 888-906.
    9. Remy Spliet & Adriana F. Gabor, 2015. "The Time Window Assignment Vehicle Routing Problem," Transportation Science, INFORMS, vol. 49(4), pages 721-731, November.
    10. Hernandez, Florent & Feillet, Dominique & Giroudeau, Rodolphe & Naud, Olivier, 2016. "Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 249(2), pages 551-559.
    11. Baldacci, Roberto & Mingozzi, Aristide & Roberti, Roberto, 2012. "Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints," European Journal of Operational Research, Elsevier, vol. 218(1), pages 1-6.
    12. Müller, Juliane, 2010. "Approximative solutions to the bicriterion Vehicle Routing Problem with Time Windows," European Journal of Operational Research, Elsevier, vol. 202(1), pages 223-231, April.
    13. Russell Bent & Pascal Van Hentenryck, 2004. "A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 38(4), pages 515-530, November.
    14. Sarac, Abdulkadir & Batta, Rajan & Rump, Christopher M., 2006. "A branch-and-price approach for operational aircraft maintenance routing," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1850-1869, December.
    15. Range, Troels Martin, 2013. "Exploiting Set-Based Structures to Accelerate Dynamic Programming Algorithms for the Elementary Shortest Path Problem with Resource Constraints," Discussion Papers on Economics 17/2013, University of Southern Denmark, Department of Economics.
    16. Taş, D. & Gendreau, M. & Dellaert, N. & van Woensel, T. & de Kok, A.G., 2014. "Vehicle routing with soft time windows and stochastic travel times: A column generation and branch-and-price solution approach," European Journal of Operational Research, Elsevier, vol. 236(3), pages 789-799.
    17. Diego Pecin & Claudio Contardo & Guy Desaulniers & Eduardo Uchoa, 2017. "New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 489-502, August.
    18. Lu, Da & Gzara, Fatma, 2019. "The robust vehicle routing problem with time windows: Solution by branch and price and cut," European Journal of Operational Research, Elsevier, vol. 275(3), pages 925-938.
    19. Vicky Mak & Andreas Ernst, 2007. "New cutting-planes for the time- and/or precedence-constrained ATSP and directed VRP," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 66(1), pages 69-98, August.
    20. Said Dabia & Stefan Ropke & Tom van Woensel, 2019. "Cover Inequalities for a Vehicle Routing Problem with Time Windows and Shifts," Transportation Science, INFORMS, vol. 53(5), pages 1354-1371, September.

    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:32175. 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 (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.