A Heuristic for the Uncapacitated Multiple Allocation Hub Location Problem

無容量限制的多重分派轉運點位址問題

10.29977/JCIIE.200609.0002

陳正芳(Jeng-Fung Chen)

模擬退火法 ； 禁忌名單 ； 轉運點位址問題 ； hub network ； simulated annealing ； tabu list ； uncapacitated hub location problem

工業工程學刊

23卷5期（2006 / 09 / 01）

371 - 381

英文

無容量限制的多重分派轉運點位址問題為轉運點架構的決策問題。在轉運點路網的架構中，有n個互動的節點，其中有p個會設為轉運點(hub)(p可預先決定或為決策的一部份)，以在路網中擔任集中、轉運的角色，而非轉運點(non-hub)間必須經由連結轉運點來相互連結。非轉運點與轉運點間的連結可分為多重分派(multiple allocation)與單一分派(single allocation)。影響轉運點路網效益的主要關鍵因素在於轉運點的選定(包括轉運點的數目及位址)與非轉運點連結轉運點的分派決策。本論文對有建置成本的多重分派轉運點位址問題推導出一個轉運點數目的上界(upper bound)，及很有效地轉接點位址的選定程序，並將其應用於結合模擬退火法和禁忌名單的混合演算法中。我們以文獻中常使用的CAB(Civil Aeronautics Board)及AP(Australia Post)例題作測試，測試結果顯示，此混合演算法能很有效率地求得大問題的極佳解，並且能很有效率地求得所有測試之小問題的最佳解。

The uncapacitated multiple allocation hub location problem (UMAHLP) is a decision problem with the hub network structure. In hub networks, all hubs, which act as transshipment points for internodal flows, are interconnected and none of the non-hubs are directly connected. The critical factors for designing an economical hub-and-spoke network are to determine the optimal number of hubs, to properly locate hubs, and allocate the non-hubs to the hubs. In this paper an approach to derive an upper bound for the optimal number of hubs along with an effective heuristic based on the simulated annealing method, tabu list, and improvement procedure are presented to resolve the UMAHLP. Computational experiences indicate that by applying the derived upper bound for the number of hubs the proposed heuristic is capable of obtaining the optimal solution for the widely tested CAB and small-sized AP problems very efficiently.

1. Abdinnour-Helm, S.(1998).A hybrid heuristic for the uncapacitated hub location problem.European Journal of Operational Research,106,489-499.
2. Abdinnour-Helm, S.(2001).Using simulated annealing to solve the p-hub median problem.International Journal of Physical Distribution & Logistics Management,31,203-220.
3. Abdinnour-Helm, S.,M. Venkataramanan(1998).Solution approaches to hub location problems.Annals of Operational Research,78,31-50.
4. Ahuja, R.,T. Magnanti,J. Orlin(1993).Network Flows: Theory Algorithms and Applications.
5. Aykin, T.(1995).Networking policies for hub-and-spoke systems with application to the air transportation system.Transportation Science,29,201-221.
6. Aykin, T.(1994).Lagrangian relaxation based approaches to capacitated hub-and-spoke network design problem.European Journal of Operational Research,79,501-523.
7. Bania, N.,P. Bauer,T. Zlatoper(1998).U.S. air passenger service: a taxonomy of route networks, hub locations, and competition.Logistics and Transportation Review,34,53-74.
8. 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.
9. Bryan, D.(1998).Extensions to the hub location problems: formulations and numerical examples.Geographical Analysis,30,315-330.
10. Bryan, D.,M. O`Kelly(1999).Hub-and-spoke networks in air transportation: an analytical review.Journal of Regional Science,39,275-295.
11. Campbell, J.(1994).Integer programming formulations of discrete hub location problems.European Journal of Operational Research,72,387-405.
12. Campbell, J.(1996).Hub location and the p-hub median problem.Operations Research,44,923-935.
13. Campbell, J.,A. Ernst,M. Krishnamoorthy,H. Hamacher,Z. Drezner(2002).Hub location problems.Facility Location-Theory and Applications.
14. Don, T.,S. Harit,J. English,G. Whicker(1995).Hub and spoke networks in truckload trucking: configuration, testing, and operational concerns.Logistics and Transportation,31,209-237.
15. Ernst, A.,M. Krishnamoorthy(1998).Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem.European Journal of Operational Research,104,100-112.
16. Ernst, A.,M. Krishnamoorthy(1996).Efficientalgorithms for the uncapacitated single allocation p-hub median problem.Location science,4,139-154.
17. Glover, F.(1989).Tabu search, part Ⅰ.ORSA Journal on Computing,1,190-206.
18. Kirkpatrick, S.,C. Gelatt,M. Vecchi(1983).Optimization by simulated annealing.Science,220,671-680.
19. Klincewicz, J.(1992).Avoiding local optima in the p-hub location problem using tabu search and GRASP.Annals of Operations Research,40,283-302.
20. Klincewicz, J.(1996).A dual algorithm for the uncapacitated hub location problem.Location Science,4,173-184.
21. Klincewicz, J.(1998).Hub location in backbone tributary network design: a review.Location Science,6,307-335.
22. Kuby, M.,R. Gray(1993).Hub network design problem with stopovers and feeders: case of Federal Express.Transportation Research,27,1-12.
23. Lee, Y.,B. Lim,J. Park(1996).A hub location problem in designing digital data service networks: Lagrangian relaxation approach.Location Science,4,185-194.
24. Mayer, G.,B. Wagner(2002).HubLocator: an exact solution method for the multiple allocation hub location problem.Computers and Operations Research,29,715-739.
25. Metropolis, N.,A. Rosenbluth,A. Teller(1953).Equationof state calculations by fast computing machines.The Journal of Chemical Physics,21,1087-1092.
26. O`Kelly, M.(1992).Hub facility with fixed costs.The Journal of RSAI,71,293-306.
27. O`Kelly, M.(1987).A quadratic integer problem for the location of interacting hub facilities.European Journal of Operational Research,32,393-404.
28. O`Kelly, M.,H. Miller(1994).The hub network design problem: a review and synthesis.Journal of Transport Geography,2,31-40.
29. Skorin-Kapov, D.,J. Skorin-Kapov(1994).On tabu search for the location of interacting hub facilities.European Journal of Operational Research,73,502-509.
30. Toh, R.,R. Higgins(1985).The impact of hub and spoke network centralization and route monopoly on domestic airline profitability.Transportation Journal,24,16-27.

1. Wu, Tai-Hsi,Chen, Jeng-Fung(2008).A NOTE ON SOLUTION OF THE UNCAPACITATED SINGLE ALLOCATION P-HUB MEDIAN PROBLEM.工業工程學刊,25(1),11-17.