Improved Methods for the Travelling Salesperson Problem with Hotel Selection

Marco Castro, Kenneth Sörensen, Pieter Vansteenwegen, Peter GoosGhent 2012

Abstract

This paper presents a novel integer programming formulation and a high-performance metaheuristic solution procedure for the Travelling Salesperson Problem with Hotel Selection (TSPHS). The TSPHS is a complex variant of the classic TSP that incorporates realistic constraints, such as daily working hour limits and the necessity of overnight stays. Our proposed metaheuristic—a multi-start procedure—outperforms all existing heuristics across standard benchmark instances. Furthermore, by extending a commercial solver with a dedicated cutting plane procedure, we provide several new optimal solutions and establish new best-known solutions for the majority of the benchmark set.

Introduction

The classic Travelling Salesperson Problem (TSP) is a cornerstone of combinatorial optimization, seeking the shortest route to visit a set of customers and return to the origin. However, in practical logistics, salespeople are constrained by human factors: labor regulations, fatigue, and the need for rest.

The Travelling Salesperson Problem with Hotel Selection (TSPHS) addresses these realities. In this variant, a salesperson cannot visit all customers in a single day due to a fixed limit on working hours. Consequently, they must select a hotel to stay in each night. Every workday must begin and end at a hotel, and the hotel where one day concludes must serve as the starting point for the next. This creates a multi-objective optimization challenge:

  1. Primary Objective: Minimize the total number of days (trips) required.
  2. Secondary Objective: Minimize the total travel time across those days.

Methodology

The TSPHS is significantly more complex than the standard TSP because it blends elements of sequencing (TSP) with partitioning (Vehicle Routing Problem, or VRP). The algorithm must decide not only the order of visits but also where to "break" the tour and which specific lodging to utilize.

1. Exact Mathematical Approach

The authors developed a new Integer Programming (IP) formulation to find mathematically proven optimal solutions. To handle the computational complexity, they extended a commercial solver with a dedicated cutting plane procedure. Cutting planes are used to tighten the search space by adding constraints that eliminate non-integer solutions, allowing the solver to converge on the true optimum more efficiently than "off-the-shelf" configurations.

2. The Multi-Start Metaheuristic

For larger instances where exact solvers become computationally prohibitive, the authors introduced a two-phase metaheuristic procedure:

  • Phase I (Construction): The algorithm builds an initial feasible solution that respects the daily time constraints.
  • Phase II (Improvement): The solution is refined using local search operators.

The effectiveness of this metaheuristic stems from the adaptation of successful operators from related fields:

  • TSP Operators: The Lin-Kernighan heuristic, a gold standard for TSP, is used for route optimization.
  • VRP Operators: Relocation (moving a customer to a different day) and exchange (swapping two customers) moves are used to optimize the partitioning of the tour.
  • Custom Operators: Specific moves were designed to handle the unique logic of hotel selection and transitions between workdays.

The "multi-start" nature of the algorithm ensures that these phases are repeated from various starting points, preventing the search from becoming trapped in local optima.

Experimental Evaluation

The study utilized four sets of benchmark instances from existing literature, ranging in scale from 10 to 1,002 customers. This broad range allowed for a rigorous test of both the exact solver (on smaller instances) and the metaheuristic (on large-scale instances).

Key Insights

  • Hybridization: By treating the TSPHS as a hybrid of TSP and VRP, the authors leveraged the most effective algorithms from both domains.
  • Quality vs. Speed: While the multi-start metaheuristic is slightly slower than previous single-pass heuristics, the authors argue that the extra computational time is a justified trade-off. In real-world logistics, reducing the total number of workdays represents a far greater cost saving than the computational cost of the optimization itself.
  • Solver Enhancement: The success of the cutting plane procedure demonstrates that dedicated optimization logic can significantly extend the capabilities of standard commercial solvers.

Results

The proposed methods achieved a "clean sweep" in performance metrics:

  • Superiority: The metaheuristic outperformed all existing heuristics on every benchmark instance tested.
  • New Benchmarks: The IP formulation successfully found several new optimal solutions, providing a new baseline for the research community.
  • Best-Known Solutions: For the largest instances, the authors established new best-known solutions for the majority of the benchmark set.

Conclusion and Future Work

This research significantly advances the state-of-the-art for the TSPHS. However, the authors identify three areas to further align the model with industrial reality:

  1. Vehicle Capacity: Integrating constraints related to the physical limits of the delivery vehicle.
  2. Variable Hotel Costs: Moving beyond the assumption that all hotels are equal to account for varying price points.
  3. Time Windows: Incorporating specific time slots for customer availability, which increases the complexity of the scheduling component.

Summary updated

Abstract

In this talk, a new formulation and a new metaheuristic solution procedure for the travelling salesperson problem with hotel selection (TSPHS) is presented. The metaheuristic is a multi-start procedure that outperforms existing heuristics on all benchmark instances. We also provide a number of new optimal solutions found by a commercial solver extended with a dedicated cutting plane procedure, as well as new best known solutions for most benchmark instances.
BibTeX
@inproceedings{castro2012improved,
  author = {Marco Castro and Kenneth Sörensen and Pieter Vansteenwegen and Peter Goos},
  title = {{Improved Methods for the Travelling Salesperson Problem with Hotel Selection}},
  booktitle = {Ghent},
  year = {2012},
}
Figure