臺灣博碩士論文加值系統

近年來，隨著電子商務與電視購物等虛擬通路的蓬勃發展，以網際網路與電話為主要交易媒介之方式，逐漸成為現代人之主流購物型式，使得貨物運送的方式由傳統將大量的成品運送至固定的大賣場或零售商等銷售點鋪貨的型式，逐漸轉型成將小量的貨物直接運送至顧客手中，因此國內的宅配市場逐漸的受到重視，使得傳統的運輸產業紛紛轉型成宅配之運輸產業以配合市場的脈動，然而，在宅配業者彼此激烈的競爭下，如何有效降低營運成本，提升服務品質，使業者能維持其競爭之優勢將是一重要的課題。
本研究將探討宅配車輛之路線巡迴問題(VRP)，並且考慮時窗限制下之路線規劃研究，規劃求解設計是利用已知資訊先進行靜態車輛路線規劃問題解，依已知需求點規劃車輛行駛路線，藉由禁制搜尋法(Tuba Search, TS)改善路線起始解，進而獲得最佳車輛配送路線，而在車輛開始巡迴後針對動態的需求以及臨時取消的需求進行即時規劃，在符合時窗限制下以最短的巡迴路徑營運來節省營運路線成本、提升服務績效。
由於實際宅配配送由宅配工程師所屬之責任分區負責規劃，因此本研究只考慮單一場站及單一責任分區來規劃配送路線，研究方法在時窗限制為軟性時窗限制(Soft Time Windows)，而在設計上一般客戶採上、下午兩大時段規劃而契約客戶則賦予個別特定時窗限制，以符合實際之配送方式，而路線規劃求解採三階段設計，前兩階段為靜態路線規劃，第三階段為動態路線規劃，第一階段初始解建構階段先利用最近鄰點法(Nearest Neighbor Heuristics, NNH)將需求點作初始可行解的規劃，此方法類似宅配工程師規劃之經驗法則，以此方法快速取得初始解，再於第二階段之路線改善階段利用禁制搜尋法(TS)作為改善解的規劃，而交換法分別利用Swap交換法及Or-Opt交換法擬出四種混合策略模式作為禁制搜尋法之核心交換法做測試比較，評選出為兩次改善策略最佳決策模式，而第三階段則在有即時需求產生時進行動態規劃，實驗證實透過此模式路線成本節省可達到約40%之改善效果，最後將最佳模式以實際路網進行實證分析仍可獲得約20%的成本節省改善效果。

Recently, as the virtual approach is developing, such as electric business and TV shopping, etc. The form of product transfer is changing from traditional way into Home delivery. The traditional transportation transfers a large number of products to specific selling places or retailers, etc. And Home delivery is transfer a small number of products to customer. It is getting important to Home Delivery of domestic market, and it makes traditional transportation industry transfer to keep up with the market changes.
The study discusses the Vehicle Routing Problem (VRP) of home delivery car and Consider the constraint of Time Window to offer a Home Delivery assignment model. The design of planning is using known information to solve static VRP and improve initial solution by Tabu Search algorithm to obtain optimal delivery path. After operating car start delivery, we focus dynamic or canceling demands to start real time planning. We plan the shortest path Under Time window to save the routing cost and operate efficiently.
The practical Home Delivery is planning by sales driver whose duty area, so the study only consider one depot and one duty area to plan the delivery path. The method of research in time constraint is soft time windows and separate in morning and afternoon two times to fit in practical operation. In route planning, we design three stage planning. First two stages plan static demands and the third stage plans dynamic demands. Stage 1: Using the Nearest Neighborhood Heuristics to construct initial solution. Stage 2: Using Tabu Search algorithm to improve initial solution. The local search engine we use swap and op-opt interchange methods to make four alternatives and test in experimental design. After test, we choose the optimal alternative which is two times improving method to improve initial solution. Stage 3: As the real time demands occur, we start dynamic route planning improving.
After experimental design test, we find out in this way it can be almost reached 40% cost down improving effect. We put the optimal model into actual network to analyze and it also can be reached 20% cost down improving effect.

