臺灣博碩士論文加值系統

本研究之目的在探討物流中心低溫冷凍食品的車輛配送路線規劃問題。冷凍食品有其保存期限之限制，同時顧客之消費習性為偏好挑選最新鮮的商品，因此在吾人所建立的模式中，將合併考慮運送成本及商品本身的保存期限與銷售特性。物流中心在實際的配送作業上需考慮滿足顧客對配送抵達時間的要求，亦即時窗（Time Windows）的限制。本研究中，吾人將冷凍食品之保存期限與銷售特性合併於時窗的限制之中，其做法是建立一適切之懲罰函數（Penalty Function）以定義各項因派車績效不佳所發生之隱性及顯性成本。
本研究中所建立之數學模型包含一特殊的架構，可進一步分解成一個分群（Clustering）主問題及許多各別獨立的巡迴子問題。針對此一分解後之架構，吾人制定一個二階段的啟發式求解過程，並發展相關的演算法。在第一階段，先利用遺傳演算法（Genetic Algorithm）以車輛為中心對所有顧客進行分群。亦即，某一車輛應該服務那些顧客。第二階段即針對第一階段中分群之結果，以每一車輛及其所服務之顧客為範圍，找出一最佳的巡迴路線。在第二階段所獲得之巡迴結果再回饋至第一階段做為分群的績效指標。利用此一反覆的方式，最後求得一個滿意的車輛排程。
本研究所建立的模式之優點在於同時考慮車輛配送路線之運輸成本，以及違反顧客要求送達時間所造成之各項顯性與隱性成本。在求解演算法方面，遺傳演算法提供快速求解並簡化求解過程的優點，具有實務上應用的潛力。

The purpose of this study is to investigate the planning of vehicle routing of a frozen food distribution center. Frozen food is perishable and customers always pick up the freshest one among all displayed products. To emphasize the influence of frozen food’s sales behavior to vehicle scheduling, we not only consider transportation costs but also incorporate some implicit costs into our model. In practice, a distribution center must deliver customers’ demands in an acceptable time window. In case the delivery arrives beyond the time window, penalty costs will occur. In this study we build a mathematical model which employs penalty functions to reflect the characteristic of frozen food and time window constraints. Moreover, an algorithm is proposed to solve model to obtain an optimal vehicle routing schedule.
Our mathematical model comprises a special structure which enables us to decompose the original model into a clustering master problem and many mutually independent routing subproblems. Based on this decomposition, we formulate a two-stage solution procedure. In the first stage, genetic algorithm is used to cluster customers with respect to each vehicle. That is, it determines a subset of customers for each vehicle. The second stage finds an optimal routing for each cluster, and the results are fed back to the first stage as a performance measurement of the current clustering. Finally, the problem is solved in such an iterative manner.
The advantage of our model is that it simultaneously considers the transportation costs and other explicit and implicit costs due to poor customer satisfaction. Meanwhile, the efficiency of genetic algorithm provides potential in practical implementation for solving the vehicle scheduling problem.

目 錄
中文摘要 …………………………………………………………… Ⅰ
英文摘要 …………………………………………………………… Ⅲ
誌謝 ………………………………………………………………… Ⅴ
目錄 ………………………………………………………………… Ⅵ
圖目錄 ……………………………………………………………… Ⅸ
表目錄 ……………………………………………………………… Ⅹ
第一章 緒 論 ……………………………………………….…… 1
1.1 研究背景與動機 ………………………………………… 2
1.2 研究目的 ………………………………………………… 4
1.3 台灣冷凍食品業與低溫冷凍物流中心之發展現況 …… 5
1.3.1 冷凍食品業現況 ……………………………………… 6
1.3.2 低溫冷凍物流中心現況 …………………………… 7
1.4 研究範圍與限制 …………………………….………… 12
第二章 時窗限制下車輛配送問題之文獻回顧 …………..…… 16
2.1 車輛配送問題的種類 ………………………….……… 17
2.2 早期車輛配送問題之文獻回顧 ………….…………… 19
2.3 近期車輛配送問題之文獻回顧 ……………….……… 20
2.4 其他車輛配送問題之相關文獻回顧 …………….…… 23
2.5 車輛配送問題之求解 …………………………….…… 30
第三章 物流中心車輛配送數學模式之建構與求解 …………… 40
3.1 含時間限制之車輛配送問題模式之建構 ……….…… 40
3.1.1 時窗說明 …………………………………….…… 40
3.1.2 使用混合型時窗之理由 …………………….…… 43
3.1.3 懲罰函數之建立 ………………………….……… 44
3.2 模式建立 …………………………………………….… 51
3.3 模式之求解 ……………………………………….…… 56
第四章 以遺傳演算法求解混合型時窗車輛排程問題 ……….. 60
4.1 遺傳演算法之探討 ……………………………………. 61
4.1.1 簡單遺傳演算法 ………………………….……… 65
4.1.2 遺傳演算法的優缺點 …………..………….…… 78
4.2 求解VRPSTW之演算法………………..……….………… 80
4.2.1 求解分群主問題（遺傳演算法） …………..…….. 80
4.2.2 求解巡迴子問題（列舉法） …………………….… 87
4.3 釋例 ……………………………………………………. 88
第五章 結論與未來研究方向 …………………………….……… 95
5.1 結論 ………………………………………………….… 95
5.2 未來研究方向 ………………………………………... 97
附錄：參考文獻 ………………………………………….……… 99

