臺灣博碩士論文加值系統

摘要
本研究主要的目的乃針對國軍聯保廠之區位途程存貨問題進行理論與實務的探討分析，由於國軍聯保廠配銷系統，走向物流中心規劃，符合區位途程存貨問題(Location Routing & Inventory Problem, LRIP)之特性，其應用範圍廣泛且具高度的複雜性，為近年來學界所探討的熱門主題之一；軍方之配送作業常需滿足諸多內部及外部限制條件，例如：運輸能量限制、顧客位置，物流中心區位，貨物種類與數量等，在計算求解上構成NP-Hard型態問題，故在處理複雜或較龐大配送計劃時，面臨求解時間隨著決策變數的增加而成指數（exponential-time）增加的困難，使得傳統演算法求最佳解更為困難。因而構建一適合於國軍零附件運輸補給系統之啟發式解法是當務之急。為能有效解決複雜區位途程存貨問題，配合國軍零附件運輸補給系統特性，本研究依現行配送模式發展出一改良式啟發式演算法，在最適的顧客服務水準與經濟訂購量前提下，以最低的存貨路徑總成本來規劃聯保廠的運補路線。最後採用聯保廠所提供的實際資料進行驗證，其演算結果與現行人工規劃，與單獨考慮運輸成本的節省法比較時，皆顯示本研究之求解成效較佳，可做為聯保廠運輸補給規劃相關依據。
關鍵詞：聯保廠、區位途程存貨問題、啟發式演算法、節省法

ABSTRACT
The objective of this research is to discuss location and routing- inventory problem for the joint maintenance shops in R.O.C. Army. The application scope of Location and Routing- Inventory Problem (LRIP) is comprehensive and extremely complicated, which has recently become one of the hot topics in the academic field. The military distribution process often needs to match up to many interior and exterior limitations such as transportation capacity control, customer position, distribution center location, cargo category and quantity etc. It is obviously a typical NP-Hard problem. Therefore, while dealing with complicated and bulkier distribution plans, it faces the difficulty of increasing exponential-time with ascending policy-making variables, making it more difficult to find the optimal solution for traditional algorithm. At situations like these, the application of heuristic algorithm is more appropriate to find the solution for the distribution problem of spare parts supply system of R.O.C.Army. And supply system for the army.
To efficiently tackle the LRIP problem, which matches up the characteristics of spare parts supply system of R.O.C.Army, this research, based on the current distribution pattern, develop a modified heuristic algorithm to scheme the supplying route of the joint maintenance shops at the lowest total cost with the consideration of balancing customer service level with economic order quantity.
Finally, the numerical examples are illustrated with the existing data offered by the joint maintenance shops, the results of this proposed algorithm turn out to be superior to those from current artificial planning as well as saving method only considering the transportation cost.








Key word: Joint maintenance shops in the R.O.C.; Location Routing & Inventory Problem; Heuristic algorithm; the Saving Approach.

目錄
摘要 V
ABSTRACT VI
誌 謝 VIII
目錄 IX
圖目錄 XII
表目錄 XIV
第一章、緒論 1
1.1研究背景與動機 1
1.2研究目的 3
1.3研究流程 5
第二章 現行作業程序與相關文獻探討 8
2.1陸軍補給支援特性 8
2.1.1現行保修補給作業方式 10
2.1.2缺失探討： 12
2.2設施區位選擇問題 16
2.3 車輛路徑規劃 16
2.4區位途程問題 17
2.5區位途程存貨問題 18
2.6區位途程存貨問題求解策略 21
2.6.1 求解方法的探討 22
2.6.2 萬用啟發式演算法 25
2.6.3 啟發式演算法求解 29
2.7 小結 30
第三章、相關理論與演算工具介紹 31
3.1存貨管理 31
3.1.1存貨成本 31
3.1.2 經濟批量模式 32
3.2 運輸路線的規劃原則 35
3.3 節省法求解說明 36
3.4節點插入與交換改善解法 43
第四章 模型建構 45
4.1研究問題 45
4.2研究假設與限制 45
4.3符號說明與定義 46
4.4數學模式建構 48
4.5 模式推導與驗證步驟 55
4.6 模式的比較： 62
第五章 實例驗證與分析 63
5.1 實例說明與參數設定 63
5.2 演算結果之分析與比較 66
5.2.1 現行作業成本分析 67
5.2.2 Logware軟體介紹與成本分析 69
5.2.3 啟發式解法成本分析 77
5.2.4 改善啟發式解法成本分析 83
5.3 各方法成本因素分析 89
第六章 結論與未來研究方向 91
6.1 研究結論 91
6.2 建議 92
參 考 文 獻 94
一、中文部分 94
二、英文部分： 97

