含時窗限制式卡車與拖車途程問題之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：14

、訪客IP：3.144.252.197

姓名

劉建宏(Chien-Hung Liu) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

含時窗限制式卡車與拖車途程問題之研究
(Truck and Trailer Routing Problem with Time Window)

相關論文

★ 圖書館系統通閱移送書籍之車輛途程問題	★ 起迄對旅行時間目標下高速公路匝道儀控之研究
★ 結合限制規劃法與螞蟻演算法求解運動排程問題	★ 共同邊界資料包絡分析法在運輸業之應用-以國內航線之經營效率為例
★ 雙北市公車乘客知覺服務品質、知覺價值、滿意度、行為意向路線與乘客之跨層次中介效果與調節式中介效果	★ Investigating the influential factors of public bicycle system and cyclist heterogeneity
★ A Mixed Integer Programming Formulation for the Three-Dimensional Unit Load Device Packing Problem	★ 高速公路旅行時間預測之研究--函數資料分析之應用
★ Behavior Intention and its Influential Factors for Motorcycle Express Service	★ Inferring transportation modes (bus or vehicle) from mobile phone data using support vector machine and deep neural network.
★ 混合羅吉特模型於運具選擇之應用-以中央大學到桃園高鐵站為例	★ Preprocessing of mobile phone signal data for vehicle mode identification using map-matching technique
★ 含額外限制式動態用路人均衡模型之研究	★ 動態起迄旅次矩陣推估模型之研究
★ 動態號誌時制控制模型求解演算法之研究	★ 不同決策變數下動態用路人均衡路徑選擇模型之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

卡車與拖車途程問題(Truck and Trailer Routing Problem, TTRP)是傳統車輛途程問題(Vehicle Routing Problem, VRP)的一種衍生性問題，此類問題的特性在於車輛可以卡車或整車(卡車附掛拖車)兩種不同的車輛型態服務不同可及性的顧客，而兼顧高車容量以及機動性的特點。
而在配送問題中，準時一向是業者與顧客皆重視的課題，輔以近年來宅配業、貨運業者服務的範圍更擴大至食品以及其他的易腐性商品，準時與效率更顯重要，因此本研究增加考量了顧客的時間限制，構建出包含時窗限制的卡車與拖車路線問題(Truck and Trailer Routing Problem with Time Window, TTRPTW)，並提出啟發式的求解架構。最後以Solomon的標準測試題庫為基礎設計17題TTRPTW的測試例題作測試分析。

摘要(英)

The Truck and Trailer Routing Problem (TTRP) is a variant of the Vehicle Routing Problem (VRP). The problem extends the basic VRP to take a real-life application into account. In the TTRP, customers can be serviced by a truck alone or a vehicle (a truck pulling a trailer), therefore there are three types of routes in a solution to the TTRP: a pure truck route, a pure vehicle route, and a complete vehicle route which includes the vehicle route and the sub-tours serviced by a truck alone.
This research extends TTRP to consider time window constraint, and defines the Truck and Trailer Routing Problem with Time Window (TTRPTW). This research also applies a heuristic to solve the TTRPTW and test on 17 problems which were designed based on Solomon’s standard VRPTW problems.

關鍵字(中)

★ 車輛途程問題
★ 卡車與拖車途程問題
★ 時窗限制

關鍵字(英)

★ truck and trailer routing problem
★ vehicle routing problem
★ time window

論文目次

