需求可分割的同时送取货车辆路径问题求解
Model and Algorithm for the Simultaneous Pickup and Delivery Vehicle Routing Problem with Split Loads
摘要:
针对企业生产原料调运过程，建立多品种货物且供需未匹配情况下需求可分割的大规模送取货车辆路径问题的数学模型，以运输成本最小化为目标。提出基于车辆运输效率的启发式算法构造初始解，并采用变邻域搜索算法对初始解进行改进。测算结果表明基于运输效率的启发式算法对实际运输费用降低20%左右，加入变邻域搜索算法后对初始解有3%左右的改进。
Abstract:
This paper establishes a mathematical model for a large scaled vehicle routing problem with sim-ultaneous pickup and delivery, the objective is to minimize total transportation cost. A heuristic transportation efficiency based algorithm (TEBA) is developed to gain initial feasible solution, and a local search algorithm based on the variable neighborhood search is used to improve the solution. The computational results show that the TEBA could reduce the actual cost about 20%, and an improvement can be achieved about 3% by the variable neighborhood search.
参考文献
|
[1]
|
Dantzig, G.B. and Ramser, J.H. (1959) The Truck Dispatching Problem. Management Science, 6, 80-91.
[Google Scholar] [CrossRef]
|
|
[2]
|
Dror, M. and Trudeau, P. (1989) Savings by Split Delivery Routing. Transportation Science, 23, 141-145.
[Google Scholar] [CrossRef]
|
|
[3]
|
Min, H. (1989) The Multiple Vehicle Routing Problem with Simultaneous Delivery and Pick-Up Points. Transportation Research Part A: General, 23, 377-386.
[Google Scholar] [CrossRef]
|
|
[4]
|
Mitra, S.A. (2008) Parallel Clustering Technique for the Vehicle Routing Problem with Split Deliveries and Pickups. Journal of the Operational Research Society, 59, 1532-1546.
[Google Scholar] [CrossRef]
|
|
[5]
|
Nowak, M., Ergun, Ö. and White, C.C. (2008) Pickup and Delivery with Split Loads. Transportation Science, 42, 32-43.
[Google Scholar] [CrossRef]
|
|
[6]
|
Nowak, M., Ergun, Ö. and White, C.C. (2009) An Empirical Study on the Benefit of Split Loads with the Pickup and Delivery Problem. European Journal of Operational Research, 198, 734-740.
[Google Scholar] [CrossRef]
|
|
[7]
|
Şahin, M., Çavuşlar, G., Öncan, T., et al. (2013) An Efficient Heuristic for the Multi-Vehicle One-to-One Pickup and Delivery Problem with Split Loads. Transportation Research Part C: Emerging Technologies, 27, 169-188.
[Google Scholar] [CrossRef]
|
|
[8]
|
Chen, Q., Li, K. and Liu, Z. (2014) Model and Algorithm for an Unpaired Pickup and Delivery Vehicle Routing Problem with Split Loads. Transportation Research Part E: Logistics and Transportation Review, 69, 218-235.
[Google Scholar] [CrossRef]
|
|
[9]
|
Mladenović, N. and Hansen, P. (1997) Variable Neighborhood Search. Computers & Operations Research, 24, 1097-1100.
[Google Scholar] [CrossRef]
|