張慶華，吳光譜

（北京科技大學(xué)機(jī)械工程學(xué)院，北京100083）

（?通信作者電子郵箱zqhustb@163.com）

0 引言

近年來(lái)，我國(guó)經(jīng)濟(jì)迅速發(fā)展，人們對(duì)現(xiàn)代物流的服務(wù)要求也逐漸增多，從以往的僅僅只有收寄快遞的需求，逐步發(fā)展到包含定點(diǎn)配送、上門攬件、同城配送、準(zhǔn)時(shí)服務(wù)等多元化的物流需求。隨著逆向物流導(dǎo)致客戶退換貨的增多，上門取件逐漸成為了物流服務(wù)中必不可少的一環(huán)。帶時(shí)間窗的同時(shí)取送貨車輛路徑問題（Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows，VRPSPDTW）也隨之備受關(guān)注。

VRPSPDTW 是在經(jīng)典車輛路徑問題（Vehicle Routing Problem，VRP）的基礎(chǔ)上，增加了時(shí)間窗約束，車輛必須在客戶指定的時(shí)間窗內(nèi)對(duì)客戶進(jìn)行服務(wù)；同時(shí)還在為客戶進(jìn)行配送的基礎(chǔ)上，增加了取貨服務(wù)，車輛不僅要對(duì)客戶進(jìn)行配送服務(wù)，還要對(duì)在客戶所在的位置進(jìn)行取貨，將客戶所要寄送的貨物運(yùn)回配送中心。

同時(shí)取送貨問題（Vehicle Routing Problem with Simultaneous Pickup-Delivery，VRPSPD）由Min［1］于1989 年首次提出；而VRPSPDTW 則由Angelelli 等［2］在2002 提出，并使用精確算法進(jìn)行求解；Wang 等［3］使用遺傳算法（Genetic Algorithm，GA）對(duì)VRPSPDTW 進(jìn)行了求解，并在Solomon 測(cè)試算例［4］的基礎(chǔ)上設(shè)計(jì)了測(cè)試算例；Liu 等［5］采用了遺傳算法和模擬退火算法求解家庭醫(yī)療物流的VRPSPDTW；Wang 等［6］提出一種并行的模擬退火算法，對(duì)大規(guī)模的VRPSPDTW 進(jìn)行了求解；王超等［7］采用離散布谷鳥搜索（Discrete Cuckoo Search，DCS）算法對(duì)VRPSPDTW 求解，并取得了較好的效果。

模因算法（Memetic Algorithm，MA）最早是由Moscato［8］提出的一種模擬文化進(jìn)化的算法。遺傳算法中的變異操作是隨機(jī)的，在成千上萬(wàn)的變異操作中找到對(duì)適應(yīng)度有所提升的解非常困難。而模因算法又稱文化基因算法，模擬的是文化進(jìn)化的過程，對(duì)于文化基因而言，基因總是向著前進(jìn)的方向發(fā)展，基因的傳播過程是在上一代基因中嚴(yán)格復(fù)制的，子代在繼承父代優(yōu)秀基因的同時(shí)，對(duì)子代變異操作不是隨機(jī)的，而是在大量知識(shí)的基礎(chǔ)上，向更好的方向發(fā)展的。

國(guó)內(nèi)對(duì)模因算法的研究較少，而國(guó)外采用模因算法解決的一般是帶時(shí)間窗的車輛路徑問題（Vehicle Routing Problem with Time Windows，VRPTW），如Nagata 等［9］提出了一種基于懲罰函數(shù)的邊界組合模因算法，以求解VRPTW；Nalepa 等［10］采用自適應(yīng)參數(shù)的模因算法對(duì)VRPTW 進(jìn)行了求解。目前國(guó)內(nèi)外采用模因算法解決VRPSPDTW 的文獻(xiàn)較少，本文采用基于引導(dǎo)彈射搜索（Guided Ejection Search，GES）［11］和邊界組合交叉的模因算法對(duì)VRPSPDTW 求解，通過GES 進(jìn)行初始種群生成，采用多種鄰域結(jié)構(gòu)提升算法的搜索效率，同時(shí)與多種算法進(jìn)行比較，驗(yàn)證了本文提出的模因算法的有效性。

1 帶時(shí)間窗的同時(shí)取送貨車輛路徑問題

1.1 問題描述

VRPSPDTW 是在傳統(tǒng)車輛路徑問題上引入時(shí)間窗，將客戶需要服務(wù)的時(shí)間標(biāo)示出來(lái)，在客戶能夠接受的時(shí)間內(nèi)進(jìn)行配送或取貨，從而提高物流服務(wù)水平和服務(wù)質(zhì)量。因此，本文針對(duì)帶時(shí)間窗的同時(shí)取送貨車輛路徑問題進(jìn)行模型構(gòu)建和求解。

