臺灣博碩士論文加值系統

本研究乃針對包含了一個工廠、多個物流中心以及多個零售商之供應鏈，進行三階補貨暨配送規劃模式探討。在給定零售商每日的訂單資訊下，進行補貨暨配送的總體最小成本之整合性考量，以決定相關的作業層次管理決策。本研究問題之主要特性為探討横向調度(Lateral Supply)問題，考量藉著各物流中心的車輛及存貨之互相支援以降低總體運輸成本。我們首先將此問題構建為一混合整數規劃數學模式，然因其具有NP-hard特性，於實務應用上有所限制，經由CPLEX最佳化軟體實際測試後發現大部分測試題的求解時間超過10小時仍常無法達到最佳解。故進而提出一結合類似運輸問題模式與最小成本網路流量模式兩個最佳化子模式之啟發式演算法，與最佳化混合整數規劃模式之求解品質與計算時間進行比較分析。實驗測試證實橫向調度無論是針對車輛或貨品以至於兩者兼具且合作的調度方式，皆顯示出此調度模式對總體成本之降低是有助益的。

This research focuses on a problem of replenishment and distribution for a three-echelon distribution system including a single plant, multiple distribution centers, and multiple retailers. Based on daily orders from retailers, we tend to suggest related operational plans according to the criteria of minimizing inventory replenishment and routing cost. Our study focuses on how to transfer inventory and vehicles among distribution centers to save total transportation costs. A mixed integer linear programming model is formulated first. Due to practical needs, we then develop a heuristic to solve problem of real world size, which is embedded with two optimization models: a variant of transportation model and a variant of minimum cost network flow model. Several small size problems were solved optimally in order to justify the performance of our heuristic. Through testing problems of 100 customers, we testified the mechanism of laterl supply is workable and may lower total transportation costs.

目錄
書名頁 i
論文口試委員審定書 ii
教育部授權書 iii
國科會授權書 iv
中文摘要 v
英文摘要 vi
誌謝 vii
目錄 viii
表目錄 x
圖目錄 xi
第一章 緒論 1
1.1 研究動機 1
1.2 研究假設 2
1.3 研究目的 3
第二章 相關研究 5
2.1 車輛途程問題 5
2.1.1 車輛途程問題的特性 6
2.1.2 車輛途程問題的求解策略 8
2.1.3 車輛途程問題的啟發式解法 10
2.2 設施區位問題 11
2.2.1 區位途程問題 12
2.3 存貨途程問題 12
2.4 小結 15
第三章 混合整數規劃模式 16
3.1 模式之索引及參數 16
3.2 模式之決策變數 17
3.3 混合整數規劃模式 18
3.3.1 模式之目標函數及限制式之說明 20
3.3.2 工廠配貨、顧客指派和存貨調度相關限制式 20
3.3.3 配送路線的相關限制式 21
3.3.4 決策變數的範圍限制式 22
第四章 啟發式演算法 23
4.1 演算步驟 23
4.2 車輛調度模式 24
4.3 貨品調度模式 26
第五章 測試分析與探討 30
5.1 實驗1的設計 30
5.2 實驗1的測試結果之分析 32
5.3 實驗2的設計 36
5.4 實驗2的測試結果之分析 39
第六章 結論與建議 43
6.1 結論 43
6.2 建議 44
參考文獻 46
附錄 50
A.1 實驗1在R1題組下的測試明細 50
A.2 實驗1在R2題組下的測試明細 51
A.3 實驗2在R1題組下的測試明細 51
A.4 實驗2在R2題組下的測試明細 64
表目錄
表2.1 影響車輛途程問題的主要特性 7
表5.1 實驗1之重要節點的相關資料 30
表5.2 實驗1的委外車輛計價方式 31
表5.3 最佳化模式在R101與R105下的測試結果 33
表5.4 最佳化模式在R102至R104的測試結果 33
表5.5 最佳化模式在R201與R205的測試結果 33
表5.6 最佳化模式在R202至R204的測試結果 33
表5.7 實驗1中演算法在R1題組的求解品質 34
表5.8 實驗1中演算法在R2題組的求解品質 34
表5.9 實驗1中演算法在R101至R105之平均成本、求解品質 35
表5.10 實驗1中演算法在R201至R205之平均成本、求解品質 35
表5.11 實驗1中由R101至R105演算法在四種情況下以及最佳化模式的平均計算時間 35
表5.12 實驗1中由R201至R205演算法在四種情況下以及最佳化模式的平均計算時間 36
表5.13 實驗2之重要節點的相關資料 36
表5.14 R1題組的物流中心車輛數-1 37
表5.15　R1題組的物流中心車輛數-2 .38
表5.16　R2題組的物流中心車輛數 38
表5.17 實驗2的委外車輛計價方式 38
表5.18 實驗2在R1題組下變動委外固定成本匯總其他各項因子對四種情況的平均成本、計算時間(time)及成本下降率(off)之影響 40
表5.19 實驗2在R2題組下變動委外固定成本匯總其他各項因子對四種情況的平均成本、計算時間(time)及成本下降率(off)之影響 40
表5.20 實驗2在R1題組下變動物流中心與工廠的車容量匯總其他各項因子對四種情況的平均成本、計算時間(time)及成本下降率(off)之影響 41
表5.21 實驗2在R2題組下變動物流中心與工廠的車容量匯總其他各項因子對四種情況的平均成本、計算時間(time)及成本下降率(off)之影響 41
表5.22 實驗2在R1題組下變動物流中心數匯總其他各項因子對四種情況的平均成本、計算時間(time)及成本下降率(off)之影響 42
表5.23 實驗2在R2題組下變動物流中心數匯總其他各項因子對四種情況的平均成本、計算時間(time)及成本下降率(off)之影響 42
圖目錄
圖4.1 貨品調度模式中相對於 集合的新節點建構 27
圖4.2 四個物流中心的最小成本網路流量問題模式 29
圖5.1 實驗1之重要節點的XY座標位置圖(顧客數為30) 30
圖5.2 實驗2之重要節點的XY座標位置圖 37

