帶時間窗的同時取送貨車輛路徑問題建模及模因求解算法

張慶華，吳光譜

（北京科技大學機械工程學院，北京100083）

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

0 引言

近年來，我國經濟迅速發展，人們對現代物流的服務要求也逐漸增多，從以往的僅僅只有收寄快遞的需求，逐步發展到包含定點配送、上門攬件、同城配送、準時服務等多元化的物流需求。隨著逆向物流導致客戶退換貨的增多，上門取件逐漸成為了物流服務中必不可少的一環。帶時間窗的同時取送貨車輛路徑問題（Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows，VRPSPDTW）也隨之備受關注。

VRPSPDTW 是在經典車輛路徑問題（Vehicle Routing Problem，VRP）的基礎上，增加了時間窗約束，車輛必須在客戶指定的時間窗內對客戶進行服務；同時還在為客戶進行配送的基礎上，增加了取貨服務，車輛不僅要對客戶進行配送服務，還要對在客戶所在的位置進行取貨，將客戶所要寄送的貨物運回配送中心。

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

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

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

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

1.1 問題描述

VRPSPDTW 是在傳統車輛路徑問題上引入時間窗，將客戶需要服務的時間標示出來，在客戶能夠接受的時間內進行配送或取貨，從而提高物流服務水平和服務質量。因此，本文針對帶時間窗的同時取送貨車輛路徑問題進行模型構建和求解。

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

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

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

3）每個客戶有自身所要求的時間窗，包括最早開始服務時間、最晚開始服務時間、服務時間。

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

5）若一位客戶同時具有配送需求和取貨需求，則對該客戶進行服務時，先進行卸貨，再進行裝貨。

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

本文所研究的問題主要目標是使車隊的規模最小，即所使用的車輛數最少；次要目標是車輛配送的總距離最短。

1.2 模型構建

根據以上對VRPSPDTW 的描述，構建合理的數學模型，模型參數定義如下:

K:配送中心進行服務的車輛集合。

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

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

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

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

V0:配送中心。

di，i ∈{1，2，…，M}:客戶i對應的配送量。

pi，i ∈{1，2，…，M}:客戶i對應的取貨量。

si，i ∈{1，2，…，M}:客戶i對應的服務時間。

s0:車輛在配送中心的服務時間，一般s0= 0。

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

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

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

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

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之間的車輛行駛時間。

ai，i ∈{1，2，…，M}:車輛到達客戶i處時刻。

a0:車輛到達配送中心的時刻，一般a0= e0。

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

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

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

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

根據上述參數，建立數學模型如下:

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

2 求解VRPSPDTW 的模因算法設計

2.1 模因算法主流程

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

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

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

2.2 初始種群生成

首先，采用整數編碼［13］的方式對帶時間窗的車輛路徑問題進行編碼，對于一個可行解而言，其中包含多個車輛運輸路徑，每輛車只對一條路徑上的客戶進行服務。使用1～m 表示每個客戶的編號，1～k 表示每輛車的編號，每條路徑使用一個整型向量進行表示，表示一輛車從配送中心出發，對所有客戶進行服務后，再次返回到配送中心。每一個解中對應k 條路徑。由于每個客戶只接受一次服務，因此路徑中不存在重復的客戶編號。編碼結構如圖2所示。

圖2 編碼結構Fig. 2 Coding structure

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

2.2.1 初始種群生成算法流程

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

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

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

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

通過多次生成初始解，逐步形成一個種群規模為N 的初始種群。

2.2.2 制定基本解

首先制定一個基本解，每一個客戶對應一條路徑，即一輛車只對一個客戶進行服務。此時，路徑的條數是最多的，與客戶數目相同，而后逐一減少路徑數目。

2.2.3 路徑刪除

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

2.2.4 插入客戶

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

若存在多個可行插入位置，可以采用就近原則進行客戶插入，選擇將客戶插入到對應的插入位置后，對原有路徑長度的改變量最小的位置進行插入。

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

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

若連續多代優化后，彈射池中的客戶仍未減少到0，則回到該條路線刪除前的狀態，重新隨機選擇一條路線進行刪除，若經過Ireadmax次重復刪除后，仍無法找到更少路線的解，則以該條路線刪除前的解作為滿意解，或舍棄該解。

2.2.5 路徑壓縮

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

首先對客戶插入一個位置后的違反約束函數Fp進行計算，違反約束函數計算公式如式（12）所示。

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

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

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

2.2.6 客戶彈出

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

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

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

2.2.7 終止條件

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

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

2.3 種群進化

物種進化的基本單位是種群，一個種群經過個體之間的交配可以產生新的個體，模因算法是在普通的遺傳算法的基礎上，在新個體產生的同時，不僅可以繼承父代已接受的文化知識，還能通過教育，學習新的知識，使整個種群獲得更快的進化速度。

產生初始種群之后，需要對初始種群的內的個體進行優化，優化目標為產生車輛行駛總路徑S 更短的個體，車輛行駛總路徑的計算公式見式（14），表示所有配送車輛完成配送任務需行駛的路徑總和。