VRPSPDTW 研究一隊(duì)車輛從配送中心出發(fā)對(duì)一系列客戶進(jìn)行配送和取貨服務(wù)，要求對(duì)路徑進(jìn)行合理規(guī)劃，在滿足時(shí)間窗約束和車輛載重約束的前提下，使配送成本最小。本文研究的VRPSPDTW 描述如下:

1）研究若干車輛由配送中心向客戶配送物品，車輛對(duì)客戶除了配送貨物，還可能要從客戶位置取走貨，物配送中心和客戶的地理位置以及客戶的貨物量已知。

2）車輛從配送中心出發(fā)并最終返回配送中心，在配送的過程中每個(gè)客戶只被訪問一次，并滿足該客戶的配送需求或取貨需求，車輛所裝載的貨物在任何時(shí)刻都不能超過車輛自身載重。關(guān)鍵時(shí)間節(jié)點(diǎn)在車輛從配送中心出發(fā)時(shí)和在客戶位置取貨后。

3）每個(gè)客戶有自身所要求的時(shí)間窗，包括最早開始服務(wù)時(shí)間、最晚開始服務(wù)時(shí)間、服務(wù)時(shí)間。

4）車輛對(duì)客戶進(jìn)行配送的過程中，到達(dá)客戶所在位置的時(shí)間不能晚于最晚開始服務(wù)時(shí)間，但可以早于最早開始服務(wù)時(shí)間。若早于最早開始服務(wù)時(shí)間，則車輛需要在客戶位置進(jìn)行等待，直到最早開始服務(wù)時(shí)間，才能進(jìn)行配送或取貨服務(wù)。

5）若一位客戶同時(shí)具有配送需求和取貨需求，則對(duì)該客戶進(jìn)行服務(wù)時(shí)，先進(jìn)行卸貨，再進(jìn)行裝貨。

因此，本文研究的VRPSPDTW 是某配送中心向一定數(shù)量的客戶提供配送服務(wù)，配送中心具有若干車輛，車輛具有相同的最大承載能力，配送中心與各個(gè)客戶之間的距離和行駛時(shí)間已知，每個(gè)客戶具有固定的配送需求和取貨需求；同時(shí)客戶要求有固定的時(shí)間窗，包括最早開始服務(wù)時(shí)間、最晚開始服務(wù)時(shí)間、服務(wù)時(shí)間。每輛車為若干個(gè)客戶提供服務(wù)，只能在客戶所要求的時(shí)間窗內(nèi)對(duì)客戶進(jìn)行服務(wù)，若車輛在客戶所要求的最早服務(wù)時(shí)間之前到達(dá)，則需要進(jìn)行等待至最早服務(wù)時(shí)間，才能進(jìn)行服務(wù)。要求在滿足時(shí)間窗約束和車輛載重約束的前提下，對(duì)每個(gè)客戶完成所需要服務(wù)。

本文所研究的問題主要目標(biāo)是使車隊(duì)的規(guī)模最小，即所使用的車輛數(shù)最少；次要目標(biāo)是車輛配送的總距離最短。

1.2 模型構(gòu)建

根據(jù)以上對(duì)VRPSPDTW 的描述，構(gòu)建合理的數(shù)學(xué)模型，模型參數(shù)定義如下:

K:配送中心進(jìn)行服務(wù)的車輛集合。

M:所有需要提供服務(wù)的客戶總量。

Q:車輛的最大載重限制。

V:配送中心和所有需要提供服務(wù)的客戶集合。

Vi，i ∈{1，2，…，M}:所有需要提供服務(wù)的客戶。

V0:配送中心。

di，i ∈{1，2，…，M}:客戶i對(duì)應(yīng)的配送量。

pi，i ∈{1，2，…，M}:客戶i對(duì)應(yīng)的取貨量。

si，i ∈{1，2，…，M}:客戶i對(duì)應(yīng)的服務(wù)時(shí)間。

s0:車輛在配送中心的服務(wù)時(shí)間，一般s0= 0。

ei，i ∈{1，2，…，M}:客 戶i 可 以 接 受 開 始 服 務(wù) 的 最 早時(shí)間。

e0:車輛從配送中心離開的最早時(shí)間。

li，i ∈{1，2，…，M}:客 戶i 可 以 接 受 開 始 服 務(wù) 的 最 晚時(shí)間；

l0:車輛返回配送中心的最晚時(shí)間。

cij（i ≠j），i ∈{0，1，…，M}，j ∈{0，1，…，M}:客戶或配送中心i與客戶或配送中心j之間的車輛行駛距離。

tij（i ≠j），i ∈{0，1，…，M}，j ∈{0，1，…，M}:客 戶 或 配 送中心i與客戶或配送中心j之間的車輛行駛時(shí)間。

