跳到主要內容

臺灣博碩士論文加值系統

(3.238.225.8) 您好!臺灣時間:2022/08/09 01:13
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:謝伯昂
論文名稱:考慮收送貨與選擇貨運公司服務的車輛途程問題
指導教授:朱經武 
學位類別:碩士
校院名稱:國立海洋大學
系所名稱:航運管理學系
學門:運輸服務學門
學類:運輸管理學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:68
中文關鍵詞:啟發解最適解零擔禁忌搜尋
外文關鍵詞:Heuristic algorithmoptional solutions  less-than-truckloadTabu Search
相關次數:
  • 被引用被引用:7
  • 點閱點閱:197
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1
 運銷管理者所面臨的決策問題很多,如何選擇一合適的運輸方式或業者運送貨物對運銷管理而言,是一很重要的決策,因為運輸成本在運銷各項成本中所佔之比例最高。
 基本上有兩種運輸方式可供業者選擇,一種是以自有車隊運送,另者是以貨運公司運送。以自有車隊運送,運銷管理者需要決定的是合併那些運送在同一車和規劃運送路線。
 以貨運公司運送,貨運公司,負責規劃每次從運送地至目的地的路線,運銷管理者只需將貨物交與給他們即可。市場上常見的新竹貨運、與大榮貨運屬於上述情形。
 於實際生活中,因需求具不確定性之特性,所以當需求大於業者本身車隊容量時,業者必須考慮將過剩的需求委託給貨運公司運送;當需求小於業者本身車隊容量時,則自行規劃以自有車隊運送即可。
 本研究主要目的為構建一同時考慮收送貨與選擇貨運公司的數學模式與啟發式演算法,協助運銷管理者解決問題,但因配送車輛途程問題具有NP-hard的性質,由本研究發展的整數規劃求解此問題,雖然可獲得最佳解,但是相當耗費人力與時間,僅適用於小型問題。而本研究的啟發式演算法,於15個測試範例中均能十分快速獲得,就求解效率而言相當優異,在精準度方面,演算之平均誤差均為12%以內尚可接受。
 基於本研究之改良式節省演算法,若再結合禁忌搜尋、大洪水或門檻接受法產生新的演算法應可提供更佳的精確度。
