朱顥（湖州職業(yè)技術(shù)學(xué)院，浙江 湖州 313000）

基于改進(jìn)粒子群算法的帶模糊時(shí)間和需求量的VRP問題

朱顥
（湖州職業(yè)技術(shù)學(xué)院，浙江 湖州 313000）

針對車輛旅行時(shí)間、卸貨時(shí)間和客戶需求量均為模糊變量的VRP問題，建立了基于可信性測度的模糊機(jī)會(huì)約束規(guī)劃模型，并用改進(jìn)的粒子群算法進(jìn)行優(yōu)化，算法以實(shí)數(shù)形式進(jìn)行編碼，針對不可行解，設(shè)計(jì)了專門的修復(fù)算子。通過仿真實(shí)驗(yàn)證明，該算法對于解決此類模糊VRP問題是行之有效的。

車輛調(diào)度問題；模糊旅行時(shí)間；模糊需求量；粒子群算法

1 引言

車輛路徑問題(Vehicle Routing Problems)作為一類NP難的組合優(yōu)化問題，由學(xué)者Dantzig和Ramser[1]于1959年首次提出,可以描述為：配送中心根據(jù)現(xiàn)有的資源和信息（如車輛、客戶、距離等），在某些約束條件下（如客戶服務(wù)時(shí)間要求、車輛容積限制等），為一系列客戶安排送貨車輛并選擇合適的行車路線，以達(dá)到某些目標(biāo)的最優(yōu)（如總成本最低，總路線最短）。在實(shí)際應(yīng)用中，由于受客觀世界不確定因素及人類認(rèn)識事物的模糊性影響，車輛路徑問題中的某些信息可能是模糊的、不確定的，如車輛旅行時(shí)間、客戶需求量等均存在不確定的情況，此時(shí)需要從模糊的視角來處理該類問題。

目前，國內(nèi)外有關(guān)模糊VRP問題的研究文獻(xiàn)中，以模糊需求量為特征的文獻(xiàn)有：Teodorovic等[2]引入決策者偏好，采用模糊推理算法求解了帶模糊需求的車輛路徑問題；祝崇雋等[3]等在國內(nèi)較早地針對帶模糊需求的VRP問題，通過模糊模擬來估算車輛額外行程，并運(yùn)用基于可能性分布和基于需求上界的2-OPT算法進(jìn)行尋優(yōu)；張建勇等[4-5]考慮了由于任務(wù)“失敗”而產(chǎn)生的額外行駛距離，設(shè)計(jì)了一種新穎的交叉算子,并運(yùn)用遺傳算法進(jìn)行求解；張建勇等[6]還對于同一類問題，設(shè)計(jì)了相應(yīng)的weeping啟發(fā)式算法；曹二保等[7-8]運(yùn)用差分進(jìn)化算法對此類問題進(jìn)行了求解，在該算法中設(shè)計(jì)了基于整數(shù)序規(guī)范的輔助算子；戎麗霞[9]針對同樣的問題，運(yùn)用遺傳算法進(jìn)行了求解；吳天羿等[10]運(yùn)用遺傳算法研究了該問題，在算法中運(yùn)用掃描算子進(jìn)行種群的初始化，設(shè)計(jì)了專門的混合交叉算子和差分掃描變異算子；Lian xue[11]利用改進(jìn)的差分進(jìn)化算法進(jìn)行求解，在交叉環(huán)節(jié)，交叉概率隨迭代次數(shù)線性增加；R.J.Kuo等[12]將粒子群算法和遺傳算法結(jié)合，通過每個(gè)粒子與其自身經(jīng)歷過的最優(yōu)狀態(tài)及粒子群最優(yōu)粒子之間的多次交叉操作，選取較優(yōu)的子代粒子替代當(dāng)前粒子；Cao Erbao等[13]用所有車輛的總距離（包括計(jì)劃行駛距離和額外行駛距離的）作為尋優(yōu)的目標(biāo)，設(shè)計(jì)了相應(yīng)的隨機(jī)模擬算法來估算額外行駛距離，針對有可能產(chǎn)生的不可行解，引入了相應(yīng)的懲罰函數(shù)，最后利用差分進(jìn)化算法進(jìn)行了求解；Yang Peng等[14]針對帶模糊需求量的VRP問題，提出了基于整數(shù)編碼的粒子群算法，對粒子更新過程中產(chǎn)生的實(shí)數(shù)，利用基于升序的排序規(guī)則，將實(shí)數(shù)轉(zhuǎn)換成整數(shù)。