ai，i ∈{1，2，…，M}:車輛到達(dá)客戶i處時(shí)刻。

a0:車輛到達(dá)配送中心的時(shí)刻，一般a0= e0。

wi，i ∈{1，2，…，M}:車輛在客戶i處等待的時(shí)間。

oij，i ∈{1，2，…，M}，k ∈K:車輛k在離開客戶i時(shí)，車輛的裝載量。

o0k:車輛k在離開配送中心時(shí)的裝載量。

X(i，j，k)（i ≠j），i ∈{1，2，…，M}，j ∈{1，2，…，M}，k ∈K:表示在車輛k 在執(zhí)行配送或取貨任務(wù)時(shí)，是否由客戶i駛向客戶j。X(i，j，k)= 1 表示車輛k 對(duì)客戶i 進(jìn)行服務(wù)后，隨即對(duì)客戶j 進(jìn)行服務(wù)。X(i，j，k)= 0表示車輛k對(duì)客戶i進(jìn)行服務(wù)后，下一個(gè)服務(wù)對(duì)象不是客戶j。

根據(jù)上述參數(shù)，建立數(shù)學(xué)模型如下:

其中:式（1）表示首要目標(biāo)函數(shù)，即車輛數(shù)最少；式（2）表示次要目標(biāo)函數(shù)，即車輛行駛的總路徑最短；式（3）表示每個(gè)客戶只被服務(wù)一次；式（4）表示車輛需要從配送中心出發(fā)，并最終返回配送中心，即起始點(diǎn)和終止點(diǎn)均為配送中心；式（5）表示從配送中心出發(fā)的總車輛數(shù)為K，即配送車輛數(shù)為K；式（6）表示車輛k 在離開配送中心時(shí)的裝載量，即配送路線上所有客戶的配送量之和；式（7）表示車輛k 在離開各個(gè)客戶時(shí)的裝載量，等于離開上一個(gè)客戶時(shí)的裝載量減去在本客戶位置的接收量，再加上本客戶的寄送量；式（8）表示車輛在任何時(shí)刻，所裝載貨量都不超過車輛最大載重限制；式（9）表示時(shí)間窗符合要求；式（10）表示車輛在對(duì)上一位客戶服務(wù)之后，能及時(shí)到達(dá)下一個(gè)客戶所在位置，即上一個(gè)客戶在車輛到達(dá)時(shí)刻的基礎(chǔ)上，加上等待時(shí)間、服務(wù)時(shí)間和路程耗費(fèi)時(shí)間之和不晚于下一個(gè)客戶的最晚服務(wù)開始時(shí)間，同時(shí)客戶的最早開始服務(wù)的時(shí)間也不能晚于最晚開始服務(wù)的時(shí)間；式（11）表示車輛在對(duì)最后一位客戶服務(wù)之后，能及時(shí)返回配送中心。

2 求解VRPSPDTW 的模因算法設(shè)計(jì)

2.1 模因算法主流程

模因算法的運(yùn)算過程中，首先生成一個(gè)初始種群，然后對(duì)種群進(jìn)行進(jìn)化，進(jìn)化過程是在上一代個(gè)體進(jìn)行交叉后，對(duì)所產(chǎn)生的子代通過鄰域搜索等操作進(jìn)行教育，選出優(yōu)于父代的個(gè)體進(jìn)行繼承。相對(duì)于遺傳算法，模因算法的方向更加明確，收斂速度和求解效果都有大幅提高［12］。

本文所研究的模因算法包括初始種群生成算法和種群進(jìn)化算法，首先對(duì)初始種群進(jìn)行生成，然后對(duì)種群中的個(gè)體逐代進(jìn)行交叉、修復(fù)、教育等操作，實(shí)現(xiàn)種群的進(jìn)化過程，最終得到滿意解。本文模因算法總流程見圖1。

圖1 模因算法流程Fig. 1 Flowchart of memetic algorithm

2.2 初始種群生成

首先，采用整數(shù)編碼［13］的方式對(duì)帶時(shí)間窗的車輛路徑問題進(jìn)行編碼，對(duì)于一個(gè)可行解而言，其中包含多個(gè)車輛運(yùn)輸路徑，每輛車只對(duì)一條路徑上的客戶進(jìn)行服務(wù)。使用1～m 表示每個(gè)客戶的編號(hào)，1～k 表示每輛車的編號(hào)，每條路徑使用一個(gè)整型向量進(jìn)行表示，表示一輛車從配送中心出發(fā)，對(duì)所有客戶進(jìn)行服務(wù)后，再次返回到配送中心。每一個(gè)解中對(duì)應(yīng)k 條路徑。由于每個(gè)客戶只接受一次服務(wù)，因此路徑中不存在重復(fù)的客戶編號(hào)。編碼結(jié)構(gòu)如圖2所示。