參 考 文 獻
（一）中文部分
[1] 中華民國冷凍食品發展協會（民87），中華民國冷凍食品年鑑，pp. 31~46.
[2] 王培珍（民85），「應用遺傳演算法與模擬在動態排程問題之探討」，私立中原大學工業工程研究所未出版之碩士論文。
[3] 吳淑貞（民82），「顧客服務導向之整合物流網路規劃」，國立中央大學工業工程管理研究所未出版之碩士論文。
[4] 吳淵齊（民84）「物流中心運輸成本及短缺罰金之最佳化模式」，國立雲林技術學院工業工程與管理技術研究所碩士論文。
[5] 杜世文（民81），「多目標與模糊時窗貨物配送啟發式解法之研究」，國立交通大學交通運輸研究所碩士論文。
[6] 易德華（民87），「軟時窗車輛巡迴問題之研究」，國立中央大學土木工程學系碩士論文。
[7] 林書銘（民87），「禁制搜尋法於含時窗與裝載限制車輛途程問題解算之研究」，私立元智大學工業工程研究所碩士論文。
[8] 徐明輝（民86），「多部車一般性車輛途程解算法之研究」，私立元智大學工業工程研究所碩士論文。
[9] 梅明德（民81），「地理資訊系統輔助物流中心及時配送系統之研究」，國立中央大學土木工程研究所碩士論文。
[10] 許英同（民88），「流通新聞：國內冷凍食品發展面臨瓶頸，各相關單位盼能提升競爭力、再創新機運」，流通快訊雜誌，230期，pp. 8~9.
[11] 陳柏文（民85），「物流中心易腐物品之機動配送模式研究」，國立雲林技術學院工業工程與管理技術研究所碩士論文。
[12] 曾敏雅（民87），「時窗限制下都會區夜間之低溫物流配送路線規劃研究」，國立中興大學農產運銷研究所碩士論文。
[13] 黃文昌（民81），「時窗限制下貨物配送問題求解方法之研究─時空雙準則平行節省啟發法之研擬」，國立交通大學交通運輸研究所碩士論文。
[14] 廖忠雄（民83），「物流中心運輸服務途程規劃」，國立台灣大學工業工程研究所碩士論文。
[15] 廖亮富（民87），「含時窗限制多部車車輛途程問題解算之研究」，私立元智大學工業工程研究所碩士論文。
[16] 鄭博王（民84），「以遺傳演算法及類神經網路應用於旅行推銷員問題上」，私立淡江大學土木工程研究所碩士論文。
[17] 戰略生產力雜誌（民86），Vol. 35, p. 22.
[18] 蘇純繒（民84），「自組織映射網路在車輛配送問題之研究」，國立雲林技術學院工業工程與管理技術研究所碩士論文。
[19] 蘇純繒（民86），「物流中心位置與車輛路徑之規劃」，第十二屆全國技術及職業教育研討會，pp. 205~222.
（二）英文部分
[20] Battiti, R. and Tecchiolli, G.（1994）,“The Reactive Tabu Search”, OSRA Journal on Computing, Vol.6(2), pp. 126-140.
[21] Jr. Blanton, J. L. and Wainwright, R. L.（1993）,“Multiple Vehicle Routing with Time and Capacity Constraints Using Genetic Algorithms”, In Proceedings of the Fifth International Conference on Genetic Algorithms and Their Applications, pp. 452-459.
[22] Bodin, L. D., and Golden, B.（1981）,“Classification in Vehicle Routing and Scheduling”, Networks, Vol.11, pp. 97-108.
[23] Bodin, L.（1990）,“Twenty Years of Routing and Scheduling”, Operations Research, Vol.38(4), pp. 571-579.
[24] Bowerman et al.（1994）,“A Parallel Implementation of the Tabu Search Heuristic for Vehicle Routing Problems with Time Windows Constraints”, Computers and Operatons Research, Vol.21. pp. 1025-1033.
[25] Bramel, J. and Simchi-levi, D.（1996）,“Probabilistic Analysis and Practical Algorithms for the Vehicle Routing Problem with Time Windows”, Operations Research, Vol.45, pp. 501-509.
[26] Cai et al.（1997）,“Vehicle Routing with Time Windows：Two Optimization Algorithms”, Operations Research, Vol.45, pp. 488-492.
[27] Carlton, W. B. and Barners, J. W.（1996）,“Solving and Traveling Salesman Problem with Time Windows Using Tabu Search”, IIE Trans., pp. 617-629.
[28] Christofides, N., Mingozzi, A. and Toth, P.（1981）,“State Space Relaxation Procedures for the Computation of Bounds to Routing Problems”, Networks, Vol.11, pp. 145-164.
[29] Chung, K. J. and Ting, P. S.（1993）,“A Heuristic for Replenishment of Deteriorating Items with a Linear Trend in Demand”, Journal of Opl Res., Soc., Vol.44, No.12, pp. 1235-1241.
[30] 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.
[31] Gillett, B. L. and Miller, L.（1992）,“A Heuristics Alogorithm for the Vehicle Dispatching Problem”, Operations Research, Vol.22, pp. 340-349.
[32] Goldberg, D. E.（1989）,“Genetic Algorithms in Search, Optimization and Machine Learning”, Addison-Wesley Publishing Company, INC.
[33] Golden, B. L. and Assad, A. A.（1988）,“Vehicle Routing: Methods and Studies”, North-Holland, Inc. Netherlands.
[34] Holland, J. H.（1975）,“Adaptation in Natural and Artificial Systems”, Univ. of Michigan Press, Ann Arbor. Mich.
[35] Knox, J.（1994）,“TABU Search Performance on the Symmetric Traveling Salesman Problem”, Computers and Operations Research, Vol.21, No.8, pp. 867-874.
[36] Kolen, A., Rinnooy, K. A. and Trienekens, W.（1987）,“Vehicle Routing with Time Windows”, Operations Research, Vol.35, pp. 266-273.
[37] Koskosidis, Y. A., Powell, W. B. and Solomon M. M.（1992）,“An Optimization-based Heuristic for Vehicle Routing and Scheduling with Soft Time Window Constraints”, Transportation Science, Vol.26, No.2. pp. 124-132.
[38] Koskosidis, Y. A., Powell, W. B. and Solomon, M. M.（1992）,“An Optimization-based Heuristic for Vehicle Routing and Scheduling with Soft Time Window Constraints”, Transportation Science, Vol.26(2), pp. 69-85.
[39] Krolak et al.（1971）,“A Computational Modification to the Savings Method of Vehicle Scheduling”, Operation Research Quarterly, Vol.24. pp. 281-283.
[40] Laporte S., Minoux M. and Odier E.（1995）,“Exact Algorithm for the Vehicle Routing Problem”, Annals of Discrete Mathematic, Vol.31, pp. 147-184.
[41] Lawler et al.（1985）, “The Traveling Salesman Problem, A Guided Tour of Combinatorial Optimization”, Wiley, Chichester.
[42] Lin, S.（1965）,“Computer Solution of the Traveling Salesman Problem”, Bell System Computer Journal, Vol.44, pp. 2245-2269.
[43] Malmborg, C. J.（1996）,“A Genetic Algorithm for Service Level Based Vehicle Routing Scheduling”, European Journal of Operation Research, Vol.93, pp.121-134.
[44] Mario et al.（1995）,”Vehicle Routing”,Handbooks in Operations Research and Management Science, Vol.8：Network Routing, North-Holland, Amsterdam, pp.1-33.
[45] Miller, L. R. and Gillet, B. E.（1974）, “A Heuristic Algorithm for the Vehicle Dispatch Problem”, Operations Research, Vol.22, pp. 340-349.
[46] Mitsuo, G. and Runwei, C.（1992）,“Genetic Algorithms and Engineering Design”, A Wiley-Interscience Publication. pp. 113-115.
[47] Savelsbergh, M. W. P.（1985）, “Local Search for Routing Problems with Time Windows”. Operations Research, Vol.4, pp. 285-305, 1985.
[48] Solomon, M.（1987）,“Algorithms for the Vehicle Routing and Scheduling with Time Window Constraints”, Operations Research, Vol.15, pp. 254-265.
[49] Srinivas, M., and Patnaik, L. M.（1994）, “Genetic Algorithms: A Survey”, IEEE Computer, June, pp. 17-26.
[50] Tabucanon, M. T., Kovavisaruch, L. E., and Malaivongs, K.（1995）, “Microcomputer-based Heuristic Approach to Vehicle Routing for After-sales Servicing”, Decision Support Systems, Vol.13, No.2, pp.195-205.
[51] Taillard et al.（1997）, “A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows”, Transportation Science, Vol.31, pp.170-186.
[52] Thangiah, S. R., Osman, I. H. and Sun, T.（1995）, ”Metaheuritics for Vehicle Routing Problems with Time Windows,” Technical Report, SRU-CpSc-TR-95-32, Artificial Intelligence and Robotics Laboratory, Computer Science Department, Slippery Rock University, Pennsylvania.
[53] Thangiah, S. R., Osman, I. H. and Sun. T.（1994）,“Hybrid Genetic Algorithm, Stimulated Annealing and Tabu Search Methods for Vehicle Routing Problems with Time Windows,” Working Paper UKC/OR94/4, Institute of Mathematics and Statistics, University of Kent, Canterbury.
[54] Thomas, E. M.（1993）,“Near Myopic Heuristics for the Fixed-life Perishable Problem”, Management Science, Vol.39, No.12, pp.1490-1498.
[55] Whitely, D., Starkweather, T. and Fuquay, D.（1989）,“Scheduling Problems and Traveling Salesman: The Genetic Edge Recombination Operator”, in Schafer(ed), Proceedings of the Third International Conference for Genetic Algorithms, Morgan Kaufmann PubIishers, Inc., pp.133-140.