新型蟻群優(yōu)化算法在帶時(shí)間窗口的車輛路徑問題中的應(yīng)用.pdf

1、帶時(shí)間窗口的車輛路徑問題(VRPTW)是現(xiàn)實(shí)物流問題的一個(gè)數(shù)學(xué)抽象模型。本文將蟻群優(yōu)化算法(ACO)用于求解該問題。我們的首要目標(biāo)函數(shù)是降低VRPTW中的車輛數(shù)，第二目標(biāo)函數(shù)是降低總行駛代價(jià)。
　　在本文中，我們改進(jìn)了基本的蟻群算法以更好求解目標(biāo)函數(shù)。本文主要從以下四個(gè)方面做了改進(jìn)。第一，為了減小解構(gòu)建過程中的搜索空間，我們提出了域這個(gè)概念，且這個(gè)概念貫穿于整篇文章。該方法根據(jù)問題在時(shí)間上的約束，預(yù)先排除了時(shí)間上不可行的城市。將該

2、概念應(yīng)用到Solomon問題中，搜索空間平均減小了28％。第二，我們將基于數(shù)量的蟻群優(yōu)化算法(PACO)首次運(yùn)用于解決VRPTW，并發(fā)現(xiàn)該算法性能優(yōu)于本文中提到的所有蟻群算法。第三，本文針對(duì)PACO提出了一種全新的概率初始方法(PI-PACO)。該方法對(duì)問題中條件以及實(shí)際物流情況建模并最終給出城市間訪問的初始信息素。通過實(shí)驗(yàn)我們發(fā)現(xiàn)，該方法不僅能同時(shí)提升兩個(gè)目標(biāo)函數(shù)的質(zhì)量也能加速算法的收斂。第四，為了提高解的質(zhì)量，我們?cè)谒惴ㄖ性黾恿司植?/p>