## Abstract

We present an algorithm for solving the time-dependent traveling-salesman problem (TDTSP), a generalization of the classical traveling salesman problem in which the cost of travel between two cities depends on the distance between the cities and the position of the transition in the tour. The algorithm is derived by applying Benders decomposition to a mixed-integer linear programming formulation for the problem. We identify trivial TDTSPs for which a standard implementation of the algorithm requires an exponential number of iterations to converge. This motivates the development of an efficient, network-flow-based method for finding Pareto-optimal dual solutions of a highly degenerate subproblem. Preliminary computational experience demonstrates that the use of these Pareto-optimal solutions has a dramatic impact on the performance of the algorithm.

Original language | English (US) |
---|---|

Pages (from-to) | 797-820 |

Number of pages | 24 |

Journal | Naval Research Logistics |

Volume | 43 |

Issue number | 6 |

DOIs | |

State | Published - Sep 1996 |

## ASJC Scopus subject areas

- Modeling and Simulation
- Ocean Engineering
- Management Science and Operations Research