在考慮模糊環(huán)境時(shí)，以車輛旅行時(shí)間為特征的文獻(xiàn)有：Y.Zeng和B.Liu[15]運(yùn)用混合遺傳算法研究了帶模糊旅行時(shí)間的車輛路徑問題；Ghannadpour等[16]提出了一類帶模糊旅行時(shí)間和客戶滿意度的多目標(biāo)動(dòng)態(tài)VRP問題，并提出了基于遺傳算法的動(dòng)態(tài)解決策略。Jianyong Zhang 等[17]分析了一類旅行時(shí)間具有模糊特征的VRP問題，建立了以最小化總模糊旅行時(shí)間為目標(biāo)的數(shù)學(xué)模型，提出了針對決策者偏好和旅行時(shí)間的模糊集，并建立了基于模糊邏輯的優(yōu)化選擇規(guī)則，最后針對該問題，提出了一種混合遺傳算法。Seyed Farid Ghannadpour等[18]考慮了帶模糊旅行時(shí)間的動(dòng)態(tài)多目標(biāo)VRP問題，運(yùn)用遺傳算法進(jìn)行了優(yōu)化。

從有關(guān)模糊VRP問題的文獻(xiàn)來看，模型主要集中于帶模糊需求量的VRP問題上，對具有模糊旅行時(shí)間的VRP問題研究文獻(xiàn)還不多，特別是同時(shí)帶模糊需求量、模糊車輛旅行時(shí)間、模糊卸貨時(shí)間特征的文獻(xiàn)更少。本文考慮同時(shí)帶模糊需求量、模糊旅行時(shí)間、模糊卸貨時(shí)間的VRP問題，并假設(shè)車輛到達(dá)客戶處時(shí)，不管到達(dá)時(shí)間是否處于時(shí)間窗口內(nèi)，均立即卸貨，基于此假設(shè)，構(gòu)建相應(yīng)的模糊機(jī)會(huì)約束規(guī)劃模型，利用改進(jìn)的粒子群算法進(jìn)行優(yōu)化。

2 模糊可信性理論

Zadeh于1965年提出了模糊理論，劉寶碇等[19]在此基礎(chǔ)上,提出了模糊可信性理論。假設(shè)Θ為非空集合，Ρ(Θ)表示 Θ的冪集，若 Pos是可能性測度，則(Θ,Ρ(Θ),Pos)為可能性空間，若A是冪集Ρ(Θ)中的一個(gè)元素，則為事件A的必要性測度；(Pos{} A+Nec{}

A)稱為事件A的可信性測度。

假設(shè) q，ξ均為三角模糊數(shù)，q=(q1,q2,q3)，ξ=(r1,r2,r3)，Q、a、b為常數(shù)且a＜b，根據(jù)可信性理論，可知：

Cr{a ≤ξ≤b}的取值經(jīng)過歸類，分為7種情況，見表1。

表1 Cr} ≤ξ≤b的各種取值情況

表1 Cr} ≤ξ≤b的各種取值情況

Cr{ } a≤ξ≤b Cr{ } a≤ξ≤b , 0 b-r3r2-r3條件b＜r1或者a＞r3r1≤b＜r2a＜r1且r2≤b≤r3a＜r1且b＞r31-12max{ } a-r1r2-r1(b-r1) 2(r2-r1) 2r2-r3-b 2(r2-r3) 1 2r2-r1-a 2(r2-r1)條件r1≤a＜r2且r2≤b≤r3r1≤a＜r2且b＞r3r2≤a≤r3(a-r3) 2(r2-r3)

