基于大規(guī)模車輛路徑問題的配送分區(qū)優(yōu)化研究.pdf

1、隨著現(xiàn)代城市經(jīng)濟(jì)的快速發(fā)展，企業(yè)與企業(yè)之間，企業(yè)與個(gè)人之間的商品交易發(fā)展日益迅速，物資流通的頻繁也進(jìn)一步顯現(xiàn)了物流的力量。配送作為物流系統(tǒng)的重要組成部分，與人們的生活息息相關(guān)，是反映城市物流服務(wù)水平的重要因素。隨著城市規(guī)模的擴(kuò)大，商品交易日益頻繁，城市配送客戶點(diǎn)規(guī)模日益增大，物流企業(yè)在大規(guī)?？蛻酎c(diǎn)的配送中如何合理地規(guī)劃車輛配送線路，如何有效地減少配送車輛行駛距離，降低運(yùn)輸成本，實(shí)現(xiàn)效益的最大化，成為企業(yè)關(guān)心的重要課題。車輛路徑問題由于問

2、題本身是從實(shí)際生活中抽象出來，與現(xiàn)實(shí)生活密切相關(guān)，因此一直是學(xué)術(shù)界中多個(gè)學(xué)科的研究熱點(diǎn)。小規(guī)模車輛路徑問題的各種算法研究已經(jīng)相對(duì)成熟，已經(jīng)可以在50個(gè)點(diǎn)的范圍內(nèi)得到精確解，但是由于實(shí)際問題的大規(guī)模及多樣性，增加了該類問題的復(fù)雜程度。
　　 在目前各種分區(qū)聚類算法的研究基礎(chǔ)上，本文針對(duì)大規(guī)模車輛路徑問題的特點(diǎn)，提出了“先分區(qū)，再排程，后改進(jìn)”的三階段求解算法，首先，利用改進(jìn)的k-means算法將大規(guī)?？蛻酎c(diǎn)進(jìn)行分區(qū)，通過分區(qū)，將大

3、規(guī)模數(shù)據(jù)集分成若干個(gè)小規(guī)模數(shù)據(jù)集，并通過詳細(xì)的試驗(yàn)對(duì)比分析了分區(qū)數(shù)目對(duì)結(jié)果的影響;然后，在第一階段分區(qū)的基礎(chǔ)上，采用并行節(jié)約算法對(duì)各個(gè)區(qū)域進(jìn)行車輛排程;最后，為了提高區(qū)域之間的關(guān)聯(lián)性，采用可變鄰域搜索算法改進(jìn)結(jié)果。
　　 為了驗(yàn)證算法的有效性，本文進(jìn)行了大量的仿真試驗(yàn)。試驗(yàn)算例不僅包括分布密度均勻的客戶點(diǎn)算例，同時(shí)結(jié)合現(xiàn)實(shí)生活中真實(shí)配送數(shù)據(jù)，構(gòu)造分布密度不均的客戶點(diǎn)算例，得到不同規(guī)?？蛻酎c(diǎn)不同分區(qū)個(gè)數(shù)的仿真結(jié)果，由于相同算法在不