最鄰近點為準之集群調整法於求解具容量限制之車輛途程問題

A Nearest-based Clustering Adjustment Algorithm for the Capacitated Vehicle Routing Problem

本研究考慮具容量限制車輛途程問題，對於先分群再排路徑之兩階段求解法提出新的改善方法，主要概念為於集群形成階段後，檢視集群內的需求點，提出依集群重心為準，和依最鄰近點為準兩種集群調整法，重新調整需求點之所屬集群。經由測試標準範例後發現，依最鄰近點為準之集群調整法，可獲得較小之總路徑成本，此外，本研究進一步測試將Shin and Han（2012）所發表之演算法結合依最鄰近點為準之調整法，結果發現結合使用最鄰近點之集群調整法後，可顯著改善總路徑成本。未來可將所提之改善方法應用區位途程問題或多車場之車輛途程問題。

The capacitated vehicle routing problem (CVRP) is considered in this paper. We propose two new cluster adjustment methods inserted into the classic cluster-first route-second heuristic. The first is the centroid-based adjustment and the second is the nearest-based adjustment. Experimental results on Augerat benchmark dataset show that the nearest-based clustering adjustment had a better performance than the centroid-based adjustment. Moreover, the inclusion of the nearest-based adjustment approach can further improve the distance obtained from Shin and Han (2012) in more cases of the benchmark.