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:	INPR
Lenguaje:	English
Materias:	Branch and Cut Combinatorial optimization Integer programming Time-Dependent TSP
Acceso en línea:	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	todo:paper_03772217_v_n_p_MirandaBront
record_format	dspace
spelling	todo:paper_03772217_v_n_p_MirandaBront2023-10-03T15:31:32Z 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 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. INPR English info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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)
language	English
orig_language_str_mv	English
topic	Branch and Cut Combinatorial optimization Integer programming Time-Dependent TSP
spellingShingle	Branch and Cut Combinatorial optimization Integer programming Time-Dependent TSP 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
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	INPR
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_v_n_p_MirandaBront
work_keys_str_mv	AT mirandabrontjj facetsandvalidinequalitiesforthetimedependenttravellingsalesmanproblem AT mendezdiazi facetsandvalidinequalitiesforthetimedependenttravellingsalesmanproblem AT zabalap facetsandvalidinequalitiesforthetimedependenttravellingsalesmanproblem
_version_	1782030570540236800

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

Ejemplares similares