需求分割之車輛路線問題啟發式解法研究

Abstract

傳統之車輛路線問題(VRP)對每一個顧客點的需求，必須由單獨一個車輛 路線完成服務。需求分割之車輛路線問題(SDVRP)，則允許每個顧客的需求可 以分割由不同車輛路線分別服務。SDVRP 的研究文獻可追溯自1989 年，但應 用巨集啟發式解法的研究則出現在2006 年以後，相對於傳統之VRP，SDVRP 仍屬新興研究課題之一。現有文獻巳發現SDVRP 較VRP 可有效節省成本，最 多可達50%。 本研究經由文獻對現有SDVRP 啟發式解法進行比較分析，發現現行的DT, SPLITABU 與EMIP 等方法，在鄰域搜尋機制與巨集求解的架構兩個方面均有 改善的空間。因而提出具體之研究計畫，擬結合k 分割交換改善與端點重置來 強化鄰域搜尋機制，並以回溯式門檻接受法(BATA)構建一套新的巨集解法。

Traditional vehicle routing problem (VRP) requires that the delivery of each customer can not be split over to more than one vehicle. In the split delivery vehicle routing problem (SDVRP), 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%. Current heuristic and meta-heuristic methods for SDVRP include DT, SPLITABU, EMIP etc. Through a thorough study of these methods, we found that they can be improved in many ways. We thus propose a new meta-heuristic solution approach based on the backtrack adaptive threshold accepting (BATA) method. We also propose a new generalized insertion heuristic method, which includes both k-split interchange and endpoint re-allocation processes, to serve as the neighborhood search engine for the new solution approach.