趙玉蘋(píng) 張惠珍

（上海理工大學(xué)　　管理學(xué)院，上海，200093）

帶柔性時(shí)間窗車(chē)輛路徑問(wèn)題的混沌蟻群算法*

趙玉蘋(píng) 張惠珍

（上海理工大學(xué)管理學(xué)院，上海，200093）

帶柔性時(shí)間窗的開(kāi)放式車(chē)輛路徑問(wèn)題（Opening Vehicle Routing Problemwith Flexible Time Windows，OVRPFTW）對(duì)物流配送中的延遲或者提早具有一定程度的容忍.本文首先建立了OVRPFTW的數(shù)學(xué)模型，然后分別將Sine映射，Chebyshev映射和Logistic映射引入基本蟻群算法，構(gòu)建了三種混沌蟻群算法，并將其用于求解OVRPFTW.算例測(cè)試表明：Sine映射和Chebyshev映射能夠明顯地改進(jìn)基本蟻群算法的優(yōu)化性能，基于Sine映射和Chebyshev映射的混沌蟻群算法的求解性能優(yōu)于基本蟻群算法和基于Logistic映射的混沌蟻群算法.

車(chē)輛路徑問(wèn)題 柔性時(shí)間窗 混沌優(yōu)化 蟻群算法

1　引言

開(kāi)放式車(chē)輛路徑問(wèn)題（Opening Vehicle Routing Problem）和帶時(shí)間窗的車(chē)輛路徑問(wèn)題（Vehicle Routing Problem with Time Windows，VRPTW）是組合優(yōu)化問(wèn)題中應(yīng)用相當(dāng)廣泛的模型［1］，它們是車(chē)輛路徑問(wèn)題（Vehicle Routing Problem，VRP）的擴(kuò)展.在物料運(yùn)輸、郵政快遞以及校車(chē)路徑規(guī)劃中都可以看到VRPTW的應(yīng)用，它要求為顧客提供服務(wù)的時(shí)間必須在此顧客的時(shí)間窗內(nèi)，允許車(chē)輛在顧客服務(wù)時(shí)間窗開(kāi)始之前到達(dá)，并且在等待期間不產(chǎn)生成本，但是不允許車(chē)輛在顧客服務(wù)時(shí)間窗結(jié)束之后到達(dá).帶軟時(shí)間窗的車(chē)輛路徑問(wèn)題（Vehicle Routing Problem with Soft Time Windows，VRPSTW）假定可以違背顧客服務(wù)時(shí)間窗，但必須要為車(chē)輛的早到或者遲到接受適當(dāng)?shù)膽土P［2］.對(duì)于開(kāi)放式車(chē)輛路徑問(wèn)題（Opening Vehicle Routing Problem，OVRP）來(lái)說(shuō)，不要求車(chē)輛完成配送任務(wù)后返回原出發(fā)點(diǎn)，若要求返回原出發(fā)點(diǎn)，則沿原路線返回［3］.目前，用于求解開(kāi)放式且有時(shí)間要求的物流配送問(wèn)題的啟發(fā)式算法主要包括：模塊啟發(fā)式算法［4］，混合粒子禁忌搜索算法［5］，變鄰域搜索算法［6］，蟻群算法［7］，遺傳算法［8-10］等等，這些算法主要用于解決帶硬時(shí)間窗或軟時(shí)間窗的開(kāi)放式車(chē)輛路徑問(wèn)題.

帶柔性時(shí)間窗的開(kāi)放式車(chē)輛路徑問(wèn)題（Opening Vehicle Routing Problem with Flexible Time Windows，OVRPFTW）表示客戶(hù)對(duì)配送時(shí)間具有一定程度的容忍，容忍度是根據(jù)配送物品的特點(diǎn)以及顧客的時(shí)間彈性來(lái)確定，允許配送時(shí)間窗的違反［11］.國(guó)內(nèi)外關(guān)于帶柔性時(shí)間窗的車(chē)輛路徑問(wèn)題的研究并不多見(jiàn)，而對(duì)于多配送中心、開(kāi)放式的帶柔性時(shí)間窗的車(chē)輛路徑問(wèn)題更是鮮有研究.本文首先建立帶柔性時(shí)間窗的多配送中心、開(kāi)放式的車(chē)輛路徑問(wèn)題的數(shù)學(xué)模型，然后分別將基于Sine映射，Chebyshev映射和Logistic映射的混沌策略引入基本蟻群算法，構(gòu)建了三種不同的混沌蟻群算法，并將其用于求解OVRPFTW，最后通過(guò)測(cè)試算例分析了三種混沌蟻群算法和基本蟻群的求解性能.

