Title page for 92322080


[Back to Results | New Search]

Student Number 92322080
Author WEN-CHING SU(蘇文清)
Author's Email Address No Public.
Statistics This thesis had been viewed 2321 times. Download 1531 times.
Department Civil Engineering
Year 2004
Semester 2
Degree Master
Type of Document Master's Thesis
Language zh-TW.Big5 Chinese
Title Vehicle Routing Problem with Soft Time Window for Concurrent Bi-Directional Logistics
Date of Defense 2005-06-27
Page Count 137
Keyword
  • reverse logistics
  • simultaneous deliveries and pickups
  • soft time window
  • Abstract Abstract
     The introduction of reverse logistics may significantly reduce the cost of returned merchandise, improve the customer’s satisfaction, and therefore increase enterprise profit. Recently, most of enterprises pay their great attention to the inclusion of reverse logistics to proceed hand in hand with already regularly-operated forward logistics. Transportation of physical distribution plays a critical role in logistics. In general, transportation cost is the majority of the total cost in supply chain, fifty-two percent approximately. The principal objective of the study is therefore to concurrently accomplish the delivery and pickup commodities at customer’s specified time window, i.e. to perform forward and reverse logistics at the identical trip. It may be classified as a vehicle routing problem with soft time window for simultaneous commodity delivery and pickup. The traditional vehicle routing problem is mostly considered the single object, the total distance, however the operation of companies is based on multiple objects rather than a single object. Therefore this study is to integrate the shortest distance and the fewest penalty cost by the weighting method in terms of both the cost and the level of service. This study suggested that pickup during the delivery only requires the rest capacity enough for the goods. There is no such constraint that pickup only can be performed when the certain capacity of the car is left. We solved the modified Solomon benchmark with random pickup demand by using Genetic Algorithms with soft time window (The penalty is dramatically increased by increasing the time of being late and waiting to emphasize the value of time for customers). In addition, we program a computer to demonstrate the accuracy of this idea. The results showed that total cost was slightly increased by increasing the demand of pickup and the cost was increased maximally about 6.44% when the quantity of pickup was about half of that of delivery. As a result, the idea, pickup during the delivery, actually improved the efficiency of the vehicle usage and reduced the waste of the capacity of returned vehicles. 
    Table of Content 目 錄
    中文摘要..............................Ⅰ
    英文摘要..............................Ⅱ
    誌謝................................Ⅲ
    目錄................................Ⅳ
    圗目錄...............................Ⅶ
    表目錄...............................Ⅸ
    第一章 緒論............................1
    1-1研究背景與動機.......................1
    1-2研究目的與範圍........................6
    1-3研究架構與方法........................9
    1-4研究內容與流程.......................12
    第二章 文獻回顧..........................15
    2-1逆物流問題論述.......................15
    2-2同時考量撿收與配送之車輛途程問題..............22
    2-3軟時窗限制之車輛途程問題回顧................24
    2-4途程問題解法回顧......................26
    2-5巨集啟發式解法.......................31
    2-6基因演算法.........................33
    2-7小結............................46
    第三章 撿收與配送車輛途程問題研究模型構建.............48
    3-1問題描述..........................48
    3-2模式構建..........................52
    3-3權重法...........................58
    3-4構建初始路徑........................58
    3-5執行演算法.........................60
    3-6路線改善法.........................65
    3-7軟性時窗限制........................69
    第四章 範例測試..........................72
      4-1測試例題說明........................72
      4-2硬性時窗問題測試......................74
      4-3權重測試..........................77
      4-4突變率與交配率的決定....................90
      4-5同時構建初始途程與依序構建初始途程.............92
      4-6固定及變動交配率與突變率測試................95
      4-7路徑失敗..........................98
    4-8車輛使用率的提升......................100
    4-9結果分析與探討.......................102
    第五章 結論............................107
      5-1測試結論..........................107
      5-2未來研究方向........................108
      5-3逆物流建議.........................109
    參考文獻..............................110
    參考網站..............................117
    附錄(一).............................118
    附錄(二).............................120
    圖 目 錄
    圖1-1 研究架構流程圖.......................10
    圖1-2 求解演算流程圖.......................12
    圖1-3 研究流程圖.........................14
    圖2-1 VRP示意圖.........................23
    圖2-2 VRPB示意圖........................24
    圖2-3 基因演算法流程圖......................45
    圖3-1 模式構建流程圖.......................57
    圖3-2 輪盤法圖示.........................62
    圖3-3 路線交換改善法前後比較圖..................66
    圖3-4 1-0節點轉移改善法前後比較圖................67
    圖3-5 1-1節點交換改善法前後比較圖................67
    圖3-6 2-opt交換法前後改善比較圖..................68
    圖3-7 懲罰成本比較圖.......................70
    圖3-8 本研究之懲罰成本設計圖...................71
    圖4-1 R107總行駛距離圖......................78
    圖4-2 R108總行駛距離圖......................79
    圖4-3 R110總行駛距離圖......................79
    圖4-4 RC104總行駛距離圖.....................80
    圖4-5 RC106總行駛距離圖.....................80
    圖4-6 RC107總行駛距離圖.....................81
    圖4-7 R107總違反時間成本圖....................82
    圖4-8 R108總違反時間成本圖....................82
    圖4-9 R110總違反時間成本圖....................83
    圖4-10 RC104總違反時間成本圖..................83
    圖4-11 RC106總違反時間成本圖..................84
    圖4-12 RC107總違反時間成本圖..................84
    表 目 錄
    表1-1 車輛繞徑問題分類表......................7
    表1-1 車輛繞徑問題分類表(續)...................8
    表2-1 逆物流定義表........................17
    表2-1 逆物流定義表(續)......................18
    表2-1 逆物流定義表(續二).....................19
    表2-2 逆物流分類表........................21
    表2-3 撿收VRP文獻整理......................30
    表2-3 撿收VRP文獻整理(續)...................31
    表4-1 本研究硬時窗解列表.....................75
    表4-1 本研究硬時窗解列表(續)...................76
    表4-2 各車輛數測試資料表.....................86
    表4-2 各車輛數測試資料表(續)...................87
    表4-2 各車輛數測試資料表(續二)..................88
    表4-3 交配率與突變率交叉測試表..................91
    表4-4 同時構建途程與依序構建途程比較表..............93
    表4-5 同時構建途程與依序構建途程運算時間比較表..........94
    表4-6 固定交配率、突變率與變動交配率、突變率比較表........96
    表4-7 固定交配率、突變率與變動交配率、突變率運算時間比較表....97
    表4-8 R型與RC型路網送貨需求表.................98
    表4-9 總取貨量佔總送貨量比率與路徑失敗率比較表..........99
    表4-10 撿收量對於總目標值的影響..................101
    Reference 參 考 文 獻
    宋明弘,徐俊能(1994),「以遺傳基因演算法則解決多目標考量的推銷員旅行問題之研究」,私立大葉大學事業經營研究所碩士論文,民國八十三年六月。
    吳泰熙,徐俊誠(2000),「車輛途程含取貨問題解法之研究」,私立大葉大學工業工程研究所碩士論文,民國八十九年六月。
    吳志遠,邵惠鶴,吳新余(1999),「一種新的自適應遺傳算法及其在多峰值函數優化中的應用」,控制理論與應用,第十六卷,第一期,127-129頁。
    李健(2002),「逆向供應鏈」、IT經理世界,第十四期。
    胡黃德,敖君瑋(1999),「禁制搜尋法於軟性時窗限制之車輛途程問題研究」,私立元智大學工業工程研究所碩士論文,民國八十八年六月。
    胡黃德,曾維豪(2000),「軟性時窗與回程撿收之車輛途程問題研究」,私立元智大學工業工程研究所碩士論文,民國八十九年六月。
    胡黃德,魏宗徹(2001),「整合時窗限制與回程撿收之多車種車輛途程問題」,私立元智大學工業工程與管理研究所碩士論文,民國九十年六月。
    徐旭昇,顏成佑(2000),「基因演算法解軟性時窗車輛途程問題之研究」,私立元智大學工業工程與管理研究所碩士論文,民國八十九年六月。
    耿伯文,楊昭峰(2002),「製造策略對逆向供應鏈績效之影響」,國立成功大學工業管理科學研究所碩士論文,民國九十一年六月。
    郝皓(2002),「逆向物流」IT經理世界,第十五期。
    張美香,陳祥瑞(2002),「含時窗限制與撿收之動態車輛途程規劃之研究」,私立中華大學經營管理研究所碩士論文,民國九十一年六月。
    許志義(2003),「多目標決策」,五南出版社,民國九十二年十月。
    陳正芳,莊英群(2003),「應用禁忌搜尋法混合送收貨之車輛途程問題」,私立逢甲大學工業工程研究所碩士論文,民國九十二年一月。
    陳昭華,王妙娜(2003),「動態交通號誌維修路線規劃模式之研」究,私立中華大學科技管理研究所碩士論文,民國九十二年六月。
    陳昭華,廖凱怡(2004),「時間相依路網之動態交通號誌維修問題之研究」,私立中華大學科技管理研究所碩士論文,民國九十三年六月。
    陳珠龍,劉雅魁(1996),「運用路線鄰域法求解車輛路線含回程取貨問題」,國立國防館理學院資源管理研究所碩士論文,民國八十七年六月。
    陳惠國,易德華(1998),「軟時窗車輛途程問題之研究」,國立中央大學土木工程研究所碩士論文,民國八十七年六月。
    陳柳欽(2002),「綠色物流探討」,http://www.56net.com
    曾國雄,黃文昌(1992),「時窗限制下貨物配送問題求解方法之研究-時空雙準則平行節省啟發法之研擬」,國立交通大學交通運輸研究所碩士論文,民國八時一年六月。
    曾國雄,杜世文(1992),「多目標與模糊時窗貨物配送啟發式解法之研究」,國立交通大學交通運輸研究所碩士論文,民國八十一年六月。
    曾國雄,王日昌,黃明居(1996),「以基因演算法與樣版路徑求解旅行推銷員問題」,運輸計畫季刊,第二十五卷,第三期,第493-516頁。
    曾國雄,王日昌(1997),「基因演算法在多目標組合最佳化問題之研究-以旅行推銷員問題為例」,國立交通大學交通運輸研究所博士論文,民國八十六年六月。
    曾國雄,邱裕鈞,許書耕(1997),「主線柵欄式收費站最佳區位遺傳演算尋優法與逐步尋優法之比較分析」,中國土木水利工程學刊,第九卷,,第一期,第171-178頁。
    馮正民,邱裕鈞(2004),「研究分析方法」,建都文化事業股份有限公司,民國九十三年六月。
    廖文慈(1999),「應用基因演算法求解優先順序旅行推銷員問題之研究」,私立元智大學工業工程與管理研究所碩士論文,民國八十八年六月。
    鄧振源(2002),「計畫評估~方法與應用~」,海洋大學運籌規劃與管理研究中心,民國九十一年十月。
    劉復華,申生元(1999),「時窗限制車輛途程問題」,國立交通大學工業工程與管理研究所碩士論文,民國八十八年六月。
    駱景堯,黃聖峰(1999),「考量回程撿收之車輛途程問題研究」,私立大葉大學工業工程研究所碩士論文,民國八十八年六月。
    顏上堯,陳建榮(2001),「含凹形節線成本最小成本網路流動問題之全域搜尋演算法研究」,國立中央大學土木工程研究所碩士論文,民國九十年六月。
    蘇義雄,黃詩彥(2000),「企業逆物流之探索研究」,私立東吳大學企業管理學研究所碩士論文,民國八十九年六月。
    Blumberg, D. F. (1999), “Strategic Examination of Reverse Logistics & Repair Service Requirements, Needs Market Size, and Opportunities”, Journal of Business Logistics. 20:141-159.
    Bodin, L. and Golden, B. (1981), “Classification in Vehicle Routing and Scheduling”, Networks. 11:97-108.
    Bodin, L., Golden, B., Assad, A. and Bull, D. (1983), “Routing Scheduling of Vehicles and Crews: The State of Art”, Computers and Operational Research. 10:63-211.
    Carter, C. R. and Ellram, L. M. (1998), “Reverse Logistics: A review of the Literature and Framework for Future Investigation”, Journal of Business Logistics. 19:85-102.
    Casco, D.O., Golden, B. L. and Wasil, E. A. (1988), “Vehicle Routing with Backhauls: models, algorithms, and case studies. In: Golden, L. and Assad, A. (eds)”, Vehicle Routing: Methods and Studies, North-Holland, Amsterdam. 127-147.
    Cohen, M. (1988), “Replace, rebuild or remanufacture”, Equipment Management. 16:22-26.
    Council of Logistics Management (1998), “Reuse and Recycling-Reverse Logistics Opportunities”, Glossary.
    Dale, S. R. and Ronald, S. T. (1998), “Going Backwards: Reverse Logistics Trends and Practices”, Reverse Logistics Executive Council.
    Daugherty, P. J., Chad, W. A. and Alexander, E. E. (2001), “Reverse Logistics: The Relationship between Resource Commitment and Program Performance”, Journal of Business Logistics. 22:107-123.
    Deif, I. and Bodin, L. (1984), “Extension of the Clarke and Wright Algorithm for Solving the Vehicle Routing Problem with Backhauling. In proceedings of the babson conference on sofeware use”, In Transportation and logistic management, A. E. Kidder, Babson Prak, MA. 75-96.
    Dowlatshahi, S. (2000), “Developing a Theory of Reverse Logistics”, Interfaces. 30:143-155.
    Fisher, M and Jaikumar, R. (1981), “ A Generalized Assignment Heuristic for Vehicle Routing”, Networks. 11:109-124.
    Fleischmann, M., Bloemhof-Ruwaard, J. M., Dekker, R., van der Laan, E., van Nunen, J. A. E. E. and van Wassenhove, L. N. (1997), “Quantitative Models for Reverse Logistics: A Revies”, European Journal of Operation Research. 103:1-17.
    Fleischmann, M., Krikke, H. R., Dekker, R. and Flapper, S. P. (2000), “A Characterization of Logistics Networks for Product Recovery”, Omega. 28:653-666.
    Guide Jr., V., Daniel, R. and Srivastava, R. (1997), “An Evaluation of Order Release Strategies in a Remanufacturing Environment”, Computer Operations Research. 24:37-47.
    Guide Jr., V., Daniel, R., Wassenhove, V. and Luk, N. (2002), “The Reverse Supply Chain”, Harvard Business Review. 80:25-26.
    Golden, B. L. (1977), “Evaluting a Sequential Vehicle Routing Algorithm”, AIIE Transactions. 9:204-208.
    Golden, B., Assad, A., Levy, L. and Gheysens, F. (1984), “The Fleet Size and Mix Vehicle Routing Problem”, Computers and Operations Research. 11:49-66.
    Golden, B., Baker, E., Alfaro, J. and Schaffer, J. (1985), “The Vehicle Routing Problem with Backhauling: two approaches”, Proceeding of the Twenty-First Annual Meeting of S. E. TIMS, Myrtle Beach, SC. 90-92.
    Golden, B. L. and Assad, A. (1986), “Vehicle Routing with Time Window Constraints”, American journal of Mathematical and Management Sciences. 6:251-260.
    Goldberg, D. E. (1989), Genetic Algorithm in search, Optimization and Machine Learning, Addison Wesley.
    Koskosidis, Y. A., Powell, W. B. and Solomon, M. M. (1992), “An Optimization-Based Heuristic for Vehicle Routing and Scheduling with Soft Time Windows Constraints”, Transportation Science. 26:69-85.
    Louis S. J., Yin, X. and Yuan, Z. Y. (1999), “Multiple Vehicle Routing with Time Windows Using Genetic Algorithms”, Proceedings of the Congress of Evolutionary
    Computation. 1804-1808.
    Lenstra, J. and Rinnooy, K. (1981), “Complexity of Vehicle Routing and Scheduling Problem”, Network. 1:221-227.
    Lin, S. (1965), “Computer Solutions of the Traveling Salesman Problem”, The Bell System Technical Journal. 44:2245-2269.
    Gen, M. and Cheng R. (2000), “Genetic Algorithms and Engineering Optimization”, Ashikaga Institute of Technology.
    Gen, M. (2004), “Evolutionary Algorithms and Optimization: Theory and Applications”, Graduate School of Information, Production & Systems. Waseda University.
    Osman, I. (1993), “Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem”, Annals of Operations Research. 41:421-451.
    Potvin, JY. and Laporte, G. (1996), “Genetic Algorithm for the Traveling Salesman Problem”, Annals of Operations Research. 63:339-370.
    Rudolph, G. (1994), “Convergence properties of canonical genetic algorithms”, IEEE Trans. Neural Networks. 5:96-101.
    Salhi, S. and Nagy, G. (1999), “A Cluster Insertion Heuristic for Single and Multiple Depot Vehicle Routing Problems with Backhauling”, Journal of the Operational Research Society. 50:1034-1042.
    Sexton, T. and Choi, Y. (1986), “Pickup and Delivery of Partial Loads with Time Windows”, American Journal of Math Management Science. 6:369-398.
    Solomon, M. M. (1987), “Algorithm for the Vehicle Routing and Scheduling Problems with Time Window Constrains”, Operations Research. 35:254-265.
    Solomon, M. M. (1988), “Survey Paper: Time Window Constrained Routing and Scheduling Problems”, Transportation Science. 22:1-13.
    Solomon, M. M. , Baker E. and Schaffer, J. (1988), “Vehicle Routing and Scheduling Problems with Time Window Constrains: Effectient Implementations of Solution Improvement Procedures”, In B.L. Golden and A.A. Assad, editors, Vehicle muting: Methods and studies, North-Holland, Amsterdam, 85-106.
    Srinivas, M. M. and Patnaik, L. M. (1994), “Genetic Algorithms: A Survey”, IEEE Computer. 17-26.
    Stock, J. R. (1998), “White Paper: Reverse Logistics. USA”, Council of Logistics Management.
    Stock, J. R. (1998), “Development and Implementation of Reverse Logistics Programs”, Council of Logistics Management. 579-586.
    Toth, P. and Vigo, D. (1997), “An Exact Algorithm for the Vehicle Routing Problem with Backhauls”, Transportation Science. 31:372-385.
    Yano, C., Chan, T., Richter, L., Cutler, T., Murty, k. and McGettigan, D. (1987), Vehicle Routing at Quality Stores”, Interfaces. 17:52-63.
    Zhu, K. Q. (2000), “A New Genetic Algorithm for VRPTW”, International Conference on Artificial Intelligence, Las Vegas, USA.
    Advisor
  • How-Ming Shieh(謝浩明)
  • Files
  • 92322080.pdf
  • approve in 2 years
    Date of Submission 2005-07-13

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have dissertation-related questions, please contact with the NCU library extension service section.
    Our service phone is (03)422-7151 Ext. 57407,E-mail is also welcomed.