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.
Información general
Fecha de exposición:septiembre 2019
Fecha de publicación:2019
Idioma del documento:Inglés
Evento:I Simposio Argentino de Informática Industrial e Investigación Operativa (SIIIO 2019) - JAIIO 48 (Salta)
Institución de origen:Sociedad Argentina de Informática e Investigación Operativa
Excepto donde se diga explícitamente, este item se publica bajo la siguiente licencia Creative Commons Attribution-ShareAlike 3.0 Unported (CC BY-SA 3.0)