針對分割配送相關車輛路線問題特性設計之多重起點啟發式方法與其應用

A Multi-start Heuristic with a Problem-specific Operator for the Split Delivery Vehicle Routing Problem and Its Variants

朱佑旌(Yu-Ching Chu)

指導教授 ： 韓復華 ； 卓裕仁

國立交通大學/管理學院/運輸與物流管理學系/博士(2017年)

摘要

分割配送車輛路線問題 (Split Delivery Vehicle Routing Problem, SDVRP) 允許單一顧客的需求可分批被多部車輛服務;它是傳統車輛路線問題的衍生問題。由於配送限制的放鬆，SDVRP具有降低運輸成本的效益，進可提昇企業之競爭力。但就實務而言，需求分割配送會造成顧客的不便，亦伴隨作業成本的增加。有鑑於此，如何使SDVRP兼顧成本效率與服務品質是一重要議題。近年巳有文獻 (Gulczynski et al. [29]) 將最小配送量列入考慮，提出最小配送量限制之分割配送車輛路線問題 (SDVRP with minimum delivery amounts, SDVRR-MDA)。本研究則首次提出以配送次數作為限制的「具配送次數限制的分割配送車輛路線問題」(SDVRP with limited number of deliveries, SDVRP-LND)，以期分割配送能有更高的應用價值。
針對分割問題特性，本研究提出一套一體適用於求解SDVRP，SDVRP-MDA與SDVRP-LND的多重起點啟發式解法，稱為SRC+IMP (Split-delivery Route Construction + solution IMProvement)。SRC為起始解構建模組，適應性地選擇「插入路線」或是「新增路線」的方式逐點構建起始路線。IMP為多鄰域求解改善模組，其中包含一套針對分割問題特性新設計的驅逐鏈鄰域搜尋法。整個演算法SRC+IMP則採用多重起點策略整合SRC與IMP以兼顧搜尋的深度與廣度。
SRC+IMP演算法以目前所有SDVRP相關之國際標竿題庫進行測試，在IMP模組部分採用變動鄰域下降 (Variable Neighborhood Decent,VND) 與隨機變動鄰域下降 (Randomized VND, RVND) 兩種方式執行。測試結果發現SRC+RVND的績效較SRC+VND佳；其結果在SDVRP方面，對32個標竿題求解的平均誤差為0.36%，其績效僅次於ILS (Silva et al. [44])；在SDVRP-MDA方面，對128個標竿題求解的平均誤差為-0.27%，且求得81題並突破36題已知最佳解；在SDVRP-LND方面，22題標竿例題中則求得5題已知最佳解並突破5題，平均求解誤差為0.07%。
本研究亦分析配送次數上限kmax對成本的影響，結果發現當kmax  3時，SDVRP-LND的成本節省效益為4.11%，其與無次數限制的SDVRP相差僅0.06%；這顯示以最多配送三次執行SDVRP-LND可對物流界提供相當的實用價值。

關鍵字

車輛路線問題 ； 分割配送 ； 最小配送量 ； 配送次數限制 ； 多重起點 ； 變動鄰域尋優 ； 節點驅逐鏈

並列摘要

The split-delivery vehicle routing problem (SDVRP), in which the demand of a customer can be split and delivered by several vehicles, would result in less cost than the conventional vehicle routing problem. However, split deliveries also incur extra work for logistics operations and undesirable distractions to customers. How to tradeoff cost efficiency and customer service in the split-delivery related problems thus is an important issue. Recently, Gulczynski et al. [29] proposed a variant of the SDVRP called the SDVRP-MDA, in which the customers each require a minimum delivery amount (MDA) every time they are visited. In this dissertation, we propose a new variant of the SDVRP, i.e., the spit-delivery VRP with limited number of deliveries (SDVRP-LND), which considers the number of deliveries for each customer is restrained to kmax.
We propose a unified multi-start heuristic method, i.e., SRC+IMP (Split-delivery Route Construction + solution IMProvement), to solve the SDVRP and its variants of the SDVRP-MDA and the SDVRP-LND. The initial-solution generator SRC adaptively applies either node-insertion or route-addition procedures, which were designed specifically for the SDVRP and its variants, to generate an initial solution. The IMP conducts local search with multiple neighborhoods for solution improvement, in which we developed a novel node ejection-chain operator for the split-delivery related problems. The overall SRC+IMP combines the SRC and the IMP modules to implement a multi-start solution procedure with a single parameter to control the restart.
The proposed SRC+IMP algorithms are tested with all the related benchmark problems. We conduct the IMP module with two variable neighborhood descent methods, i.e., VND and RVND. It is found that the performance of the SRC+RVND is better than that of the SRC+VND. The results of the SRC+RVND for the SDVRP show that, out of 32 instances tested, the average deviation from the best known solutions (BKS) is 0.36%, which is only second to the ILS algorithm (Silva et al. [44]). For the SDVRP-MDA, out of the 128 instances tested, the results reveal 81 BKS and 36 new best solutions; the average deviation is -0.27%. For the SDVRP-LND, out of the 22 instances tested, we find 5 BKS and 5 new best solutions; the average deviation is 0.07%.
We also investigate the impact of kmax to the potential cost saving of the SDVRP-LND. It is found that, for kmax=3, the average cost saving is 4.11%, which is only 0.06% less than that of the SDVRP. This implies that the SDVRP-LND with kmax=3 can provide a valuable and easy-to-implement tool for logistics operations.

並列關鍵字

Vehicle routing ； Split delivery ； Minimal delivery amount ； Limited number of delivery ； Multi-start ； Variable neighborhood descent ； Node ejection chain

參考文獻

1 7-Eleven. (2017). Takeout service order. from https://www.7-11.com.tw/service/takeout.asp

2 Ahuja, R., Magnanti, T. and Orlin, J. (1993). Network Flows: Theory, Algorithms, and Applications: Prentice Hall.

3 Aleman, R. E. and Hill, R. R. “A Tabu Search with Vocabulary Building Approach for the Vehicle Routing Problem with Split Demands.” International Journal of Metaheuristics, Vol. 1, No. 1, pp. 55-80, 2010.

4 Aleman, R. E., Zhang, X. and Hill, R. R. “An Adaptive Memory Algorithm for the Split Delivery Vehicle Routing problem.” Journal of Heuristics, Vol. 16, No. 3, pp. 441-473, 2010.

5 Archetti, C., Bianchessi, N. and Speranza, M. G. “Branch-and-cut Algorithms for the Split Delivery Vehicle Routing Problem.” European Journal of Operational Research, Vol. 238, No. 3, pp. 685-698, 2014.