圖2 編碼結(jié)構(gòu)Fig. 2 Coding structure

初始種群生成時(shí)，采用引導(dǎo)彈射搜索（Guided Ejection Search，GES）［11］進(jìn)行種群生成。首先制定一個(gè)基本解，基本解中包含與客戶數(shù)目相同的數(shù)量的車輛，每輛車只對(duì)一個(gè)客戶進(jìn)行服務(wù)，而后逐步減少路線，將每條路線上的客戶插入到其他路線中去，直到求出車輛數(shù)較小且不違反約束的初始解。通過生成多個(gè)初始解，產(chǎn)生一個(gè)初始種群。

2.2.1 初始種群生成算法流程

初始種群生成算法流程如圖3所示。

圖3 初始種群生成算法流程Fig. 3 Flowchart of initial population generation algorithm

首先設(shè)定一個(gè)初始種群，種群大小設(shè)定為N，初始種群中不包含任何個(gè)體；隨后通過一系列客戶插入、路徑壓縮、客戶彈出等操作生成可行初始解。逐個(gè)產(chǎn)生初始解，形成初始種群。

初始種群生成的算法偽碼如算法1 所示。依次對(duì)一個(gè)基本解循環(huán)進(jìn)行客戶插入、路徑壓縮、客戶彈出等操作，生成可行初始解。

通過多次生成初始解，逐步形成一個(gè)種群規(guī)模為N 的初始種群。

2.2.2 制定基本解

首先制定一個(gè)基本解，每一個(gè)客戶對(duì)應(yīng)一條路徑，即一輛車只對(duì)一個(gè)客戶進(jìn)行服務(wù)。此時(shí)，路徑的條數(shù)是最多的，與客戶數(shù)目相同，而后逐一減少路徑數(shù)目。

2.2.3 路徑刪除

此時(shí)，對(duì)具有多條路徑的解進(jìn)行操作。隨機(jī)選擇一條路線，將這條路線刪除，并將路線上的所有客戶加入到彈射池中。

2.2.4 插入客戶

對(duì)彈射池中的客戶使用后進(jìn)先出（Last In First Out，LIFO）的策略，從彈射池中選擇客戶，依次嘗試將客戶插入到其余路線的每一個(gè)位置中進(jìn)行檢驗(yàn)，若存在滿足車輛載重和時(shí)間窗約束的位置，則將該位置記為可行插入位置。統(tǒng)計(jì)所有的可行插入位置，選擇一個(gè)位置插入客戶，形成新的解。

若存在多個(gè)可行插入位置，可以采用就近原則進(jìn)行客戶插入，選擇將客戶插入到對(duì)應(yīng)的插入位置后，對(duì)原有路徑長(zhǎng)度的改變量最小的位置進(jìn)行插入。

若嘗試所有可行插入位置，找不到可行插入位置，則采用路徑壓縮方法進(jìn)行處理，對(duì)路徑進(jìn)行壓縮。

若通過路徑壓縮方法仍未得到可行解，則采用客戶彈出方法，嘗試將不可行的客戶插入后，彈出其他客戶到彈射池中，再進(jìn)行優(yōu)化。

若連續(xù)多代優(yōu)化后，彈射池中的客戶仍未減少到0，則回到該條路線刪除前的狀態(tài)，重新隨機(jī)選擇一條路線進(jìn)行刪除，若經(jīng)過Ireadmax次重復(fù)刪除后，仍無(wú)法找到更少路線的解，則以該條路線刪除前的解作為滿意解，或舍棄該解。

2.2.5 路徑壓縮

若一個(gè)客戶無(wú)法在不違反車輛載重約束和時(shí)間窗約束的情況下，插入到一個(gè)可行位置，則嘗試將該客戶插入到較為合適的位置后，對(duì)路線進(jìn)行鄰域搜索，找到不違反車輛載重和時(shí)間窗約束的鄰域解。

首先對(duì)客戶插入一個(gè)位置后的違反約束函數(shù)Fp進(jìn)行計(jì)算，違反約束函數(shù)計(jì)算公式如式（12）所示。

其中:Fp表示違反約束函數(shù)的值；Pc表示違反的載重約束，表示車輛在配送中心和客戶位置貨物超出車輛載重的和；Ptw表示違反的時(shí)間窗約束，即車輛到達(dá)客戶時(shí)間晚于客戶要求的最晚到達(dá)時(shí)間的時(shí)間段；α為比例系數(shù)。

查找鄰域中Fp更小的解，若能找到則在新解的基礎(chǔ)上繼續(xù)查找，直至找到Fp= 0的解，說明路徑壓縮成功。

若路徑壓縮失敗，則執(zhí)行客戶彈出方法。