摘要 i
Abstract ii
誌謝 iii
目錄 v
圖目錄 viii
表目錄 x
第一章緒論 1
1.1 研究背景與動機 1
1.2 研究範圍與假設 3
1.2.1 研究內容 3
1.2.2 研究假設 4
1.3 研究內容與流程 6
第二章文獻回顧 8
2.1 車輛途程問題與相關問題 8
2.2 含時窗限制式之車輛途程問題 11
2.2.1 時窗的種類 11
2.2.2 含時窗限制之車輛途程問題之求解方法 13
2.3 卡車與拖車途程相關問題 18
2.4 小結 22
第三章模型構建 23
3.1 TTRPTW問題 23
3.2 TTRPTW模型構建 24
3.2.1 符號說明 25
3.2.2 數學模型 27
第四章求解演算法 35
4.1 TTRPTW求解特性之探討 36
4.2 構建起始途程模組 38
4.2.1 構建整車路線階段 39
4.2.1.1 構建整車起始路線方法A 40
4.2.1.2 構建整車起始路線方法B 41
4.2.2 構建卡車子路線階段 42
4.2.3 構建卡車路線構建階段 43
4.2.3.1構建卡車起始路線方法A 43
4.2.3.2構建卡車起始路線方法B 43
4.3 改善途程模組 44
4.3.1 路線內改善交換過程 45
4.3.2 路線間改善交換過程 48
4.3.2.1 同種路線間改善交換過程 48
4.3.2.2 異種路線間改善交換過程 53
4.3.3 拖車停放點交換改善過程 56
第五章 TTRPTW範例測試與分析 59
5.1 TTRPTW測試例題建立 59
5.2 TTRPTW範例測試 61
5.3 不同規模之TTRPTW問題測試 65
5.4 小結 67
第六章結論與建議 68
6.1 結論 68
6.2 建議 69
參考文獻 70

參考文獻

