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: 2013
Materias:
Branch and Cut
Combinatorial optimization
Integer programming
Time-Dependent TSP
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03772217_v_n_p_MirandaBront
http://hdl.handle.net/20.500.12110/paper_03772217_v_n_p_MirandaBront
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_03772217_v_n_p_MirandaBront
record_format dspace
spelling paper:paper_03772217_v_n_p_MirandaBront2023-06-08T15:39:01Z 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 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. 2013 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03772217_v_n_p_MirandaBront http://hdl.handle.net/20.500.12110/paper_03772217_v_n_p_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
spellingShingle Branch and Cut
Combinatorial optimization
Integer programming
Time-Dependent TSP
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
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 2013
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03772217_v_n_p_MirandaBront
http://hdl.handle.net/20.500.12110/paper_03772217_v_n_p_MirandaBront
work_keys_str_mv AT mirandabrontjuanjose facetsandvalidinequalitiesforthetimedependenttravellingsalesmanproblem
AT mendezdiazisabel facetsandvalidinequalitiesforthetimedependenttravellingsalesmanproblem
AT zabalapaula facetsandvalidinequalitiesforthetimedependenttravellingsalesmanproblem
_version_ 1768544136505327616

Ejemplares similares