基于扇形掃描的大規(guī)模VRP優(yōu)化算法研究.pdf

1、目前在大規(guī)模的車輛路徑問題（Vehicle Routing Problem，VRP）的求解算法研究上還存在很多不足，為了使得VRP的求解算法能夠應(yīng)用于實(shí)際的大規(guī)模物流配送，本論文以大規(guī)模VRP求解算法作為對象展開研究。 論文首先基于一定的前提和假設(shè)建立了大規(guī)模VRP的數(shù)學(xué)模型，然后根據(jù)模型的要求和大規(guī)模VRP的特性提出了一種“先分組后排程”的兩階段算法——基于扇形掃描的啟發(fā)式算法。該算法分兩步來求解VRP：第一步先應(yīng)用扇形掃描分

2、組算法把全部客戶根據(jù)一定的約束條件分派到多個(gè)組中；第二步利用具有交叉和變異特征的蟻群算法對第一步運(yùn)算得到的各個(gè)組進(jìn)行組內(nèi)客戶排程。這種啟發(fā)式求解算法的創(chuàng)新之處在于： 1）分組階段以動態(tài)掃描的方式確定每次的搜索區(qū)域，這不僅達(dá)到了縮小搜索區(qū)域的目的，而且基本能夠得到與全區(qū)域搜索方式相同質(zhì)量的分組結(jié)果； 2）在組內(nèi)客戶排程階段所用的具有交叉和變異特征的蟻群算法融合了遺傳算法和蟻群算法的思想，實(shí)現(xiàn)了兩種算法的優(yōu)勢互補(bǔ)，其中在交叉

3、環(huán)節(jié)上采用了順序插入交叉的方式，這種交叉方式能夠使優(yōu)秀的基因得以很好的遺傳到下一代，加快了算法向最優(yōu)解收斂的速度。 為了驗(yàn)證算法的有效性和可行性，本文進(jìn)行了大量的仿真試驗(yàn)。在對標(biāo)準(zhǔn)TSP測試算例仿真得到的最優(yōu)解與目前已知的最優(yōu)解的誤差只有0．81％，對標(biāo)準(zhǔn)的VRP測試算例仿真得到的最優(yōu)解與目前已知的最優(yōu)解的誤差只有2．98％，這些標(biāo)準(zhǔn)算例的仿真結(jié)果充分證明了算法的可行性。而在對某卷煙配送中心實(shí)際客戶的仿真試驗(yàn)中，只用了14分鐘就