3 帶模糊時(shí)間和模糊需求量的VRP模型

本文描述的帶模糊時(shí)間和模糊需求量的VRP問題為：一個(gè)配送中心（用“0”表示）為客戶提供送貨服務(wù)；該配送中心有m輛車可以利用，每輛車的標(biāo)記載重量固定不變；每輛車一次只能有一條行駛路線；每輛車從配送中心出發(fā)，完成若干客戶的送貨任務(wù)后返回；每個(gè)客戶每次只能由一輛車提供服務(wù)；每個(gè)客戶均有一個(gè)服務(wù)時(shí)間窗口，送貨盡可能在此范圍內(nèi)完成（同時(shí)假設(shè)配送中心也有一個(gè)時(shí)間窗口，所有車輛在某一時(shí)間前按時(shí)返回）；每個(gè)客戶的貨物需求不確定，為三角模糊數(shù)；每輛車的途中旅行時(shí)間和在客戶處的卸貨時(shí)間均不確定，為三角模糊數(shù)。本問題的實(shí)質(zhì)是在滿足一些列的約束條件下，為每輛車選擇相應(yīng)的客戶，并合理地安排送貨順序，安排每輛車從配送中心出發(fā)的時(shí)間，使得某一個(gè)目標(biāo)最優(yōu)（如距離最短）。為方便敘述，給出如下符號：

i=0,1,2,...,n，其中0表示配送中心，1,2,…,n表示客戶，客戶總數(shù)為n；

k=1,2,...,m表示車輛編號，車輛總數(shù)量為m；

qi表示客戶i的貨物需求量，i=1,2,...,n；qi為一個(gè)三角模糊數(shù)(qi1,qi2,qi3)；

Qk表示車輛k的標(biāo)記載重量，k=1,2,...,m；

Dij表示客戶i和 j之間的距離，i,j=0,1,2,...,n；

[ai,bi]為客戶i的服務(wù)時(shí)間窗口，i=0,1,2,...,n；

Tij表示車輛從客戶i到客戶 j的途中旅行時(shí)間，i,j=0,1,2,...,n；Tij為一個(gè)三角模糊數(shù)(Tij1,Tij2,Tij3)；

Si表示車輛在客戶i處的持續(xù)卸貨時(shí)間，i=1,2,...,n；Si為一個(gè)三角模糊數(shù)(Si1,Si2,Si3)；

fi為車輛抵達(dá)客戶i的時(shí)間，i=1,2,...,n；車輛到達(dá)客戶處時(shí)，不管是否處于時(shí)間窗口[ai,bi]內(nèi)，均立即卸貨。

定義問題的變量為yik、xijk和tk，其含義分別如下：當(dāng)客戶i由車輛k送貨時(shí)，yik取值為1，其他情況時(shí)yik取值為0；當(dāng)車輛k由客戶i訪問客戶 j時(shí)，xijk取值為1，其他情況時(shí)xijk取值為0；tk表示車輛k從配送中心出發(fā)的時(shí)間。

由于qi均為三角模糊數(shù)，因此qiyik也為一個(gè)三角模

糊數(shù)。

車輛抵達(dá)客戶 j的時(shí)間 fj為：

該問題的模型如下：

該模型中：式（3）表示模型的目標(biāo)函數(shù)；式（4）表示車輛能力約束，即每輛車所裝貨物的總重量小于其額定載重量的可信性大于給定的主觀決策值α；式（5）表示客戶的時(shí)間約束，車輛到達(dá)客戶的時(shí)間位于時(shí)間窗口內(nèi)的可信性大于給定的主觀決策值β；式（6）表示每個(gè)客戶由且只由一輛車提供送貨服務(wù)；式（7）和式（8）表示yik和xijk之間的關(guān)系，且保證每個(gè)客戶只被訪問一次；式（9）為消去支路約束；式（10）表示每輛車從車場出發(fā)，送完貨后需要返回車場。

4 算法介紹