第一章 緒論 1
1.1研究背景 1
1.2研究動機 3
1.3研究範圍 4
1.4問題描述 4
1.5研究目的 6
1.6研究流程 6
第二章 問題定義與文獻回顧 8
2.1問題定義 8
2.2文獻回顧 12
2.2.1車輛途程規劃問題 12
2.2.2旅行者銷售員問題 19
2.2.3啟發式解法 22
第三章 研究方法 36
3.1 DPDTSPTW之解題架構 36
3.2 建構數學模式 37
3.2.1 基本假設 38
3.2.2 決策變數與參數定義 38
3.2.3 PDTSPTW數學模式 39
3.2.4 DPDTSPTW數學模式 40
3.3 啟發式解法之設計 42
3.3.1起始路線規劃階段 42
3.3.2路線改善階段與改善策略 43
3.3.3動態路線規劃階段 44
第四章 實驗設計與測試分析 46
4.1實驗設計與說明 46
4.1.1實驗設計流程 46
4.1.2簡易範例設計 46
4.1.3相關參數設定與假設說明 48
4.2實驗設計測試 48
4.2.1路線建構階段 49
4.2.2路線改善階段 53
4.2.3動態路線規劃階段 61
第五章 實證分析 66
5.1實證範例說明 66
5.2靜態解求解結果分析 67
5.2.1上午時段求解分析 67
5.2.2下午時段求解分析 70
5.2.3上、下午時段合併分析 72
5.3動態解求解結果分析 73
5.3.1動態資料說明 73
5.3.2動態需求求解分析 74
第六章 結論與建議 82
6.1結論 82
6.2建議 83
參考文獻 85
附錄一 89
附錄二 104
附錄三 111

