INTEC 05402
INSTITUTO DE DESARROLLO TECNOLOGICO PARA LA INDUSTRIA QUIMICA
Unidad Ejecutora - UE
congresos y reuniones científicas
Título:
On Alternative Formulations to the Shortest Path Problem with Time Windows and Capacity Constraints
Autor/es:
VITALE, IGNACIO; DONDO, RODOLFO; VITALE, IGNACIO; DONDO, RODOLFO
Lugar:
Salta
Reunión:
Simposio; Simposio Argentino de Informática Industrial e Investigación Operativa. Jornadas Argentinas de Informática; 2019
Institución organizadora:
Universidad Nacional de Salta
Resumen:
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 is NP-hard in the strong sense. We review integer-linear formulation to the problem and compare them in order to study their computational efficiency.