4.1 問題解的編碼及解碼

為方便粒子的更新操作，以實(shí)數(shù)形式進(jìn)行編碼，編碼結(jié)構(gòu)為(Ge1,Ge2,…,Gen,t1,t2,…,tm)，每個(gè)元素和客戶及車輛的對應(yīng)關(guān)系見表2。

表2 問題解與客戶和車輛對應(yīng)關(guān)系

其中：Ge1,Ge2,…,Gen分別對應(yīng)客戶1,2,…,n，為區(qū)間(1,m+1)內(nèi)的實(shí)數(shù)；t1,t2,…,tm依次代表第1,2,...,m輛車的出發(fā)時(shí)間，限定在區(qū)間(a0,b0)內(nèi)，當(dāng)某輛車不執(zhí)行任務(wù)時(shí)，為了編碼和解碼的方便，也給其一個(gè)出發(fā)時(shí)間。

對于上述編碼方式，按照以下方法解碼：

Step1:對于Ge1,Ge2,…,Gen部分的元素，取其整數(shù)部分。根據(jù)整數(shù)部分進(jìn)行分組，如整數(shù)部分為1的客戶均由第1輛車提供送貨服務(wù)，依次類推。

Step2:對同一個(gè)組內(nèi)的客戶，再取其元素Gei中小數(shù)部分，按照從小到大排列，作為該車輛送貨的順序。

如一個(gè)由10個(gè)客戶、4輛車構(gòu)成的問題，某編碼如下：

根據(jù)Step1，得到如下四組：（1.92，1.07），（2.94，2.82），（3.42，3.46），（4.80，4.56，4.04，4.28），然后根據(jù)Step2，可知第1輛車服務(wù)的客戶按順序?yàn)?、2，出發(fā)時(shí)間為8.02；第2輛車服務(wù)的客戶按順序?yàn)?、4，出發(fā)時(shí)間為8.17；第3輛車服務(wù)的客戶按順序?yàn)?、10，出發(fā)時(shí)間為8.40；第4輛車服務(wù)的客戶按順序?yàn)?、9、5、1，出發(fā)時(shí)間為8.00。將問題解所對應(yīng)的車輛配送路線用一個(gè)矩陣code表示如下：

圖1 問題解對應(yīng)的code矩陣

在該矩陣中，第k行中非0元素依次表示第k輛車服務(wù)的客戶編號及訪問的順序，0元素表示此處無安排。由此可知，上述編碼方式肯定能滿足問題的約束條件（6）-（10）。

4.2 模糊因素的處理

對問題解進(jìn)行解碼后，可知每輛對應(yīng)的客戶及送貨順序，車輛k所裝載貨物的總重量為qiyik，由于qi均為三角模糊數(shù)(qi1,qi2,qi3)，根據(jù)模糊理論，iyik也為三角模糊數(shù)，令：

同理，由于Si、Tij均為三角模糊數(shù)，tk為實(shí)數(shù)，根據(jù)模糊理論，則車輛抵達(dá)客戶 j的時(shí)間 fj也為三角模糊數(shù)。由式（2），當(dāng)i=0且xijk=1時(shí)有：Cr{aj≤fj≤bj}的值即可根據(jù)表1得到。

4.3 問題解的修復(fù)

對本文所描述的問題解，在進(jìn)行解碼后，可根據(jù)4.2部分判斷出該問題解是否滿足車輛能力約束（4）和客戶的時(shí)間約束（5），若不滿足，則表示該問題解為不可行解，需要按照如下思路進(jìn)行修正：

（1）若車輛k不滿足能力約束，表明車輛k所在的子路徑內(nèi)客戶數(shù)量過多，需要調(diào)整。將對應(yīng)矩陣code中第k行（如圖2中第4輛車）最后的一個(gè)非0元素（假設(shè)為客戶i，如圖2中客戶1）用0代替，同時(shí)該客戶i加入到其他車輛（假設(shè)為車輛k'，圖2中第1輛車）所在的子路徑中（優(yōu)先選擇已執(zhí)行任務(wù)且服務(wù)客戶數(shù)最少的那輛車），且將該客戶i插入到新車輛k'當(dāng)前子路徑最后一個(gè)客戶（假設(shè)為i'）之后，與此對應(yīng)，該問題解中客戶i所對應(yīng)的基因Gei用區(qū)間(Gei',k'+1)內(nèi)的任意一個(gè)實(shí)數(shù)代替（Gei'