Selecting the right mode to transport a shipment is an important decision to a logistics manager. Because transportation costs mount for a large portion of the average sales dollars.
Logistics managers can make a selection between a truckload (a private vehicle) and less-than-truckload carrier. A private vehicle allows a company to consolidate several shipments, going to different destinations, in a single vehicle.
A less-than-truckload carrier usually handles each of a company’s shipments independently and assumes the responsibility for routing each shipment from origin to destination.
In reality, we are facing the uncertainty of demand. When the demands are greater than the whole vehicle capacity, the logistics managers may consider to use an outsider carrier.
The main purpose of this study is to develop both mathematical model and the Heuristic algorithm for solving the delivery and pickup vehicle routing and the selection of less-than-truckload carriers. Some computational results are presented. Our Heuristic algorithm, obtains the optional or near-optional solutions in an efficient way in terms of time.
As for future research, Searching algorithms, such as Tabu Search、The Great Deluge and Threshold Acceptance, should be incorporated into our algorithm to provide better results.
謝辭 I
摘要 II
Abstract III
目錄 V
表目錄 IX
圖目錄 X
第一章 緒 論 1
1.1研究動機與目的 1
1.2 研究問題的探討 2
1.3研究方法 3
1.4研究內容與項目 4
第二章 配送車輛途程問題文獻探討 6
2.1配送車輛途程問題之定義與分類 6
2.1.1車輛途程問題型態 9
2.1.2網枝途程問題 10
2.1.3節點途程問題 12
2.2收送貨( Pickup and Delivery )車輛途程問題的文獻 15
2.2.1 收貨與送貨的車輛排程問題(PDP) 16
2.2.2 時窗限制車輛途程問題(VRPTW) 16
2.2.3 回程收貨的車輛排程問題(VRPB) 18
2.2.4收送貨一併解決問題 20
2.3配送車輛送程問題求解策略之探討 21
2.3.1先分群再排路徑 22
2.3.2先排路線再分群 22
2.3.3節省法或插入法 22
2.3.4改善和交換 23
2.3.5數學規劃法 23
2.3.6人機互動法 24
2.3.7最佳解法 24
2.4 配送車輛途程問題之最佳解法 25
2.4.1分支界限法 25
2.4.2整數規劃法 26
2.4.3動態規劃法 27
2.5配送車輛途程問題之啟發式解法 27
2.5.1 節省法 28
2.5.2 插入法 31
2.5.3修正節省法 32
2.5.4 萬用啟發法 33
第三章模式之構建 35
3.1最佳法---整數規劃法 35
3.1.1基本假設 35
3.1.2符號定義 36
3.1.3數學模式 36
3.2 啟發式演算法---修正節省法 38
3.2.1節省法 38
3.2.2途程內改善 41
3.2.3途程間改善 43
3.2.4改良節省法 46
第四章範例說明 48
4.1 測試例題之蒐集與說明 48
4.2 求解結果 49
第五章結論與建議 56
5.1 結論 56
5.2建議 57
參考文獻 58
中文部份 58
英文部份 58
附錄 64
中文部份
1、吳淵齊,物流中心運輸成本及短缺罰金之最佳化模式,國立雲林技術學院工業工程與管理技術研究所碩士論文,民國84年。
2、莊志諒,配送網路之設計研究,國立交通大學交通運輸研究所,碩士論文,民國77年6月。
3、陳正元,節省法與路線間交換改善法在車輛路線問題(VRP)上之應用,國立交通大學,土木工程研究所碩士論文,民國81年6月。
4、陳昭堯,石油產品最適儲運體系之研究,交大交研所碩士論文,76年6月。
5、蘇義雄、張學孔,網枝途程問題之設定與求解,運輸計畫季刊,第22卷第2 期,P139-166,民國82年。
6、廖忠雄,物流中心運輸服務途程規劃,國立台灣大學工業工程研究所碩士論文,民國83年。
英文部份
【1】Bodin, L. and Golden, B., Assad, A. and Bull, D., “Routing and Scheduling of Vehicles and Scheduling of Vehicles and Crews : The States of The Art,” Comp. Oper. Res ., Vol. 10, No. 2, 63-211(1983).
【2】Bodin, L. and Berman, L., “Routing and Scheduling of School Buses by Computer,” Transportation Science, Vol. 13, No. 2, 113-129(1979).
【3】Baker, E.K. and J.R. Schaffer, “Solution Improvement Heuristics for the Vehicle Routing and Scheduling Problem with Time Window Constrations ,” American Journal of Mathematical and Management Sciences, 6(3,4), 261-300(1986).
【4】Bramel, J. and SimchiLevi, D., “On the Effectiveness of Set Covering Formulations for the Vehicle Routing Problem with Time Windows,” Operations Research, 45, 295-301(1997).
【5】Badeau, P., Guertin, F., Gendreau, M., Potvin, Jean-Yves and Tailard, E., “A Parallel Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows,” Transportation Research, 5(2), 109-122 (1997).
【6】Bodin, L. and Golden, B., Assad, A. and Bull, D., “Routing and Scheduling of Vehicles and Scheduling of Vehicles and Crews: The States of The Art,” Computers Operations Research, Vol.10, No.2, 63-211 (1983).
【7】Bodin, L. and Berman, L., “Routing and Scheduling of School Buses by Computer,” Transportation Science, Vol. 13, No. 2, 113-129(1979).
【8】Bodin, L. and Sexton, T., “The Subscriber Dial-A-Ride Problem,” Final Report, V.S. Department of Transportation, Urban Mass Transportation Administration, Washington D.C.(1979).
【9】Bellman, R., “Dynamic Programming Treatment of the Traveling Salesman Problem,” Vol. 19, 61-63(1962).
【10】Clarke, G. and Wright, W., “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Oper. Res., Vol. 12, 569-581 (1964).
【11】Chen, X., and Wan, W., and Xu, X., “ Modeling Rolling Batch Planning as Vehicle Routing Problem with Time Windows,” Computers Operations Research, 25(12), 1127-1136(1998).
【12】Casco , D., and Golden, B. and Wasil, E., “Vehicle routing with backhauls: models algorithm and case-studies .In Vehicle Routing: Methods and Studies,” wd. B. Golden, A. Assad, A. Assad , Studies in Management Science and Systems , Vol.16, North Holland, Amsterdam(1988).
【13】Clarke, G. and Wright, W., “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Operations Research, Vol. 12, 569-581(1964).
【14】Christofides, N., and Eilon S., “An Algorithm for The Vehicle Dispatching Problem,” Operations Research Question, Vol. 20, 309-318 (1969).
【15】Christofides, N., “Exact Algorithms for The Vehicles Routing Problems, Based on Spanning Tree and Shortest Path Relaxations,” Math. Prog., Vol. 20, 255-282(1981).
【16】Cullen, F., Jarvis, J. and Ratiliff, H., “Set Partitioning Based Heuristics for Interactive Routing,” Network, Vol. 11, 125-144(1981).
【17】Clark, G. and J. W. Wright, “Scheduling of Vehicles from a central depot to a number of delivery points,” Operations Research, Vol. 12, 568-581(1964).
【18】Dumas, Y., and Desrosiers, J.and Soumis, F., “The Pickup and Delivery Problem with Time Windows,” European Journal of Operation Research, Vol. 54, 7-22(1991).
【19】Desrochers, M., and Desrosiers, J. and Solomon, M., “A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows,” Operations Research, 40, 342-354(1992).
【20】Duhamel, C., and Potvin, J.Y. and Rousseau, J.M., “ A Tabu Search Heuristic for Vehicle Routing Problem with Backhauls and Time Windows,” Transportation Science, 31, 49-59(1997).
【21】Dantzig, G., Fulkerson, R., and Johnson, S., “Solution of A Large-scale Traveling-Salesman Problem,” Operations Research, Vol. 2, 393-410(1954).
【22】Flood, M.M., “The Traveling Salesman Problem,” Operation Research,Vol.4, 61-75(1955).
【23】Fisher, M.L. and Jornsten, K.O. and Madsen, O.B.G., “Vehicle Routing with Time Windows :Two Optimization Algorithms ,” Operations Research, 45, 488-492(1997).
【24】Fahrion, R. and Wrede, M., “On a Principle of Chain-Exchange for Vehicle-Routing Problems (1-VRP),” Journals of Operations Research Society, Vol. 41, No. 9, 821-827(1990).
【25】Golden, B.L. and Assad, A.A., “In Vehicle Routing: Methods and Studies. Studies in Management Science and Systems,” Vol. 16. North Holland , Amsterdam, (1988).
【26】Golden, E.B., and Alfaro, J. and Schagger, J., “The Vehicle Routing Problem with Backhauling :Two Approaches,” Proceedings of the XII Annual Meeting of S.E.TIMS, Myrtle Beach, S.C, 90-92(1985).
【27】Gillett, B. and Miller. L, “ A heuristic algorithm for the vehicle dispatch problem, ” Operations Research 22, pp. 340-349 (1974).
【28】Golden, B., et al., “The Fleet Size and Mix Vehicle Routing Program,” Computer and Operations Research, Vol. 11, No. 1, 49-66(1994).
【29】Golden, B., Assad, A., and Arjang, A., “Vehicle Routing: Methods and Studies, North-Holland,” 7-45(1988).
【30】Glover, F., “Heuristic for Integer Programming Using Surrogate Constraints,” Decision Science, 8, 156-166(1977).
【31】Golden, B. L. and Bodin, L., “Microcomputer-Based Vehicle Routing and Scheduling Software,” Computers&Operations Research, 13(2), 277-285(1986).
【32】Held, M. and Karp, R.M., “A dynamic programming approach to sequencing problems,” Journal of Society Industrial and Applied Mathmatics,Vol.10, 196-210(1962).
【33】Held, M. and Karp, R., “A Dynamic Programming Approach to Sequencing Problem,” SIAM Journal Applied Mathematics, Vol. 10, pp. 196-210(1962).
【34】Held, M. and R. Karp, 1970, “The Traveling Salesman Problem and Minimum Spanning Trees,” Operations Research, Vol. 18,1138-1162(1970).
【35】Held, M. and Karp, R., “The Traveling-Saleman Problem and Minimun Spaning Trees, ” Oper. Res., Vol. 18, 1138-1162(1970).
【36】 Jacques Renaud, Gilbert Laporte and fayez F. Boctor. “A Tabu Search Heuristic for the Multi-Depot Vehicle Routing Problem,” Vol. 23, 229-235(1996).
【37】Karp, R., “Reducibility Among Combinatorial Problems,” in Complexity of Computer Computations, 85-104(1972).
【38】Koskosidis, I.A., “Optimization Based Models and Algorithms for Routing Civil Engineering and Operations Research ,” Ph.D. Dissertation, Dept. of Civil Engineering and Operations Research, University of Princetion(1988).
【39】Krolak, P., Felts, W., and Marble, G., “A Man Machine Approach Toward Solving The Traveling-Saleman Problem,” CACM, Vol. 14, 327-334(1971).
【40】Koskosidis, Y. A., Powell, W. B. and Solomon, M. M., “An Optimization-based Heuristic for Vehicle Routing and Scheduling with Soft Time Windows Constraints,” Transportation Science, Vol. 26(2), 69-85(1992).
【41】Lin, S., “Computer Solution of the Traveling salesman Problem,” The Bell Technical Journal, Vol. 44,2245-2269(1965).
【42】Laporte, G., Nobert,Y. and Desrochers, M., “Optimal Routing Under Capacity and Distance Restriction, ” Operations Research, Vol. 33, 1015-1073(1985).
【43】Laporte, G. and Y. Nobert, “Exact Algorithms for the Vehicle Routing Problem,” Surveys in Combinatorial Optimization, 147-184(1987).
【44】Little, J. et al., “An Algorithm for the Traveling Salesman Problem,” Operations Research, Vol. 11, 972-989(1963)
【45】Lin, S. and Kernighan, B. “An Effective Heuristic Algorithm for The Traveling Salesmen Problem, ” Operations Research, Vol. 21, 498-516(1973).
【46】Miroslaw, M., and Mohan, G., and Mihir, P., “Serial and parallel simulated annealing and tabu search algorithms for the Traveling Salesman Problem,” Annals of Operations Research, Vol. 21, 59-84(1989).
【47】Mole, R. and Jameson, S., “A Sequential Route-Building Algorithm Employing A Generalized Savings Criterion,” Operations Research Q., Vol. 27, 503-511(1976).
【48】Miller, C.E., et al., “Integer Programming Formulation of Traveling Salesman Problem,” Journal of Association for Computing Machinery, Vol. 7, 326-329(1960).
【49】Potvin, J. Y. and Rousseau, “A Parallel Route Building Algorithm for the Vehicle Routing and Scheduling Problem with Time Windows,” European Journal of Operational Research, 66, 331-340(1993).
【50】 Quinn, M. J., Parallel Computing: Theory and Practice, 2nd. Ed., McGraw-Hill, inc.,(1994).
【51】Solomon , M.M., “On the Worst-Case Performance of Some Heuristics for the Vehicle Routing and Scheduling Problem with Windows Constraints,” Networks,16,161-174(1986).
【52】Sutcliffe , C. and Board J., “Optimal Solution of a Vehicle-routing Problem : Transporting Mentally Handicapped adults to an Adult Training Center ,” Journal of Operational Research Society, 14(1), 61-67(1990).
【53】Sateesh, C. and Pradip, K., “ Vehicle Routing in Large Organizations: a Case Study, ” International Journal of Operations & Production Management, Vol. 12, No. 3, 71-78(1991).
【54】Stewart, W. and Golden, B., “A Vehicle Routing Algorithm Based on Generalized Lagrange Mutipliers,” Proceedings of The AIDS 1979 Annual Convention, Moore, L., Monore,K., Taylor B. Eds., New Orleans, LA, Vol. 2, 108-110(1979).
【55】Thangiah, S.R., Potvin, Jean.-Yves and Sun, T., “Heuristic Approaches to Vehicle Routing with Backhauls and Time Windows,” Computers Operations Research, 23, 1043-1057(1996).
【56】Vigo, D., “A Heuristic Algorithm for the Asymmetric Capacitated Vehicle Routing Problem,” European Journal of Operational Research, 89, 108-126(1996).
【57】Vliet, A. V., and Kan, C. G., “Interactive Optimization of Bulk Sugar Deliveries,” Interface, Vol. 22(3), 4-14(1992).
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