求解带时间窗的装-卸载问题的概率式禁忌搜索算法

中国管理科学 ›› 2004, Vol. ›› Issue (2): 66-72.

求解带时间窗的装-卸载问题的概率式禁忌搜索算法

蓝伯雄, 张跃

清华大学经济管理学院北京 100084

收稿日期:2003-07-30 修回日期:2004-03-12 出版日期:2004-04-28 发布日期:2012-03-07
基金资助:
国家自然科学基金(70071013)

A Probability Tabu Search Method for Solving Pickup And Delivery Problem with Time Windows

LAN Bo-xiong, ZHAN Yue

School of Economics and Management, Tsinghua University, Beijing 100084, China

Received:2003-07-30 Revised:2004-03-12 Online:2004-04-28 Published:2012-03-07

摘要/Abstract

摘要： 本文介绍一个求解有时间窗的装载—卸载问题的概率式禁忌搜索算法。论文首先回顾了求解VRP、PDP问题的主要方法,介绍了搜索算法的基本概念,给出了基于概率式禁忌搜索的详细算法。初步实验表明新算法优于传统禁忌搜索算法。

关键词: 禁忌搜索, 运输路线优化问题(VRP), 装—卸载问题(PDP), 带时间窗的装—卸载问题(PDPTW)

Abstract: In this paper, a new probability tabu search method is proposed to solve the Pickup and Delivery Problem with Time Windows (PDPTW). We first review the basic method of solving VRP and PDP problems, introduce the basic concepts of search method, and then illustrate the heuristic algorithm, which solves PDPTW with probability tabu search technique. Experimental results show that our probability tabu search algorithm yields better solutions than that the traditional method produced.

Key words: tabu search, VRP, PDP, PDPTW

中图分类号:

O224

蓝伯雄, 张跃. 求解带时间窗的装-卸载问题的概率式禁忌搜索算法[J]. 中国管理科学, 2004, (2): 66-72.

LAN Bo-xiong, ZHAN Yue. A Probability Tabu Search Method for Solving Pickup And Delivery Problem with Time Windows[J]. Chinese Journal of Management Science, 2004, (2): 66-72.

参考文献

[1] Psaraftis, H.. An Exact Algorithm for the Single Vehicle Many-to-many Dial-a-ride Problem with time windows[J]. Transportation Science, 1983, 17:351-360.
[2] Sexton, T. R., Lawrence, D. B.. Optimizing single vehicle many-to-many operations with desired delivery times: I Scheduling [J]. Transportation Science, 1985,19: 378-410.
[3] Sexton, T. R., Lawrence, D. B.. Optimizing single vehicle many-to-many operations with desired delivery times: Ⅱ Routing[J]. Transportation Science, 1985, 19:411-435.
[4] Dumas, Y., Desrosiers, J., Soumis, F.. The pickup and delivery problem with time windows[J]. European Journal of Operational Research, 1991, 54: 7-22.
[5] Clarke, G. , Wright, J. W.. Scheduling of Vehicles from A Central Depot to A Number of Delivery Points[J]. Operations Research, 1964, 12: 568-581.
[6] Van der Bruggen, L. J. J. Lenstra, J. K., Schuur, P.C.. Variable-depth search for the single vehicle pickup and delivery problem with time windows[J]. Transportation Science, 1993, 27: 298-311.
[7] Thangiah, S., Nygard, K., Gideon, J. P.. A Genetic lgorithm System for Vehicle Routing with Time Windows[C]. Proceedings of the Seventh Conference on Artificial Intelligence Applications, Miami, Florida, 1991, 322-325.
[8] 李大卫,王莉,王梦光.遗传算法在有时间窗车辆路径问题上的应用[J].系统工程理论与实践,1999,8:65-69.
[9] Glover, F.. Tabu search part I[J]. ORSA Journal of Computing, 1989, 1: 190-206.
[10] Glover, F.. Tabu search: a tutorial [J]. Interfaces,1990, 20: 74-94.
[11] Carlton, W. B., Barnes, J. W.. Solving the traceling salesman problem with time windows using tabu search[J].ⅡE Transactions, 1996, 28: 617-629.
[12] William P. N. , Barnes, J. W.. Solving the pickup and delivery problem with time windows using tabu search[J].Transportation Research Part B, 2000, 34: 107-121.
[13] Lau C. , Liang Z.. Pickup and Delivery with Time Windows, Algorithms and Test Case[Z]. http://www. worldscinet. com/ijait/11/1103/S0218213002000988. html.
[14] Haibing L., Andrew L.. A Metaheuristic for the Pickup and Delivery Problem with Time Windows [R]. ICTAI 2001: 160-168.
[15] Solomon, M.. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research, 1987, 35: 254-265.