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

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

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

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