【1】李洪鑫，2000，含時間窗車輛途程問題各演算法適用範圍之探討，東海大學工業工程研究所，碩士論文。
【2】林正章，1998，「The Load Planning of Time Definite Freight Distribution Common Carriers」，運輸計劃季刊，27(3)，頁371~頁406。
【3】林志鴻、陳春益、許晉嘉，2003，宅配業車輛路線規劃問題之啟發式解法，中華民國運輸學會第十八屆學術論文研究會論文集。
【4】周淑蓉，2004，以群聚及禁制搜尋法求解含時窗限制之車輛巡迴路線問題，朝陽科技大學資訊管理系，碩士論文。
【5】柯景文，2002，禁制搜尋法於動態車輛巡迴路線問題之研究，逢甲大學交通工程與管理學系，碩士論文。
【6】胡大瀛、呂英志、陳仲強、陳佳貝，2001，「動態車路線問題之研究」，中華民國運輸學會第十六屆學術論文研究會論文集， 頁133-142。
【7】陳怡芳，2005，單一宅配車輛路線規劃之研究，逢甲大學交通工程與管理學系，碩士論文。
【8】陳建良，2002，以啟發式演算法求解時窗限制車輛途程問題，中原大學工業工程學系，碩士論文。
【9】陳建緯，2001，大規模旅行推銷員問題之研究：鄰域搜尋法與巨集啟發式解法之應用，交通大學運輸工程與管理學系，碩士論文。
【10】陳隆熙，2002，「一個解決TSP問題最佳解的穩定方法—以TA演算法為例」，大葉大學工業工程學系，碩士論文。
【11】陳振，2000，「風起雲湧-台灣宅配戰國元年」，物流技術與戰略，第16期，頁62-69。
【12】陳致元，2001，單一物流中心車輛途程問題求解模式之空間分析研究，台灣大學地理環境資源研究所，碩士論文。
【13】陳蕙國等人合著，2001，運輸網路分析，五南圖書出版有限公司，頁203-221。
【14】許再豐，2004，即時資訊下動態車輛途程規劃研究，朝陽科技大學工業工程與管理學系，碩士論文。
【15】許晉嘉，2003，宅配業貨物配送路線規劃問題之研究，成功大學交通管理科學研究所，碩士論文。
【16】莊英群，2003，應用禁忌搜尋法於混合送收貨之車輛途程問題，逢甲大學工業工程研究所，碩士論文。
【17】梅明德、謝浩明，2001，「時窗限制動態車輛路線問題之線上型路線建立啟發式解」，運輸學刊，13(2)，頁73~頁111。
【18】曾惠鈺，2003，即時行車資訊下物流配送作業規劃之研究，淡江大學運輸管理學系運輸科學碩士班，碩士論文。
【19】盧步雲，2002，應用塔布搜尋法於含軟性時窗限制之動態需求撿取配送途程規劃問題，中原大學工業工程學系，碩士論文。
【20】蘇昭銘、張志鴻、莊子駿，2001，「應用GIS分析宅配業車輛路線排程作業之研究」，中華民國運輸學會第十六屆學術論文研討會論文集，頁411-420。
【21】馮正民、邱裕鈞，2004，研究分析方法，建都文化事業股份有限公司，頁53-81&頁369-384。
【22】韓復華、卓裕仁，1996，「門檻接受法、噪音擾動法與搜尋空間平滑法在車輛路線問題之應用研究與比較分析」，運輸學刊第9卷第3期，頁113-144。
【23】Beimcorn, E.A., Peng, Z.R., Octania, S., & Zygowicz, R.J. 1999.Evaluation of the Benifuts of Automated Vehicle Location Systems in Small and Medium Sized Transit Agencies. Center for Urban Transportation Studies.
【24】Bell, W. J., Dalberto, L. M., Fisher, M. L., Greenfield, A. J., Jaikumar, R., Kedia, P., Mack, R. G. and Prutzman, P. J., 1983, “Improving the distribution of industrial gases with and on-line computerized routing and scheduling optimizer,” Interfaces, Vol.13, pp.4-23.
【25】Benyahia, I., Potvin, J. Y., 1995, “Decision Support for Vehicle Dispatching Using Genetic Progrmming,” Publication CRT-95-23, Centre de recherche sur les transports, Universite de Montreal, Montreal, Canada.
【26】Bodin, L., Golden, B., Assad, A. and Ball, M., 1983, “Routing and scheduling of vehicles and crews: the state of the art,” Computers and Operations Research, Vol.10, pp.63-211.
【27】Brown, G. G., Graves, G. W., 1981, “Real-time dispatch of petroleum tank trucks,” Management Science, Vol.27, No.1, pp.19-32.
【28】D.T. Pham and D. Karaboga, UK, 2000, “Intelligent Optimisation Techniques ” Springer.
【29】Fisher M. L. 1995. Vehicle Routing. Network Routing, Handbooks in Operation Research and Management Science, 8, 1-33.
【30】Glover, F., 1990, “Tabu search: A tutorial,” Interfaces, Vol.20, pp.74-94.
【31】Glover, F., 1990, “Tabu Search-Part Ⅱ” ORSA Journal on Computing, Vol.2, pp.4-32.
【32】Horbury, A.G., 1999. Using non-real-time Automatic Vehicle Location data to improve bus services. Transportation Research Part B. 33. pp.559-579.
【33】Ichoua, S., Gendreau, M., Potvin, J. Y., 2000, “Diversionissues in real-time vehicle dispatching,” TransportationScience, Vol.34, No.4, pp.426-438.
【34】Lin. S., 1965, “Computer Solutions of Traveling Salesman Problem” Bell System Tech. J., 44, pp.2245-2269.
【35】Madsen, B. G., Ravn, H. f. ahd Rygaard, J. M., 1995, “A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities and multiple objectives”, Annals of Operations Research, Vol.60, pp.193-208.
【36】Or, I., 1976, Traveling salesman-type Combinatorial Problems and Their Relation to the Logistics of Regional Blood Banking. Ph. D Dissertation, Northwestern University, Evanston, IL.
【37】Powell, W. B., Jaillet, P. and Odoni, A., 1995, “Stochastic and dynamic networks and routing,” in Network Routing, Handbooks in Operations Research and Management Science, Vol.8, eds. Ball M. O., Magnanti T. L., Monma C.L., and Nemhauser G. L., Vol.8, North Holland:Amsterdam.
【38】Psaraftis, H. N., 1988, “Dynamic vehicle routing problems”, in Vehicle Routing: Methods and Studies, eds. Golden B. L. and Assad A. A., North Holland: Amsterdam.
【39】Psaraftis, H. N., “Dynamic vehicle routing : Status and Prospects”, Annals of Operations Research, Vol.61, pp.143-164, 1995.
【40】Psaraftis, H. N., “Dynamic vehicle routing: Status and Prospects”, Annals of Operations Research, Vol.61, pp.143-164, 1995.
【41】Regan, A. C., Mahmassani, H. S., Jailiet, P., 1994,“Improving efficiency of commercial vehicle operations using real-time information: potential uses and assignment strategies,” Transportation Research Record, Vol.1493, pp.188-198.
【42】Shen, Y., Potvin, J. Y., 1995, “A Computer Assistant for Vehicle Dispatching with Learning Capabilities,” Annal Operations Research, Vol.61, pp.189-211.