This dissertation presents a number of algorithms for solving the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW is a generalization of the well known capacity constrained Vehicle Routing Problem (VRP). In the VRP a fleet of vehicles based at a central depot must service a set of customers. In the VRPTW each customer has a time window. Service of a customer must begin within the interval given by the time window. The objective is to minimize some aspect of operating costs (e.g. total distance traveled, number of vehicles needed or a combination of parameters). Since the late 80's and the beginning of the 90's optimal methods for the VRPTW have appeared in the literature. Methods have basicly been based on three approaches: dynamic programming, Lagrange relaxation and column generation (Dantzig-Wolfe). The most successful approaches rely on column generation. Good results have also been obtained using Lagrange relaxation. This dissertation is divided into three parts. First the theoretical framework is described. Thereafter a number of techniques to improve the performance of the column-generation framework are proposed and analyzed. Finally a parallel algorithm based on the sequential algorithm developed in the previous part of the dissertation is developed and analyzed.


    Access

    Download


    Export, share and cite



    Title :

    Parallelization of the Vehicle Routing Problem with Time Windows


    Contributors:

    Publication date :

    1999-05-01


    Remarks:

    Larsen , J 1999 , Parallelization of the Vehicle Routing Problem with Time Windows . IMM-PHD-1999-62 , Technical University of Denmark , Kgs. Lyngby .


    Type of media :

    Book


    Type of material :

    Electronic Resource


    Language :

    English


    Classification :

    DDC:    629



    Agents Toward Vehicle Routing Problem With Time Windows

    Kalina, Petr / Vokřínek, Jiří / Mařík, Vladimír | Taylor & Francis Verlag | 2015


    A vehicle routing problem with flexible time windows

    Tas, D. / Jabali, O. / Woensel, van, T. | BASE | 2013

    Free access

    A vehicle routing problem with flexible time windows

    Taş, Duygu / Van Woensel, Tom / JABALI, OLA | BASE | 2014

    Free access


    Vehicle routing problem with time windows under availability constraints

    Dhahri, Amine / Zidi, Kamel / Ghedira, Khaled | IEEE | 2013