以螞蟻群聚最佳化整合基因演算法求解無資源限制單一指派中位轉接點問題

Integrating Ant Colony Optimization and Genetic Algorithms to Solve Uncapacitated Single Allocation p-Hub Median Problem

軸輻網路(Hub-and-Spoke Network)能有效地提高經濟效率，因此被廣泛地應用於貨運業、網路配線等產業中，但由於問題結構包括轉接點(hub)的選擇及需求點(non-hub)的指派，所以要在合理的時間內求解，大多採用屆主發式演算法來進行求解。因此，本研究以螞蟻群眾最佳化(Ant Colony Optimization, ACO) 演算法為基礎來求解無資源、限制單一指派p個中位轉接點問題(Uncapacitated Single Allocation p-Hub Median Problem, USA p-HMP)。本研究之敘發式演算法，首先針對此問題發展蟻群的法則，有效地選擇適當的轉接點位置，按著以基因演算法(Genetic Algorithm,GA)對需求點進行指派。除此之外，為了加快螞蟻群眾最佳化的收斂效果，並採用資料挖掘(Data Mining)中的挖掘關聯規則(Mining Association Rules)技術將問題的資料先作處理，再把整理出來的結果作為ACO演算法費洛蒙(pheromone)的起始訓練值。在經過例題CAB(Civil Aeronautics Board)的測試後，發現本研究演算法在求解品質上有良好的表現，但在求解時間上因為通過搜尋法則來求解，所以比起其它故發式演算法較慢。

Since hub-and-spoke network is able to increase economic efficiency, it is widely used in many areas. However, due to complexity ofthe problem, it is usualiy solved by heuristic algorithms in a reasonable time. This paper intends to solve uncapacitated single allocation p-hub median problem by integrating ant colony optimization (ACO) and genetic algorithms. In the proposed algorithm, the appropriate position of a hub is first decided by A CO algorithm, the genetic algorithm is then used for customer allocation. Besides, in order to speed up ACO convergence, mining association rules from data mining are adopted to analyze the data first. The results are then used as initial inputs of pheromone. After testing of CAB (Civil Aeronautics Board) data, it is found that the proposed method can obtain better results, although the solution searching time is longer.