Facets and valid inequalities for the time-dependent travelling salesman problem

Mostrar todas las versiones(2)

The Time-Dependent Travelling Salesman Problem (TDTSP) is a generalization of the traditional TSP where the travel cost between two cities depends on the moment of the day the arc is travelled. In this paper, we focus on the case where the travel time between two cities depends not only on the dista...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Miranda-Bront, J.J., Méndez-Díaz, I., Zabala, P.
Formato: JOUR
Materias:
Branch and Cut
Combinatorial optimization
Integer programming
Time-Dependent TSP
Linear programming
Branch and cut
Branch-and-cut algorithms
Travel costs
Travelling salesman problem
Valid inequality
Traveling salesman problem
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_03772217_v236_n3_p891_MirandaBront
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_03772217_v236_n3_p891_MirandaBront
record_format dspace
spelling todo:paper_03772217_v236_n3_p891_MirandaBront2023-10-03T15:31:31Z Facets and valid inequalities for the time-dependent travelling salesman problem Miranda-Bront, J.J. Méndez-Díaz, I. Zabala, P. Branch and Cut Combinatorial optimization Integer programming Time-Dependent TSP Combinatorial optimization Integer programming Linear programming Branch and cut Branch-and-cut algorithms Time-Dependent TSP Travel costs Travelling salesman problem Valid inequality Traveling salesman problem The Time-Dependent Travelling Salesman Problem (TDTSP) is a generalization of the traditional TSP where the travel cost between two cities depends on the moment of the day the arc is travelled. In this paper, we focus on the case where the travel time between two cities depends not only on the distance between them, but also on the position of the arc in the tour. We consider two formulations proposed in the literature, we analyze the relationship between them and derive several families of valid inequalities and facets. In addition to their theoretical properties, they prove to be very effective in the context of a Branch and Cut algorithm. © 2013 Elsevier B.V. All rights reserved. Fil:Miranda-Bront, J.J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Méndez-Díaz, I. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Zabala, P. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_03772217_v236_n3_p891_MirandaBront
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Branch and Cut
Combinatorial optimization
Integer programming
Time-Dependent TSP
Combinatorial optimization
Integer programming
Linear programming
Branch and cut
Branch-and-cut algorithms
Time-Dependent TSP
Travel costs
Travelling salesman problem
Valid inequality
Traveling salesman problem
spellingShingle Branch and Cut
Combinatorial optimization
Integer programming
Time-Dependent TSP
Combinatorial optimization
Integer programming
Linear programming
Branch and cut
Branch-and-cut algorithms
Time-Dependent TSP
Travel costs
Travelling salesman problem
Valid inequality
Traveling salesman problem
Miranda-Bront, J.J.
Méndez-Díaz, I.
Zabala, P.
Facets and valid inequalities for the time-dependent travelling salesman problem
topic_facet Branch and Cut
Combinatorial optimization
Integer programming
Time-Dependent TSP
Combinatorial optimization
Integer programming
Linear programming
Branch and cut
Branch-and-cut algorithms
Time-Dependent TSP
Travel costs
Travelling salesman problem
Valid inequality
Traveling salesman problem
description The Time-Dependent Travelling Salesman Problem (TDTSP) is a generalization of the traditional TSP where the travel cost between two cities depends on the moment of the day the arc is travelled. In this paper, we focus on the case where the travel time between two cities depends not only on the distance between them, but also on the position of the arc in the tour. We consider two formulations proposed in the literature, we analyze the relationship between them and derive several families of valid inequalities and facets. In addition to their theoretical properties, they prove to be very effective in the context of a Branch and Cut algorithm. © 2013 Elsevier B.V. All rights reserved.
format JOUR
author Miranda-Bront, J.J.
Méndez-Díaz, I.
Zabala, P.
author_facet Miranda-Bront, J.J.
Méndez-Díaz, I.
Zabala, P.
author_sort Miranda-Bront, J.J.
title Facets and valid inequalities for the time-dependent travelling salesman problem
title_short Facets and valid inequalities for the time-dependent travelling salesman problem
title_full Facets and valid inequalities for the time-dependent travelling salesman problem
title_fullStr Facets and valid inequalities for the time-dependent travelling salesman problem
title_full_unstemmed Facets and valid inequalities for the time-dependent travelling salesman problem
title_sort facets and valid inequalities for the time-dependent travelling salesman problem
url http://hdl.handle.net/20.500.12110/paper_03772217_v236_n3_p891_MirandaBront
work_keys_str_mv AT mirandabrontjj facetsandvalidinequalitiesforthetimedependenttravellingsalesmanproblem
AT mendezdiazi facetsandvalidinequalitiesforthetimedependenttravellingsalesmanproblem
AT zabalap facetsandvalidinequalitiesforthetimedependenttravellingsalesmanproblem
_version_ 1807322108308488192

Ejemplares similares