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

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 15

Metrics

Comments

Recommended 0

[1]	Zheng Wang,Peng Lu,Xiangpei Hu. Method of Locating Racks in Mobile-Rack Warehousing System [J]. Chinese Journal of Management Science, 2024, 32(8): 84-94.
[2]	ZHAI Meng-yue, WANG Zheng, LI Yan-tong, HU Xiang-pei. Research on the Problem of Allocating Commodity Storage Locations in a Mobile-rack Storage System [J]. Chinese Journal of Management Science, 2023, 31(3): 167-176.
[3]	GE Xian-long, WEN Peng-zhe, XUE Gui-qin. Two-echelon Dynamic Vehicle Routing Problem with Request Forecasting [J]. Chinese Journal of Management Science, 2022, 30(8): 210-220.
[4]	HUANG Xiao-ling, CHEN Huan-ping, GAO Xiao-nan, WANG Dan, LIU Jin-ping, CHEN Ji-hong. Deliverysplit Milkrun and Supplyhub Collaborate to Optimize Automobiles Parts Inbound logistics [J]. Chinese Journal of Management Science, 2022, 30(7): 59-68.
[5]	YAN Rui, CHEN Li-shuang, ZHU Xiao-ning, TIAN Hao-tong, WEN Ya, ZHANG Qun. Research on Vehicle Routing Problem with Truck and Drone Considering Regional Restriction [J]. Chinese Journal of Management Science, 2022, 30(5): 144-155.
[6]	MOU Jin-jin, CHEN Ju-wei, WANG Shu-yun. Optimization Model of Cold Accumulated Multi-temperature Joint Pickup and Distribution [J]. Chinese Journal of Management Science, 2022, 30(10): 236-246.
[7]	ZHEN Lu, TAN Zhe-yi, XIAO Li-yang, MA Cheng-le. Research on Parcel Sorting Optimization Model and Algorithm for Double-layer Automatic Sorting Systems [J]. Chinese Journal of Management Science, 2021, 29(7): 171-180.
[8]	XU Xiao-feng, LIN Zi-ru, ZHOU Peng. Research on Vehicle Routing Problem of Multiple Oil Depot Passive Distribution under Multi Oil Supply Constraints [J]. Chinese Journal of Management Science, 2021, 29(5): 157-165.
[9]	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.
[10]	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.
[11]	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.
[12]	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.
[13]	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.
[14]	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.
[15]	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.