A dynamic programming algorithm for the shortest path problem with time windows and linear node costs
✍ Scribed by Ioachim, Irina; G�linas, Sylvie; Soumis, Fran�ois; Desrosiers, Jacques
- Publisher
- John Wiley and Sons
- Year
- 1998
- Tongue
- English
- Weight
- 154 KB
- Volume
- 31
- Category
- Article
- ISSN
- 0028-3045
No coin nor oath required. For personal study only.
✦ Synopsis
This paper presents an optimal dynamic programming algorithm, the first such algorithm in the literature to solve the shortest path problem with time windows and additional linear costs on the node service start times. To optimally solve this problem, we propose a new dynamic programming algorithm which takes into account the linear node costs. This problem has numerous applications: Two examples are job-shop scheduling and aircraft routing and scheduling. To underline the efficiency of the proposed method, we compare it with an approach based on partial discretization of the time windows. It clearly outperformed the discretization approach on test problems with wide time windows and many nodes with negative costs.