為客戶i'對應(yīng)的基因），然后重新判斷每輛車是否滿足能力約束，若該方法在所有車輛上均嘗試過后還不滿足約束條件，則新開一輛車。

圖2 客戶在子線路間的調(diào)整

（2）若滿足車輛能力約束，但不滿足客戶的時(shí)間約束，則表明各子路徑客戶數(shù)量沒有問題，但是子路徑內(nèi)客戶順序及車輛出發(fā)時(shí)間需要調(diào)整。由此，若客戶i不滿足時(shí)間約束，則根據(jù)以下情況進(jìn)行分析：若客戶i位于子路徑內(nèi)第1個(gè)位置，則說明車輛出發(fā)時(shí)間需要調(diào)整；否則，將客戶i依次與前面或后面的其他客戶（假設(shè)為客戶 j）進(jìn)行位置交換（如圖3中客戶5和1交換），與此對應(yīng)，將該問題解中客戶i所對應(yīng)的基因Gei和客戶 j所對應(yīng)的基因Gej進(jìn)行交換。然后判斷是否滿足該約束，若客戶i與該子路徑內(nèi)的其它所有客戶均交換完畢，仍然不能滿足約束，則對車輛出發(fā)時(shí)間進(jìn)行變異，隨機(jī)生成一個(gè)新的出發(fā)時(shí)間tk，直至滿足約束條件。

圖3 客戶在子線路內(nèi)的調(diào)整

4.4 改進(jìn)的粒子群算法

設(shè)粒子群集合為pop，種群規(guī)模為popsize，粒子的狀態(tài)采用4.1所述的編碼結(jié)構(gòu) (Ge1,Ge2,…,Gen,t1,t2, …,tm)，粒子的速度向量具有和粒子狀態(tài)相同的維數(shù)，每個(gè)粒子的適應(yīng)度為：

每個(gè)粒子 pop[p]（p=1,2,...,popsize）在迭代時(shí)，采用如下的規(guī)則進(jìn)行更新：

式（16）和（17）中，popt[p]和popt+1[p]分別表示第 p個(gè)粒子 pop[p]在第t代和第t+1代的狀態(tài)，Vt[p]和Vt+1[p]分別表示粒子 pop[p]在第t代和第t+1代的速度，Pind_best[p]為 pop[p]經(jīng)歷過的最優(yōu)狀態(tài)，Pg_best表示粒子群經(jīng)歷過的最優(yōu)狀態(tài)。ω表示慣性權(quán)重，c1和c2分別為加速度常數(shù)，rand()為0到1之間的隨機(jī)數(shù)。

根據(jù)有關(guān)粒子群算法的研究文獻(xiàn)表明，慣性權(quán)重ω和加速度常數(shù)c1、c2對粒子群算法的尋優(yōu)性能有著非常顯著的影響，其中慣性權(quán)重ω對算法的尋優(yōu)性能影響最為顯著，ω越大，算法的全局尋優(yōu)能力越強(qiáng)，局部尋優(yōu)能力越弱；反之，則算法的局部尋優(yōu)能力越強(qiáng)。通過調(diào)整ω的值，控制以前速度對當(dāng)前速度的影響，在全局尋優(yōu)和局部尋優(yōu)之間取得相對的平衡。

采用兩種動(dòng)態(tài)調(diào)整慣性權(quán)重ω的方法：

（1）線性權(quán)重調(diào)整法

式（18）中ωmax和ωmin分別表示最大慣性權(quán)重和最小慣性權(quán)重，max_iter為最大迭代次數(shù)，iter為當(dāng)前迭代次數(shù)。

