Optimization Online


A Time Bucket Formulation for the TSP with Time Windows

Sanjeeb Dash (sanjeebd***at***us.ibm.com)
Oktay Gunluk (gunluk***at***us.ibm.com)
Andrea Lodi (andrea.lodi***at***unibo.it)
Andrea Tramontani (andrea.tramontani***at***unibo.it)

Abstract: The Traveling Salesman Problem with Time Windows (TSPTW) is the problem of finding a minimum-cost path visiting a set of cities exactly once, where each city must be visited within a given time window. We present an extended formulation for the problem based on partitioning the time windows into sub-windows, which we call "buckets". We present cutting planes for this formulation that are computationally more effective than the ones known in the literature as they exploit the division of the time windows into buckets. To obtain a good partition of the time windows, we propose an iterative LP-based procedure that may produce buckets of different sizes. The LP relaxation of this formulation yields strong lower bounds for the TSPTW and provides a good starting point for our branch-and-cut algorithm. We also present encouraging computational results on hard test problems from the literature, namely asymmetric instances arising from a practical scheduling application, as well as randomly generated symmetric instances. In particular, we solve a number of previously unsolved benchmark instances.


Category 1: Integer Programming


Download: [PDF]

Entry Submitted: 11/05/2009
Entry Accepted: 11/05/2009
Entry Last Modified: 11/12/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society