動(dòng)態(tài)車輛路徑問題的算法設(shè)計(jì)與系統(tǒng)實(shí)現(xiàn).pdf

1、車輛路徑問題是為一系列結(jié)點(diǎn)規(guī)劃最優(yōu)訪問路徑的組合優(yōu)化問題，其廣泛應(yīng)用于物流配送等領(lǐng)域。隨著科技的發(fā)展和人們生活水平的提高，現(xiàn)實(shí)生活中的物流配送要求其能夠接收并處理動(dòng)態(tài)出現(xiàn)的新顧客，且配送司機(jī)有固定的工作時(shí)間區(qū)間。因此，研究動(dòng)態(tài)的、帶時(shí)間期限的車輛路徑問題成為現(xiàn)實(shí)需要。
　　針對(duì)當(dāng)前物流配送的實(shí)際情況，本課題研究了帶時(shí)間期限的動(dòng)態(tài)車輛路徑問題，并設(shè)計(jì)了始發(fā)結(jié)點(diǎn)的選取策略和一種混合大鄰域搜索算法。該算法引入周期性優(yōu)化策略將工作時(shí)間區(qū)間

2、劃分成多個(gè)等長的時(shí)間片，在每個(gè)時(shí)間片末采用一種基于鄰域分析的插入算法處理新顧客。同時(shí)，選取有效的始發(fā)結(jié)點(diǎn)組成當(dāng)前的靜態(tài)子問題，對(duì)其建立以車輛行駛總路程為優(yōu)化目標(biāo)的數(shù)學(xué)模型并采用一種基于三個(gè)remove策略和隨機(jī)貪婪re-insert策略的大鄰域搜索算法進(jìn)行優(yōu)化。本課題對(duì)22組包含顧客數(shù)為50-385的數(shù)據(jù)集分別進(jìn)行了靜態(tài)實(shí)驗(yàn)和動(dòng)態(tài)模擬實(shí)驗(yàn)。在10次靜態(tài)實(shí)驗(yàn)中，算法求得所有數(shù)據(jù)集的目標(biāo)值相比于當(dāng)前已知最優(yōu)解的平均相對(duì)誤差為3.11％，超過

3、80%的數(shù)據(jù)集其目標(biāo)值的相對(duì)誤差低于5%，通過結(jié)合顧客的位置分布分析得出本算法在求解聚集分布的顧客方面有較好的表現(xiàn)；在5次動(dòng)態(tài)實(shí)驗(yàn)中，本算法求得的最優(yōu)結(jié)果、平均結(jié)果和方差分別與遺傳算法GA求得的最優(yōu)解、平均解和方差相比，其中有13個(gè)數(shù)據(jù)集的最優(yōu)解優(yōu)于GA，10個(gè)數(shù)據(jù)集的平均解優(yōu)于GA，11個(gè)數(shù)據(jù)集的方差低于GA，綜合對(duì)比22組結(jié)果的最優(yōu)值、平均值和方差之和，可以得出本課題設(shè)計(jì)的算法在求得最優(yōu)值方面和算法的穩(wěn)定性方面具有有效的競爭力。