臺灣博碩士論文加值系統

區位選擇及車輛途程問題都是物流中心運作非常重要的兩個環節。傳統上在探討設施區問題時，為了降低問題的複雜度，皆以設施間直接往返總距離最小化為目標來求解。此外，在探討車輛途程問題時，通常假設在區位已知的條件下求解。但事實上，在多個物流中心體系中，不同的物流中心數量與位置之組合將會影響未來的配送路線規劃、車隊規模，進而影響到物流總成本。因此，在決定物流中心區位時，不能只考慮區位的因素，必須同時考慮影響車輛途程之因素，這種整合性的問題稱為區位途程問題。
雖然Perl 和Daskin是最早求解區位途程問題的研究者，但是因為他們所提出的演算法相當複雜且耗時，所以本研究乃修正Perl 和 Daskin的演算，搭配節省法及基因演算法以加快求解速度。在車輛途程問題方面，由於過去的研究大都限制每輛車只能巡迴送貨一次，實務上不允許車輛重覆使用是不合理的。因此，本研究構建車輛可重覆使用的數學規劃模式，並發展一種三階段探索式演算法，允許車輛在總行駛距離和車容量的限制下，可以重新出發，以提高車輛的利用率。
研究結果顯示，本研究所發展的啟發式演算法與最佳解法比較方面，在需求點數7、物流中心數2、車容量限制150、行駛距離限制300的9個測試問題中，本研究之啟發式解法在小型問題上，不僅能求得最佳解而且能大幅縮短運算時間，此顯示本研究所提出之啟發式演算法對於小型問題之求解能兼具高準確性和效率性。此外，本研究的啟發式演算法與現行四種啟發式演算法比較，結果本研究之解法有非常不錯的表現。本研究允許車輛可以重複使用有助於物流業者降低物流總成本。

摘要Ⅰ
誌謝Ⅱ
目錄Ⅲ
圖目錄Ⅴ
表目錄Ⅵ
第一章 緒論1
1.1研究背景與目的1
1.2研究方法與架構2
1.3相關文獻探討4
1.3.1設施區位問題相關文獻探討4
1.3.2車輛途程問題相關文獻探討5
1.3.3區位途和問題相關文獻探討6
1.4研究範圍與限制8
第二章車輛不可重覆使用之現行數學規劃模式與啟發式演算法10
2.1問題描述10
2.2符號定義與基本假設11
2.2.1 符號定義11
2.2.2 基本假設12
2.3車輛不可重覆使用之現行數學規劃模式13
2.3.1 Perl數學規劃模式13
2.3.2 求解範例14
2.4車輛不可重覆使用之現行啟發式演算法15
2.4.1 Perl和Daskin啟發式演算法15
2.4.2 求解範例17
第三章車輛可重覆使用之本研究數學規劃模式與啟發式演算法18
3.1 符號定義與基本假設18
3.1.1 符號定義18
3.1.2 基本假設19
3.2 車輛可重覆使用之本研究數學規劃模式20
3.2.1 本研究模式之建構20
3.2.2 求解範例21
3.3 車輛可重覆使用之啟發式演算法24
3.3.1 物流中心區位分派模式26
3.3.2 車輛途程模式31
3.3.3 區位及途程改善模式35
3.3.4 求解範例42
第四章演算法績效之比較44
4.1實驗設計及重要參數敏感度分析44
4.1.1 影響演算法的重要參數分析44
4.1.2 影響模式的重要參數分析47
4.2本研究啟發式演算法與本研究最佳解法之比較51
4.3本研究啟發式演算法與現行主要解法之比較52
第五章結論與建議54
5.1 結論與建議54
5.2 未來研究方向56
參考文獻57
附錄一 本研究啟發式演算法電腦程式61
附錄二 區位-途程問題測試範例（用於比較本研究啟發式解法與現行啟發式解
法）68
作者簡介77