2　帶柔性時(shí)間窗的多配送中心開(kāi)放式車(chē)輛路徑問(wèn)題

2.1問(wèn)題及描述符號(hào)定義

帶柔性時(shí)間窗的多配送中心開(kāi)放式車(chē)輛路徑問(wèn)題可以描述為：車(chē)輛k從配送中心D出發(fā)，一次為多個(gè)顧客配送貨物，配送完成之后返回就近的配送中心.其中，每個(gè)顧客i只能被一輛車(chē)服務(wù)且只能被服務(wù)一次.假設(shè)顧客i的服務(wù)時(shí)間窗為［li，ui］，考慮到該時(shí)間窗對(duì)早到或晚到具有一定的容忍度后的時(shí)間窗為［l′i，u′i］，車(chē)輛k超出這一限定區(qū)間到達(dá)要受到一定的懲罰，即若車(chē)輛k早到，則必須等到最早開(kāi)始服務(wù)時(shí)間l′i才能服務(wù)；若車(chē)輛k晚到，則必須在最晚開(kāi)始服務(wù)時(shí)間u′i之前到達(dá).該問(wèn)題的目標(biāo)是求解從所有配送中心出發(fā)的車(chē)輛對(duì)所有顧客配送服務(wù)的最小運(yùn)輸總成本，這里的運(yùn)輸成本包括固定成本和可變成本，固定成本為車(chē)輛啟動(dòng)費(fèi)用，可變成本只考慮車(chē)輛的行駛距離.

為便于問(wèn)題描述，現(xiàn)將變量及符號(hào)定義如下：

G=（V，E）：運(yùn)輸網(wǎng)絡(luò)；V：節(jié)點(diǎn)集，包括客戶(hù)集C=1，2，…，A｛

｝和配送中心集D= 1，2，…，B｛

｝，任意一個(gè)配送中心車(chē)輛的集合；o：油耗費(fèi)用系數(shù)；r：調(diào)用一輛車(chē)的固定啟動(dòng)費(fèi)用系數(shù)；W：每輛車(chē)的最大裝載量；［li，ui］：客戶(hù)點(diǎn)i的時(shí)間窗；pli：違背客戶(hù)i時(shí)間窗早到的最大容忍度；pui：違背客戶(hù)i時(shí)間窗晚到的最大容忍度；：考慮客戶(hù)i 最大容忍度的時(shí)間窗，其中；tik：車(chē)輛k到達(dá)客戶(hù)點(diǎn)i的時(shí)間；tij：每輛車(chē)從節(jié)點(diǎn)i到節(jié)點(diǎn)j的行駛時(shí)間；t0：每輛車(chē)在客戶(hù)點(diǎn)的服務(wù)時(shí)間；hij：節(jié)點(diǎn)i到j(luò)之間的距離；dl：車(chē)輛在原時(shí)間窗之外，最大容忍時(shí)間窗之內(nèi)早到的懲罰系數(shù)；du：車(chē)輛在原時(shí)間窗之外，最大容忍時(shí)間窗之內(nèi)晚到的懲罰系數(shù)；P：懲罰函數(shù)，

決策變量：

2.2數(shù)學(xué)模型

上述模型中，式（1）為目標(biāo)函數(shù)，表示車(chē)輛運(yùn)行總成本最小；約束（2）表示每個(gè)客戶(hù)必須被服務(wù)且只能被服務(wù)一次；約束（3）和（4）確?？蛻?hù)僅被訪問(wèn)一次，且從客戶(hù)點(diǎn)離開(kāi)的車(chē)輛僅有一輛；約束（5）保證每輛車(chē)不會(huì)從一個(gè)配送中心不經(jīng)過(guò)客戶(hù)直接到達(dá)另一個(gè)配送中心；約束（6）為車(chē)容量約束；約束（7）表示到達(dá)客戶(hù)點(diǎn)i的車(chē)輛數(shù)與離開(kāi)客戶(hù)點(diǎn)i的車(chē)輛數(shù)相同且均為1；約束（8）為時(shí)間窗約束；式（9）為計(jì)算車(chē)輛k到達(dá)節(jié)點(diǎn)j的時(shí)間公式；約束（10）保證車(chē)輛行駛的先后順序；約束（11）為消去支路約束，排除不完整線路.

