Branch-and-cut-and-price for the traveling salesman problem with time windows

Stefan Røpke (Invited author), Oli B.G. Madsen (Invited author)

    Research output: Contribution to conferenceConference abstract for conferenceResearch

    Abstract

    In the traveling salesman problem with time windows (TSPTW) one is given a depot and a set of nodes to be visited by a salesman. The salesman starts his trip at the depot and must visit all nodes while respecting time windows at the nodes. The objective of the problem is to minimize the total distance traveled by the salesman. The TSPTW is formulated as a set-partitioning problem which is solved by using combined cut and column generation. The pricing sub problem in the column generation procedure is a shortest path problem with time window constraints and 2-cycle elimination. A standard column generation process converges slowly for the problem and therefore a stabilization procedure is implemented. Valid inequalities expressed in the original, arc-based variables are added to the LP relaxation to strengthen the lower bound. The proposed algorithm is compared to exact algorithms based on other paradigms such as branch-and-cut, dynamic programming and constraint programming. We cannot conclude that the branch-and-cut-and-price approach always is superior to the others paradigms, but several instances are reported solved to optimality for the rst time and bounds are strengthened for other, still unsolved, instances.
    Original languageEnglish
    Publication date2009
    Publication statusPublished - 2009
    EventInternational workshop on vehicle routing, intermodal transport and related areas - Skodsborg, Denmark
    Duration: 1 Jan 2009 → …

    Conference

    ConferenceInternational workshop on vehicle routing, intermodal transport and related areas
    CitySkodsborg, Denmark
    Period01/01/2009 → …

    Fingerprint

    Dive into the research topics of 'Branch-and-cut-and-price for the traveling salesman problem with time windows'. Together they form a unique fingerprint.

    Cite this