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, Juan José, Méndez Díaz, Isabel, Zabala, Paula
Publicado: 2014
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:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03772217_v236_n3_p891_MirandaBront
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 paper:paper_03772217_v236_n3_p891_MirandaBront
record_format dspace
spelling paper:paper_03772217_v236_n3_p891_MirandaBront2023-06-08T15:39:00Z Facets and valid inequalities for the time-dependent travelling salesman problem Miranda Bront, Juan José Méndez Díaz, Isabel Zabala, Paula 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. 2014 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03772217_v236_n3_p891_MirandaBront 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, Juan José
Méndez Díaz, Isabel
Zabala, Paula
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.
author Miranda Bront, Juan José
Méndez Díaz, Isabel
Zabala, Paula
author_facet Miranda Bront, Juan José
Méndez Díaz, Isabel
Zabala, Paula
author_sort Miranda Bront, Juan José
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
publishDate 2014
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03772217_v236_n3_p891_MirandaBront
http://hdl.handle.net/20.500.12110/paper_03772217_v236_n3_p891_MirandaBront
work_keys_str_mv AT mirandabrontjuanjose facetsandvalidinequalitiesforthetimedependenttravellingsalesmanproblem
AT mendezdiazisabel facetsandvalidinequalitiesforthetimedependenttravellingsalesmanproblem
AT zabalapaula facetsandvalidinequalitiesforthetimedependenttravellingsalesmanproblem
_version_ 1768543373687259136

Ejemplares similares