（2）自適應(yīng)權(quán)重調(diào)整法。借鑒文獻(xiàn)[20]的方法，采用自適應(yīng)慣性權(quán)重調(diào)整方案，即每個(gè)粒子根據(jù)其當(dāng)前速度、當(dāng)前位置與自身經(jīng)歷過的最優(yōu)位置的距離，以及與種群最優(yōu)位置的距離三部分信息，動(dòng)態(tài)調(diào)整其下一步的飛行速度。具體方法如下：

首先定義第p個(gè)粒子pop[p]與當(dāng)前種群最優(yōu)粒子Pg_best的距離為，第 p個(gè)粒子 pop[p]與自身經(jīng)歷過的最優(yōu)位置Pind_best[p]的距離為則對于任意粒子pop[p]，當(dāng)其不處于種群最優(yōu)位置和自身經(jīng)歷過的最優(yōu)位置上時(shí)，locp表示其位置比，見公式（19）：

則粒子pop[p]在第t+1代的慣性權(quán)重ωp可以表示為：

式（20）中ωinitial表示權(quán)重的初始值，一般設(shè)定為1。當(dāng)粒子處于種群最優(yōu)位置或自身經(jīng)歷過的最優(yōu)位置上時(shí)，其慣性權(quán)重保持不變，為上次移動(dòng)時(shí)的慣性權(quán)重。

4.5 算法步驟

Step1：初始化粒子群規(guī)模 popsize、迭代次數(shù)max_iter、慣性權(quán)重ω、加速度常數(shù)c1和c2等參數(shù)。

Step2：令t=1，初始化粒子群pop的狀態(tài)popt[p]和速度Vt[p]，并令Pind_best[p]=popt[p]，（p=1,2,...,popsize）。將處于最優(yōu)狀態(tài)的粒子popt[p]賦給Pg_best。

Step3：計(jì)算每個(gè)粒子popt[p]的適應(yīng)度Fpopt[p]。

Step4：對每個(gè)粒子，若其適應(yīng)度Fpopt[p]＞FPind_best[p]，則令 Pind_best[p]=popt[p] ；若 Fpopt[p]＞FPg_best，則 令 Pg_best= popt[p]。

Step5：令t=t+1，若t＞max_iter，則終止迭代，否則，根據(jù)公式（16）—（20）更新每個(gè)粒子的狀態(tài)。

Step6：進(jìn)行元素取值范圍判斷。若更新后的粒子元素Ge1,Ge2,…,Gen部分取值超過區(qū)間(1,m+1)，則隨機(jī)產(chǎn)生一個(gè)位于區(qū)間(1,m+1)的實(shí)數(shù)，取代該元素。若t1,t2,…,tm部分的元素超過區(qū)間(a0,b0)，則隨機(jī)產(chǎn)生一個(gè)位于(a0,b0)的實(shí)數(shù)，取代該元素。

Step7：進(jìn)行約束條件判斷。若滿足約束條件（4）和（5），則該粒子可行，返回Step3；否則，按照4.3所述對粒子進(jìn)行修正，并返回Step3。

5 仿真實(shí)例

本文以一個(gè)含20個(gè)客戶、4輛車的模糊VRP問題為例進(jìn)行仿真，部分?jǐn)?shù)據(jù)如車輛運(yùn)載能力、各節(jié)點(diǎn)之間的距離和旅行時(shí)間、各客戶的時(shí)間窗口來源于文獻(xiàn)[19]，部分?jǐn)?shù)據(jù)如模糊需求、模糊卸貨時(shí)間基于假設(shè)，見表3，置信水平α和β均為0.6。（1）實(shí)驗(yàn)結(jié)果。利用Matlab進(jìn)行仿真實(shí)驗(yàn)，仿真參數(shù)如下：粒子群規(guī)模 popsize=100、迭代次數(shù)max_iter=1 000、加速度常數(shù)c1=1.5、c2=1.5。最大慣性權(quán)重ωmax=1、最小慣性權(quán)重ωmin=0.1。經(jīng)過Matlab 7.0編程，慣性權(quán)重采用自適應(yīng)權(quán)重調(diào)整法時(shí)得到問題的最優(yōu)解為：

