完整後設資料紀錄
DC 欄位語言
dc.contributor.author葉珮婷en_US
dc.contributor.authorYeh, Pei-Tingen_US
dc.contributor.author王晉元en_US
dc.contributor.authorWang, Jin-Yuanen_US
dc.date.accessioned2014-12-12T01:31:27Z-
dc.date.available2014-12-12T01:31:27Z-
dc.date.issued2008en_US
dc.identifier.urihttp://140.113.39.130/cdrfb3/record/nctu/#GT079632502en_US
dc.identifier.urihttp://hdl.handle.net/11536/42816-
dc.description.abstract本研究目的為替貨運業之預先派遣作業產生具有效率的路線,除了須考量路徑成本外,尚需考量貨運業收送貨之特性,包含優先限制、聯結限制、時間窗限制與車容量限制。本研究將有時間窗限制的收送貨問題(Pickup and Delivery Problem with Time Windows, PDPTW)建構為一集合分割問題,並提出兩套以變數產生法(Column Generation)為基礎的演算法求解。此兩套演算法皆以變數產生法、分支定限法與解決重覆涵蓋問題之啟發式解法三大部分所組成,兩套演算法不同之處在於變數產生法之求解子問題演算法。本研究將子問題設計為考慮有時間窗限制收送貨特性之最短路徑問題,第一套演算法之子問題使用修正後的Dijkstra’s 演算法與啟發式解法求解;第二套演算法之子問題使用修正後之Label Correcting 演算法求解。 測試結果發現第一套演算法與第二套演算法於小例題測試範例之求解績效誤差在5%內,但使用第一套演算法之求解時間遠較第二套演算法快。本研究將第一套演算法求解子問題時之啟發式演算法分為三種組合方式,測試結果發現三種組合方式對於平均旅行成本在小範圍時間窗客戶群與同一客戶大小有顯著差異;三種組合方式對於平均車輛數僅在LR2客戶類型無顯著差異,在其餘客戶類型與同一客戶大小皆有顯著差異;三種組合方式對於不包含分支定限法之平均求解時間皆為第三種組合最快。由測試結果可知使用第一套演算法且子問題啟發式演算法使用第二種組合方式能在較快速之運算時間內求得不錯的路徑組合。zh_TW
dc.description.abstractPickup and delivery problem with time windows (PDPTW) is an important and fundamental problem for many logistic service providers. We first formulate this problem as a set-partitioning problem. Two column generation based algorithms are proposed for solving this model. Both algorithms consist of three phases: column generation, branch-and-bound, and heuristic local search. The column generation subproblem is formulated as a shortest path problem with multiple side constraints. The major differences between these two algorithms are the adopted solution techniques. The first algorithm is based on the traditional Dijkstra’s algorithm and the second algorithm is basically a modified Label Correcting. We use benchmark testing problems to evaluate the performance of these two algorithms. Numerical experiments show that the proposed algorithms can find near optimal solution for smaller test problems, and the second algorithm could get better solutions efficiently on large test problems generalized from benchmark problems in the literature.en_US
dc.language.isozh_TWen_US
dc.subject有時間窗限制的收送貨問題zh_TW
dc.subject集合分割問題zh_TW
dc.subject變數產生法zh_TW
dc.subjectPDPTWen_US
dc.subjectset-partitioning problemen_US
dc.subjectColumn Generationen_US
dc.title應用變數產生法求解有時間窗限制的收送貨問題zh_TW
dc.titleA Column Generation Approach for the Pickup and Delivery Problem with Time Windowsen_US
dc.typeThesisen_US
dc.contributor.department運輸與物流管理學系zh_TW
顯示於類別:畢業論文


文件中的檔案:

  1. 250201.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。