臺灣博碩士論文加值系統

本研究包含兩個部分，第一個部分根據倉儲選位問題的兩個特性：有無容量限制以及配送是否可分割來探討成本之差異。在第二個部分提出兩個方法：模擬退火法和變動鄰域搜尋法，來求解有容量限制配送可分割之倉儲選位問題，並且根據OR Library的標竿測試例題來討論兩者之成效。
倉儲選位問題之目標為找出一組使總成本為最小之配送倉儲，總成本包含配送倉儲之建構成本以及運輸成本。倉儲選位問題可以根據配送倉儲是否有分擔其他倉儲的配送量而進一步地分類成有容量限制或無容量限制問題。同樣地，倉儲選位問題在每一位顧客只能由單一倉儲配送時，被稱為不可分割問題；否則稱為可分割問題。本研究透過簡單的證明得知無容量限制倉儲選位問題之最佳解會發生在配送不可分割的情形，證明的方式為使用LINGO軟體求解OR Library的標竿測試題而來，從這項證明的結果中可以清楚得知無容量限制倉儲選位問題在配送可分割及配送不可分割倉儲選位問題方面的成本為最小，實驗中也指出配送是否可分割問題兩者間成本的差異並不大。
本研究在提出的模擬退火演算法以及變動鄰域搜尋法中使用三種產生鄰近解的方式：一個交換一個、增加一個及減少一個配送倉儲；並使用數個移動策略來找尋可行解：隨機選取、最大未使用量、最大未使用率及最大單位成本率，成本率計算方式為建構成本加上配送之運輸成本，其總和成本除以實際配送量而來。實驗透過使用OR Library的標竿測試題的結果發現在兩種演算法中：隨機選取及最大單位成本率在平均解算數量下，求解品質上皆優於其他三者，但是解算時間較差。

The study consists of two parts. In the first part, we explore the cost difference due to two attributes of the warehouse location problem (WLP) – capacitated and uncapacitated, single source and multi-source. In the second part, we propose two methods for solving the multi-source capacitated warehouse location problem (MS-CWLP): Simulated annealing (SA) and Variable neighborhood search (VNS) algorithm, and discuss their performance using the benchmark instances of OR Library.
In the WLP, the cost to be considered contains warehouse construction cost and transportation cost, and the objective is to choose a set of warehouses such that the total cost is the minimum. The WLP can be further classified into capacitated and uncapacitated according to whether capacity is imposed on the warehouses or not. Likewise, a WLP is called single-source if each customer’s demand must be supplied by exactly one warehouse; otherwise, the WLP is called multi-source. A simple proof for the existence of a single-source optimal solution to the uncapacitated WLP is presented. Meanwhile, an experiment is conducted using LINGO software to solve the benchmark instances of the OR Library. It is clear that the uncapacitated-WLP has the least cost than the MS-WLP and the single-source WLP. Our experiments indicate that there is little cost difference in terms of percentage between the MS-WLP and the single-source WLP.
Three types of neighborhood are used for the proposed SA and VNS: one for one exchange, increase by one, and decrease by one. Several solution-search moving strategies are considered in the SA and VNS: random selection, the maximum unused quantity, the maximum unused rate, and the maximum cost rate per unit transported. The cost rate for a warehouse is defined as the ratio of the sum of the construction cost and the total transportation cost over the total transported units from that warehouse. Our computational results using the benchmark instances of the OR Library indicate that in both algorithms, two moving strategies - the random selection and the maximum cost rate - are superior to the other three in solution quality and the average number of solutions computed to reach the best or optimal solution, but are inferior in computational time.

