( 您好!臺灣時間:2021/03/04 01:21
字體大小: 字級放大   字級縮小   預設字形  


研究生(外文):Chien-Yu Liu
論文名稱(外文):Solving Un-capacitated Single Allocation p-Hub-Median Problem with Self-Organizing Feature Map
外文關鍵詞:Location-Allocation problemp-hub median problemSOFM
  • 被引用被引用:3
  • 點閱點閱:219
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:21
  • 收藏至我的研究室書目清單書目收藏:0
「區位---指派問題」在運輸問題中被視為一重要的研究問題。因為人類活動需要在一定的空間佔有特定的區位,而距離在決定這些區位中佔有極大的角色;由於空間是由點線面所組成的,在相同的空間結構裡,常因活動與需求的不同產生不同的結果,因此,區位---指派問題在不同的結構理會表現出不同的特性。其中的p-hub中心問題被廣泛的應用在航空、通訊、郵件送發問題上;回顧文獻對於p-hub中心問題之求解,已有釵h啟發式的方法被廣泛應用求解最佳值,包括基因演算法、模擬退火法、Hopfield network、Branch and Bound Method等等;而這些方法都是預先決定服務中心的數目,找尋最佳的區位,並且使得各需求點的總加權距離最小化。
「Location-Allocation」is a important research area in transportation problem. Human activity need specific location in space, and distance is very important in Location-Allocation problem;Space was composed of points, lines and faces. Different activity and demand generate variational result in the same space structure. Therefore, Location-Allocation problem show different character in different structure. P-hub median was application wide to air, communicate, post system and etc. Much heuristic methods was applied to find optimal solution in p-hub median problem, include genetic algorithm, simulated annealing, hopfield network, branch and bound and etc. all of these heuristic methods were know number of hub previously, and sum of nodes demand must be mini-sum criterion.
This paper solve p-hub median problem with SOFM in number of hub and node were decided. This concept is using self-learning of neurons to get optimal location and cluster. On the side, using experiment design to check parameters in algorithm whether significant in solution quality and efficiency.
This paper is organized as follows:Section 1 introduces background and motive of this paper;Section 2 presents literature related p-hub median problem and SOFM in the past;Section 3 gives p-hub median problem and its mathematical model, In addition, introduces proposed method with SOFM applied to p-hub median problem;A case study and experiment are reported in Section 4 and conclusion follows in Section 5.
中文摘要 I
誌謝 III
目錄 IV
表目錄 VI
圖目錄 VIII
第一章 緒論 1
1.1 研究背景與動機 1
1.2 問題描述 1
1.3 研究目的 2
1.4 研究架構 3
第二章 文獻探討 4
2.1 軸輻網路以及折扣率問題 4
2.3 P-中心中位問題(P-HUB MEDIAN PROBLEM) 7
第三章 研究方法 16
3.1 問題描述 16
3.2 問題模式假設 16
3.3 應用SOFM於無產能限制單一指派P-中心中位問題中 17
3.4 測試資料 29
第四章 實驗設計 30
4.1 兩水準因子實驗(高低因子) 30
4.2 變異數分析 37
4.3 簡化前後比較 70
第五章 實驗結果 72
第六章 結論與建議 76
6.1 結論 76
6.2 未來研究方向 77
參考文獻 78
附錄A AP座標資訊 84
附錄B 各問題最佳值 86
1.A. D. Sherali, C. M. Shetty, ”The rectilinear distance location-allocation problem.”, AIIE TRANS.,V.9,pp.136-143.
2.A. M. Geoffrion and G. W. Graves, ”Multicommodity Distribution System Design By Benders Decomposition”, MANAGEMENT SCIENCE, V.20, N.5, January, p.822-844,1974.
3.A. S. Fotheringham, ”A new set of spatial-interaction models:the theory of competing destinations.”, ENVIRONMENT AND PLANNING A, V.15, pp.15-36, 1983.
4.A. T. Ernst and M. Krishnamoorthy, “Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem, ”EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 104,p.100-112, 1998.
5.T. Aykin, ”Networking policies for hub-and-spoke systems with applications to the air transportation system”, TRANSPORTATION SCIENCE, 29/3, p.199-221, 1995
6.B. Y. Kara, B. C. Tansel, ”On the single-assignment p-hub center problem”, EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 125, PP.648-655, 2000
7.J. E. Beasley,”Or-library:Distributing test problems by electronic mail”, JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 41, pp.1069-1072, 1990
8.B. Bourbeau, T. G. Crainic, B. Gendron, ”Branch-and-bound parallelization strategies applied to a depot location and container fleet management problem”, PARALLEL COMPUTING, 26, pp27-46, 2000
9.J. F. Campbell, ”Hub location and the p-hub median problem”, OPERATIONS RESEARCH 44, No.6, p.923-935, 1996
10.J. F. Campbell,”integer programming formulations of discrete hub location problems”, EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 72, p.387-405, 1994
11.C. M. Liu, R.L. Kao & A.H. Wang”Solving Location-allocation problems with rectilinear distances by simulated annealing”, JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, V.45, No.11, pp.1304-1315, 1994
12.C. T. Su, G. R. Lii, C. C. Tsai, ”Optimal capacitor allocation using fuzzy reasoning and genetic algorithms for distribution systems”, MATHEMATICAL AND COMPUTER MODELLING, 33, p.745-757, 2001
13.Z. Drezner, and G. O.Wesolowsky, ”Facility Location When Demend is Time Dependent”, NAVAL RESEARCH LOGISTICS, Vol.38, NO.5,p.763-777, 1991
14.A.T. Ernst, and M. Krishnamoorthy, ”Efficient algorithms for the uncapacitated single allocation p-hub median problem”, LOCATION SCIENCE, V.4, pp.139-154, 1996
15.A. S. Frank, ”Developmental selection and self-organization.”, BIO SYSTEMS, 40, p.237-243, 1997.
16.G. Mayer, B. Wanger, ”HubLocator:an exact solution method for the multiple allocation hub location problem”, COMPUTERS & OPERATIONS RESEARCH, 29, p.715-739, 2002
17.S. A. Helm & M. A. Venkataramanan, ”Using simulated annealing to solve the p-hub location problem”, IRMIS Working paper, 9304, School of Business, Indina University, Bloomington, Indina, 1993
18.J. Ebery, ”Solving large single allocation p-hub problems with two or three hubs”, EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 128, pp447-458, 2001
19.J. Ebery, M. Krishnamoorthy, A. Ernst, N. Boland, ”The capacitated multiple allocation hub location problem: Formulations and algorithms”, EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 120, pp614-631, 2000
20.Y. Kathawala, and H. Gholamnezhad, ”New Approach to Facility Locations Decisions”, INTERNATIONAL JOURNAL OF SYSTEMS SCIENCE, Vol.18, No.2, pp.389-402, 1987
21.K. A. Willoughby, D. H. Uyeno, ”Resolving splits in location/allocation modeling:a heuristic procedure for transit center decisions”, TRANSPORTATION RESEARCH PART E, 37, p.71-83, 2001
22.Kevincullinane and Mahimkhanna, ”Economies of scale in large container ships”, JOURNAL OF TRANSPORT ECONOMICS AND POLICY, V.33, part2, pp.185-208, 1999
23.J.G. Klincewicz, ”Avoiding local optima in the p-hub location problem using tabu search and grasp”, ANNALS OF OPERATIONS RESEARCH, 40, pp.283-302, 1992
24.J.G. Klincewicz, ”Dual algorithms for the uncapacited hub location problem and the p-hub median problem”, AT&T BELL LAB., Holmedl, NJ 07733, 1994
25.T. Kohonen ,”Automatic formation of topological maps of patterns in a self-organizing system. Proc.2nd Scand. Conf. on Image Analysis”, p. 214-220, Oja, E., Simula. O. (eds.). Espoo: Suomen Hahmontunnistutkimuksen Seura.1981
26.T. Kohonen ,”Self-Organized Formation of Topologically Correct Feature Maps”, BIOLOGICAL CYBERNETICS, Vol. 43, pp. 59-69, 1982
27.S. I. Kusumoto, ”On a Foundation of The Economic Thery of Location-Transport Distance vs. Technological Substitution”, JOURNAL OF REGIONAL SCIENCE, Vol.24, pp.249-270, 1984
28.L. K. Nozick, M. A. Turnquist, ”A two-echelon inventory allocation and distribution center location analysis”TRANSPORTATION RESEARCH PART E, p.425-441, 2001
29.R. F. Love and H. Juel, ”Properties and solution methods for large location-allocation problems.”, J. Opl. Res. Soc., V.33, pp.443-452, 1982.
30.R. F. Love, J. G. Morris, and G. O. Wesolowsky, ”Facilits Location:Models and Methods”, NORTH HOLLAND, NEW YORK, 1988
31.M. C. Su, N. DeClaris, and T. K. Liu, ”Application of neural networks in cluster analysis”, IEEE INT.CONF. ON SYSTEMS, MAN, AND CYBERNETICS, pp.1-6, Orlando, 1997.
32.M. E. O’Kelly, D. L. Bryan, D. Skorin-Kapov and J. Skorin-Kapov, ”Hub network design with single and multiple allocation:A computational study”, LOCATION SCIENCE, Vol.4, No.3, pp.125-138, 1996
33.M. E.O’Kelly, ”Hub-and-spoke network in air transportation:an analytical review”, JOURNAL OF REGIONAL DCIENCE, Vol.39, No.2, p.275-295, 1999
34.M. E. O’Kelly, ”The location of interacting hub facilities”, TRANSPORTATION SCIENCE, Vol.20, No.2, pp.92-105, 1986
35.M. E. O’Kelly, ”A quadratic integer program for the location of interaction hub facilities.”, EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 32, pp.393-404, 1987
36.O. W. Wojahn, ”Airline network structure and the gravity model”, TRANSPORTATION RESEARCH PART E, 37, p.267-279, 2001
37.M. Perez, F. Almeida, ”Genetic Algorithm With Multistart Search for the p-Hub Median Problem”, EUROMICRO CONFERENCE, 1998, Proceedings, 24th, V.2, 1998, pp.702-707, V.2
38.R. E. Kuenne, R. M. Soland, ”Exact and approximate solutions to the multisource weber problem.”, MATH. PROG. , V.3, p.193-209, 1972.
39.R. F. Love & J. G. Morris, ”A computation procedure for the exact solution of location-allocation problems with rectangular distances”, NAVAL RESEARCHS LOGISTIC QUARTERLY, p.441-453, 1975
40.D. Skorin-Kapov &J. Skorin-Kapov, ”On tabu search for the location of interacting hub facilities”, EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 73, pp.502-509, 1994
41.D. Skorin-Kapov, J. Skorin-Kapov, and M. E. O’Kelly, ”Tight linear programming relaxations of uncapacitated p-hub median problems”, EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, V.94, pp.582-593, 1996
42.K. Smith, M. Krishnamoorthy & M. Palaniswami, ”Neural versus traditional approaches to the location of interacting hub facilities”, LOCATION SCIENCE, Vol.4, No.3, p.155-171, 1996
43.C. K. Sydney, L. C. Chu, ”A modeling framework for hospital location and service allocation”, INTERATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 7, pp539-568, 2000
44.J. Tony, Van Roy, ”A cross Decomposition Algorithm for capacitated facility location”, OPERATIONS RESEARCH, V.34, p.145-163, 1986.
45.U. Aking and B. M. Khumawala, ”An Efficient Branch and Bound Algorithm For The Capacitated Warehouse Location Problem”, MANAGEMENT SCIENCE, V.23, N.6, February, pp.585-594, 1977.
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