基于聚類的車輛線路優(yōu)化算法研究.pdf

1、本文針對大規(guī)模VRP問題的特點，提出了“先聚類，再分派，后排程”的三階段求解算法。首先，利用改進的基于密度的聚類算法(DBSCAN，Density Based Spatial Clustering of Applications with Noise)對客戶點進行分區(qū)聚類，生成一些虛擬客戶，將大規(guī)模問題轉(zhuǎn)化為小規(guī)模問題；然后，在第一階段聚類的基礎(chǔ)上，以生成的虛擬客戶集合作為輸入，采用Clark-Wright節(jié)約里程算法進行車輛分派；最后

2、，將車輛服務(wù)的虛擬客戶重新轉(zhuǎn)化為實際客戶，將問題變?yōu)槿舾蓚€小規(guī)模的旅行商問題(TSP，Traveling Salesman Problem)，采用蟻群算法或最鄰近點算法對每輛車安排最優(yōu)的客戶訪問次序。 為驗證算法的有效性，本文進行了大量的仿真試驗。試驗主要包括兩部分：對標(biāo)準(zhǔn)試驗庫(benchmark)的測試和山西某市煙草配送中心實際線路優(yōu)化問題的求解。一方面，在對標(biāo)準(zhǔn)試驗庫A集部分算例的試驗中，探討了算法相關(guān)參數(shù)值選擇問題，而且