3　混沌蟻群算法

蟻群算法是模擬蟻群覓食行為的一種基于種群的模擬進(jìn)化算法，其在求解組合優(yōu)化難題和連續(xù)優(yōu)化問(wèn)題中取得了較好的結(jié)果［12］.近年來(lái)，越來(lái)越多的學(xué)者利用蟻群算法求解物流配送中的車(chē)輛調(diào)度和路徑優(yōu)化問(wèn)題［13］.相比于其他智能優(yōu)化算法，蟻群算法具有較強(qiáng)的魯棒性，易與其他方法結(jié)合的優(yōu)點(diǎn).首先，蟻群算法對(duì)初始路線的要求不高，即蟻群算法的求解結(jié)果不依賴(lài)于初始路線的選擇，而且在搜索的過(guò)程中不需要進(jìn)行人工調(diào)整.其次蟻群算法的參數(shù)數(shù)目少，設(shè)置簡(jiǎn)單.但蟻群算法也具有一定的不足之處，如：容易陷入局部最優(yōu)，搜索速度比較慢等.

本文針對(duì)基本蟻群算法收斂速度慢和易陷入局部最優(yōu)等缺點(diǎn)，分別將Sine映射，Chebyshev映射和Logistic映射三種混沌映射方法與蟻群算法結(jié)合，設(shè)計(jì)不同的混沌蟻群算法，以便有效抑制算法的早熟現(xiàn)象，跳出局部最優(yōu).

3.1混沌擾動(dòng)策略

混沌是一種普遍的非線性現(xiàn)象，其表面上是混亂的，但實(shí)際上卻含有內(nèi)在規(guī)律性，規(guī)律性、隨機(jī)性和遍歷性是混沌的特點(diǎn).混沌優(yōu)化的基本思想是：將優(yōu)化變量通過(guò)混沌映射規(guī)則映射到混沌變量空間的取值區(qū)間內(nèi)，利用混沌變量的遍歷性和規(guī)律性尋優(yōu)搜索，最后將獲得的優(yōu)化解線性轉(zhuǎn)化到優(yōu)化空間.

當(dāng)蟻群算法循環(huán)迭代中最優(yōu)解的值（最小費(fèi)用）連續(xù)重復(fù)出現(xiàn)多次時(shí)，即可認(rèn)定算法進(jìn)入早熟、停滯的狀態(tài).蟻群算法進(jìn)入早熟、停滯狀態(tài)后，可利用混沌擾動(dòng)策略幫助其跳出局部最優(yōu).不同的混沌映射產(chǎn)生的混沌效果不同，本文分別利用Logistic混沌映射、Chebyshev混沌映射和Sine混沌映射（三種混沌的參數(shù)、映射表達(dá)式和區(qū)間表達(dá)式如表1所示）調(diào)整螞蟻算法中螞蟻的信息素含量，構(gòu)建了三種不同的混沌蟻群算法.

表1　三種混沌擾動(dòng)策略

表1中，g表示選出的需要混沌的路徑個(gè)數(shù)；n表示混沌迭代次數(shù)；xn為第n次混沌迭代的數(shù)值；τg為第g個(gè)要進(jìn)行混沌的螞蟻信息素含量；τmax表示所選螞蟻路徑上信息素含量的最大值；τmin表示所選螞蟻路徑上信息素含量的最小值.

混沌優(yōu)化過(guò)程為：假設(shè)進(jìn)入混沌迭代時(shí)各路徑的信息素含量為τi（0＜i≤m，m為螞蟻數(shù)），首先利用映射空間計(jì)算表達(dá)式將信息素含量轉(zhuǎn)換到各混沌策略的映射空間上；然后用映射表達(dá)式對(duì)得到的x1進(jìn)行混沌擾動(dòng)，得到混沌序列x=x1，x2，…，xn（

），最后將混沌序列通過(guò)逆映射表達(dá)式映射到解空間.若混沌迭代過(guò)程中更新了全局最優(yōu)解或達(dá)到最大混沌迭代次數(shù)仍未更新最優(yōu)解，則停止混沌擾動(dòng).

3.2混沌蟻群算法的設(shè)計(jì)

3.2.1轉(zhuǎn)移規(guī)則