2.2.6 客戶彈出

若路徑壓縮失敗，則允許將客戶插入到一個(gè)位置，同時(shí)彈出部分客戶到彈射池中，制定客戶最大彈出數(shù)量EJmax，使每次客戶最多彈出數(shù)目不超過EJmax。

在初始種群生成算法的初始階段，制定懲罰計(jì)數(shù)器p[vi]，i ∈{1，2，…，M}，懲罰計(jì)數(shù)器的值代表每個(gè)客戶嘗試插入或路徑壓縮失敗的次數(shù)，即該客戶插入到路線后能夠成為可行解的難度［11］。選擇彈出客戶懲罰函數(shù)之和最小的客戶組合進(jìn)行彈出，將彈出客戶放置到彈射池中，使彈出客戶懲罰函數(shù)Psum最小。

彈出客戶懲罰函數(shù)之和計(jì)算公式如式（13）所示，表示所有彈出客戶的重新插入路線形成可行解的難度之和。此舉可以保證在將部分客戶彈出之后，該部分客戶也較容易找到其他可行位置進(jìn)行插入。

2.2.7 終止條件

對(duì)于一個(gè)解的求解過程而言，連續(xù)Iinmax次客戶插入、路徑壓縮、客戶彈出操作后未使彈射池中所有客戶全部插入到已有路徑中，此時(shí)將返回最后一條路徑刪除前對(duì)應(yīng)的可行解。

設(shè)定初始種群大小為N，整個(gè)初始種群生成的終止條件設(shè)定為生成N個(gè)包含相同數(shù)量車輛路線的解。若連續(xù)Iinmax次客戶插入、路徑壓縮、客戶彈出操作失敗，則對(duì)該解停止優(yōu)化，并與之前的解進(jìn)行比較，若車輛路徑數(shù)目更多，則說明該解不是滿意解，舍棄該解；若該解與之前的解路徑數(shù)目相同，則將該解加入到初始種群中；若該解路徑數(shù)目更少，則說明該解為更優(yōu)解，此時(shí)清空初始種群中的所有解，將該解加入到初始種群中。

2.3 種群進(jìn)化

物種進(jìn)化的基本單位是種群，一個(gè)種群經(jīng)過個(gè)體之間的交配可以產(chǎn)生新的個(gè)體，模因算法是在普通的遺傳算法的基礎(chǔ)上，在新個(gè)體產(chǎn)生的同時(shí)，不僅可以繼承父代已接受的文化知識(shí)，還能通過教育，學(xué)習(xí)新的知識(shí)，使整個(gè)種群獲得更快的進(jìn)化速度。

產(chǎn)生初始種群之后，需要對(duì)初始種群的內(nèi)的個(gè)體進(jìn)行優(yōu)化，優(yōu)化目標(biāo)為產(chǎn)生車輛行駛總路徑S 更短的個(gè)體，車輛行駛總路徑的計(jì)算公式見式（14），表示所有配送車輛完成配送任務(wù)需行駛的路徑總和。

對(duì)種群中的個(gè)體通過選擇、交叉、修復(fù)、教育等一系列操作后，形成新的更優(yōu)秀的種群，作為下一代新種群。

首先對(duì)種群個(gè)體進(jìn)行選擇，確定新的個(gè)體交叉順序，隨后個(gè)體之間進(jìn)行交叉。

對(duì)于交叉過程而言，本文采用邊界組合交叉進(jìn)行個(gè)體之間的交叉。邊界組合交叉（Edge Assembly Crossover，EAX）最初由Nagata 等［14］提出，有向車輛路徑問題的邊界組合交叉能夠更好地繼承父代個(gè)體的子路徑，保持父代個(gè)體的基本結(jié)構(gòu)，從而能夠繼承父代的優(yōu)秀基因，產(chǎn)生更接近最優(yōu)解的新個(gè)體［15］。

在個(gè)體交叉結(jié)束后，對(duì)個(gè)體進(jìn)行修復(fù)、教育，以獲得更優(yōu)的個(gè)體。修復(fù)、教育的過程采用鄰域搜索的方法進(jìn)行。種群進(jìn)化算法的終止條件設(shè)定為連續(xù)Igemax的操作中種群中的最優(yōu)解未發(fā)生改善。種群進(jìn)化算法流程如圖4 所示:描述了一個(gè)初始種群個(gè)體經(jīng)過交叉、修復(fù)、教育等操作，得到最終解的過程。

種群進(jìn)化算法偽碼如算法2 所示。種群進(jìn)化過程中，首先對(duì)種群隨機(jī)重排，確定新的交叉順序，然后對(duì)所對(duì)應(yīng)的父代交叉?zhèn)€體進(jìn)行交叉操作，產(chǎn)生子個(gè)體，隨后對(duì)子個(gè)體進(jìn)行修復(fù)、教育。直到連續(xù)Igemax代個(gè)體未得到改善，輸出最終的解。

