A Note on Solution of the Uncapacitated Single Allocation P-Hub Median Problem

無容量限制單一分派p-中位問題的解法

陳正芳(Jeng-Fung Chen) ； 吳泰熙(Tai-Hsi Wu)

《工業工程學刊》 25卷1期 (2008/01) Pp. 11-17

https://doi.org/10.29977/JCIIE.200801.0002

摘要

本研究係探討無容量限制的單一分派p-中位址問題。在此轉運路網問題中，有n個互動的節點，其中有p個會設為轉運點，以在路網中擔任集中、轉運的角色。而非轉運點間必須經由連結轉運點來相互連結。影響轉運點路網效益的關鍵因素在於轉運點的選定與非轉運點連結轉運點的分派決策。本研究對此問題發展了很有效地非轉接點分派程序，並將其應用於先前所發展的模擬退火法和禁忌名單的混合演算法中。我們以文獻中的AP(Australia Post)例題及新產生的例題作測試，測試結果顯示，此混合演算法能很有效率地求得所有測試之小問題的最佳解。而在求得大問題方面，此混合演算法極優於文獻的最好解法。

關鍵字

p中位址問題 ； 模擬退火法 ； 禁忌搜尋法

並列摘要

We deal with the uncapacitated single allocation p-hub median problem (USApHMP) in this paper. The USApHMP is a location-allocation decision problem with the hub network structure. In hub networks, all hubs, which act as switching points for internodal flows are interconnected and none of the non-hub nodes are directly. The key factors for the hub network design are to properly locate the hubs and allocate the non-hub nodes to the hubs. In this paper, a hybrid heuristic previously developed for solving the uncapacitated multiple allocation hub location problem is adapted to resolve the USApHMP. Computational characteristics of the proposed heuristic are evaluated through extensive computational experiments using a data set from the literature and a newly created data set. Computational results indicate that the proposed heuristic is capable of obtaining optimal solutions for all small-sized problems very efficiently and outperforms a simulated annealing method from the literature for solving large-sized problems.

並列關鍵字

p-hub median problem ； simulated annealing ； tabu search

參考文獻

Chen J. F.(2006).A heuristic for the uncapacitated multiple allocation hub location problem.Journal of the Chinese Institute of Industrial Engineers.23,371-381.

Abdinnour-Helm, S.(1998).A hybrid heuristic for the uncapacitated hub location problem.European Journal of Operational Research.106,489-499.

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

Aykin, T.(1995).Networking policies for hub-and-spoke systems with application to the air transportation system.Transportation Science.29,201-221.

Boland, N.,M. Krishnamoorthy,A. Ernst,J. Ebery(2004).Preprocessing and cutting for multiple allocation hub location problems.European Journal of Operational Research.155,638-653.