[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

贾永基;  谷寒雨;  席裕庚

上海交通大学自动化研究所, 上海 200030

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.

提出了一类特殊的动态车辆调度问题——动态独占性带时间窗口装卸货问题.给出了问题的数学描述, 分析了其静态性质, 并把问题简化为不对称带时间窗口旅行商问题.提出了求解该动态问题的滚动时域调度算法, 通过时域的不断滚动, 不仅可以跟踪问题的动态变化, 还由于每次滚动只对部分客户进行处理, 可以减少问题的求解时间.并分析了算法的3个要素:当前客户窗口、当前客户窗口的调度和滚动策略.测试结果验证了算法在求解动态车辆调度问题中的有效性.

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