對種群中的個體通過選擇、交叉、修復、教育等一系列操作后，形成新的更優秀的種群，作為下一代新種群。

首先對種群個體進行選擇，確定新的個體交叉順序，隨后個體之間進行交叉。

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

在個體交叉結束后，對個體進行修復、教育，以獲得更優的個體。修復、教育的過程采用鄰域搜索的方法進行。種群進化算法的終止條件設定為連續Igemax的操作中種群中的最優解未發生改善。種群進化算法流程如圖4 所示:描述了一個初始種群個體經過交叉、修復、教育等操作，得到最終解的過程。

種群進化算法偽碼如算法2 所示。種群進化過程中，首先對種群隨機重排，確定新的交叉順序，然后對所對應的父代交叉個體進行交叉操作，產生子個體，隨后對子個體進行修復、教育。直到連續Igemax代個體未得到改善，輸出最終的解。

圖4 種群進化算法流程Fig. 4 Flowchart of population evolution algorithm

2.3.1 選擇

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

2.3.2 交叉

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

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

2.3.3 修復、教育

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

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

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

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

2.3.4 終止條件

終止條件設定為連續Igemax的操作中種群中的最優解未得到改善。進化終止后，選取種群中車輛行駛總路徑最短的個體作為最終解。

3 算例實驗與分析

3.1 測試環境和參數確定

本文模因算法使用Java 語言進行編寫，算法運行環境采用Intel Core i5-3230M CPU@2.60 GHz（8.00 GB 內 存），Windows 10 x64操作系統。

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

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

種群進化過程中需要確定的參數包括種群規模N；連續多代未發生優化的終止迭代次數Igemax。以計算結合和程序運行實驗為評價因素，實驗需要確定的參數較少，采取固定一個參數，調整另一個參數的方法對參數進行確定實驗。確定種群進化過程參數設置為N=40，Igemax=50。

算例實驗過程中，為保證算法的準確性，對每個算例進行3次實驗，取3次的最優值作為實驗結果。

3.2 小規模客戶算例實驗

為測試本文模因算法計算小規模客戶帶時間窗的同時取送貨問題的性能，本文采用Wang 等［3］的小規模標準算例進行實驗。小規模標準算例包括10 個客戶規模、25 個客戶規模、50 個客戶規模的算例各三個。在滿足車輛載重約束和時間窗約束的條件下進行實驗，將實驗結果與Wang 等［3］設計的遺傳 算 法（GA）、Wang 等［6］設 計 的 并 行 模 擬 退 火（parallel-Simulated Annealing，p-SA）算法、王超等［7］設計的離散布谷鳥搜索（Discrete Cuckoo Search，DCS）算法取得的最優實驗結果進行比較。

實驗對比結果如表1 所示，四種算法實驗結果中，NV 和TD 分別表示配送車輛數和配送總路徑，加粗的結果代表本文算法取得的最優解。分析發現，本文模因算法可以求得全部9 個小顧客規模算例的已知最優車輛和最短路徑，驗證了本算法在求解小規模客戶帶時間窗的同時取送貨問題的有效性。

表1 小規模客戶算例實驗結果對比Tab. 1 Comparison of experimental results of small-scale customer examples

3.3 標準規模客戶算例實驗

為測試本文模因算法計算標準規模客戶帶時間窗的同時取送貨問題的性能，本文采用Wang 等［3］的標準規模算例進行實驗。隨機選取10 個算例進行實驗，每個算例包括100 個客戶。

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

表2 標準規模客戶算例實驗結果對比Tab. 2 Comparison of experimental results of standard-scale customer examples

對結果進行分析，發現在10個標準算例中，算例Rdp103、Rdp201、Rdp206、Cdp107、Rcdp201 共5 個算例更新了當前最優解；算例Cdp201、Cdp205 共2 個算例取得了與當前最優解相同的結果；僅有1 個算例未取得比其余三種算法更優的結果。

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

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

本文采取通過建立合適的數學模型，采用基于引導彈射搜索和邊界組合交叉的模因算法，使用彈射池方法生成初始解，大幅度提升了初始解的質量，同時在種群進化過程中，采用EAX 對父代個體進行交叉，保留了父代個體的優良基因，采用多種算子對種群中的解進行修復、教育，提升了鄰域搜索的廣度。算例實驗中，對于更新了當前最優解的5 個算例結果而言，其中Rcdp201 算例對當前最優解有超過5%的提升，Rdp201 對當前最優解有約2%的提升，Rdp206 對當前最優解有超過1%的提升。本文算法更新或達到最優解的算例占測試算例的70%，其中50%的算例更新了最優解，充分說明了本文模因算法在求解標準規模客戶帶時間窗的同時取送貨問題的有效性。

4 結語

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

現代物流的發展不僅會面臨同時取送貨問題，還會面臨諸如搬家服務之類的帶時間窗的取送貨車輛路徑問題，接下來的研究方向是對兩類問題進行整合求解，設計適應范圍更廣的算法。