式（12）中，Nki代表螞蟻k可以訪問(wèn)的客戶(hù)點(diǎn)集；τij為邊（i，j）的軌跡強(qiáng)度；ηij為邊（i，j）的能見(jiàn)度，一般表示為路徑長(zhǎng)度的倒數(shù)；μij為邊（i，j）的節(jié)省量，即uij=hib+hbj-hij（b ∈D），節(jié)省量的值越大表示螞蟻越應(yīng)當(dāng)在訪問(wèn)完節(jié)點(diǎn)i之后訪問(wèn)節(jié)點(diǎn)j.α，β和γ分別表示τij，ηij和μij的相對(duì)重要性.

螞蟻構(gòu)造路徑時(shí)，遵循以下的偽隨機(jī)規(guī)則：q為0到1之間的隨機(jī)數(shù)，當(dāng)q＞q0（q0=0.05）時(shí)，根據(jù)式（12）計(jì)算出的轉(zhuǎn)移概率并按照輪盤(pán)賭的方法確定下一個(gè)訪問(wèn)客戶(hù)；否則，取轉(zhuǎn)移概率最大的點(diǎn)為下一個(gè)要訪問(wèn)的客戶(hù)點(diǎn)n，即

3.2.2信息素更新

當(dāng)所有螞蟻完成一次循環(huán)迭代后，各邊上的信息素強(qiáng)度由式（14）-（16）進(jìn)行更新：

3.3算法

求解帶柔性時(shí)間窗、多配送中心、開(kāi)放式車(chē)輛路徑問(wèn)題的混沌蟻群算法的步驟如下：

步驟1 初始化各參數(shù)，輸入所有客戶(hù)及配送中心的數(shù)據(jù)，最大迭代次數(shù)Nc_max=200；

步驟2 將m只螞蟻隨機(jī)均勻地放到B個(gè)配送中心，初始化螞蟻k已走的客戶(hù)點(diǎn)集tabuk，以及候選點(diǎn)集Nki（包括配送中心）；設(shè)置完成任務(wù)的螞蟻數(shù)量l=0；

步驟3 對(duì)螞蟻k，當(dāng)車(chē)輛剩余載重量能滿(mǎn)足至少一個(gè)客戶(hù)時(shí)，按轉(zhuǎn)移規(guī)則確定下一個(gè)訪問(wèn)節(jié)點(diǎn)j，并更新tabuk，Nki以及車(chē)輛的剩余載重量；

步驟4 如果Nki≠?，并且至少有一個(gè)候選點(diǎn)的需求量小于車(chē)輛的剩余載重，則轉(zhuǎn)步驟3；否則轉(zhuǎn)步驟5；

步驟5 若Nki≠?，并且車(chē)輛剩余載重不能滿(mǎn)足所有候選點(diǎn)的需要量，則增加一輛車(chē)，令其載重量為W，并轉(zhuǎn)步驟3；否則，轉(zhuǎn)步驟6；

步驟6 若Nki=?，且當(dāng)前螞蟻的最后一個(gè)訪問(wèn)點(diǎn)不是配送中心，則令其返回到離其最近的配送中心，l++.若l≤m，轉(zhuǎn)步驟3；否則，轉(zhuǎn)步驟7；

步驟7 所有螞蟻遍歷一次后，按照公式（14）-（16）對(duì)所有路徑的信息素進(jìn)行更新；Nc ++；

步驟8 由各螞蟻的tabuk得到路徑集L=L1，L2，…，Lm｛

｝，根據(jù)約束條件計(jì)算每個(gè)可行解的罰函數(shù)以及目標(biāo)函數(shù)值，記錄本次迭代的最優(yōu)解，同時(shí)更新全局最優(yōu)解（全局最優(yōu)解為迭代至今求得的最優(yōu)解）；

步驟9 若同一全局最優(yōu)解連續(xù)出現(xiàn)Nbest_max 次，則轉(zhuǎn)步驟10，否則轉(zhuǎn)步驟11；

步驟10 利用混沌映射改變路徑上信息素含量，求出可行解的目標(biāo)函數(shù)值并與當(dāng)前全局最優(yōu)解比較，若混沌過(guò)程中得到了優(yōu)于當(dāng)前最優(yōu)的解，則更新全局最優(yōu)解，并跳出混沌迭代；若在混沌迭代過(guò)程中未找到優(yōu)于當(dāng)前最優(yōu)的解，直接跳出混沌過(guò)程.

