Integer programming formulations for the time-dependent elementary shortest path problem with resource constraints

The impact of congestion in transportation has become one of the main concerns regarding urban planing in large cities. Time-Dependent Vehicle Routing Problems (TDVRPs) is the name given to a broad family of VRPs that explicitly incorporate the congestion by considering variable travel times. In thi...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Lera-Romero, G., Miranda-Bront, J.J.
Formato:	JOUR
Materias:	Elementary Shortest Path Integer Programming Time-Dependent Travel Times
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_15710653_v69_n_p53_LeraRomero
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	todo:paper_15710653_v69_n_p53_LeraRomero
record_format	dspace
spelling	todo:paper_15710653_v69_n_p53_LeraRomero2023-10-03T16:27:10Z Integer programming formulations for the time-dependent elementary shortest path problem with resource constraints Lera-Romero, G. Miranda-Bront, J.J. Elementary Shortest Path Integer Programming Time-Dependent Travel Times The impact of congestion in transportation has become one of the main concerns regarding urban planing in large cities. Time-Dependent Vehicle Routing Problems (TDVRPs) is the name given to a broad family of VRPs that explicitly incorporate the congestion by considering variable travel times. In this paper we study the Time-Dependent Elementary Shortest Path Problem with Resource Constraints (TDESPPRC), that appears as the pricing sub-problem in column generation-based approaches for TDVRPs. We consider two integer programming formulations which exploit the characteristics of the time-dependent travel time function and are evaluated on benchmark instances. On preliminary computational experiments, the approach is able to effectively solve instances with up to 25 vertices in reasonable times, showing its potential to be used within a Branch and Price algorithm. © 2018 Elsevier B.V. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_15710653_v69_n_p53_LeraRomero
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Elementary Shortest Path Integer Programming Time-Dependent Travel Times
spellingShingle	Elementary Shortest Path Integer Programming Time-Dependent Travel Times Lera-Romero, G. Miranda-Bront, J.J. Integer programming formulations for the time-dependent elementary shortest path problem with resource constraints
topic_facet	Elementary Shortest Path Integer Programming Time-Dependent Travel Times
description	The impact of congestion in transportation has become one of the main concerns regarding urban planing in large cities. Time-Dependent Vehicle Routing Problems (TDVRPs) is the name given to a broad family of VRPs that explicitly incorporate the congestion by considering variable travel times. In this paper we study the Time-Dependent Elementary Shortest Path Problem with Resource Constraints (TDESPPRC), that appears as the pricing sub-problem in column generation-based approaches for TDVRPs. We consider two integer programming formulations which exploit the characteristics of the time-dependent travel time function and are evaluated on benchmark instances. On preliminary computational experiments, the approach is able to effectively solve instances with up to 25 vertices in reasonable times, showing its potential to be used within a Branch and Price algorithm. © 2018 Elsevier B.V.
format	JOUR
author	Lera-Romero, G. Miranda-Bront, J.J.
author_facet	Lera-Romero, G. Miranda-Bront, J.J.
author_sort	Lera-Romero, G.
title	Integer programming formulations for the time-dependent elementary shortest path problem with resource constraints
title_short	Integer programming formulations for the time-dependent elementary shortest path problem with resource constraints
title_full	Integer programming formulations for the time-dependent elementary shortest path problem with resource constraints
title_fullStr	Integer programming formulations for the time-dependent elementary shortest path problem with resource constraints
title_full_unstemmed	Integer programming formulations for the time-dependent elementary shortest path problem with resource constraints
title_sort	integer programming formulations for the time-dependent elementary shortest path problem with resource constraints
url	http://hdl.handle.net/20.500.12110/paper_15710653_v69_n_p53_LeraRomero
work_keys_str_mv	AT leraromerog integerprogrammingformulationsforthetimedependentelementaryshortestpathproblemwithresourceconstraints AT mirandabrontjj integerprogrammingformulationsforthetimedependentelementaryshortestpathproblemwithresourceconstraints
_version_	1782027150517338112

Integer programming formulations for the time-dependent elementary shortest path problem with resource constraints

Ejemplares similares