EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
3940. Solving the Consistent Travelling Salesman Problem
Invited abstract in session MD-29: Vehicle Routing II, stream Combinatorial Optimization.
Monday, 14:30-16:00Room: 157 (building: 208)
Authors (first author is the speaker)
| 1. | Juan José Salazar González
|
| Estadística e Investigación Operativa, Universidad de La Laguna (Tenerife) | |
| 2. | Daniel Díaz-Ríos
|
| Universidad de La Laguna |
Abstract
The consistent travelling salesman problem looks for a minimum-cost set of Hamiltonian routes, one for every day of a given period. When a customer requires service over several days, the service times on different days must differ by no more than a given threshold (for example, one hour). We analyze two variants of the problem, depending on whether the vehicle is allowed to wait or not at a customer location before its service starts. There are three mathematical models in the literature for the problem without waiting times, and this paper describes a new model appropriated to be solved with a branch-and-cut algorithm. The new model is a multi-commodity flow formulation on which Benders’ Decomposition helps manage a large number of flow variables. There were no mathematical models in the literature for the variant with waiting times, and this paper adapts the four mathematical models to it. We analyze the computational results of the formulations on instances from the literature with up to 100 customers and three days.
Keywords
- Vehicle Routing
- Branch and Cut
- Mathematical Programming
Status: accepted
Back to the list of papers