In this paper, we consider the Time-Dependent Vehicle Routing Problem with Time Windows (TDVRPTW).Travel times are time-dependent, meaning that depending on the departure time from a customer a different travel time is incurred. Because of time-dependency, vehicles' dispatch times from the depot are crucial as road congestion might be avoided. Due to its complexity, all existing solutions to the TDVRPTW are based on (meta-) heuristics and no exact methods are known for this problem. In this paper, we propose the first exact method to solve the TDVRPTW. The MIP formulation is decomposed into a master problem that is solved by means of column generation, and a pricing problem. To insure integrality, the resulting algorithm is embedded in a Branch and Cut framework. We aim to determine the set of routes with the least total travel time. Furthermore, for each vehicle, the best dispatch time from the depot is calculated.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Branch and cut and price for the time dependent vehicle routing problem with time windows


    Beteiligte:
    Dabia, S. (Autor:in) / Röpke, S. (Autor:in) / Woensel, van, T. (Autor:in) / Kok, de, A.G. (Autor:in)

    Erscheinungsdatum :

    01.01.2011


    Anmerkungen:

    Dabia , S , Röpke , S , Woensel, van , T & Kok, de , A G 2011 , Branch and cut and price for the time dependent vehicle routing problem with time windows . BETA publicatie : working papers , vol. 361 , Technische Universiteit Eindhoven , Eindhoven .


    Medientyp :

    Buch


    Format :

    Elektronische Ressource


    Sprache :

    Englisch


    Klassifikation :

    DDC:    000



    Branch and Price for the Time-Dependent Vehicle Routing Problem with Time Windows

    Dabia, S. / Ropke, S. / van Woensel, T. et al. | British Library Online Contents | 2013





    Branch-and-Price on the Split Delivery Vehicle Routing Problem with Time Windows and Alternative Delivery Periods

    Breier, H. / Gossler, T. / Gesellschaft fur Operations Research; Dutch Society of Operations Research; Erasmus Universiteit Rotterdam | British Library Conference Proceedings | 2014