中文摘要 i
英文摘要 ii
誌 謝 iv
目 錄 v
圖 目 錄 viii
表 目 錄 x
一、導論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究流程 2
1.4 研究範圍及限制 3
1.5 章節概要 4
二、文獻探討 5
2.1配送倉儲區位問題 5
2.1.1 連續型區位模式 5
2.1.2 離散型區位模式 6
2.2 無容量限制倉儲選位問題 6
2.3 有容量限制倉儲選位問題 7
2.4 模擬退火演算法 8
2.4.1 模擬退火演算法簡介 8
2.4.2 Metropolis演算法 9
2.4.3 退火程序 10
2.4.4 模擬退火基本解算方式及流程 10
2.5 變動鄰域搜尋法 13
2.5.1 變動鄰域搜尋法簡介 13
2.5.2 變動鄰域搜尋法演算範例 13
2.5.3變動鄰域搜尋法解算流程 15
三、問題描述及數學模式 18
3.1 無容量限制下配送不可分割問題 19
3.1.1 無容量限制下配送不可分割數學模式 19
3.1.2 最佳解性質與配送不可分割關係 21
3.2 有容量限制下配送不可分割問題 23
3.2.1 有容量限制下配送不可分割之數學模式 23
3.2.2 有無容量限制目標值之影響 25
3.3 有容量限制下配送可分割問題 25
3.3.1 有容量限制下配送可分割問題之數學模式 25
3.3.2 影響可分割與不可分割問題成本差益之因素 26
四、研究方法 28
4.1 模擬退火法 30
4.1.1 模擬退火法架構 31
4.1.2 模擬退火法之執行步驟 31
4.2 變動鄰域搜尋法 34
4.2.1 變動鄰域搜尋法架構 34
4.2.2 變動鄰域搜尋法之解算流程 35
4.3 運輸問題 37
4.3.1 平衡運輸問題之數學模式 37
4.3.2 運輸單體法 38
4.3.2.1初始解建構 40
4.3.2.2運輸單體法之解算範例說明 43
4.3.2.3運輸單體法之數學特性 45
4.3.2.4 矩陣上尋找迴圈之方法 48
五、實驗分析及研究成果 51
5.1 實驗所使用之電腦設備及軟體 51
5.2 測試例題之產生 51
5.2.1無容量限制測試例題產生方式 51
5.2.2 有容量限制測試例題產生方式 51
5.2.3各模式綜合比較分析之測試例題產生方式 52
5.3 測試例題使用LINGO解算之結果分析 52
5.3.1 無容量限制測試例題解算結果 52
5.3.2 有容量限制測試例題解算結果 53
5.3.3 有容量限制可分割問題與其他類型問題之綜合比較分析 55
5.4啟發式演算法解算有容量限制配送可分割問題之結果分析 58
5.4.1 使用模擬退火演算法求解測試例題之解算結果 58
5.4.1.1 固定顧客數量下採用模擬退火演算法之解算結果 59
5.4.1.2 固定倉儲數量下採用模擬退火演算法之解算結果 61
5.4.2 使用變動鄰域搜尋演算法求解測試例題之解算結果 63
5.4.2.1 固定顧客數量下採用變動鄰域搜尋演算法之解算結果 63
5.4.2.2 固定倉儲數量下採用變動鄰域搜尋演算法之解算結果 65
5.4.3 兩種演算法之綜合比較分析 67
5.4.3.1 固定顧客數量下採用兩種演算法之解算結果 68
5.4.3.2 固定倉儲數量下採用兩種演算法之解算結果 69
六、結論及未來發展 72
6.1 結論 72
6.2 未來發展 73
參考文獻 74
附錄A 模擬退火法測試結果 78
附錄B 變動鄰域搜尋法測試結果 91

一、中文
張厚祺，「模擬退火應用在自動倉儲儲位規劃之研究」，元智工學院工業工程與管理研究所碩士論文，民國86年6月。
許哲榮，「多產品配送中心場址規劃與選擇」，元智工學院工業工程與管理研究所碩士論文，民國87年6月。
王璟瑩，「應用禁忌搜尋法於物流中心區位選擇之研究」，國立雲林科技大學工業工程與管理研究所碩士論文，民國87年6月。
顏憶茹，張淳智，物流管理，二版，台北，前程企業管理公司，民國88年2月。
柯惠雯，「結合模擬退火法與禁忌搜尋法在流程式生產排程之應用」，私立大葉大學工業工程研究所碩士論文，民國90年6月。
羅中育，「田口品質工程應用於模擬退火法參數組合─以旅行推銷員問題（TSP）為例」，國立雲林科技大學工業工程與管理研究所碩士論文，民國90年6月。
紅名鴻，「無容量限制下之動態需求設施區位問題研究」，元智工學院工業工程與管理研究所碩士論文，民國91年6月。
周佳彥，「運用雙影像對應求取3D座標資訊-模擬退火法之應用」，朝陽科技大學工業工程與管理所碩士論文，民國92年6月。
胡正宏，「有容量限制之動態設施區位問題」，國立高雄第一科技大學運輸倉儲營運所碩士論文，民國92年6月。
陳怡靜，「變動鄰域搜尋法於串並聯系統複置配置問題之研究」，元智工學院工業工程與管理研究所碩士論文，民國93年6月。