步驟11 若Nc=Nc_max ，則算法終止，并輸出全局最優(yōu)解L*；否則，Nc++，轉(zhuǎn)步驟2.

4　算例及分析

本文利用文獻(xiàn)［10］中的算例來(lái)測(cè)試算法的求解性能，其中客戶(hù)點(diǎn)、配送中心的位置坐標(biāo)以及需求量等數(shù)據(jù)如表2所示.設(shè)1-24為客戶(hù)編號(hào)，25-27為配送中心編號(hào)，它們分布在不同的地方.所有車(chē)輛的裝載容量為4t，車(chē)輛在顧客點(diǎn)的服務(wù)時(shí)間t0為定值20.

算法運(yùn)行環(huán)境為Windows7平臺(tái)，32位操作系統(tǒng)，Intel處理系統(tǒng)，3.40GHz，4 GB內(nèi)存；仿真軟件為MATLAB2010a.

表2　算例數(shù)據(jù)

為了確保算法之間的可比性，使它們?cè)谙嗤钠瘘c(diǎn)上進(jìn)行比較，計(jì)算過(guò)程中對(duì)三種混沌蟻群算法和基本蟻群算法共有的參數(shù)設(shè)定了相同的值：螞蟻數(shù)m=60，軌跡的相對(duì)重要性α=1，能見(jiàn)度的相對(duì)重要性β=1，節(jié)省量的相對(duì)重要性γ=2，初始信息素總量Q=10，時(shí)間窗容忍度ρli=ρui=0.2，算法迭代次數(shù)Nc_max=200.對(duì)三種混沌迭代中的共有參數(shù)設(shè)定如下：達(dá)到混沌標(biāo)準(zhǔn)的最優(yōu)解重復(fù)次數(shù)Nbest_max=30，最大混沌迭代次數(shù)Tc=10.三種混沌蟻群算法和基本蟻群算法各運(yùn)行20次，求解結(jié)果如表3所示.

表3　基本蟻群算法與混沌蟻群算法計(jì)算結(jié)果

由表3不難看出，雖然基本蟻群算法的計(jì)算效率以及計(jì)算結(jié)果的穩(wěn)健性要高于幾種混沌蟻群算法，但基于Sine映射的混沌蟻群算法和基于Chebyshev映射的混沌蟻群算法的優(yōu)化結(jié)果明顯優(yōu)于基于Logistic映射的混沌蟻群算法和基本蟻群算法，且Sine映射的混沌蟻群算法的計(jì)算結(jié)果更優(yōu)，Chebyshev映射的混沌蟻群算法穩(wěn)定性更好.與基本蟻群算法相比，帶Logistic映射的混沌蟻群算法并沒(méi)有改善問(wèn)題的最優(yōu)解，且計(jì)算時(shí)間更長(zhǎng).

圖1　滿(mǎn)意解圖示

基于Chebyshev映射和Sine映射的混沌蟻群算法求得相同的滿(mǎn)意解（如圖1所示），配送總成本為162472.50，車(chē)輛數(shù)為7.每輛車(chē)的配送路線如下，車(chē)輛1：25-16-11-8-22-7-25；車(chē)輛2：25-14-3-18-23-25；車(chē)輛3：25-9-5 -27；車(chē)輛4：27-20-6-19-27；車(chē)輛5：27-4 -15-24-17-27；車(chē)輛6：27-2-10-21-26；車(chē)輛7：26-13-12-1-26.

5　結(jié)論

本文首先建立了帶柔性時(shí)間窗的開(kāi)放式車(chē)輛路徑問(wèn)題（OVRPFTW）的數(shù)學(xué)模型，然后將Sine映射，Chebyshev映射以及Logistic混沌映射分別與基本蟻群算法融合，提出了三種求解OVRPFTW的混沌蟻群算法.測(cè)試算例結(jié)果表明：基于Sine映射的混沌擾動(dòng)對(duì)蟻群算法在解決帶柔性時(shí)間窗的開(kāi)放式車(chē)輛路徑問(wèn)題中產(chǎn)生了很明顯的優(yōu)化作用，混沌優(yōu)化后的最優(yōu)解平均值171046遠(yuǎn)遠(yuǎn)優(yōu)于基本蟻群算法得到的結(jié)果174019；利用Chebyshev映射的混沌擾動(dòng)策略也能夠改進(jìn)最優(yōu)解的質(zhì)量，且穩(wěn)定性要高于基于Sine映射的混沌蟻群算法；利用Logistic映射的混沌擾動(dòng)策略對(duì)解決此類(lèi)問(wèn)題的優(yōu)化效果卻并不明顯.

