Solving the Traveling Salesman Problem with release dates via branch and cut

In this paper we study the Traveling Salesman Problem with release dates (TSP-rd) and completion time minimization. The TSP-rd considers a single vehicle and a set of customers that must be served exactly once with goods that arrive to the depot over time, during the planning horizon. The time at...

Descripción completa

Detalles Bibliográficos
Autores principales: Miranda Bront, Juan José, Montero, Agustín, Méndez-Díaz, Isabel
Formato: Artículo publishedVersion
Lenguaje:Inglés
Publicado: EURO Journal on Transportation and Logistics (ISSN 2192-4384) 2023
Materias:
Acceso en línea:https://repositorio.utdt.edu/handle/20.500.13098/12234
Aporte de:
id I57-R163-20.500.13098-12234
record_format dspace
spelling I57-R163-20.500.13098-122342023-12-21T07:00:23Z Solving the Traveling Salesman Problem with release dates via branch and cut Miranda Bront, Juan José Montero, Agustín Méndez-Díaz, Isabel Programación lineal Traveling Salesman Problem In this paper we study the Traveling Salesman Problem with release dates (TSP-rd) and completion time minimization. The TSP-rd considers a single vehicle and a set of customers that must be served exactly once with goods that arrive to the depot over time, during the planning horizon. The time at which each requested good arrives is called release date and it is known in advance. The vehicle can perform multiple routes, however, it cannot depart to serve a customer before the associated release date. Thus, the release date of the customers in each route must not be greater than the starting time of the route. The objective is to determine a set of routes for the vehicle, starting and ending at the depot, where the completion time needed to serve all customers is minimized. We propose a new Integer Linear Programming model and develop a branch and cut algorithm with tailored enhancements to improve its performance. The algorithm proved to be able to significantly reduce the computation times when compared to a compact formulation tackled using a commercial mathematical programming solver, obtaining 24 new optimal solutions on benchmark instances with up to 30 customers within one hour. We further extend the benchmark to instances with up to 50 customers where the algorithm proved to be efficient. Building upon these results, the proposed model is adapted to new TSP-rd variants (Capacitated and Prize-Collecting TSP), with different objectives: completion time minimization and traveling distance minimization. To the best of our knowledge, our work is the first in-depth study to report extensive results for the TSP-rd through a branch and cut, establishing a baseline and providing insights for future approaches. Overall, the approach proved to be very effective and gives a flexible framework for several variants, opening the discussion about formulations, algorithms and new benchmark instances. 2023-12-20T18:35:19Z 2023-12-20T18:35:19Z 2023 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion https://repositorio.utdt.edu/handle/20.500.13098/12234 eng info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-nd/4.0/deed.es 12 p. application/pdf application/pdf EURO Journal on Transportation and Logistics (ISSN 2192-4384) Elsevier
institution Universidad Torcuato Di Tella
institution_str I-57
repository_str R-163
collection Repositorio Digital Universidad Torcuato Di Tella
language Inglés
orig_language_str_mv eng
topic Programación lineal
Traveling Salesman Problem
spellingShingle Programación lineal
Traveling Salesman Problem
Miranda Bront, Juan José
Montero, Agustín
Méndez-Díaz, Isabel
Solving the Traveling Salesman Problem with release dates via branch and cut
topic_facet Programación lineal
Traveling Salesman Problem
description In this paper we study the Traveling Salesman Problem with release dates (TSP-rd) and completion time minimization. The TSP-rd considers a single vehicle and a set of customers that must be served exactly once with goods that arrive to the depot over time, during the planning horizon. The time at which each requested good arrives is called release date and it is known in advance. The vehicle can perform multiple routes, however, it cannot depart to serve a customer before the associated release date. Thus, the release date of the customers in each route must not be greater than the starting time of the route. The objective is to determine a set of routes for the vehicle, starting and ending at the depot, where the completion time needed to serve all customers is minimized. We propose a new Integer Linear Programming model and develop a branch and cut algorithm with tailored enhancements to improve its performance. The algorithm proved to be able to significantly reduce the computation times when compared to a compact formulation tackled using a commercial mathematical programming solver, obtaining 24 new optimal solutions on benchmark instances with up to 30 customers within one hour. We further extend the benchmark to instances with up to 50 customers where the algorithm proved to be efficient. Building upon these results, the proposed model is adapted to new TSP-rd variants (Capacitated and Prize-Collecting TSP), with different objectives: completion time minimization and traveling distance minimization. To the best of our knowledge, our work is the first in-depth study to report extensive results for the TSP-rd through a branch and cut, establishing a baseline and providing insights for future approaches. Overall, the approach proved to be very effective and gives a flexible framework for several variants, opening the discussion about formulations, algorithms and new benchmark instances.
format Artículo
publishedVersion
author Miranda Bront, Juan José
Montero, Agustín
Méndez-Díaz, Isabel
author_facet Miranda Bront, Juan José
Montero, Agustín
Méndez-Díaz, Isabel
author_sort Miranda Bront, Juan José
title Solving the Traveling Salesman Problem with release dates via branch and cut
title_short Solving the Traveling Salesman Problem with release dates via branch and cut
title_full Solving the Traveling Salesman Problem with release dates via branch and cut
title_fullStr Solving the Traveling Salesman Problem with release dates via branch and cut
title_full_unstemmed Solving the Traveling Salesman Problem with release dates via branch and cut
title_sort solving the traveling salesman problem with release dates via branch and cut
publisher EURO Journal on Transportation and Logistics (ISSN 2192-4384)
publishDate 2023
url https://repositorio.utdt.edu/handle/20.500.13098/12234
work_keys_str_mv AT mirandabrontjuanjose solvingthetravelingsalesmanproblemwithreleasedatesviabranchandcut
AT monteroagustin solvingthetravelingsalesmanproblemwithreleasedatesviabranchandcut
AT mendezdiazisabel solvingthetravelingsalesmanproblemwithreleasedatesviabranchandcut
_version_ 1808040631600152576