A dynamic programming algorithm for the shortest path problem with time windows and linear node costs
1998; Wiley; Volume: 31; Issue: 3 Linguagem: Inglês
10.1002/(sici)1097-0037(199805)31
ISSN1097-0037
AutoresIrina Ioachim, Sylvie G�linas, Fran�ois Soumis, Jacques Desrosiers,
Tópico(s)Scheduling and Optimization Algorithms
ResumoThis 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. © 1998 John Wiley & Sons, Inc. Networks 31: 193–204, 1998
Referência(s)