西文部分：
[1] Anily, S. and A. Federgruen, 1990. "One Warehouse Multiple Retailer Systems with Vehicle Routing Costs", Management Science, 36: 92-114.
[2] Bard, L. H., Jaillet, P., and Dror, M., 1998, "A Decomposition Approach to the Inventory Routing Problem with Satellite Facilities", Transportation Science, 32: 189-203.
[3] Bodin, L., Golden, B., Assad, A., Ball, M., Routing and scheduling of vehicles and crews - the state of the art, Comput. & Oper. Res. 10, 1983, 63-211.
[4] A. Campbell, L. Clarke, AJ Kleywegt, and MWP Savelsbergh, 1998, The Inventory outing Problem, in: TG Grainic and G. Laporte, eds., Fleet Management and Logistics, Kluwer Academic Publishers, 95-113.
[5] Chandra, P. and M.L. Fisher, 1994, "Coordination of Production and Distribution Planning", European Journal of Operational Research, 72(3): 503-517.
[6] Chao, I-M., Golden, B. L. and Wasil, E., 1993, "A New Heuristic for the Multi-depot Vehicle Routing Problem that Improves Upon Best Solutions", American Journal of Mathematical & Management Science, 13: 71-401.
[7] Chien, T., Balakrishnan, A., and Wong, R., 1989, "An Integrated Inventory Allocation and Vehicle Routing Problem", Transportation Science, 23: 67-76.
[8] Christofides, N. and Beasley, J., 1984, "The Period Routing Problem", Networks, 14: 237-256.
[9] Clarke, G. and Wright, J. W., 1964, "Scheduling Vehicle from a Central Delivery Depot to a Number of Delivery Points", Operation Research Quarterly, 12: 568-581.
[10] Dantzig, G.B., and J.H. Ramser, 1959, "The truck dispatching problem", Management Science, 6: 1.
[11] Federgruen, A. and Zipkin, P., 1984, "A Combined Vehicle Routing and Inventory Allocation Problem", Operations Research, 32: 5, 1019-1036.
[12] Fisher, M. L. and Jaikumar, R., 1981, "A Generalized Assignment Heuristic for Vehicle Routing Problems", Network, 11: 109-124.
[13] Flynn, J., and S. Ratick, 1988, "A Multiobjective Hierarchical Covering Model for the Essential Air Services Program", Transportation Science, 22: 139-147.
[14] Gillett B. and Miller L., 1974. "A Heuristic Algorithm for the Vehicle-Dispatch Problem", Operations Research, 22: 340-349.
[15] Golden, B., Assad, A., and Dahl, R., 1984. "Analysis of a Large Scale Vehicle Routing Problem with an Inventory Component", Large Scale System, 7: 181-190.
[16] Golden, B., Assad, A., Levy, L., and Gheysens, F., 1984. "The Fleet Size and Mix Vehicle Routing Problem", Comput and Operation Research, 11: 49-66.
[17] ILOG S.A., August 2000. ILOG OPL Studio 3.1 User’s Manual.
[18] ILOG S.A., August 2000. ILOG CPLEX 7.0 User ''s Manual.
[19] Kleywegt, A., Nori, V., and Savelsbergh, M., 2002, "The Stochastic Inventory Routing Problem with Direct Deliveries", Transportation Science, 29: 3.
[20] Kontoravdis, G. and Bard, J.F., 1995, "A GRASP for the Vehicle Routing Problem with Time Windows", Journal on Computing 7, 10-23.
[21] Kuehn, A. and Hamburger, M. J., 1963, "A Heuristic Program for Locating Warehouse", Management Science, 19: 643-666.
[22] Lin, S., 1965, "Computer Solution of the Traveling salesman Problem", The Bell System Technical Journal, 44: 2245-2269.
[23] Lin, S., and Kernighan, B. W., 1973, "An Effective Heuristic Algorithm for Traveling Salesman Problem", Operations Research, 21: 498-516.
[24] Liu, F. and Shen., S., 1999, "A route-neighborhood-based metaheuristic for vehicle routing problem with time windows”, European Journal of Operations Research, 118: 485-504.
[25] Mole, R. and Jameson, S., 1973, "A Sequential Route-Building Algorithm Employing A Generalized Savings Criterion", Operation Research Quarterly, 27: 503-511.
[26] Or, I., and W.P. Pierskalla, 1979, "A Transportation Location-Allocation Model For Reginal Blood Banking", AIIE Transaction, A11: 86-95.
[27] Perl, J., 1983, "A Unified Warehouse Location-Routing Analysis", UMI Dissertation Information Service.
[28] Perl, J.,and M.S.Daskin, 1985, "A Warehouse Location-Routing Problem", Transportation Research B, 19: 381-396.
[29] Potivin, J.Y. and Rousseau, J.M., 1993, "A Parallel route building algorithm for the vehicle routing and scheduling problem with time windows", European Journal of Operations Research, 66331-340
[30] Russell, R.A., 1995, "Hybrid heuristics for the vehicle routing problem with time windows", Transportation Science 29, 156-166.
[31] Simchi-Levi, D., 1991, "The Capacitated Traveling Salesman Location Problem", Transportation Science, 25: 9-18.
[32] Solomon, M., 1987, "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints", Operations Research, 15: 254-265.
[33] Solomon’s VRPTW Data Sets: http://web.cba.neu.edu/~msolomon/problems.htm
[34] Verter, V., and Dincer, M. C., 1995, "Facility Location and Capacity Acquisi- tion: An Integrated Approach", Navel Research Logistics, 42: 1141-1160.
中文部分：
[c1] 林惠民，民91，具時窗之多趟次車輛途程問題，私立元智大學資訊管理研究所碩士論文
[c2] 紅名鴻，民91，無容量限制下之動態需求設施區位問題研究，私立元智大學工業工程與管理研究所碩士論文