應用蟻群系統演算法求解區位途程問題

An Ant Colony System Based Heuristic for the Location Routing Problem

陳家和(Chia-Ho Chen)

指導教授 ： 丁慶榮

元智大學/工程學院/工業工程與管理學系/博士(2007年)

https://doi.org/10.6838/YZU.2007.00052

摘要

對於許多企業來說，一個好的物流系統可有效降低供應鏈中的物流成本。透過設施區位與配送途程等決策將可建立一個物流系統，而這些決策可視為一個區位-途程問題(Location Routing Problem)。區位-途程問題即同時針對設施數量、設施區位與配送途程進行最佳化以達到系統總成本的最小化。一個典型的區位-途程問題將包含三個主要的決策：選擇設施區位、指派顧客到已建置的設施與決定車輛配送之途程。由於區位-途程結合了兩個NP-hard的問題：設施區位問題(Facility Location Problem)以及車輛途程問題(Vehicle Routing Problem)，故其求解非常困難。因此，大部分之研究均採用啟發式演算法進行求解。
蟻群最佳化演算法(Ant Colony Optimization)是根據自然界蟻群搜尋食物之方式所建構出之萬用啟發式演算法(Meta-heuristic)。蟻群最佳化演算法已經被廣泛的應用於許多組合最佳化問題(Combinational Optimization Problems)。然而，蟻群最佳化演算法於區位-途程問題之應用並不多，而且至目前為止並無相關研究採用蟻群最佳化演算法求解整個區位-途程問題。蟻群最佳化演算法僅被應用於求解區位-途程問題中的車輛途程問題(Vehicle Routing Problem)。因此，本研究將建構一具有多階段初始解建構準則(multi-phase solution construction rule)之蟻群最佳化演算法，並將其應用於多場站時窗限制區位-途程問題(Multiple Depots Location Routing Problem with Time Windows)與其相關子問題，包括：車輛途程問題、時窗限制車輛途程問題(Vehicle Routing Problem with Time Windows)、多場站車輛途程問題(Multiple Depot Vehicle Routing Problem)、多場站時窗限制車輛途程問題(Multiple Depot Vehicle Routing Problem with Time Windows)、單一資源容量限制設施區位問題(Single Source Capacitated Facility Location Problem)與多場站區位-途程問題(Multiple Depot Location Routing Problem)。此外，本研究亦結合蟻群最佳化演算法、模擬退火法(Simulated Annealing)與拉式啟發式演算法 (Lagrangian Heuristic)建構出數個混合式演算法(Hybrid Algorithm)以改善蟻群最佳化演算法之求解績效。最後，透過大量標竿題庫之求解以測試各演算法之績效。求解結果顯示本研究所建構之演算法在求解多場站時窗限制區位-途程問題與其相關子問題方面均有非常不錯的表現。

關鍵字

蟻群最佳化演算法 ； 多場站時窗限制區位-途程問題 ； 模擬退火法 ； 拉式啟發式演算法 ； 混合式演算法

並列摘要

The design of a logistics system is an important issue in many organizations due to the significant contribution of distributing cost to the total supply chain cost. The success of the logistics system may depend on the location-distribution decisions which are the same as the location routing problem (LRP). The LRP is to find the optimal number and locations of the distribution centers (DCs) as well as the distribution routes starting and ending at the DC, so as to minimize the total system cost. A typical LRP includes the making of three decisions: facility location, customer allocation to facilities and vehicle routing. The LRPs are very difficult to solve since they combine two NP-hard problems: the Facility Location Problem (FLP) and the Vehicle Routing Problem (VRP). Due to the problem complexity, simultaneous solution methods are limited to heuristic algorithms.
The Ant Colony Optimization (ACO) is a distributed meta-heuristic algorithm based on the behavior of ant searching for food. The ACO has been applied extensively in the fields of the combinational optimization problems. However, to our best knowledge, few researchers applied the ACO to solve LRPs and no one solved the whole problem only using ACO. The ACO is only applied to solve the VRP in LRP. Therefore, the main purpose of this dissertation is to propose a novel framework of ACO, which adopts a multi-phase solution construction rule, to solve a Multiple Depot Location Routing Problem with Time Windows (MDLRPTW) and its variant problems, including Vehicle Routing Problem, Vehicle Routing Problem with Time Windows (VRPTW), Multiple Depot Vehicle Routing Problem (MDVRP), Multiple Depot Vehicle Routing Problem with Time Windows (MDVRPTW), Single Source Capacitated Facility Location Problem (SSCFLP) and Multiple Depot Location Routing Problem (MDLRP). An additional purpose here is to hybrid ACO with Simulated Annealing (SA) or Lagrangian heuristic to improve the solution quality. Finally, enormous benchmark instances are tested for all the proposed algorithms. The computational results demonstrate the suitability of applying ACO and hybrid ACO for aforementioned problems.

並列關鍵字

Ant Colony Optimization ； Multiple Depot Location Routing Problem with Time Windows ； Simulated Annealing ； Lagrangian Heuristic ； Hybrid Algorithm

參考文獻

1. Ahuja, R. K., Orlin, J. B., Pallottino, S., Scaparra, M. P., Scutellà, M. G. (2004) “A Multi-exchange Heuristic for the Single-source Capacitated Facility Location Problem,” Management Science, Vol. 50, pp. 749-760.

2. Albareda-Sambola, M., Fernández, E. and Laporte G. (2007) “Heuristic and Lower Bound for a Stochastic Location-routing Problem,” European Journal of Operational Research, Vol. 179, pp. 940-955.

3. Alfa, A. S., Heragu, S. S. and Chen, M. (1991) “A 3-opt Based Simulated Annealing Algorithm for Vehicle Routing Problems,” Computers & Industrial Engineering, Vol. 21, pp. 635-639.

4. Ambrosino, D. and Scutellà, M. G. (2005) “Distribution Network Design: New Problems and Related Models,” European Journal of Operational Research, Vol. 165, pp. 610-624.

5. Bahnski, M. L. (1965) “Integer Programming: Methods, Uses, Computation,” Management Science, Vol. 12, pp. 253-313.