［1］A D López-Sánchez，A.G.Hernández-Díaz，Vigo D，et al.A multi-start algorithm for a balanced real -world Open Vehicle Routing Problem［J］.European Journal of Operational Research，2014，238（1）：104-113.

［2］Beheshti A K，Hejazi S R.A novel hybrid column generation-metaheuristic approach for the vehicle routing problem with general soft time window［J］.Information Sciences，2015，316：598-615.

［3］楊進(jìn)，馬良.蜂群優(yōu)化算法在帶軟時(shí)間窗的車(chē)輛路徑問(wèn)題中的應(yīng)用［J］.預(yù)測(cè)，2010，29（6）：67-70.

［4］Rahimi-Vahed A，Crainic T G，Gendreau M，et al.Fleet-sizing for multi-depot and periodic vehicle routing problems using a modular heuristic algorithm［J］.Computers&Operations Research，2015，（53）：9-23.

［5］Escobar J W，Linfati R，Toth P，et al.A hybrid granular tabu search algorithm for the multi-depot vehicle routing problem［J］.Journal of Heuristics，2014，20（5）：483-509.

［6］王征，張俊，王旭坪.多車(chē)場(chǎng)帶時(shí)間窗車(chē)輛路徑問(wèn)題的變鄰域搜索算法［J］.中國(guó)管理科學(xué)，2011，（2）：99 -109.

［7］Reed M，Yiannakou A，Evering R.An ant colony algorithm for the multi-compartment vehicle routing problem［J］.Applied Soft Computing，2014，15（2）：169-176.

［8］孫賓松，符卓.求解帶軟時(shí)間窗的車(chē)輛路徑問(wèn)題的改進(jìn)遺傳算法［J］.系統(tǒng)工程，2003，21（6）：12-15.

［9］潘震東，唐加福，韓毅.帶貨物權(quán)重的車(chē)輛路徑問(wèn)題及遺傳算法［J］.管理科學(xué)學(xué)報(bào)，2007，10（3）：23-29.

［10］鐘石泉，杜綱，賀國(guó)光.有時(shí)間窗的開(kāi)放式車(chē)輛路徑問(wèn)題及其遺傳算法［J］.計(jì)算機(jī)工程與應(yīng)用，2007，42（34）：201-204.

［11］Duygu Ta?，Ola Jabali，Tom Van Woensel.A Vehicle Routing Problem with Flexible Time Windows［J］. Computers and Operations Research，2014，52：39-54.

［12］Dorigo M，Bonabeau E，Theraulaz G.Ant algorithms and stigmergy［J］.Future Generation Computer Systems，2000，16（8）：851-871.

［13］李婭，王東.基于混沌擾動(dòng)和鄰域交換的蟻群算法求解車(chē)輛路徑問(wèn)題［J］.計(jì)算機(jī)應(yīng)用，2012，02：444 -447.

The Chaos Ant Colony Optimization Algorithm for Solving Vehicle Routing Problem with Flexible Time Windows

Zhao Yuping Zhang Huizhen
（School of Business，University of Shanghai for Science and Technology，Shanghai 200093，China）

Opening Vehicle Routing Problemwith Flexible Time Windows（OVRPFTW）allows vehicles to serve customers ahead of schedule or behind schedule by a given tolerance.In this paper，the mathematical model of the OVRPFTW is formulated firstly，then three chaos Ant Colony Optimization（ACO）algorithms for solving the OVRPFTW are proposed by combining ACO with Sine mapping，Chebyshev mapping and Logistic mapping，respectively.Numerical results show that Sine mapping and Chebyshev mapping can significantly improve the ACO algorithm，and comparing with the basic ACO algorithm and the chaos ACO algorithm based on Logistic mapping，the chaos ACO algorithms based on Sine mapping and Chebyshev mapping have better optimization performance.

Vehicle routing problem Flexible time window Chaos optimization Ant Colony Optimization

國(guó)家自然科學(xué)基金項(xiàng)目（71401106）；高等學(xué)校博士學(xué)科點(diǎn)專(zhuān)項(xiàng)科研基金聯(lián)合資助課題（20123120120005）；上海市教育委員會(huì)科研創(chuàng)新項(xiàng)目（14YZ090）資助

2016年03月19日