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

Abstract

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

CLC Number:

O224

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.

References

[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.

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

PDF (PC)

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 11

Metrics

Comments

Recommended 10

[1]	MA Yong, HE Zheng-wen, ZHENG Wei-bo. Proactive Project Scheduling Optimization Based on Flexible Resource Constraint [J]. Chinese Journal of Management Science, 2020, 28(7): 220-230.
[2]	ZHAO Quan-wu, ZHAO Jun-ping, LIN Ya. A City Logistics Network Optimization Model for Large Chain Retailers under Online-Offline Channel Integration [J]. Chinese Journal of Management Science, 2017, 25(9): 159-167.
[3]	WANG Jing, LIU Hao-tian, Huang Jun. Research on the Route Optimization of Ambulance Treatment and Transportation after Disaster Based on the Injured Classification [J]. Chinese Journal of Management Science, 2017, 25(8): 114-122.
[4]	FU Zhuo, LIU Wen, QIU Meng. A Tabu Search Algorithm for the Vehicle Routing Problem with Soft Time Windows and Split Deliveries by Order [J]. Chinese Journal of Management Science, 2017, 25(5): 78-86.
[5]	LOU Zhen-kai. Bi-level Programming Model and Algorithmof Location-routing Problem in Emergency Logistics [J]. Chinese Journal of Management Science, 2017, 25(11): 151-157.
[6]	LI Jin, FU Pei-hua, LI Xiu-lin, ZHANG Jiang-hua, ZHU Dao-li. Study on Vehicle Routing Problem and Tabu Search Algorithmunder Low-carbon Environment [J]. Chinese Journal of Management Science, 2015, 23(10): 98-106.
[7]	FU Shao-chuan, HU Meng-fei, TANG Fang-cheng. The Optimization of Hub and Spoke Logistics Network Design based on Tabu Search Algorithm [J]. Chinese Journal of Management Science, 2012, (3): 145-151.
[8]	YU Ming-zhu, LI Jian-bin, LEI Dong. The Research of VRP with Pick-up and Delivery and a New Tabu Search Based on Insertion Method [J]. Chinese Journal of Management Science, 2010, 18(2): 89-95.
[9]	WANG Xiao-bo, LI Yi-jun. Research on Optimization of VRPTW Based on Improved Two Phase Algorithm under Electronic Commerce [J]. Chinese Journal of Management Science, 2007, 15(6): 52-59.
[10]	LU Lin, TAN Qing-mei. Vehicle Routing Problem with Simultaneous Delivery and Pick-up Studied Based on Self-telepathy Ant Colony Algorithm [J]. Chinese Journal of Management Science, 2007, 15(2): 97-103.
[11]	Hu Bin, Li Zhicheng. An Optimization-Simulation System for Job Shop Scheduling [J]. Chinese Journal of Management Science, 1999, (4): 11-16.