Show simple item record

dc.rights.licensehttps://creativecommons.org/licenses/by-nc-nd/4.0/deed.eses_AR
dc.contributor.authorMiranda Bront, Juan Josées_AR
dc.contributor.authorMontero, Agustínes_AR
dc.contributor.authorMéndez-Díaz, Isabeles_AR
dc.date.accessioned2023-12-20T18:35:19Z
dc.date.available2023-12-20T18:35:19Z
dc.date.issued2023
dc.identifier.urihttps://repositorio.utdt.edu/handle/20.500.13098/12234
dc.description.abstractIn 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.es_AR
dc.format.extent12 p.es_AR
dc.format.mediumapplication/pdfes_AR
dc.languageenges_AR
dc.publisherEURO Journal on Transportation and Logistics (ISSN 2192-4384)es_AR
dc.publisherElsevieres_AR
dc.rightsinfo:eu-repo/semantics/openAccesses_AR
dc.subjectProgramación lineales_AR
dc.titleSolving the Traveling Salesman Problem with release dates via branch and cutes_AR
dc.typeinfo:eu-repo/semantics/articlees_AR
dc.subject.keywordTraveling Salesman Problemes_AR
dc.type.versioninfo:eu-repo/semantics/publishedVersiones_AR


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record