表3 各客戶的模糊需求、模糊卸貨時(shí)間(單位：min)

該編碼進(jìn)行解碼，得到其對應(yīng)的配送方案為：

車輛1的行駛路線為：0-7-12-5-15-14-6-13-0，服務(wù)的客戶數(shù)量為7，其出發(fā)時(shí)間為8.332 6；車輛2的行駛路線為：0-3-9-18-1-11-16-2-0，服務(wù)的客戶數(shù)量為7，其出發(fā)時(shí)間為8.395 2；車輛3不執(zhí)行任務(wù)；車輛4的行駛路線為：0-4-17-19-20-10-8-0，服務(wù)的客戶數(shù)量為6，其出發(fā)時(shí)間為8.248 3。該配送方案對應(yīng)的總行駛里程為740。

圖4為粒子群算法1 000次迭代后總行駛里程的迭代示意圖。

圖4 總行駛里程迭代結(jié)果

（2）對比分析。將本文所提的算法與傳統(tǒng)的遺傳算法、模擬退火算法進(jìn)行對比，在種群規(guī)模均為100，迭代次數(shù)均為1 000的前提下，平均運(yùn)行10次，統(tǒng)計(jì)各種算法運(yùn)行10次所取得的最優(yōu)值、平均值、均方差以及獲取最優(yōu)解時(shí)的平均迭代次數(shù)，見表4。

表4 本文算法與遺傳算法、模擬退火算法的比較

表4中算法1為慣性權(quán)重采用線性權(quán)重調(diào)整的粒子群算法，算法2為慣性權(quán)重采用自適應(yīng)權(quán)重調(diào)整的粒子群算法。從表4可以看出，本文所提算法1略優(yōu)于遺傳算法，但遜于模擬退火算法，主要原因是由于慣性權(quán)重采用線性調(diào)整，且是針對整個(gè)粒子群的，即在一次迭代中，每個(gè)粒子都使用相同的慣性權(quán)重，此方法還不能較好地反映算法的動(dòng)態(tài)性能。算法2的結(jié)果最優(yōu)，這得益于該算法采用慣性權(quán)重自適應(yīng)調(diào)節(jié)的策略，每個(gè)粒子在選擇下一時(shí)刻的飛行速度時(shí)，根據(jù)其當(dāng)前速度和位置、所在環(huán)境等因素自動(dòng)調(diào)節(jié)，且每個(gè)粒子的慣性權(quán)重不一樣，這能更好地保證種群的多樣化，能在更大范圍內(nèi)搜索到最優(yōu)解。

6 結(jié)束語

本文考慮了一類車輛旅行時(shí)間、卸貨時(shí)間和客戶需求量均為模糊變量的VRP問題，在該問題中假設(shè)車輛到達(dá)客戶處時(shí)，不管到達(dá)時(shí)間是否處于時(shí)間窗口內(nèi)，均立即卸貨，基于此假設(shè)，建立了基于可信性測度的模糊機(jī)會(huì)約束規(guī)劃模型，并用改進(jìn)的粒子群算法進(jìn)行優(yōu)化。最后給出了仿真實(shí)驗(yàn)，通過仿真實(shí)驗(yàn)證明，該算法對于解決此類模糊VRP問題是行之有效的。

[1]Dantzing G,Ramser J.The truck dispatching problem[J].Management Science,1959,10(6):80-91.

[2]Teodorovic D,et al.The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain[J]. Fuzzy Sets and Systems,1996,82:307-317.

[3]祝崇雋,劉民,吳澄,等.針對模糊需求的VRP的兩種2-OPT算法[J].電子學(xué)報(bào),2001,29(8):1-2.

[4]張建勇,郭耀煌,李軍.模糊需求信息條件下的車輛路徑問題研究[J].系統(tǒng)工程學(xué)報(bào),2004,19(1):74-78.

