An integer programming approach for the time-dependent traveling salesman problem with time windows

Congestion in large cities and populated areas is one of the major challenges in urban logistics, and should be addressed at different planning and operational levels. The Time Dependent Travelling Salesman Problem (TDTSP) is a generalization of the well known Traveling Salesman Problem (TSP) where...

Descripción completa

Detalles Bibliográficos
Publicado:	2017
Materias:	Branch-and-Cut Integer linear programming Time windows Time-dependent TSP Benchmarking Integer programming Branch and cut Integer Linear Programming Integer linear programming models Operational level Time dependent Time-dependent traveling salesman Travelling salesman problem Traveling salesman problem
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03050548_v88_n_p280_Montero http://hdl.handle.net/20.500.12110/paper_03050548_v88_n_p280_Montero
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_03050548_v88_n_p280_Montero
record_format	dspace
spelling	paper:paper_03050548_v88_n_p280_Montero2023-06-08T15:30:27Z An integer programming approach for the time-dependent traveling salesman problem with time windows Branch-and-Cut Integer linear programming Time windows Time-dependent TSP Benchmarking Integer programming Branch and cut Integer Linear Programming Integer linear programming models Operational level Time dependent Time windows Time-dependent traveling salesman Travelling salesman problem Traveling salesman problem Congestion in large cities and populated areas is one of the major challenges in urban logistics, and should be addressed at different planning and operational levels. The Time Dependent Travelling Salesman Problem (TDTSP) is a generalization of the well known Traveling Salesman Problem (TSP) where the travel times are not assumed to be constant along the day. The motivation to consider the time dependency factor is that it enables to have better approximations to many problems arising from practice. In this paper, we consider the Time-Dependent Traveling Salesman Problem with Time Windows (TDTSP-TW), where the time dependence is captured by considering variable average travel speeds. We propose an Integer Linear Programming model for the problem and develop an exact algorithm, which is compared on benchmark instances with another approach from the related literature. The results show that the approach is able to solve instances with up to 40 customers. © 2017 Elsevier Ltd 2017 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03050548_v88_n_p280_Montero http://hdl.handle.net/20.500.12110/paper_03050548_v88_n_p280_Montero
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 Integer linear programming Time windows Time-dependent TSP Benchmarking Integer programming Branch and cut Integer Linear Programming Integer linear programming models Operational level Time dependent Time windows Time-dependent traveling salesman Travelling salesman problem Traveling salesman problem
spellingShingle	Branch-and-Cut Integer linear programming Time windows Time-dependent TSP Benchmarking Integer programming Branch and cut Integer Linear Programming Integer linear programming models Operational level Time dependent Time windows Time-dependent traveling salesman Travelling salesman problem Traveling salesman problem An integer programming approach for the time-dependent traveling salesman problem with time windows
topic_facet	Branch-and-Cut Integer linear programming Time windows Time-dependent TSP Benchmarking Integer programming Branch and cut Integer Linear Programming Integer linear programming models Operational level Time dependent Time windows Time-dependent traveling salesman Travelling salesman problem Traveling salesman problem
description	Congestion in large cities and populated areas is one of the major challenges in urban logistics, and should be addressed at different planning and operational levels. The Time Dependent Travelling Salesman Problem (TDTSP) is a generalization of the well known Traveling Salesman Problem (TSP) where the travel times are not assumed to be constant along the day. The motivation to consider the time dependency factor is that it enables to have better approximations to many problems arising from practice. In this paper, we consider the Time-Dependent Traveling Salesman Problem with Time Windows (TDTSP-TW), where the time dependence is captured by considering variable average travel speeds. We propose an Integer Linear Programming model for the problem and develop an exact algorithm, which is compared on benchmark instances with another approach from the related literature. The results show that the approach is able to solve instances with up to 40 customers. © 2017 Elsevier Ltd
title	An integer programming approach for the time-dependent traveling salesman problem with time windows
title_short	An integer programming approach for the time-dependent traveling salesman problem with time windows
title_full	An integer programming approach for the time-dependent traveling salesman problem with time windows
title_fullStr	An integer programming approach for the time-dependent traveling salesman problem with time windows
title_full_unstemmed	An integer programming approach for the time-dependent traveling salesman problem with time windows
title_sort	integer programming approach for the time-dependent traveling salesman problem with time windows
publishDate	2017
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03050548_v88_n_p280_Montero http://hdl.handle.net/20.500.12110/paper_03050548_v88_n_p280_Montero
_version_	1768543609155485696

An integer programming approach for the time-dependent traveling salesman problem with time windows

Ejemplares similares