以啟發式演算法求解具時窗限制車輛途程問題－以叢集分布便利商店配送為例

便利商店隨人口分布而設立，故多呈現叢集型態分布。為滿足民眾便利消費的需求，物流中心需每日依時將商品配送至便利商店。因此，本研究以便利商店配送為案例，利用啟發式演算法為其求解具時窗限制的車輛排程規劃。第一階段分別選用「最鄰近法」及「先分群後掃描排路線法」尋求初始解。第二階段以減少車輛數量與區域改善進行路線調整。研究結果顯示，透過第二階段之改善，可比第一階段初始解節省約16%的路線成本與二氧化碳排放。「先分群後掃描排路線法」的最佳解的路線成本低於「最鄰近法」。透過實際配送資料驗證的結果，顯示本研究提出的規劃程序具有實務應用之能力。

關鍵字

具時窗限制車輛途程問題；掃描法；最鄰近法；物流中心

並列摘要

This study applies heuristic approach to solve the Vehicle Routing Problem with Time Window and to search the optimal daily delivery routes for the Distribution Center of S convenient stores in Kaohsiung. The heuristic approach is divided into two stages. First, the ＂Nearest Neighbor Heuristic Method＂ and the ＂Cluster First Route Second with Sweep Approach＂ are separately adopted to search the initial routes. Second, the initial routes are merged to reduce the number of trucks and adjusted by swapping and 1-0 exchange methods to search the optimal delivery routes. Compared to the initial delivery routes, the optimal delivery routes can save 16% transportation cost and CO_2 emission. Based on the results of 20 days, the performances of the ＂Cluster First Route Second with Sweep Approach＂ are better than the performances of the ＂Nearest Neighbor Method＂. The results of computational experiments showed that the proposed approach outperforms the existing approach and can fulfill the practical use.