兼具自有與委外之車輛路線問題：巨集啟發式解法之研究

Vehicle Routing Problem with Private Fleet and Common Carrier: Metaheuristic Solution Methods

吳善哲(Shan-Che Wu)

指導教授 ： 韓復華

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

https://doi.org/10.6842/NCTU.2015.00926

摘要

兼具自有與委外之車輛路線問題 (Vehicle Routing Problem with Private Fleet and Common Carrier, VRPPC) 為傳統車輛路線問題 (Vehicle Routing Problem, VRP) 所延伸。其考慮物流中心可以根據顧客的委外成本及需求量，決定顧客是否由自有固定車隊服務，還是委外車隊服務。此問題模擬現實世界中物流配送的情形，具有相當的價值。
本研究求解流程有以下三個步驟：首先，利用委外成本及需求量的比值將顧客初步分成委外顧客及內部顧客，再利用改良式掃描法從起始相對角度掃描內部顧客，考慮最經濟之車種進行車輛路線分割指派構建起始解，每隔45度順、逆時針掃描總共會產生16組起始解，再使用鄰域搜尋改善這16組起始解，其中鄰域搜尋分別為2-opt、Or-opt、Inter-Route-Node-exchange與2-opt*。最後，選擇改善解最佳者與最差者執行紀錄更新法 (Record-to-Record Travel, RRT) ，以擾動機制加強搜尋時的廣度並跳脫局部最佳解之束縛。
本研究所提出之方法論以VRPPC國際標竿例題進行測試，68題例題中發現突破8題文獻已知最佳解，平手4題，整體平均誤差為0.59%。

關鍵字

兼具自有與委外之車輛路線問題 ； 紀錄更新法

並列摘要

The Vehicle Routing Problem with Private Fleet and Common Carrier (VRPPC) is an extension of the conventional Vehicle Routing Problem (VRP). In VRPPC, each customer has to be served by an internal fleet or an external carrier. Therefore, we have to determine which customers are to be served by internal fleets or external carriers according to each customer's demand and external transportation cost. VRPPC simulates the circumstance of distribution in the real world and its application will improve the performance of logistics delivery.
There are three steps in our proposed Meta-heuristics. First, some customers will be selected to be served by external carriers with the ratio of external transportation cost and demand, then we adopted the modified sweep method considering average cost of used full loading vehicle types to construct initial solutions. With rotating 45 degrees clockwise and counterclockwise each time, there are 16 initial solutions in total. Second, these 16 solutions will be improved by 2-opt, Or-opt, Inter-Route-Node-Exchange and 2-opt*, and the best improved solution and the worst improved solution will be chosen as a candidate. Finally, we applied Record-to-Record Travel (RRT) on this candidate to escape the local optimal solution with perturbation procedure.
We compared our best results with best known solutions (BKS) of VRPPC benchmark instances. It showed that our proposed methods have generated 8 breakthrough solutions and 4 reaching BKS. The average deviation of all the tested instances is 0.59%.

並列關鍵字

Vehicle Routing Problem with Private Fleet and Common Carrier (VRPPC) ； Record-to-Record Travel Algorithm (RRT)

參考文獻

[1] Ball, M. O., Golden, B., Assad, A., and Bodin, L., "Planning for truck fleet in the presence of a common-carrier option," Decision Sciences, vol. 14, pp. 103-120, 1983.

[2] Bolduc, M. C., Renaud, J., and Boctor, F., "A heuristic for the routing and carrier selection problem," European Journal of Operational Research, vol. 183, pp. 926-932, 2007.

[3] Bolduc, M. C., Renaudl, J., Boctor, F., and Laporte, G., "A perturbation metaheuristic for the vehicle routing problem with private fleet and common carriers," Journal of the Operational Research Society, vol. 59, pp. 773-787, 2008.

[4] Côté, J. F., and Potvin, J.-Y., "A tabu search heuristic for the vehicle routing problem with private fleet and common carrier," European Journal of Operational Research, vol. 198, pp. 464-469, 2009.

[5] Chu, C. W., "A heuristic algorithm for the truckload and less-than-truckload problem," European Journal of Operational Research, vol. 165, pp. 657-667, 2005.