### Abstract

The traveling salesman problem with time windows (TSPTW) is the problem of finding in a weighted digraph a least-cost tour starting from a selected vertex, visiting each vertex of the graph exactly once according to a given time window, and returning to the starting vertex. This NP-hard problem arises in routing and scheduling applications. This paper introduces a new tour relaxation, called ngL-tour, to compute a valid lower bound on the TSPTW obtained as the cost of a near-optimal dual solution of a problem that seeks a minimum-weight convex combination of nonnecessarily elementary tours. This problem is solved by column generation. The optimal integer TSPTW solution is computed with a dynamic programming algorithm that uses bounding functions based on different tour relaxations and the dual solution obtained. An extensive computational analysis on basically all TSPTW instances (involving up to 233 vertices) from the literature is reported. The results show that the proposed algorithm solves all but one instance and outperforms all exact methods published in the literature so far.

Original language | English |
---|---|

Journal | I N F O R M S Journal on Computing |

Volume | 24 |

Issue number | 3 |

Pages (from-to) | 356-371 |

Number of pages | 16 |

ISSN | 1091-9856 |

DOIs | |

Publication status | Published - 2012 |

Externally published | Yes |

### Keywords

- Software
- Information Systems
- Computer Science Applications
- Management Science and Operations Research
- State-space relaxations
- Time windows
- Traveling salesman problem
- Column generation
- Computational analysis
- Convex combinations
- Dual solutions
- Dynamic programming algorithm
- Exact methods
- Lower bounds
- Routing and scheduling
- State-space
- Weighted digraph
- Algorithms
- Computational complexity
- Vehicle routing
- Graph theory
- STATE-space methods
- COMPUTER
- OPERATIONS
- VEHICLE-ROUTING PROBLEM
- EXACT ALGORITHM
- INEQUALITIES
- CONSTRAINTS
- traveling salesman problem
- time windows
- state-space relaxations

## Cite this

Baldacci, R., Mingozzi, A., & Roberti, R. (2012). New State-Space Relaxations for Solving the Traveling Salesman Problem with Time Windows.

*I N F O R M S Journal on Computing*,*24*(3), 356-371. https://doi.org/10.1287/ijoc.1110.0456