[1] Jia Yongji, Gu Hanyu, Xi Yugeng,. Rolling horizon scheduling algorithmfor dynamic vehicle scheduling system [J]. Journal of Southeast University (English Edition), 2005, 21 (1): 92-96. [doi:10.3969/j.issn.1003-7985.2005.01.020]

Copy

Rolling horizon scheduling algorithmfor dynamic vehicle scheduling system()

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

21

Issue:

2005 1

Page:

92-96

Research Field:

Computer Science and Engineering

Publishing date:

2005-03-30

Info

Title:

Rolling horizon scheduling algorithmfor dynamic vehicle scheduling system

Author(s):

Jia Yongji;  Gu Hanyu;  Xi Yugeng

Institute of Automation, Shanghai Jiaotong University, Shanghai 200030, China

Keywords:

dynamic vehicle scheduling;  rolling horizon scheduling algorithm;  exclusive;  pickup and delivery problem with time windows(PDPTW)

PACS:

TP301

DOI:

10.3969/j.issn.1003-7985.2005.01.020

Abstract:

Dynamic exclusive pickup and delivery problem with time windows(DE-PDPTW), a special dynamic vehicle scheduling problem, is proposed.Its mathematical description is given and its static properties are analyzed, and then the problem is simplified as the asymmetrical traveling salesman problem with time windows.The rolling horizon scheduling algorithm(RHSA)to solve this dynamic problem is proposed.By the rolling of time horizon, the RHSA can adapt to the problem’s dynamic change and reduce the computation time by dealing with only part of the customers in each rolling time horizon.Then, its three factors, the current customer window, the scheduling of the current customer window and the rolling strategy, are analyzed.The test results demonstrate the effectiveness of the RHSA to solve the dynamic vehicle scheduling problem.

References:

[1] Nanry W P, Barnes J W.Solving the pickup and delivery problem with time windows using reactive tabu search [J].Transportation Research, Part B, 2000, 34B(2):107-121.
[2] Lau H C, Liang Z.Pickup and delivery with time windows:algorithms and test case generation[A].In:Proceedings of the 13th IEEE International Conference on Tools with Artificial Intelligence [C].Dallas, Texas:IEEE Computer Society, 2001.333-340.
[3] Li H, Lim A.A metaheuristic for the pickup and delivery problem with time windows [A].In:Proceedings of the 13th IEEE International Conference on Tools with Artificial Intelligence [C].Dallas, Texas:IEEE Computer Society, 2001.160-167.
[4] Jia Yongji, Gu Hanyu, Xi Yugeng.Analysis and algorithm of single-vehicle exclusive pickup and delivery problem with time windows [J].Journal of Shanghai Jiaotong University (Natural Science Edition), to appear in 2005, 39(3).(in Chinese)
[5] Fang Jian, Xi Yugeng.A periodic and event-driven rolling horizon job shop scheduling strategy [J].Control and Decision, 1997, 12(3):159-162.(in Chinese)
[6] Jia Yongji, Gu Hanyu, Xi Yugeng.Quick taboo search algorithm for solving PDPTW problem [J].Control and Decision, 2004, 19(1):57-60.(in Chinese)

Memo

Memo:

Biographies: Jia Yongji(1976—), male, graduate;Xi Yugeng(corresponding author), male, professor, ygxi@sjtu.edu.cn.

Common functions