圖4 種群進(jìn)化算法流程Fig. 4 Flowchart of population evolution algorithm

2.3.1 選擇

本文的選擇過程不對(duì)種群中的個(gè)體進(jìn)行舍棄，而是通過對(duì)個(gè)體進(jìn)行隨機(jī)重新排序來(lái)改變個(gè)體之間的交叉順序［16］。首先將種群進(jìn)行隨機(jī)排列。如原種群經(jīng)過隨機(jī)排列后得到種群為{ p1，p2，…，pn}，其中p1，p2，…，pn代表每個(gè)種群中的各個(gè)可行解，即交叉操作中的父代個(gè)體。則父代個(gè)體之間的交叉順序 設(shè) 定 為EAX(p1，p2)，EAX(p2，p3)，… ，EAX(pn-1，pn)，EAX(pn，p1)。

2.3.2 交叉

按照所生成的交叉順序使逐個(gè)相鄰個(gè)體進(jìn)行交叉。邊界組合交叉算法中，首先選擇兩個(gè)父代個(gè)體pa和pb，將父代個(gè)體進(jìn)行路線合并，同時(shí)刪除重復(fù)的路徑，再對(duì)合并后的路徑進(jìn)行拆分，拆分為多個(gè)子路徑。隨后選擇一條或多條子路徑，替換到第一個(gè)父?jìng)€(gè)體pa中，此時(shí)部分子路徑可能是不經(jīng)過配送中心的，若存在不經(jīng)過配送中心的子路徑，則對(duì)該個(gè)體進(jìn)行路徑修復(fù)，修復(fù)后得到新的子個(gè)體。邊界組合交叉示意圖如圖5所示。

圖5 邊界組合交叉示例圖Fig. 5 EAX sample diagram

2.3.3 修復(fù)、教育

邊界組合交叉完成后，得到新的子個(gè)體，但是新的子個(gè)體可能是違反車輛載重約束或時(shí)間約束的，即新個(gè)體可能是不可行的。此時(shí)，需要對(duì)子個(gè)體進(jìn)行修復(fù)操作［10］，恢復(fù)子個(gè)體的可行性。在修復(fù)的過程中，采用鄰域搜索的方法進(jìn)行解的修復(fù)，鄰域搜索采用In-relocate 算子（圖6（a））、Out-relocate 算子（圖6（b））、In-exchange 算子（圖6（c））、Out-exchange 算子（圖6（d））進(jìn)行搜索。對(duì)當(dāng)前解對(duì)應(yīng)的鄰域進(jìn)行搜索，查找鄰域中違反約束函數(shù)Fp更小的個(gè)體，若找到Fp更小的個(gè)體，則在新個(gè)體的基礎(chǔ)上繼續(xù)進(jìn)行搜索，直至找到違反約束函數(shù)Fp= 0的個(gè)體或找不到具有更小違反約束函數(shù)Fp的個(gè)體。使用新形成的解替換之前的子個(gè)體，形成新的子個(gè)體。若無(wú)法找到不違反約束的解，則將該子個(gè)體舍棄。

修復(fù)完成后，若得到的解是可行解，需要對(duì)子個(gè)體進(jìn)行教育［10］。教育的目的是為得到更優(yōu)的個(gè)體，即車輛行駛總路徑S 更短的解。教育的過程中，仍然是采用鄰域搜索的方法，除上述四種算子之外，還采用2-opt*算子［17］（圖6（e））進(jìn)行搜索。對(duì)當(dāng)前解對(duì)應(yīng)的鄰域進(jìn)行搜索，查找鄰域中車輛行駛總路徑S更短的個(gè)體，若找到S更小的個(gè)體，將在該個(gè)體的基礎(chǔ)上，重新對(duì)新個(gè)體的鄰域進(jìn)行搜索，直到鄰域中找不到車輛行駛總路徑S更短的個(gè)體。將新形成的解作為教育后的子個(gè)體。

每次交叉完成后，對(duì)子個(gè)體pc經(jīng)過修復(fù)、教育。此時(shí)，若新的子個(gè)體pc不違反車輛載重約束和時(shí)間窗約束，并且pc的車輛行駛總路徑小于邊界組合交叉的第一個(gè)父?jìng)€(gè)體pa的行駛總路徑，則使用pc替換掉第一個(gè)父?jìng)€(gè)體，直至所有交叉進(jìn)行完成。

圖6 算子示意圖Fig. 6 Schematic diagram of operators

2.3.4 終止條件

終止條件設(shè)定為連續(xù)Igemax的操作中種群中的最優(yōu)解未得到改善。進(jìn)化終止后，選取種群中車輛行駛總路徑最短的個(gè)體作為最終解。