參 考 文 獻
一、中文部分
1.王生德（2004），以巨集啟發式方法求解時窗限制回程取貨車輛路線問題(VRPBTW)之研究，中華大學科技管理研究所碩士論文。
2.王耿彬（2001），應用遺傳演算法於低溫冷凍物流中心之車輛配送排程規劃，朝陽科技大學工業工程與管理系碩士論文。
3.王璟瑩(1998)，應用禁忌搜尋法於物流中心區位選擇之研究，國立雲林科技大學工業工程與管理研究所碩士論文。
4.何明璋(2004)，供應商管理庫存模式下最佳之聯合補貨策略，義守大學工業工程與管理研究所碩士論文。
5.吳琴玲(2000)，物流配送系統之區位-途程問題研究，國立雲林科技大學工業工程與管理研究所碩士論文。
6.呂學忠(2005)，策略性物流整合支援對陸軍保修零附件補給效益之探討，聯合後勤月刊。
7.李洪鑫（2000），含時間窗車輛途程問題各演算法適用範圍之探討，東海大學工業工程學系碩士論文。
8.李順斌(2002)，物流配銷系統下整合區位途程與存貨問題之研究，國立屏東科枝大學資訊管理研究所碩士論文。
9.李順斌、劉書助(2004)，物流系統下整合區位途程與存貨問題之研究，管理與系統，Vol.11, No.1, page 73-88.
10.周淑蓉(2004)，以群聚及禁制搜尋法求解含時窗限制之車輛巡迴路線問題，朝陽科技大學資訊管理研究所碩士論文。
11.林清河(1995)，物料管理，修訂版，華泰書局。
12.胡大瀛(2002)，禁制搜尋法於動車輛巡迴路線之研究，逢甲大學交通工程與管理學系碩士論文。
13.徐俊誠（2000），車輛途程含取貨問題之解法之研究，大葉大學工業工程管理學系碩士論文。
14.衷嵐焜(1994)，離散區位模型應用於速食外送等業態區位評選之研究，國立中央大學土木工程研究所碩士論文。
15.國防報告書(2004)，第十八章後勤，中華民國國防部編印。
16.張有恆(1988)，物流管理，華泰書局。
17.張容瑄（2002），模擬退火法在校車路線問題上的應用，國立中正大學數學研究所碩士論文。
18.敖君瑋(1998)，禁制搜尋法於軟性時窗限制之車輛途程問題研究，元智大學工業工程研究所碩士論文。
19.莊志諒(1988)，配銷網路之設計研究，國立交通大學運輸研究所碩士論文。
20.陳契伸（2001），硬軟性時窗限制之車輛途程問題研究，中原大學工業工程學系碩士論文。
21.陳建緯（2001），大規模旅行推銷員問題之研究：鄰域搜尋法與巨集啟發式解法之應用，國立交通大學運輸工程與管理學系碩士論文。
22.陳家芳(2002)，前置時間變動下供應鏈系統成本與長鞭效應之關係，國立成功大學工業管理科學研究所碩士論文。
23.陳隆熙（2002），一個解決TSP問題最佳解的穩定方法—以TA演算法為例，大葉大學工業工程研究所碩士論文。
24.陸軍基地補給管理作業手冊(1988)，陸軍後勤司令部編印，P89。
25.陸軍補給自動化作業手冊(1998)，陸軍後勤司令部編印，P117。
26.曾惠鈺(2003)，即時行車資訊下物流配送作業規劃之研究，淡江大學運輸管理科學研究所碩士論文。
27.楊智凱（1994），以門檻接受法改善TSP及VRP路網成本之研究，國立交通大學土木工程研究所碩士論文。
28.蔡玉晶（2004），以複合啟發式演算法求解硬式時窗限制下車輛途程問題，中原大學工業工程研究所碩士學位論文。
29.韓復華、卓裕仁（1996），門檻接受法、噪音擾動法與搜尋空間平滑法在車輛路線問題之應用研究與比較分析，運輸學刊，vol.9, no.3, pp. 113-144。
二、英文部分：
1.Anily, S. and A. Federgruen, (1990) “One warehouse multiple retailer system with wehicle routing cost”, Management Science, Vol. 36, No. 1, pp. 92-114.
2.Baker, B. M. and Ayechew, M. A. (2003), ” Genetic Algorithm for The Vehicle Routing Problem “,Computers and Operations Research ,Vol.30, pp.787-800.
3.Ballou, Ronald H. (1987) Basic Business Logistics: Transportation, Materials Management and Physical Distribution. 2nd ed. Upper Saddle River, N.J... Prentice Hall.
4.Bell, W. L., Dalberto, M., Fisher, A. Greenfield, R. Jaikumar, Kedia. P., Mack, R. and Prutzman, P.(1983) Improving the distribution of industrial gases with and on-line computerized routing and scheduling optimizer. Interfaces, 13(6)：pp.4-23.
5.Berger, J., and Barkaoui, M. (2004), ”A Parallel Hybrid Genetic Algorithm for the Vehicle Routing Problem with Time Windows”,Computers and Operations Research ,Vol. 31, pp. 2037-2053.
6.Bertazzi, L., Paletta, G. and Speranza, M.G. (2002). Deterministic Order-up-To Level Policies in Inventory Routing Problem. Transportation Science, 36(1). pp. 119-132.
7.Bodin, L., and Golden, B. (1981), Classification In Vehicle Routing And Scheduling, Networks, Vol. 11, pp. 97-108.
8.Bramel, J. & Simchi-Levi, d. (1997). The logic of Logistics. Springer, New York.
9.Brandao, j(2004). A Tabu Search Algotrithm for The Open Vehichl Routing Problem, European Journal of operational research, Vol.157,pp. 552-564.
10.Breedam, V. (1995), Improvement Heuristics for the Vehicle Routing Problem Based on Simulated Annealing, European Journal of Operational Research, Vol. 86, pp. 480-490.
11.Campbell, A., Clarke, L., Kleywegt, A. and Savelsbergh, M. (1999). An Inventory Routing Problem.
12.Chen, T.K., Hay, L. L., and Ke, O. (2001), ”Hybrid Genetic Algorithms in Solving Vehicle Routing Problems with Time Window Constraints”, Asia-Pacific Journal of Operational Research, Vol. 18,pp. 121-130,.
13.Chien, T., A. Balakrishnan, and R. Wong.(1989) An integrated inventory allocation and vehicle routing problem. Transportation Science. 23(2)：pp.67-76.
14.Choi, I.C., Kim, S.I., and Kim , H.S. (2003), A Genetic Algorithm with a Mixed Region Search for the Asymmetric Traveling Salesman Problem, Computers and Operations Research ,Vol.30 ,pp. 773-786.
15.Clarke, G. and Wright, J. W. (1964), Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, Vol. 2, pp. 568-581.
16.Clarke, G., Nemhauster, G. L, and Wolsry L. A., (1990), The Uncapacitated Facility Location Theory, John Wiley and Sons, pp. 568-581.
17.Dantig, G. B. and J. H.Ramser(1959), The Truck Dispatching Problem Management Science, Vol. 6, pp.80-91.
18.Daskin, M. and S. Mark, (1995). Network and Discrete Location, JOHN WILEY & SON, Inc.
19.Dong, Y. & Xu, K. (2002). A supply chain model of vender managed inventory. Logistics & Transportation Review, 38E, pp.75-95.
20.Dror, M. & Ball, M. (1987). Inventory/routing: Reductiion from an Annual to a Short-period Problem. Naval Research Logistics, 34, pp.891-905.
21.Dueck, G. and Scheuer, T. (1990), Threshold Accepting : A General Purpose Optimizatiom Algorithm Appeared Superior to Simulated Annealing, Journal of Computational Physics, Vol. 90, pp. 161-175.
22.Federgruen, A. & Zipkin, P. (1984). A Combined Vehicle Routing and Inventory Allocation Problem. Operations Research, 32(5), pp.1019-1036.
23.Fisher, M. J. and Jaikumar, R. (1981), A Generalized Assignment Heuristic for Vehicle Routing, Networks, Vol. 11, 109-124.
24.Gendreau, m., Herz, A., and Laporte, G. (1994). A Tabu Search Heruistic for the Vehicle Routing Problem, Management Science, Vol. 40,pp. 1276-1290.
25.Gendreau, M., Laporte, G., and Seguin, R(1996). A Tabu Search Heuristic for the Vehicle Routing Problem With Stochastic Demands and Customers, Operations Research, Vol.44, no.3,pp.469-477.
26.Gillett B. E. & Miller L.R. (1974). A Heuristic Algorithm for the Vehicle-Dispatch Problem. Operations Research, 2, pp.340-349.
27.Glover, B., and, Miller L. (1977), Heuristics for Integer Programming Using Surrogate Constraints, Decision Science, Vol. 8, pp.156-166.
28.Glover, F. (1989), Tabu Search-Part Ⅰ, ORSA Journal on Computing, Vol. 1, No.3, pp.190-206.
29.Glover, F. (1990), Tabu Search-Part Ⅱ, ORSA Journal on Computing, Vol. 2, No.1, pp.4-32.
30.Glover, F., James, P.K., and M (1995) Genetic Algorithms and Tabu Search：Hybrids for Optimization, Computer Operation Research, Vol.22, pp. 111-134.
31.Golden, B., Assad, A. and Dahl R. (1984). Analysis of a large scale vehicle routing problem with an inventory component. Large scale Systems. 7(2-3) : pp.181-190.
32.Hansen, P. H. Hegedahl, B., Hjortkjaer S. and Obel B. (1994), A heuristic solution to the warehouse location-routing problem, Journal of Operation Research, Vol.76, pp. 111-127.
33.Ho, W.K., Ang, J.C., and Lim, A. (2001), A Hybrid Search Algorithm for the Vehicle Routing Problem with Time Windows, International Journal on Artificial Intelligence Tools, Vol.10, no.3, pp.431-449.
34.Krolak .et al., (1971), A computational modification to the savings method of vehicle scheduling, Operation Research Quarterly, vol. 31, pp. 147-184.
35.Laporte, g., Nobert, Y., Arpin, D. (1986), An exact algorithm for solving a capacitated location-routing Problem, Annals of Operations Research, Vol. 6, pp. 493-511.
36.Larson R. C. and Odoni, A. R. (1981) Urban Operation Research, Prentice-Hall, New Jersey.
37.Lin, S. (1965), Computer Solutions of the Traveling Salesman Problem. Bell System Technology Journal, 44, pp.2245-2269.
38.Lin, S., and Kernighan, B. W. (1973), An Effective Heuristic Algorithm for the Traveling Salesman Problem, Operations Research, Vol.21, pp.498-516.
39.Metropolis, N., Rosenbluth, A. N., Rosenbluth, M. N., Teller, A. H. and Teller, E. (1953), “Equation of State Calculation by Fast Computing Machines”, Journal of Chemical Physics, Vol. 21,no. 6,pp.1087–1092.
40.Metz, P. J. (1998). Demystifying Supply Chain Management. Supply Chain management Review, Winter Issue.
41.Oliver, K. R. & Webber, M. D. (1982). Supply-Chain anagement. Logistics Catches up with Strategy. Outlook, cit.
42.Or, I., and Pierskalla, W. P. (1979), A Transportation Location Allocation Model For Reginal Blood banking. AIIE Transaction, All pp.86-95.
43.Osman, I. H. (1993) Metastrategy Simulated Annealing and Tabu Search Algorithms for The Vehicle Routing Problem, Annals of Operations Research, Vol. 41,pp. 421-451.
44.Perl, J. (1983), A Unified Warehouse Location-Routing Problem, Tranportation Research B, Vol. 19, pp. 381-396.
45.Perl, J., and M. S. Daskin,(1985), A Warhouse Location-Routing Problem. Transportation Research B, Vol. 19, pp.381-396.
46.Potvin, J.Y., Kervahut, T., Garcia, B.L., and Rousseau, J.M. (1996), “The Vehicle Routing Problem with Time Windows Part I: Tabu Search”, Informs Journal on Computing,Vol. 8,no. 2,pp. 158-164.
47.Psaraftis, H. N. (1995), Dynamic Vehicle Routing: Status and Prospects, Annals of Operations Research, Vol.61, pp.143-164.
48.Susan, H. O. and Mark, S. D. (1998), Strategic facility location, European Journal of Operational Research, vol.111, pp. 423-447.
49.Srivastava, R., (1993), Strategic facility location, Omega International Journal of Management Science, Vol. 21, pp. 497-506.
50.Thomas, D. J. and Griffin, (1996) P. M. Coordinated supply chain management, European Journal of Operational Research, Vol.94, pp. 1-15.
51.Thompson, P. M., and Psaraftis, H. (1993), Cyclie Trabsfer Algorithms for Multi-Vehicle Routubg abd Scheduling Problems ,Operations Research Vol.41, pp.935-946.
52.Toth, P., and Vigo, D. (2003) The Granular Tabu Search and Its Application to The Vehicle-Routing Problem, journal on computer, Vol.15,no.4,pp. 333-346.