以迭代區域搜尋啟發法求解週期性區位途程問題

An Iterated Local Search Heuristic for the Periodic Location Routing Problem

林建權(Chien-Chuan Lin)

指導教授 ： 韓復華

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

摘要

週期性區位途程問題 (Periodic Location Routing Problem, PLRP) 為傳統車輛路線問題 (Vehicle Routing Problem, VRP) 的衍生形態。PLRP結合區位途程問題 (Location Routing Problem, LRP) 及週期性車輛路線問題 (Periodic Vehicle Routing Problem, PVRP) 兩者特性，同時考慮多個候選場站及多日週期內不同天數配送組合的決策，更貼近實務的狀況，但亦大幅增加了問題的求解難度。
本研究以迭代區域搜尋法 (Iterated Local Search, ILS) 巨集啟發式解法為架構，建立一套求解PLRP的演算法。主要步驟如下: 首先依據Bin Packing與 k-median的概念，產生5組不同的場站組合，構建出多重起始解。接續以隨機變動鄰域尋優法 (Randomized Variable Neighborhood Descent, RVND) 模組進行改善，其中包含八種傳統路線內與路線間交換法，以及兩種針對PLRP問題特性設計的D-shift和route_reduction交換法來加強深度搜尋能力。最後搭配兩種不同的擾動機制route_pertubation和day_pertubation反覆進行搜尋提升求解廣度。
本研究以C#語言撰寫ILS演算法程式。於PLRP國際標竿題庫共30題例題的測試結果顯示，本研究方法整體平均誤差為6.15%，與目前文獻 (Hemmelmayr [5]) 最佳的大鄰域法求解績效僅相差2.03%，此亦顯示本方法提出之ILS在求解PLRP問題上仍具有相當的競爭力。

關鍵字

週期性區位途程問題 ； 迭代區域搜尋法

並列摘要

The Periodic Location Routing Problem (PLRP) is an extension of the conventional Vehicle Routing Problem (VRP). The PLRP combines the Location Routing Problem (LRP) and the Periodic Vehicle Routing Problem (PVRP) into a more realistic yet more complicated problem to solve than the conventional VRP.
In this thesis, we develop a metaheuristic approach based on the Iterated Local Search (ILS) metaheuristic framework to solve the PLRP. Using bin packing and k-median concepts, we first generate five different depot combinations to construct multiple initial solutions. These solutions are then improved by a Randomized Variable Neighborhood Descent (RVND) module. This module includes eight conventional exchange operators and two new operators, i.e., D-shift and route_reduction that we have designed specifically for the PLRP. Finally, two perturbation mechanisms, i.e., route_pertubation and day_pertubation are applied in each iterated procedure to further diversify the search of solution.
We have coded our proposed algorithms in C# and tested on a set of 30 benchmark instances described by Prodhon [18]. The result show that the average deviation from BKS is 6.15%. The performance gap, when compared to the best solution method in literature, i.e., Large Neighborhood Search (Hemmelmayr [5]), is only 2.03%. This implies that our algorithm is a quite competitive heuristic method for solving the PLRP.

並列關鍵字

Periodic Location Routing Problem (PLRP) ； Iterated Local Search (ILS)

參考文獻

[1] Beltrami, E. J. and Bodin, L. D., (1974), “Networks and Vehicle Routing for Municipal Waste Collection.” Networks, Vol. 4, No. 1, pp. 65-94.

[2] Christofides, N. and Beasley, J. E., (1984), “The Period Routing Problem.” Networks, Vol. 14, No. 2, pp. 237-256.

[3] Clarke, G. and Wright, J. W., (1964), “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points.” Operations Research, Vol. 12, No. 4, pp. 568-581.

[4] Dantzig, G. B. and Ramser, J. H., (1959), “The Truck Dispatching Problem.” Management Science, Vol. 6, No. 1, pp. 80-91.

[5] Hemmelmayr, V. C., (2015), “Sequential and Parallel Large Neighborhood Search Algorithms for the Periodic Location Routing Problem.” European Journal of Operational Research, Vol. 243, No. 1, pp. 52-60.