3 算例實(shí)驗(yàn)與分析

3.1 測(cè)試環(huán)境和參數(shù)確定

本文模因算法使用Java 語(yǔ)言進(jìn)行編寫，算法運(yùn)行環(huán)境采用Intel Core i5-3230M CPU@2.60 GHz（8.00 GB 內(nèi) 存），Windows 10 x64操作系統(tǒng)。

由于本文模因算法求解過程分兩階段進(jìn)行，因此初始種群生成算法和種群進(jìn)化算法的參數(shù)可以分別進(jìn)行確定。

初始種群生成過程中，需要確定的參數(shù)包括:客戶最大彈出數(shù)量EJmax；客戶彈出失敗后重復(fù)刪除次數(shù)Ireadmax；最大連續(xù)迭代次數(shù)Iinmax。以計(jì)算得到滿足標(biāo)準(zhǔn)車輛數(shù)的可行解所耗費(fèi)的時(shí)間作為評(píng)價(jià)因素，所耗時(shí)間越少，說明得到初始種群速度越快，以重復(fù)三次實(shí)驗(yàn)的平均值作為評(píng)價(jià)指標(biāo)。初始種群生成中的參數(shù)確定包含3 個(gè)參數(shù)，采用三因子三水平實(shí)驗(yàn)，選用正交表L9(34)進(jìn)行實(shí)驗(yàn)。確定初始種群生成的過程中，最優(yōu)參數(shù)組合為EJmax=4，Ireadmax=10，Iinmax=10。

種群進(jìn)化過程中需要確定的參數(shù)包括種群規(guī)模N；連續(xù)多代未發(fā)生優(yōu)化的終止迭代次數(shù)Igemax。以計(jì)算結(jié)合和程序運(yùn)行實(shí)驗(yàn)為評(píng)價(jià)因素，實(shí)驗(yàn)需要確定的參數(shù)較少，采取固定一個(gè)參數(shù)，調(diào)整另一個(gè)參數(shù)的方法對(duì)參數(shù)進(jìn)行確定實(shí)驗(yàn)。確定種群進(jìn)化過程參數(shù)設(shè)置為N=40，Igemax=50。

算例實(shí)驗(yàn)過程中，為保證算法的準(zhǔn)確性，對(duì)每個(gè)算例進(jìn)行3次實(shí)驗(yàn)，取3次的最優(yōu)值作為實(shí)驗(yàn)結(jié)果。

3.2 小規(guī)模客戶算例實(shí)驗(yàn)

為測(cè)試本文模因算法計(jì)算小規(guī)?？蛻魩r(shí)間窗的同時(shí)取送貨問題的性能，本文采用Wang 等［3］的小規(guī)模標(biāo)準(zhǔn)算例進(jìn)行實(shí)驗(yàn)。小規(guī)模標(biāo)準(zhǔn)算例包括10 個(gè)客戶規(guī)模、25 個(gè)客戶規(guī)模、50 個(gè)客戶規(guī)模的算例各三個(gè)。在滿足車輛載重約束和時(shí)間窗約束的條件下進(jìn)行實(shí)驗(yàn)，將實(shí)驗(yàn)結(jié)果與Wang 等［3］設(shè)計(jì)的遺傳 算 法（GA）、Wang 等［6］設(shè) 計(jì) 的 并 行 模 擬 退 火（parallel-Simulated Annealing，p-SA）算法、王超等［7］設(shè)計(jì)的離散布谷鳥搜索（Discrete Cuckoo Search，DCS）算法取得的最優(yōu)實(shí)驗(yàn)結(jié)果進(jìn)行比較。

實(shí)驗(yàn)對(duì)比結(jié)果如表1 所示，四種算法實(shí)驗(yàn)結(jié)果中，NV 和TD 分別表示配送車輛數(shù)和配送總路徑，加粗的結(jié)果代表本文算法取得的最優(yōu)解。分析發(fā)現(xiàn)，本文模因算法可以求得全部9 個(gè)小顧客規(guī)模算例的已知最優(yōu)車輛和最短路徑，驗(yàn)證了本算法在求解小規(guī)?？蛻魩r(shí)間窗的同時(shí)取送貨問題的有效性。

表1 小規(guī)?？蛻羲憷龑?shí)驗(yàn)結(jié)果對(duì)比Tab. 1 Comparison of experimental results of small-scale customer examples

3.3 標(biāo)準(zhǔn)規(guī)?？蛻羲憷龑?shí)驗(yàn)

