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...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Objeto de conferencia |
| Lenguaje: | Inglés |
| Publicado: |
2019
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/89663 |
| Aporte de: |
| Sumario: | 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. |
|---|