二、英文
Abramson, D., Krishnamoorthy, M., and Dang, H., “Simulated Annealing Cooling Schedules for the School Timetabling Problem”, Asia-Pacific Journal of Operational Research, Vol. 16, pp. 1-22,1999.
Avanthay, C., Hertz, A., and Zufferey, N., “A variable neighborhood search for graph coloring”, European Journal of Operational Research, Vol. 151, pp. 379-388, 2003.
Beasley, J. E., “An algorithm for solving large capacitated warehouse location problems”, European Journal of Operational Research, Vol. 33, pp. 314-325, 1988.
Beasley, J. E., “Lagrangean heuristics for location problems”, European Journal of Operational Research, Vol. 65, pp. 383-399, 1991.
Cortinhal, M.J., and Captivo, M.E., “Upper and lower bounds for the single source capacitated location problem”, European Journal of Operational Research, Vol. 151, pp.333-351, 2003.
Fleszar, K., and Hindi, K.S., “Solving the resource-constrained project scheduling problem by a variable neighbourhood search”, European Journal of Operational Research, Vol. 155, pp. 402-413, 2004.
Ghiani, G., Guerriero, F., and Musmanno, R., “The capacitated plant location problem with multiple facilities in the same site”, Computers & Operations Research, Vol. 29, pp. 1903-1912, 2002.
Golden, B. L., Bodin, L., Assad, A., and Ball, M., “Routing and Scheduling of Vehicle and Crew: the State of Art”, Special Issue of Computers and Operations Research, Vol. 10, pp. 63-211, 1983.
Hinojosa, Y., Puerto, J., and Fern?鴨dez, F.R., “A multiperiod two-echelon multicommodity capacitated plant location problem”, European Journal of Operational Research, Vol. 123, pp. 271-291, 2000.
Holmberg, K., R?圢nqvist, M., and Yuan, D., “An exact algorithm for the capacitated facility location problems with single sourcing”, European Journal of Operational Research, Vol. 113, pp. 544-559, 1999.
Johnson, D., Aragon, C., McGeoch, L., and Schevon C., “Optimization by simulated annealing: An experimental evaluation; Part 1”, Graph partitioning. Vol. 37, pp. 865-892, 1989.
Kirkpatrick, S., C. D. Gelatt, Jr., and M. P. Vecchi, “Optmization by Simulated Annealing”, Science, Vol. 220, pp. 671-680, 1983.
Lejeune, M.A., “A variable neighborhood decomposition search method for supply chain management planning problems”, European Journal of Operational Research, Available online, 2005.
Metropolis, N., Rosenbluth, A., Rosenbluth, M., and Teller, E., “Equation of State Caculations by Fast Computing Machines”, Journal of Chemical Physics, Vol. 21, pp. 1087-1092, 1953.
Michel, L., and Hentenryck, P.V., “A simple tabu search for warehouse location”, European Journal of Operational Research, Vol. 157, pp. 576-591, 2004.
Mladenović, N., “A variable neighborhood algorithm: A new metaheuristic for combinatorial optimization”, Abstracts of papers presented at Optimization Days, pp. 112, 1995.
Mladenović, N., and Hansen, P., “Variable neighborhood search”, Computers & Operations Research, Vol. 24, pp. 1097-1100, 1997.
Mladenović, N., and Hansen, P., “Variable neighborhood search: Principles and applications”, European Journal of Operational Research, Vol. 130, pp. 449-467, 2001.
OR-Library: http://people.brunel.ac.uk/~mastjjb/jeb/info.html, 2006.
ReVelle, C.S., and Eiselt, H.A., “Location analysis: A synthesis and survey”, European Journal of Operational Research, Vol. 165, pp. 1-19, 2005.
Tompkins, J. A. and Smith, J. D., The Warehouse Management Handbook, McGraw, New York, 1988.