1.潘順興撰，陳稼興、陳振明指導，「遺傳演算法於配送點選擇之應用」，國立中央大學資訊管理研究所碩士論 文，1996。
2.王璟瑩撰，蘇純繒指導，「應用禁忌搜尋法於物流中心區位選擇之研究」，國立雲林科技大學工業工程與管理 技術研究所碩士論文，1998。
3.白俊偉撰，吳泰熙指導，「隨機型區位-途程問題解法之研究」，大葉大學工業工程所碩士論文，1999。
4.顏嘉宏撰，吳泰熙、王安祥指導，「區位-途程問題啟發式解法之研究」，大葉大學工業工程所碩士論文，2000 。
5.王俊傑撰，邱煥能指導，「多物流中心車輛可重覆使用之途程問題研究」，國立台灣科技大學工業管理研究所 碩士論文，2000。
6.Beasley, J. E., and Chu, P. C., "A Genetic Algorithm for the Set Covering Problem," European Journal of Operational Research, Vol. 8, No. 1, pp. 392-404, 1996.
7.Brandao , J., "A Decision Support System and Algorithms for the Vehicle Routing and Scheduling Problem," Ph. D. Thesis, Dept. of Management Science, Lancaster University, 1994.
8.Brandao , J. and Mercer, A., "A Tabu Search Algorithm for the Multi-Trip Vehicle Routing and Scheduling Problem," European Journal of Operational Research, Vol. 100, No. 1, pp. 180-191, 1997.
9.Brandao , J. and Mercer, A., "The Multi-Trip Vehicle Routing Problem," Journal of Operational Research Society, Vol. 49, No. 8, pp. 799-805, 1998.
10.Chao, I. M., Golden, B. L. and Wasil, E., "A New Heuristic for the Multi-Depot Vehicle Routing Problem that Improves upon Best-Known Solutions," American Journal of Mathematical Management Sciences, Vol. 13, Nos. 3?, pp. 371-406, 1993.
11.Clarke, G. and Wright, J. W., "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, Vol. 12, No. 5, pp. 568-805, 1964.
12.Fleischmann, B., "The Vehicle Routing Problem with Multiple Use of Vehicles," Working paper, Fachbereich Wirtschaftswissenschaften, Universitat Hamberg., 1990.
13.Gillett, B. E. and Johnson, J. G., "Multi-Terminal Vehicle-dispatch Algorithm," Omega, Vol. 4, No. 6, pp. 711-718, 1976.
14.Goldberg, D. E., "Genetic Algorithms in search, Optimization and Machine Learning," Addison-Wesley, NY, 1989.
15.Hansen, P. H., Hegedahl, B., Hjortkjar, S. and Obel, B., "A Heuristic Solution to the Warehouse Location-Routing Problem," European Journal of Operational Research, Vol. 76, No. 1, pp. 111-127, 1994.
16.Hommes, P., Howe, E. R. and Pape, C. S., "Burton''s Biscuits: A Study of the Load Planning Operation at the New Depot at Risley," Dept. of Management Science, Ph. Dissertation, University of Lancaster, 1989.
17.Laporte, G. and Nobert, Y., "An Exact Algorithm for Minimizing Routing and Operation Costs in Depot Location," European Journal of Operational Research, Vol. 59, No. 2 , pp. 224-226, 1981.
18.Laporte, G., Nobert, Y. and Tailefer, S., "Solving a Family of Multi-Depot Vehicle Routing and Location-Allocation Problem," Transportation Science, Vol. 22, No. 1, pp. 161-172, 1988.
19.Lenstra, J. and Rinnooy, K. A., "Complexity of Vehicle Routing and Scheduling Problems," Networks, Vol. 11, No. 2, pp. 221-227, 1981.
20.Min, H. , Jayaraman, V. and Srivastava, R. , "Combined Location-Routing Problem : A Synthesis and Future Research Directions," European Journal of Operational Research, Vol. 108, No. 1, pp.1-15, 1998.
21.Or, I. and Pierskalla, W. P., "A Transportation Location-Allocation Model for Regional Blood Banking," AIIE Transactions, Vol. 11, No. 1 , pp. 86-95, 1979.
22.Perl, J., " A Unified Warehouse Location-Routing Analysis," UMI Dissertation Information Service, 1983.
23.Perl, J. and Daskin, M. S., "A Warehouse Locatin-Routing Problem," Transportation Research Quarterly, B, Vol. 19, No. 5, pp.381-396, 1985.
24.Patnaik, L. M. and Srinivas, M., "Genetic Algorithms: A Survey," Computer, Vol. 27, No. 6, pp.17-26, 1994.
25.Raft, O. M., "A Modular Algorithm for Extended Vehicle Scheduling Problem," European Journal of Operational Research, Vol. 11, No. 1, pp. 67-76, 1982.
26.Renaud, J., Boctor, F. F. and Laporte, G., "An Improved Petal Heuristic for the Vehicle Routing Problem," Journal of Operational Research Society, Vol. 47, No. 2, pp. 329, 1996.
27.Taillard, E., Laporte, G. and Gendreau, M., "Vehicle Routing with Multiple Use of Vehicles," Journal of the Operational Research Society, Vol. 47, No. 8, pp. 1065-1070, 1996.
28.Tillman, F. A., "The Multiple Terminal Delivery Problem with Probabilistic Demands," Transportation Science, Vol. 3, No. 3, pp. 192-204, 1969.
29.Tuzun, D., and Burke, L. I. , "A two-phase Tabu Search Approach to the Location Routing Problem," European Journal of Operational Research, Vol. 116, No. 1, pp. 87-99, 1999.
30.Webb, M. H. J., "Cost Functions in the Location of Depot for Multi-Delivery Journeys", Operational Research Quarterly, Vol. 19, No. 3, pp. 311-328, 1968.
31.Wren, A. and Holliday, A., "Computer Scheduling of Vehicles from One or More Depots to a Number of Delivery Points," Operational Research Quarterly, Vol. 23, No. 4, pp. 333-344, 1972.