參考文獻
[1] 邱穀交通工程事務所(2000)，公路車輛行車成本調查，交通部運輸研究所委託辦理，中華民國八十九年一月。
[2] 郭國基，林文彬(1996)，我國流通業通路變革之實證研究，1996年國際商業物流管理研討會，pp. 564-581，台北。
[3] 吳志仁(2003)，(指導教授：韓復華)，一般化卡車拖車路線問題，國立交通大學運輸科技與管理學系碩士論文，新竹。
[4] 卓裕仁(2001)，(指導教授：韓復華)，以巨集啟發式解法求解多車種與週期性車輛路線問題之研究，國立交通大學運輸科技與管理學系博士論文，新竹。
[5] 易德華(1998)，(指導教授：陳惠國)，軟時窗車輛巡迴問題之研究，國立中央大學土木工程研究所碩士論文，中壢。
[6] 梅明德(1999)，(指導教授：謝浩明)，線上型時窗限制車輛路線問題之模式與求解演算法，國立中央大學土木工程研究所博士論文，中壢。
[7] 劉金維(2002)，(指導教授，謝浩明)，依時性路段暨時窗限制下單ㄧ車輛路線問題之研究，國立中央大學土木工程研究所博士論文，中壢。
[8] 洪仲林(2001)，(指導教授，張美香)，含時窗限制之動態需求車輛途程規劃問題，私立中華大學經營管理研究所碩士論文，新竹。
[9] Battiti, Roberto, Tecchiolli, Giampietro (1994), “The Reactive Tabu Search,” ORSA Journal on Computing, Vol. 6, pp. 126-140.
[10] Bodin, L., Golden, B., Assad, A., and Ball, M. (1983), “Routing and Scheduling of Vehicle and Crews: the State of the Art,” Special Issue of Computer & Operations Research, Vol. 10, No.2, pp. 63-211.
[11] Brailsford, S.C., Potts, C.N., and Smith, B.M. (1999), “Constraint Satisfaction Problem: Algorithms and Applications,” European Journal of Operational Research, Vol. 119, pp. 557-581.
[12] Carlton, W.B., Barnes, J.W. (1996), “Solving the Traveling Salesman Problem for the Vehicle Routing Problem with Time Windows,” Operations Research, Vol. 40, pp. 342-354.
[13] Chao, I. M. (2002) “A Tabu Search Method for the Truck and Trailer Routing Problem,” Computers and Operations Research, Vol. 29, pp. 31-51.
[14] Christofides, N., Mingozzi, A. and Toth, P. (1979), “The Vehicle Routing Problem,” Combinatorial Optimization, pp. 315-338.
[15] Clarke, G. and Wright, J.W. (1964), “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Operations Research, Vol. 12, No. 4, pp. 568-581.
[16] Dantzig, G.B. and Ramser R.H. (1959), “The Truck Dispatching Problem,” Management Science, Vol. 6, pp. 80–91.
[17] Dueck, G. and Scheuer, T. (1990), “Threshold Accepting – A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing,” Journal of Computational Physics, Vol. 90, pp. 161-175.
[18] Fisher, M. and Jaikumar, R. (1981), “A Generalized Assignment Heuristic for Vehicle Routing,” Networks, Vol. 11, pp. 109-124.
[19] Garey, M.R., and Johnson, D.S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, USA.
[20] Gerdessen, J. C. (1996), “Vehicle Routing Problem with Trailers,” European Journal of Operational Research, Vol. 93, pp. 135-147.
[21] Gillett, B. and Miller, L. (1974), “A Heuristic Algorithm for the Vehicle Dispatch Problem,” Operations Research, Vol. 22, pp. 340-349.
[22] Glover, F. (1977), “Heuristics for Integer Programming Using Surrogate Constraints,” Decision Science, Vol. 8, pp. 156-166.
[23] Golden, B.L., Magnanti, T.L. and Nguyen, H.Q. (1977), “Implement Vehicle Routing Algorithms,” Networks, Vol. 7, pp. 113-148.
[24] Golden, B., Wasil, E., Kelly, J., and Chao, I.M. (1998), “The Impact of Metaheuristics on Solving the Vehicle Routing Problem: Algorithms, Problem Sets, and Computational Results,” Fleet Management and Logistics, Crainic T., and Laporte G., eds., Liuwer Academic Publishers, Netherlands, pp.33-56.
[25] Held, M. and Karp, R. (1971), “The Traveling Salesman Problem and Minimum Spanning Trees Part II,” Mathematical Programming, Vol. 1, pp. 6-25.
[26] Holland, J. H. (1973), “Genetic Algorithms and the Optimal Allocations of Trials,” SIAM Journal of Computing, Vol. 2, pp. 88-105.
[27] Murty, K. G. Karel, C. and Little J. D. C. (1963), “An Algorithm for the Traveling Salesman Problem,” Operations Research, Vol. 11, pp. 972-989.
[28] Laporte, G., Nobert, Y., (1987), “Exact algorithms for the vehicle routing problem,” Surveys in Combinatorial Optimization, Vol. 31, pp. 147-184.
[29] Laporte, G. (1992), “The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms,” European Journal of Operational Research, Vol. 59, pp. 345-358.
[30] Lin, S. and Kernighan, B. (1973), “An Effective Heuristic Algorithm for the Traveling Salesman Problem,” Operations Research, Vol. 21, pp. 498-516.
[31] Miller, C.E. (1960), “Integer Programming Formulation of Traveling Salesman Problem,” Journal of Association for Computing Machinery, Vol.7, pp.326-329.
[32] Mole, R.H. and Jameson, S.R. (1976), “A Sequential Route-Building Algorithm Employing Generalized Saving Criterion,” Operation Research Quarterly, Vol. 27, pp. 503-527.
[33] Nemhauser, G.L. and Rinnooy Kan, A.H.G. (1995), Handbooks in Operations Research and Management Science (Volume 8), North-Holland, Inc. Netherlands.
[34] Or, I. (1976), Traveling Salesman-Type Combinatorial Problems and their Relation to the Logistics of Blood Banking. Ph.D. Thesis, Department of Industrial Engineering and Management Science, Northwestern University, Evanston, IL., USA
[35] Osman, I.H. (1993), “Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem,” Annals of Operations Research, Vol. 41, pp. 421-451.
[36] Potvin, J.Y., Kervahut, T., Garcia, B.L., and Rousseau, J.M. (1996), “The Vehicle Routing Problem with Time Windows Part I: Tabu Search,” INFORMS Journal on Computing, Vol. 8, No. 2, pp.158-164.
[37] Psaraftis, H.N. (1998), “Dynamic Vehicle Routing Problem,” In Vehicle Routing: Methods and Studies, Golden B.L., and Assad A.A. eds., North-Holland, Amsterdam, pp. 223-248.
[38] Solomon, M.M. (1987), “Algorithms for the Vehicle Routing and Scheduling Problem with Time Window Constraints,” Operations Research, Vol. 35, No.2, pp. 254-265.
[39] Solomon, M.M. Baker, E.K. and Schaffer, J.R. (1988), “Vehicle Routing and Scheduling Problems with Time Window Constraints: Efficient Implementations of Solution Improvement Procedures,” In Golden, B.L. and Assad, A.A. (Eds), Vehicle Routing: Methods and Studies, Elsevier Science Publishers, Amsterdam, pp. 170-186.

指導教授

陳惠國(Huey-Kuo Chen)

審核日期

2005-7-22

推文