為測(cè)試本文模因算法計(jì)算標(biāo)準(zhǔn)規(guī)?？蛻魩r(shí)間窗的同時(shí)取送貨問題的性能，本文采用Wang 等［3］的標(biāo)準(zhǔn)規(guī)模算例進(jìn)行實(shí)驗(yàn)。隨機(jī)選取10 個(gè)算例進(jìn)行實(shí)驗(yàn)，每個(gè)算例包括100 個(gè)客戶。

在滿足車輛載重約束和時(shí)間窗約束的條件下進(jìn)行實(shí)驗(yàn)，將實(shí)驗(yàn)結(jié)果與GA［3］、p-SA［6］、DCS［7］取得的最優(yōu)實(shí)驗(yàn)結(jié)果進(jìn)行比較。實(shí)驗(yàn)對(duì)比結(jié)果如表2所示，4種算法實(shí)驗(yàn)結(jié)果中，NV 和TD 分別表示配送車輛數(shù)和配送總路徑，加粗的結(jié)果代表本算法更新或取得的最優(yōu)解。

表2 標(biāo)準(zhǔn)規(guī)?？蛻羲憷龑?shí)驗(yàn)結(jié)果對(duì)比Tab. 2 Comparison of experimental results of standard-scale customer examples

對(duì)結(jié)果進(jìn)行分析，發(fā)現(xiàn)在10個(gè)標(biāo)準(zhǔn)算例中，算例Rdp103、Rdp201、Rdp206、Cdp107、Rcdp201 共5 個(gè)算例更新了當(dāng)前最優(yōu)解；算例Cdp201、Cdp205 共2 個(gè)算例取得了與當(dāng)前最優(yōu)解相同的結(jié)果；僅有1 個(gè)算例未取得比其余三種算法更優(yōu)的結(jié)果。

為更直觀地展示本文實(shí)驗(yàn)結(jié)果，選取Rdp103算例實(shí)驗(yàn)結(jié)果生成配送路線圖，路線如圖7 所示。由于本實(shí)驗(yàn)車輛配送時(shí)間完全按照客戶要求的時(shí)間窗進(jìn)行配送，并且嚴(yán)格滿足車輛的載重要求，因此路線中會(huì)出現(xiàn)部分交叉的情況，但路線圖整體取得了較好的結(jié)果。

圖7 Rdp103算例配送路線Fig. 7 Delivery route of Rdp103 example

本文采取通過建立合適的數(shù)學(xué)模型，采用基于引導(dǎo)彈射搜索和邊界組合交叉的模因算法，使用彈射池方法生成初始解，大幅度提升了初始解的質(zhì)量，同時(shí)在種群進(jìn)化過程中，采用EAX 對(duì)父代個(gè)體進(jìn)行交叉，保留了父代個(gè)體的優(yōu)良基因，采用多種算子對(duì)種群中的解進(jìn)行修復(fù)、教育，提升了鄰域搜索的廣度。算例實(shí)驗(yàn)中，對(duì)于更新了當(dāng)前最優(yōu)解的5 個(gè)算例結(jié)果而言，其中Rcdp201 算例對(duì)當(dāng)前最優(yōu)解有超過5%的提升，Rdp201 對(duì)當(dāng)前最優(yōu)解有約2%的提升，Rdp206 對(duì)當(dāng)前最優(yōu)解有超過1%的提升。本文算法更新或達(dá)到最優(yōu)解的算例占測(cè)試算例的70%，其中50%的算例更新了最優(yōu)解，充分說明了本文模因算法在求解標(biāo)準(zhǔn)規(guī)?？蛻魩r(shí)間窗的同時(shí)取送貨問題的有效性。

4 結(jié)語(yǔ)

為迎合現(xiàn)代物流發(fā)展，解決帶時(shí)間窗的同時(shí)取送貨車輛路徑問題，本文建立了相應(yīng)的車輛路徑問題模型，并使用基于引導(dǎo)彈射搜索和邊界組合交叉的模因算法對(duì)問題進(jìn)行求解。在算法求解過程中分兩階段進(jìn)行求解，首先使用GES 方法生成初始種群，隨后在種群進(jìn)化的過程中采用EAX 交叉產(chǎn)生子代，同時(shí)使用多種鄰域結(jié)構(gòu)對(duì)子代進(jìn)行修復(fù)教育，以得到更合理的路徑。使用本文模因算法對(duì)Wang 等［3］提出的標(biāo)準(zhǔn)算例進(jìn)行算例實(shí)驗(yàn)，得到了較好的求解結(jié)果，驗(yàn)證了本文模因算法的有效性。

現(xiàn)代物流的發(fā)展不僅會(huì)面臨同時(shí)取送貨問題，還會(huì)面臨諸如搬家服務(wù)之類的帶時(shí)間窗的取送貨車輛路徑問題，接下來(lái)的研究方向是對(duì)兩類問題進(jìn)行整合求解，設(shè)計(jì)適應(yīng)范圍更廣的算法。