On Alternative Formulations to the Shortest Path Problem with Time Windows and Capacity Constraints

The elementary shortest-path problem with time-windows and capac-ity constraints is a problem used for solving vehicle-routing and crew-scheduling applications. It occurs as a sub-problem used to implicitly generate the set of all feasible routes and schedules in the column-generation formulation of...

Descripción completa

Detalles Bibliográficos
Autores principales: Vitale, Ignacio, Dondo, Rodolfo
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2019
Materias:
Ciencias Informáticas
Shortest path problem
Alternative formulations
Column generation
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/89663
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-89663
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
Shortest path problem
Alternative formulations
Column generation
spellingShingle Ciencias Informáticas
Shortest path problem
Alternative formulations
Column generation
Vitale, Ignacio
Dondo, Rodolfo
On Alternative Formulations to the Shortest Path Problem with Time Windows and Capacity Constraints
topic_facet Ciencias Informáticas
Shortest path problem
Alternative formulations
Column generation
description The elementary shortest-path problem with time-windows and capac-ity constraints is a problem used for solving vehicle-routing and crew-scheduling applications. It occurs as a sub-problem used to implicitly generate the set of all feasible routes and schedules in the column-generation formulation of the vehicle routing problem with time windows and its variations. In the problem there is a directed graph with a source node and a destination node, and each arc has a cost and a vector of weights specifying its requirements of a resource with a finite capacity. A minimum cost source–destination directed path is sought such that the total consumption of the resource does not exceed the capacity. The problem ins NP-hard in the strong sense. We review integer-linear formulation to the problem and compare them in order to study their computational efficiency.
format Objeto de conferencia
Objeto de conferencia
author Vitale, Ignacio
Dondo, Rodolfo
author_facet Vitale, Ignacio
Dondo, Rodolfo
author_sort Vitale, Ignacio
title On Alternative Formulations to the Shortest Path Problem with Time Windows and Capacity Constraints
title_short On Alternative Formulations to the Shortest Path Problem with Time Windows and Capacity Constraints
title_full On Alternative Formulations to the Shortest Path Problem with Time Windows and Capacity Constraints
title_fullStr On Alternative Formulations to the Shortest Path Problem with Time Windows and Capacity Constraints
title_full_unstemmed On Alternative Formulations to the Shortest Path Problem with Time Windows and Capacity Constraints
title_sort on alternative formulations to the shortest path problem with time windows and capacity constraints
publishDate 2019
url http://sedici.unlp.edu.ar/handle/10915/89663
work_keys_str_mv AT vitaleignacio onalternativeformulationstotheshortestpathproblemwithtimewindowsandcapacityconstraints
AT dondorodolfo onalternativeformulationstotheshortestpathproblemwithtimewindowsandcapacityconstraints
bdutipo_str Repositorios
_version_ 1764820490156769283

Ejemplares similares