Refinements of the column generation process for the Vehicle Routing Problem with Time Windows

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    The Vehicle Routing Problem with Time Windows is a generalization of the well known capacity constrained Vehicle Routing Problem. A homogeneous fleet of vehicles has to service a set of the customers and fulfill their demands. The service of the customers can only start within a well-defined time interval denoted the time window. The objective is to determine routes for the vehicles that minimizes the accumulated cost (or distance) with respect to the above mentioned constraints. Currently the best approaches for determining optimal solutions are based on column generation and Branch-and-Bound, also known as Branch-and-Price. This paper presents two ideas for run-time improvements of the Branch-and-Price framework for the Vehicle Routing Problem with Time Windows. Both ideas reveal a significant potential for using run-time refinements when speeding up an exact approach without compromising optimality.
    Original languageEnglish
    JournalJournal of Systems Science and Systems Engineering
    Volume13
    Issue number3
    Pages (from-to)326-341
    ISSN1004-3756
    Publication statusPublished - 2004

    Keywords

    • column generation
    • branch-and-bound
    • shortest path
    • time windows
    • Vehicle routing

    Cite this