https://scholars.lib.ntu.edu.tw/handle/123456789/81938
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor | 楊烽正 | en |
dc.contributor | 臺灣大學:工業工程學研究所 | zh_TW |
dc.contributor.author | 黃馨怡 | zh |
dc.contributor.author | Huang, Hsin-Yi | en |
dc.creator | 黃馨怡 | zh |
dc.creator | Huang, Hsin-Yi | en |
dc.date | 2006 | en |
dc.date.accessioned | 2007-11-26T01:09:46Z | - |
dc.date.accessioned | 2018-06-29T00:33:41Z | - |
dc.date.available | 2007-11-26T01:09:46Z | - |
dc.date.available | 2018-06-29T00:33:41Z | - |
dc.date.issued | 2006 | - |
dc.identifier | zh-TW | en |
dc.identifier.uri | http://ntur.lib.ntu.edu.tw//handle/246246/51231 | - |
dc.description.abstract | 隨著都會區點對點郵件遞送需求的遞增,具載貨量限制取卸貨途程的應用問題日益重要。本研究針對該問題提出數種有效的啟發式求解演算法,在短時間求得可以接受的較佳解。具載貨量限制的取卸貨途程問題較車輛途程問題多了一對一先取後卸和車輛載貨量的限制。求解目標是車行途程最短化。本研究提出五種啟發式解建構法和四種解改進法。解建構方法,係以逐步添加取、卸貨點的方式,在不違反限制條件下選取和插入建構中的途程。各種方法的差異,在選擇時是否有考量取或卸的屬性,在插入時則都須進行限制條件的驗證。改善法則仿車輛途程的局部修改法,在不違反限制的情況下進行解品質改善。據此,求解模式可分為先建構後改進二階段模式和建構與改進同步的單階段模式。前者是使用解建構法完成一可行車行途程再使用解改進法改善解品質。單階段的求解模式則是在解建構過程中,每加入一運貨點便進行已完成的局部路線改進。此外,具載貨量限制的取卸貨途程問題目前並無公用的標竿問題,本研究在不改變最佳途程的前提下,轉換TSP-LIB內已知最佳解的旅行推銷員問題成為具載貨量限制的取卸貨途程問題,以測試演算效率。結果顯示本研究所提的演算法可在短時間內,找到可以接受的較佳解。 | zh_TW |
dc.description.abstract | Due to the increasing of point-to-point parcel deliveries in metropolitan area, capacity constrained pickup and delivery vehicle routing problems become popular. This paper presents several algorithms and methods for constructing and improving solutions. Compared with traditional Vehicle Routing Problem, this problem has introduced a one-follow-one precedence constraint on the routing sequence and a vehicle capacity constraint along the routing. Customers are partitioned into a pickup and delivery ones and paired with a pickup and a delivery customer. A vehicle having a limited parcel capacity starts from a depot and visits each customer exactly once with each pickup customer visited before the delivery target customer. The objective is to minimize the route length. This research proposes five route constructing algorithms and four improving methods. In addition, two computation modes are presented to solve this problem using these algorithms and methods: 1) two-stage mode, constructing a route then improving it, and 2) single-stage mode, constructing and improving the route step by step. Benchmarks of TSP-LIB are adopted and converted into capacity constrained pickup and delivery vehicle routing problems without changing the optimum routing solutions. The proposed constructing algorithms and improving methods are crossly combined to establish various computation cases to solve the numerical problems. Results are compared for those proposed algorithms and methods and conclusions are addressed. | en |
dc.description.tableofcontents | 致謝 i 摘要 ii 英文摘要 iii 目錄 iv 圖目錄 vi 表目錄 viii 中英文名詞對照表 ix 第1章 緒論 1 1.1 研究背景和目的 1 1.2 研究目的 2 1.3 論文架構 3 第2章 文獻探討 4 2.1 旅行推銷員問題相關文獻 4 2.2 車輛途程問題相關文獻 13 2.3 文獻探討小結 16 第3章 具載貨量限制取卸貨途程問題的啟發式演算法 17 3.1 問題定義 17 3.1.1 基本假設 17 3.1.2 PDVRP數學模式 19 3.2 具載貨量限制取卸貨途程問題的求解架構 20 3.3 具載貨量限制取卸貨途程問題的啟發式演算法 22 3.3.1 建構階段 22 3.3.2 改進階段 46 第4章 演算法效能分析與驗證 63 4.1 測試範例題庫轉換 63 4.2 演算法效能分析 65 4.3 小結 70 第5章 結論與未來研究 71 5.1 結論 71 5.2 未來研究與建議 71 參考文獻 72 附錄A 74 | zh_TW |
dc.language | zh-TW | en |
dc.language.iso | en_US | - |
dc.subject | 旅行推銷員問題 | en |
dc.subject | 一對一取卸貨途程問題 | en |
dc.subject | Vehicle Routing Problem | en |
dc.subject | VRP | en |
dc.subject | TSP | en |
dc.subject | Pickup and delivery Vehicle Routing Problem | en |
dc.subject | PDVRP | en |
dc.title | 具載貨量限制取卸貨途程問題的啟發式演算法 | zh |
dc.title | Heuristic Algorithms for Capacity constrained Pickup and Delivery Vehicle Routing Problems | en |
dc.type | thesis | en |
dc.relation.reference | 1.張振邦,2004,兼營宅配業務之快遞業車輛路線規劃問題,南台科技大學行銷與流通管理研究所碩士論文 2.許競嘉,2003,宅配業貨物配送路線規劃問題之研究,國立成功大學交通管理科學研究所碩士論文 3.Nagy, G. and Salhi, S., “Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries,” European Journal of Operation Research, Vol. 162, pp.126-141, 2005. 4.Hernández-Pérez, H. and Salazar-González, J., “A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery,” Discrete Applied Mathematics, Vol. 145, pp.126-139, 2004. 5.Bruun, A., Worsoe, U., and Pagh, M.H., “Traveling salesman with pickup and delivery”, technical report, 2003. 6.Renaud, J., Boctor, F. F. and Laporte, G., “Perturbation heuristics for the pickup and delivery traveling salesman problem,” Computers and Operations Research, Vol.29, pp.1129-1141, 2002. 7.Renaud, J., Boctor, F. F. and Ouenniche, J., “A heuristic for the pickup and delivery traveling salesman problem,” Computers and Operations Research, Vol.27, pp.905-916, 2000. 8.Swihart, M. R. and Papastavrou, J. D., “A stochastic and dynamic model for the single-vehicle pick-up and delivery problem,” European Journal of Operational Research, Vol.114, pp.447-464, 1999. 9.Gendreau, M., Laporte, G. and Vigo, D., “Heuristics for the traveling salesman problem with pickup and delivery,” Computers and Operations Research, Vol.26, No.7, pp.699-714, 1999. 10.Gendreau, M., Hertz, A. and Laporte, G., “The traveling salesman problem with backhauls,” Computers and Operations Research, Vol.23, No.5, pp.501-508, 1996. 11.Hall, R. W. “Pickup and delivery systems for overnight carriers,” Transportation Research Part A: Policy and Practice, Vol.30, No.3, pp.173-187, 1996. 12.Mosheiov, G., “The traveling salesman problem with pick-up and delivery,” European Journal of Operational Research, pp.299-310, 1994. 13.Anily, S. and Mosheiov, G., “The traveling salesman problem with delivery and backhauls,” Operations Research Letters, Vol. 16, pp.11-18, 1994. 14.Golden, B., Bodin, L., Doyle, T., and W. S. Jr. “Approximate traveling salesman algorithms,” Operations Research, Vol.28, No.3, pp.694-711, 1980. 15.Rozenkrantz, D., Stearns, R. and Lewis, P. “Approximate Algorithms for the traveling Salesman Problem,” Proceedings of the 15th Annual IEEE Symposium of Switching and Automata Theory, pp.33-42. 16.Flood, M. M., “The Traveling Salesman Problem,” Operations Research, Vol.4, pp.61-75, 1955. 17.TSPLIB標竿問題參考網址http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/index.html | zh_TW |
item.grantfulltext | none | - |
item.languageiso639-1 | en_US | - |
item.fulltext | no fulltext | - |
item.openairetype | thesis | - |
item.cerifentitytype | Publications | - |
item.openairecristype | http://purl.org/coar/resource_type/c_46ec | - |
顯示於: | 工業工程學研究所 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。