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

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

沈宗緯(Chung-Wei Shen) ； 洪迎哲(Ying-Che Hung) ； 林雨萱(Yu-Syuan Lin)

《運輸學刊》 31卷4期 (2019/12) Pp. 449-480

https://doi.org/10.6383/JCIT.201912_31(4).0004

摘要

本研究考慮具容量限制車輛途程問題，對於先分群再排路徑之兩階段求解法提出新的改善方法，主要概念為於集群形成階段後，檢視集群內的需求點，提出依集群重心為準，和依最鄰近點為準兩種集群調整法，重新調整需求點之所屬集群。經由測試標準範例後發現，依最鄰近點為準之集群調整法，可獲得較小之總路徑成本，此外，本研究進一步測試將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.

並列關鍵字

Capacitated Vehicle Routing Problem ； Cluster adjustment ； Cluster-first Route-second

參考文獻

Akhand, M., Peya, Z. J., Sultana, T., and Rahman, M. H. (2017), “Solving Capacitated Vehicle Routing Problem Using Variant Sweep and Swarm Intelligence,” Journal of Applied Science and Engineering, Vol. 20, No. 4, pp. 511-524.

Augerat, P., Belenguer, J. M., Benavent, E., Corberán, A., Naddef, D., and Rinaldi, G. (1995), Computational Results with a Branch and Cut Code for The Capacitated Vehicle Routing Problem, INPG-RR-949-M, Institut National Polytechnique de Grenoble Universite Joseph Fourier Grenoble I, Grenoble.

Baldacci, R., Mingozzi, A., and Roberti, R. (2012), “Recent Exact Algorithms for Solving the Vehicle Routing Problem under Capacity and Time Window Constraints,” European Journal of Operational Research, Vol. 218, No. 1, pp. 1-6.

Barreto, S., Ferreira, C., Paixao, J., and Santos, B. S. (2007), “Using Clustering Analysis in a Capacitated Location-Routing Problem,” European Journal of Operational Research, Vol. 179, No. 3, pp. 968-977.

Bramel, J. and Simchi-Levi, D. (1995), “A Location Based Heuristic for General Routing Problems,” Operations Research, Vol. 43, No. 4, pp. 649-660.