針對需求分割特性構建複合式鄰域搜尋法之設計與其應用

Abstract

需求分割之車輛路線問題 (SDVRP) 是傳統車輛路線問題 (VRP) 之變 型，允許每個顧客的需求可以分割由不同車輛路線分別服務。SDVRP 較VRP 可有效節省成本，尤其對企業內部物流極具應用價值。 SDVRP 的研究文獻源 自1989 年，但應用巨集啟發式解法的研究則出現在2006 年以後，而針對需求 分割特性構建有效的突破性鄰域搜尋方法則是在2010 年之後，是屬新興研究 課題之一。 鑒於目前新興方法仍有改善空間，本研究基於前期研究成果，擬針對需求 分割特性將Ejection-chain*發展為多層次、變動深度的複合式鄰域搜尋機制。 並將以其為核心，配合回溯式門檻接受法 (BATA) 或門檻接受法結合隨機變動 鄰域尋優法 (TA + RVND) 之巨集架構，建構求解SDVRP 以及具時窗之 SDVRPTW 的新方法。

The split delivery vehicle routing problem (SDVRP), a variant of conventional VRP, allows the delivery can be split and each customer can be covered by multiple vehicle routes. It has been found that SDVRP can save significant cost, as compared to VRP; the maximal saving is 50%. The SDVRP was first coined and studied by Dror and Trudeau in 1989. However, there were not many metaheuristic methods developed for SDVRP until 2006. Recently in 2010 and 2011, several studies showed that effective neighborhood structures can significantly improve the solution performance. Following this trend of research, this project would focus on the design and application of effective neighborhood search methods specifically designed for split-delivery problems. We would extend our earlier works on Ejection-chain* to a multi-level, adaptive and compound neighborhood structure. Based on this, we would further propose a new meta-heuristic solution approach using backtrack adaptive threshold accepting (BATA) or TA+RVND frameworks for solving SDVRP and SDVRPTW.