EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
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:00Room: 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
- Combinatorial Optimization
- Programming, Mixed-Integer
- Optimization Modeling
Status: accepted
Back to the list of papers