EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

2938. Models for the Traveling Salesman Problem with Job-Time

Invited abstract in session TB-26: Advanced Topics in Combinatorial Optimization, stream Combinatorial Optimization.

Tuesday, 10:30-12:00
Room: 012 (building: 208)

Authors (first author is the speaker)

1. pablo gutierrez
departamento de ingeniería industrial, universidad de concepción
2. Carlos Contreras-Bolton
Departamento de Ingeniería Industrial, Universidad de Concepción

Abstract

The traveling salesman problem with Job-Time (TSPJ) is a variant of the classic traveling salesman problem. In the TSPJ, the traveler visits a set of nodes, ensuring one visit to each of them while he initiates a job. The time of each job depends on the node where it is performed. Once started, the traveler moves to the next node, and the job continues autonomously. The aim is to minimize the maximum completion time, also known as the makespan. However, since the problem is NP-hard, the existing mixed integer linear programming (MILP) models cannot be efficiently solved for medium and large instances. Therefore, we propose a new MILP model for the TSPJ, which is improved by the computation of valid lower and upper bounds. Moreover, we propose strengthened exponential-size formulations that explicitly incorporate subtour elimination constraints and additional valid inequalities. Based on the proposed model, we also develop an exact branch-and-cut (B&C) algorithm that is able to solve instances of the TSPJ. The new model and B&C algorithm are tested on benchmark symmetric instances from the literature, four sets of instances ranging in size from 17 to 1200 vertices. The computational results show that our B&C outperforms the state-of-the-art MILPs in the two smaller sets of instances. Meanwhile, for medium and large sets, our exact method achieves promising results for both instance sets.

Keywords

Status: accepted

Back to the list of papers