[5]張建勇,李軍.模糊車輛路徑問題的一種混合遺傳算法[J].管理工程學(xué)報(bào),2005,19(2):23-26.

[6]張建勇,李軍.模糊需求VRP的一種Sweeping啟發(fā)式算法[J].中國管理科學(xué),2007,15(10):71-75.

[7]曹二保,賴明勇,張漢江.模糊需求車輛路徑問題研究[J].系統(tǒng)工程,2007,25(11):14-18.

[8]曹二保,賴明勇,李董輝.基于混合差分進(jìn)化算法的模糊需求車輛路徑問題[J].系統(tǒng)工程理論與實(shí)踐,2009,29(2):106-113. [9]戎麗霞.模糊需求條件下車輛路徑問題的模糊模擬[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(18):209-210.

[10]吳天羿,許繼恒.基于混合遺傳算法的模糊需求車輛路徑問題[J].解放軍理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,15(5):475-482.

[11]Lian Xue.Fuzzy Simulation on the Vehicle Routing Problem[J]. Information Technology Journal,2013,12(21):6 098-6 102.

[12]R J Kuo,Ferani E,Zulvia,Kadarsah Suryadi.Hybrid particle swarm optimization with genetic algorithm for solving capacitated vehicle routing problem with fuzzy demand A case study on garbage collection system[J].Applied Mathematics and Computation,2012,219:2 574-2 588.

[13]Cao Erbao,Lai Ming yong.The open vehicle routing problem with fuzzy demands[J].Expert Systems with Application,2010, 37(3):2 405-2 411.

[14]Yang Peng,Ye-mei Qian.A particle swarm optimization to vehicle routing problem with fuzzy demands[J].Journal of Convergence Information Technology,2010,8(5).

[15]Zheng Y,Liu B.Fuzzy vehicle routing model with credibility measure and its hybrid intelligent algorithm[J].Applied Mathematics and Computation.2006,176:673-683.

[16]Ghannadpour,S F,Noori S,Tavakkoli-Moghaddam R.Multiobjective Dynamic Vehicle Routing Problem With Fuzzy Travel Times and Customers’Satisfaction in Supply Chain Management[J].IEEE Transactions on Engineering Management, 2013,60(4).

[17]Jianyong Zhang.A hybrid genetic algorithm to the vehicle routing problem with fuzzy cost coefficients[A].11th International Conference on Fuzzy Systems and Knowledge Discovery[C].2014 147-152.

[18]Seyed Farid Ghannadpour,Siamak Noori,Reza Tavakkoli-Moghaddam.Multiobjective dynamic vehicle routing problem with fuzzy travel times and customers’satisfaction in supply chain management[J].IEEE transactions on engineering management,2013,(4):777-790.

[19]劉寶碇，趙瑞清，王綱.不確定規(guī)劃及應(yīng)用[M].北京:清華大學(xué)出版社.2003.

[20]吳斌.車輛路徑問題的粒子群算法研究與應(yīng)用[D].杭州:浙江工業(yè)大學(xué),2007.

Study on VRP with Fuzzy Time and Demand Based on Modified Particle Swarm A lgorithm

Zhu Hao
(Huzhou Vocational &Technical College,Huzhou 313000,China)

In this paper, in view of the vehicle routing problem where the vehicle traveling time, cargo unloading time and customer demand volume were all fuzzy, we built a fuzzy opportunity constraint programming model based on credibility measure, then used the modified particle swarm algorithm to optimize it, designed a special corrective operator for the infeasible solutions, and at the end, through a simulation example, proved the validity of this algorithm in the solution of similar fuzzy VRPs.

VRP; fuzzy traveling time; fuzzy demand volume; particle swarm algorithm

F224.0

A

1005-152X(2017)04-0084-06

2017-03-06

湖州市自然科學(xué)基金（2015YZ07）

朱顥（1980－），男，講師，碩士，研究方向：車輛路徑問題。

doi∶10.3969/j.issn.1005-152X.2017.04.020