簡易檢索 / 詳目顯示

研究生: 蘇志峰
Su, Chih-Feng
論文名稱: 具時窗限制之多場站車輛路線問題之研究
指導教授: 張秀雲
Chang, Shiow-Yun
學位類別: 碩士
Master
系所名稱: 管理學院 - 工業管理科學系
Department of Industrial Management Science
論文出版年: 2002
畢業學年度: 90
語文別: 中文
論文頁數: 72
中文關鍵詞: 禁忌搜尋法縮減移步機制具時窗限制的多場站車輛路線問題
相關次數: 點閱:65下載:4
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 近年來商品的流通通路系統產生許多改革,其中以通路階層的縮短為甚,有別於傳統複雜的多層行銷通路中商品往往要經由層層轉運,最後才能送達客戶的手中,目前的商品配送已經逐漸走向「少量、多樣化、高頻率」的趨勢,而物流中心則能因應此商品的配送趨勢,進而成為目前商品流通業的主流。
    在物流中心的實體配送成本中,以運輸成本所占比例最高,也是影響物流公司營運能力之主要關鍵,而降低運輸成本的方式首重在良好的車輛路線規劃,目前國內外學者在這方面的研究上多著重在單一物流中心的車輛路線規劃,然而一個大型的物流公司可能擁有多個物流中心同時運作,因此如何同時對多個物流中心進行妥善的車輛路線規劃亦為一值得探討的主題。目前已有多場站車輛路線規劃的研究多不涉及時窗限制,但是在現實環境中商品的配送有時卻必須滿足顧客對特定時間的要求,有鑑於禁忌搜尋法應用於求解具時窗限制的車輛問題均能獲得相當好的求解品質,但其求解速度卻並不一定令人滿意,且多場站的環境下求解所花費的時間又較單場站來得長,因此本研究引入移步縮減機制於求解具時窗限制的多場站車輛路線問題的禁忌搜尋法求解架構中,刪除一些不必要執行的移步,以提高其求解效率及導正搜尋方向,並藉由縮減移步機制中限制條件的調整來提高求解品質,使得在此物流體系下以禁忌搜尋法加入移步縮減機制後能更快速求得品質更好的車輛路線規劃解。

    none

    目錄 摘要 I 誌謝 II 目錄 III 表目錄 V 圖目錄 VI 第一章 緒論 1 1.1 研究背景與動機 1 1.2 研究目的 2 1.3 研究範圍與假設 3 1.4 研究架構與流程 3 第二章 文獻探討 5 2.1 車輛路線問題 5 2.2 車輛路線問題之解法 6 2.3 車輛路線問題之延申 7 2.4 具時窗限制之車輛路線問題 10 2.5 多場站車輛路線問題 13 第三章 數學模式之建構與驗證 21 3.1 問題描述與定義 21 3.2 具時窗限制之多場站車輛路線問題之數學模式 22 3.2.1 使用符號與參變數說明 22 3.2.2 數學模式建構與說明 24 3.3 數學模式驗證 25 3.3.1 假設情況驗證 25 3.3.2 範例驗證 28 第四章 測試解法之建構 30 4.1 起始解之建構 30 4.2 禁忌搜尋法 32 4.3 Reduction Test 36 第五章 測試結果與分析 41 5.1 測試問題描述 41 5.2 測試參數設定 41 5.3 測試結果分析 46 第六章 結論與建議 51 6.1 結論 51 6.2 建議 52 參考文獻 53 附錄 57

    參 考 文 獻
    中文部份:
    吳致昀, 「多車次車輛路線問題之研究」,國立成功大學,工業管理科學研究所碩士論文,2000。
    陳志峰, 「車輛多次載運排程問題之研究」,國立成功大學,交通管理科學研究所碩士論文,1996。
    盧永文, 「應用地理資訊系統於具時窗之貨物配送」,國立成功大學,工業管理科學研究所碩士論文,1999。
    西文部份:
    Badeau, P., F. Guertin, M. Gendreau, J. Y. Potvin and E. Taillard (1997),“A
    Parallel Tabu Search Heuristic for the Vehicle Routing Problem with Time
    Windows,” Transporation Research -C, 5(2), pp.109-122.
    Bartholdi, J. J. and L. K. Platzman (1988), “Heuristics Based on Spacefilling Cruves for Combinational Problems in Euclidean Space,” Management Science, 34(3), pp. 291- 305.
    Bodin, L., B. Golden, A. Assad and M. Ball (1983), “Routing and Scheduling of Vehicles and Crews:The State of The Art,” Computers & Operations Research, 10(1), pp.63-211.
    Breedam, A.V. (2001),“Comparing Descent Heuristics and Metaheuristics for the
    Vehicle Routing Problem,” Computers & Operations Research, 28(4), pp.289-315.
    Clark, G. and J. W. Wright (1964),“Scheduling of Vehicles from A Central Depot to A Number of Delivery Points,” Operations Research, 12(4), pp.568-581.
    Chao, I. M., B. L. Golden and E. Wasil (1993), “A New Heuristic for The Multi-Depot Vehicle Routing Problem That Improves Upon Best-Known Solutions,” American Journal of Mathematical & Management Science, 13(2), pp.371-406.
    Cordeau, J. F., M. Gendreau and G. Laporte (1997), “A Tabu Search Heuristic for Periodic and Multi-Depot Vehicle Routing Problems,” Networks, 30(2), pp.105-119.
    Cordeau, J. F., G. Laporte and A. Mercier (2001), “A Unified Tabu Search Heuristic for Vehicle Routing Problems with Time Windows,” Journal of the Operational Research Society, 52(8), pp. 928-936.
    Duhamel, C., J. Y. Potvin and J. M. Rousseau (1997), “A Tabu Search
    Heuristic for the Vehicle Routing Problem with Backhauls and Time Windows,” Transportation Science, 31(1), pp.49-59.
    Fisher, M. L. and R. Jaikumar (1981), “A Generalized Assignment Heuristic for Vehicle Routing,” Networks, 11(2), pp.109-124.
    Gillett, E. B. and L. R. Miller (1974), “A Heuristic Algorithm for The Vehicle Dispatch Problem,” Operations Research, 22(2), pp.340-349.
    Gillett, B. E. and J. G. Johnson (1976), “Multi-Terminal Vehicle-Dispatch Algorithm,” Omega, 4(6),pp.711-718.
    Golden, B. L., T. L. Magnanti and H. Q. Nguyen (1977), “Implementing Vehicle Routing Algorithms,” Networks, 7(2), pp.113-148.
    Gendreau, M., A. Hertz and G. Laporte (1994), “A Tabu Search Heuristic for The Vehicle Routing Problem,” Management Science, 40(10), pp.1276-1290.
    Gendreau, M., G. Laporte and R. Seguin (1996), “A Tabu Search Heuristic for The Vehicle Routing Problem with Stochastic Demands and Customers,” Operations Research, 44(3),pp.469-477.
    Hong, S. C. and Y. B. Park (1999), “A Heuristic for Bi-Objective Vehicle Routing with Time Window Constraints,” International Journal of Production Economics, 62(3), pp.249-258.
    Koskosidis, Y. A. and W. B. Powell (1992), “Clustering Algorithms for Consolidation of Customer Orders into Vehicle Shipments,” Transporation Research-B, 26B(5), pp.365-379.
    Koskosidis, Y. A., W. B. Powell and M. M. Solomon (1992), “An Optimization Based Heuristic for Vehicle Routing and Scheduling with Soft Time Windows Constraints,” Transportation Science, 26(2), pp.69-85.
    Kolen, A. W. J., A. H. G. R. Kan and H. W. J. M. Trienekens (1987), “Vehicle Routing with Time Windows,” Operations Research, 35(2), pp.266-273.
    Krolak, P., W. Felts and J. Nelson (1972), “A Man-Machine Approach toward Solving The Generalized Truck Dispatching Problem,” Transportation Science, 6(2), pp.149-170.
    Laporte, G., Y. Nobert and S. Taillefer (1988), “Solving A Family of Multi-Depot Vehicle Routing and Location-Routing Problems,” Transportation Science, 22(3), pp.161-172.
    Lin, S. (1965), “Computer Solutions of The Traveling Salesman Problem,” Bell System Technical Journal, 44(10), pp.2245-2269.
    Nozick, L. K. (1997), “A Study On The Transportation Network of Distribution-The Analysis of The Multi-Depot Vehicle Routing Problem,” Project Report: SEC/R-MS-97-09, Sinotech Engineering Consultants, Inc.
    Potvin, J. Y., T. Kervahut, B. L. Garcai and J. M. Rousseau (1996), “The Vehicle Routing Problem with Time Windows Part I:Tabu Search,” INFORMS Journal on Computing, 8(2), pp.158-164.
    Potvin, J. Y. and S. Bengio (1996), “The Vehicle Routing Problem with Time Windows Part II:Genetic Search,” INFORMS Journal on Computing, 8(2), pp.165-172.
    Potvin, J. Y. and J. M. Rousseau (1993), “A Parllel Route Building Algorithm for The Vehicle Routing and Scheduling Problem with Time Windows,” European Journal of Operational Research, 66(3), pp.331-340.
    Potvin,J.Y. and J. M. Rousseau (1995), “An Exchange Heuristic for Routing
    Problems with Time Windows,” Operational Research Society, 46, pp.1433-1446.
    Raft, O. M. (1982), “A Modular Algorithm for an Extended Vehicle Scheduling Problem,” European Journal of Operational Research, 11(1), pp.67-76.
    Renaud, J., G. Laporte and F. F. Boctor (1996), “A Tabu Search Heuristic for The Multi-Depot Vehicle Routing Problem,” Computers & Operations Research, 23(3), pp.229-235.
    Russell, R. A.(1995), “Hybrid Heuristics for The Vehicle Routing Problem
    with Time Windows,” Transportation Science, 29(2), pp.156-166.
    Solomon, M. M. (1987), “Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints,” Operations Research, 35(2), pp.254-265.
    Salhi, S. and M. Sari (1997), “A Multi-Level Heuristic for The Multi-Depot Vehicle Fleet Mix Problem,” European Journal of Operational Research, 103(1), pp.95-112.
    Taillard, E., P. Badeau, M. Gendreau F. Guertin and J. Y. Potvin (1997), “A Tabu Heuristic for The Vehicle Routing Problem with Soft Time Windows,” Transportation Science, 31(2), pp.170-186.
    Tillman, F. A. (1969), “The Multiple Terminal Delivery Problem with Probabilistic Demands,” Transportation Science, 3(3), pp192-204.
    Tillman, F. A. and T. M. Cain (1972), “An Upperbound Algorithm for The Single and Multiple Terminal Delivery Problem,” Management Science, 18(11), pp.664-682.
    Thangiah, S. R., J. Y. Potvin and T. Sun (1996), “Heuristic Approaches to Vehicle Routing with Backhaul and Time Windows,” Computers & Operations Research, 23(11), pp.1043-1057.
    Wren, A. and A. Holliday (1972), “Computer Scheduling of Vehicles From One or More Depots to a Number of Delivery Points,” Operational Research Quarterly, 23, pp.333-344.

    下載圖示 校內:2005-08-29公開
    校外:2007-08-29公開
    QR CODE