:::
博碩士論文
| 論文名稱 | 針對分割配送相關車輛路線問題特性設計之多重起點啟發式方法與其應用 |
|---|---|
| 年別 | 106 |
| 學位 | 博士 |
| 學校系所 | 交通大學運輸與物流管理學系 |
| 作者 | 朱佑旌 |
| 指導教授 | 韓復華、卓裕仁 |
| 論文摘要 | 分割配送車輛路線問題(Split Delivery Vehicle Routing Problem, SDVRP) 允許單一顧客的需求可分批被多部車輛服務;它是傳統車輛路線問題的衍生問題。由於配送限制的放鬆，SDVRP具有降低運輸成本的效益，進可提昇企業之競爭力。但就實務而言，需求分割配送會造成顧客的不便，亦伴隨作業成本的增加。有鑑於此，如何使SDVRP兼顧成本效率與服務品質是一重要議題。近年已有文獻(Gulczynskiet al.[29]) 將最小配送量列入考慮，提出最小配送量限制之分割配送車輛路線問題(SDVRP with Minimum Delivery Amounts, SDVRR-MDA)。本研究則首次提出以配送次數作為限制的「具配送次數限制的分割配送車輛路線問題」(SDVRP with Limited Number of Deliveries, SDVRP-LND)，以期分割配送能有更高的應用價值。 針對分割問題特性，本研究提出一套一體適用於求解SDVRP，SDVRP-MDA與SDVRP-LND的多重起點啟發式解法，稱為SRC+IMP (Split-delivery Route Construction + solution IMProvement)。SRC為起始解構建模組，適應性地選擇「插入路線」或是「新增路線」的方式逐點構建起始路線。IMP為多鄰域求解改善模組，其中包含一套針對分割問題特性新設計的驅逐鏈鄰域搜尋法。整個演算法SRC+IMP則採用多重起點策略整合SRC與IMP以兼顧搜尋的深度與廣度。 SRC+IMP演算法以目前所有SDVRP相關之國際標竿題庫進行測試，在IMP模組部分採用變動鄰域下降(Variable Neighborhood Decent,VND) 與隨機變動鄰域下降(Randomized VND, RVND) 兩種方式執行。測試結果發現SRC+RVND的績效較SRC+VND佳；其結果在SDVRP方面，對32個標竿題求解的平均誤差為0.36%，其績效僅次於ILS (Silva et al.[44])；在SDVRP-MDA方面，對128個標竿題求解的平均誤差為-0.27%，且求得81題並突破36題已知最佳解；在SDVRP-LND方面，22題標竿例題中則求得5題已知最佳解並突破5題，平均求解誤差為0.07%。 本研究亦分析配送次數上限kmax對成本的影響，結果發現當kmax3時，SDVRP-LND的成本節省效益為4.11%，其與無次數限制的SDVRP相差僅0.06%；這顯示以最多配送三次執行SDVRP-LND可對物流界提供相當的實用價值。 |
| 附件下載 | (電子檔於111-08-08後開放下載) |
檔案下載
瀏覽人次:221