多中心半開(kāi)放式送取需求可拆分的車(chē)輛路徑優(yōu)化

摘要：針對(duì)多中心半開(kāi)放式送取需求可拆分的車(chē)輛路徑問(wèn)題，構(gòu)建了以車(chē)輛配送距離最短為目標(biāo)的多中心半開(kāi)放式送取需求可拆分的數(shù)學(xué)模型。設(shè)計(jì)大變異鄰域遺傳算法進(jìn)行求解，采用二維染色體編碼及順序交叉策略，同時(shí)運(yùn)用大變異策略和鄰域搜索策略提高算法全局和局部的尋優(yōu)能力，通過(guò)算例對(duì)比驗(yàn)證了所提模型與算法的有效性。算例實(shí)驗(yàn)表明，大變異鄰域遺傳算法在求解多中心物流配送車(chē)輛路徑問(wèn)題上求解質(zhì)量較優(yōu)、求解效率較高、求解結(jié)果較為穩(wěn)定，同時(shí)驗(yàn)證了聯(lián)合配送下多中心半開(kāi)放式送取需求可拆分的配送模式優(yōu)于獨(dú)立配送下單中心送取需求可拆分的配送模式。研究成果不僅拓展了車(chē)輛路徑問(wèn)題，還可為相關(guān)快遞物流企業(yè)配送優(yōu)化提供決策參考。

關(guān)鍵詞：車(chē)輛路徑問(wèn)題；多中心；送取需求可拆分；大變異遺傳算法

中圖分類(lèi)號(hào)：TP301.6；F252文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2022）08-013-2316-06

doi：10.19734/j.issn.1001-3695.2022.01.0014

Multi-depot half open vehicle routing problem with split deliveries and pickups

Zhang Yingyu，Wu Liyun

（School of Business Administration，Henan Polytechnic University，Jiaozuo Henan 454003，China）

Abstract：To solve the problem of multi-depot half-open vehicle routing problem with split deliveries and pickups，this paper constructed a multi-depot half-open vehicle routing problem with split deliveries and pickups mathematical model with the shortest vehicle delivery distance as the goal.The solving process mainly used genetic algorithm based on big mutation and variable neighborhood search，which adopted two-dimensional chromosome coding and sequential crossover strategy，the big mutation strategy and neighborhood search strategy improved the global and local optimization capabilities of algorithm.The numerical examples verify the effectiveness of the model and the algorithm.Numerical examples show that the algorithm has benefits in solution quality，efficiency for solving the multi-center logistics distribution vehicle routing problem，and the result is relatively stable.Meanwhile，the multi-depot half-open vehicle routing problem with split deliveries and pickups is superior to the vehicle routing problem with split deliveries and pickups.The research results not only expand the vehicle routing problem，but also provide decision-making references for the distribution optimization of related logistics enterprises.

Key words：vehicle routing problem；multi-depot；split deliveries and pickups；genetic algorithm based on big mutation

0引言

近年來(lái)電商聯(lián)盟快速發(fā)展，環(huán)保政策相應(yīng)落實(shí)，促使我國(guó)逆向物流發(fā)展迅速。車(chē)輛路徑問(wèn)題（vehicle routing problem，VRP）逐漸演化成聯(lián)合配送下多中心帶回程的運(yùn)輸問(wèn)題，其中包括多中心開(kāi)放式車(chē)輛路徑問(wèn)題（multi-depot open VRP，MDOVRP）[1]、多中心半開(kāi)放式車(chē)輛路徑問(wèn)題（multi-depot half open VRP，MDHOVRP）[2]以及多中心閉合式車(chē)輛路徑問(wèn)題。隨著客戶(hù)點(diǎn)由單一的配送需求演變?yōu)樗腿‰p需求，還包括同時(shí)送取貨問(wèn)題（VRP with simultaneous delivery and pickup，VRPSDP）[3]和送取需求可拆分的車(chē)輛路徑問(wèn)題（VRP with split deliveries and pickups，SVRPPD）[4]等眾多的拓展問(wèn)題。本文研究的聯(lián)合配送下多中心半開(kāi)放式送取需求可拆分的車(chē)輛路徑問(wèn)題（multi-depot half open VRP with split deliveries and pickups，MDHOSVRPPD）是綜合了SVRPPD、MDHOVRP及聯(lián)合配送特點(diǎn)的車(chē)輛路徑問(wèn)題，它更加準(zhǔn)確地描述了現(xiàn)實(shí)物流配送的復(fù)雜情況，如在一個(gè)多配送中心聯(lián)合配送快遞的區(qū)域內(nèi)，配送車(chē)輛不僅要配送快遞，還要進(jìn)行快遞的攬件操作，當(dāng)客戶(hù)點(diǎn)需求全部滿(mǎn)足后，配送車(chē)輛可采用就近原則返回任意配送中心，共享配送網(wǎng)絡(luò)。半開(kāi)放式的配送中心及合理的拆分末端客戶(hù)點(diǎn)的送取需求有助于提高車(chē)輛載重利用率，降低物流、運(yùn)輸企業(yè)的配送成本。目前，針對(duì)該問(wèn)題的研究涉及較少，但其包含的SVRPPD、MDHOVRP等問(wèn)題仍是當(dāng)前的研究熱點(diǎn)。

關(guān)于SVRPPD、MDHOVRP國(guó)內(nèi)外學(xué)者都對(duì)其模型和求解方法進(jìn)行了廣泛和深入的研究。Mitra[5]首次深入分析了SVRPPD，并構(gòu)造了NH、SM兩種啟發(fā)式算法對(duì)其求解。Archetti等人[6]對(duì)客戶(hù)點(diǎn)需求是否拆分給出了詳細(xì)的科學(xué)論證，實(shí)驗(yàn)證明當(dāng)客戶(hù)點(diǎn)的總平均需求大于車(chē)輛容量一半但小于車(chē)輛容量的四分之三并且需求方差相對(duì)較小時(shí)；拆分可以獲得最大的收益。拆分帶來(lái)的收益主要體現(xiàn)在車(chē)輛配送路徑的減少，跟客戶(hù)點(diǎn)的位置無(wú)關(guān)。Tang等人[7]在解決現(xiàn)實(shí)中第三方物流案例中，采用了送取需求可拆分的車(chē)輛路徑模型并加入了時(shí)間窗的限制，運(yùn)用構(gòu)造型啟發(fā)式算法——競(jìng)爭(zhēng)決策算法對(duì)模型求解。Nagy等人[8]采用禁忌搜索算法對(duì)SVRPPD進(jìn)行求解，并與文獻(xiàn)[7]進(jìn)行了對(duì)比，表明禁忌搜索算法在求解精度和效率上均更優(yōu)。對(duì)于MDHOVRP的研究，Cordeau等人[9]設(shè)計(jì)了一種禁忌搜索算法，并加入了一組懲罰函數(shù)對(duì)MDHOVRP求解；Ting等人[10]將模擬退火算法與蟻群算法相結(jié)合對(duì)MDHOVRP進(jìn)行求解。辜勇等人[11]研究了帶時(shí)間窗的多中心半開(kāi)放式車(chē)輛路徑問(wèn)題，并設(shè)計(jì)了一種三段式求解方法，第一階段先用K-mediods方法將多配送中心轉(zhuǎn)換為單配送中心路徑，第二階段用GA-ACO算法進(jìn)行求解，第三階段利用節(jié)約算法將單配送中心拆分成多配送中心。范厚明等人[12]根據(jù)蟻群算法改進(jìn)信息素更新方式從而提高尋優(yōu)能力，對(duì)MDHOVRP進(jìn)行求解。王勇等人[13]將遺傳算法與粒子群算法結(jié)合求解MDHOVRP。范厚明等人[14]首次研究多中心聯(lián)盟配送與同時(shí)送取貨結(jié)合的車(chē)輛問(wèn)題（multi-depot VRP with simultaneous deterministic delivery and stochastic pickup based on joint distribution，MDVRPSDDSPJD），根據(jù)問(wèn)題特征設(shè)計(jì)了變鄰域文化基因算法求解該問(wèn)題。

綜上所述，現(xiàn)有文獻(xiàn)主要集中在對(duì)SVRPPD、MDHOVRP分開(kāi)的研究，將SVRPPD與MDHOVRP結(jié)合考慮的文獻(xiàn)涉及較少。在現(xiàn)實(shí)復(fù)雜的物流配送網(wǎng)絡(luò)中，僅靠解決以上單一問(wèn)題是不全面的，需要綜合考慮車(chē)輛共享、各配送中心之間聯(lián)合配送以及對(duì)客戶(hù)點(diǎn)送取需求合理拆分的情況，才能更好地優(yōu)化現(xiàn)實(shí)物流配送路徑。

MDHOSVRPPD是由現(xiàn)實(shí)物流配送模式發(fā)展演變而來(lái)，具有多中心、半開(kāi)放式以及客戶(hù)點(diǎn)送取需求可拆分等特點(diǎn)。在運(yùn)行至客戶(hù)點(diǎn)時(shí)，車(chē)輛負(fù)載減少或增加，導(dǎo)致負(fù)載波動(dòng)，必須對(duì)車(chē)輛每個(gè)線(xiàn)路進(jìn)行可行性檢查，進(jìn)一步增加了算法的求解難度。為了更好地求解MDHOSVRPPD，提升求解效率和解的質(zhì)量，本文設(shè)計(jì)了一種針對(duì)MDHOSVRPPD特點(diǎn)的大變異鄰域遺傳算法，采用二維染色體編碼不僅實(shí)現(xiàn)了對(duì)客戶(hù)點(diǎn)送取需求的拆分，而且提高了求解效率，并引入順序交叉算子，加強(qiáng)種群之間的交流，旨在通過(guò)該算法以獲得較高質(zhì)量的滿(mǎn)意解。

1MDHOSVRPPD的提出

MDHOSVRPPD是對(duì)傳統(tǒng)VRP的擴(kuò)展。由以下VRP擴(kuò)展而來(lái)：

a）帶回程車(chē)輛路徑問(wèn)題（VRP with backhauls，VRPB）[15]。VRPB是在配送車(chē)輛只能進(jìn)行后尾裝載（rear-loaded）的狀態(tài)下產(chǎn)生的。配送車(chē)輛負(fù)載貨物從配送中心出發(fā)，先服務(wù)具有送貨需求的客戶(hù)點(diǎn)，再服務(wù)具有取貨需求的客戶(hù)點(diǎn)，最后車(chē)輛回到配送中心。VRPB的示意圖如圖1（a）所示。

b）混合裝載帶回程車(chē)輛路徑問(wèn)題（VRP with backhaul and mixed load，VRPBM）[16]。隨著物流運(yùn)輸技術(shù)的進(jìn)步，配送車(chē)輛不僅可以后尾裝載，還可以進(jìn)行側(cè)面裝載（side-loaded）。因此，對(duì)送取順序不會(huì)加以限制，產(chǎn)生混合裝載帶回程的車(chē)輛路徑問(wèn)題。VRPBM的示意圖如圖1（b）所示。

VRPB與VRPBM都是解決單一配送中心、客戶(hù)點(diǎn)具有單一配送需求的車(chē)輛路徑問(wèn)題。隨著時(shí)代的發(fā)展解決現(xiàn)有物流運(yùn)輸問(wèn)題具有一定的局限性。

c）同時(shí)送取貨車(chē)輛路徑問(wèn)題（VRP with simultaneous deli-very and pickup，VRPSDP）[17，18]。VRPSDP是指客戶(hù)同時(shí)具有送貨、取貨兩種需求，且車(chē)輛對(duì)其只能服務(wù)一次。VRPSDP是對(duì)VRPBM的擴(kuò)展，其示意圖如圖1（c）所示。

d）送取需求可拆分車(chē)輛路徑問(wèn)題（SVRPPD）[4]。在實(shí)際應(yīng)用中，部分客戶(hù)點(diǎn)需求量較大，如果仍要求每個(gè)客戶(hù)點(diǎn)僅由一輛車(chē)提供服務(wù)，不僅造成車(chē)輛空載嚴(yán)重，還增加了車(chē)輛使用數(shù)量，使派遣成本增加。Dror等人[19]首次提出了送貨需求可拆分的車(chē)輛路徑問(wèn)題（split delivery VRP，SDVRP），合理拆分使得客戶(hù)點(diǎn)被配送車(chē)輛服務(wù)一次的限制取消了，這樣不僅提高了車(chē)輛的利用率，還可以節(jié)省運(yùn)輸距離和服務(wù)的車(chē)輛數(shù)目。后來(lái)研究者開(kāi)始探討對(duì)客戶(hù)點(diǎn)具有送貨、取貨雙重需求拆分的車(chē)輛路徑問(wèn)題。SDVRP可以看做是SVRPPD中送取需求其中一個(gè)為0時(shí)的特例，而SVRPPD可以看成是對(duì)SDVRP與VRPSDP的擴(kuò)展。SVRPPD的示意圖如圖1（d）所示。

e）多中心閉合式送取需求可拆分的車(chē)輛路徑問(wèn)題（multi-depot VRP with split deliveries and pickups，MDSVRPPD）。隨著現(xiàn)代物流業(yè)的發(fā)展，逐漸演變?yōu)樵谀骋粎^(qū)域內(nèi)有多個(gè)配送中心，來(lái)自不同配送中心的車(chē)輛完成所有客戶(hù)點(diǎn)的送取貨任務(wù)后返回原配送中心，稱(chēng)為多中心閉合式送取需求可拆分車(chē)輛路徑問(wèn)題。MDSVRPPD是對(duì)SVRPPD的擴(kuò)展，其示意圖如圖1（e）所示。

f）多中心半開(kāi)放式送取需求可拆分車(chē)輛路徑問(wèn)題（MDHOSVRPPD）。MDHOSVRPPD中配送中心具有半開(kāi)放式的特點(diǎn)。開(kāi)放式、閉合式及半開(kāi)放式三者是由配送中心對(duì)車(chē)輛始末停靠位置進(jìn)行區(qū)別的。開(kāi)放式的配送中心允許車(chē)輛在行駛路徑中自由停靠，車(chē)輛最終不一定要返回配送中心；閉合式的配送中心要求車(chē)輛的始末位置是配送中心且必須一致；半開(kāi)放式的配送中心要求車(chē)輛完成任務(wù)后可就近返回任意配送中心，車(chē)輛可以共享配送網(wǎng)絡(luò)。因此MDHOSVRPPD是進(jìn)一步降低配送成本的演變，也是MDSVRPPD的拓展，其示意圖如圖1（f）所示。

關(guān)于MDHOSVRPPD的最優(yōu)解理論，文獻(xiàn)[20]已證明多中心半開(kāi)放式下的車(chē)輛運(yùn)輸僅影響車(chē)輛在配送中心的首末停靠位置，而配送車(chē)輛對(duì)客戶(hù)點(diǎn)送取貨的行駛路徑不受影響。因此由Dror等人提出的需求拆分最優(yōu)解相關(guān)理論，也適用于本文研究的MDHOSVRPPD。

2MDHOSVRPPD的數(shù)學(xué)模型

2.1問(wèn)題描述

MDHOSVRPPD可以描述如下：給定多個(gè)配送中心和客戶(hù)點(diǎn)，各個(gè)配送中心之間可聯(lián)合配送，客戶(hù)點(diǎn)同時(shí)具有送貨需求與取貨需求，且單個(gè)客戶(hù)點(diǎn)的總需求可能超過(guò)車(chē)輛載重。同一類(lèi)型的車(chē)輛以負(fù)載狀態(tài)從配送中心出發(fā)，攜帶客戶(hù)點(diǎn)所需要的貨物，對(duì)客戶(hù)點(diǎn)執(zhí)行先送貨、后取貨服務(wù)，服務(wù)時(shí)不允許超過(guò)車(chē)輛最大載重，車(chē)輛返回時(shí)選擇距離近的配送中心。單個(gè)客戶(hù)點(diǎn)的需求可以由多輛車(chē)服務(wù)來(lái)滿(mǎn)足，目標(biāo)是找到一組滿(mǎn)足所有客戶(hù)點(diǎn)需求的車(chē)輛路線(xiàn)，并使配送距離最小化。

基于以上分析，本文將構(gòu)建車(chē)輛運(yùn)輸距離最小化的車(chē)輛路徑模型，并滿(mǎn)足以下模型假設(shè)：a）配送中心、客戶(hù)點(diǎn)位置已知；b）每個(gè)客戶(hù)點(diǎn)的送取需求量已知；c）所有車(chē)輛起止點(diǎn)均為配送中心，車(chē)輛裝載能力相同且運(yùn)輸過(guò)程中實(shí)際裝載量不得超過(guò)車(chē)輛載重；d）各客戶(hù)點(diǎn)的送取總需求允許超過(guò)車(chē)輛載重，客戶(hù)點(diǎn)可以接受多次服務(wù)；e）車(chē)輛對(duì)客戶(hù)點(diǎn)的服務(wù)無(wú)順序要求；f）車(chē)輛對(duì)客戶(hù)點(diǎn)的服務(wù)無(wú)時(shí)間要求。

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

以距離最小化為優(yōu)化目標(biāo)，建立的MDHOSVRPPD數(shù)學(xué)模型如下：

min z=∑i∈V∑j∈V∑k∈KxijkCij（1）

s.t.∑i∈L∪Byij-∑i∈L∪Byji=Dj，j∈L∪B（2）

∑i∈L∪Bzji-∑i∈L∪Bzij=Pj，j∈L∪B（3）

∑i∈Vyi0=0，∑j∈Vz0j=0（4）

∑i∈L∪B∑j∈L∪Bxijk-∑i∈L∪B∑j∈L∪Bxjik=0，k∈K（5）

∑i∈M∑j∈L∪Bxijk=∑i∈L∪B∑j∈Mxijk=1，k∈K（6）

yij+zij≤Q∑k∈Kxijk；i，j∈V（7）

xijk≥0，yij≥0，zij≥0，xijk∈Euclid Math TwoZAp+（8）

目標(biāo)函數(shù)式（1）為距離最小化；式（2）（3）保證所有客戶(hù)點(diǎn)的需求都被滿(mǎn)足；式（4）確保車(chē)輛離開(kāi)配送中心時(shí)車(chē)上只有待配送的貨物，當(dāng)車(chē)輛返回配送中心時(shí)車(chē)上只有收取的貨物；式（5）表示車(chē)輛服務(wù)客戶(hù)點(diǎn)的次數(shù)等于離開(kāi)客戶(hù)點(diǎn)的次數(shù)，車(chē)輛不能在客戶(hù)點(diǎn)進(jìn)行停靠；式（6）表示車(chē)輛從任意配送中心出發(fā)且僅離開(kāi)一次，并最終返回任意配送中心；式（7）保證車(chē)輛實(shí)際裝載不超過(guò)車(chē)輛載重；式（8）為變量的取值約束。模型中各符號(hào)含義如表1所示。

3大變異鄰域遺傳算法

MDHOSVRPPD是NP難問(wèn)題，其送取需求可拆分的特點(diǎn)增加了求解難度。對(duì)于送取需求可拆分的車(chē)輛路徑問(wèn)題的求解，大多數(shù)學(xué)者采用構(gòu)造型啟發(fā)式算法[4，6，8，9]，本文對(duì)于MDHOSVRPPD的求解采用現(xiàn)代啟發(fā)式算法，現(xiàn)代啟發(fā)式算法對(duì)于解決大規(guī)模的VRP能夠在合理的時(shí)間內(nèi)得出近似最優(yōu)解。將大變異遺傳算法（genetic algorithm based on big mutation，GAM）和鄰域算法[21]（variable neighborhood search，VNS）結(jié)合求解MDHOSVRPPD，前者具有出色的全局搜索能力，后者有較強(qiáng)的局部搜索能力，因此本文設(shè)計(jì)了大變異鄰域遺傳算法（genetic algorithm based on big mutation and variable neighborhood search，GAMVNS）。

3.1編碼與解碼

本文采用兩段式實(shí)數(shù)編碼，將真實(shí)客戶(hù)點(diǎn)在原位置的基礎(chǔ)上分成兩個(gè)虛擬客戶(hù)點(diǎn)，虛擬客戶(hù)點(diǎn)只具有送貨任務(wù)或者取貨任務(wù)。編碼第一段為送貨任務(wù)隨機(jī)全排列，第二段為對(duì)應(yīng)的取貨任務(wù)隨機(jī)全排列，所有任務(wù)儲(chǔ)存在pop_Pnum中，記錄任務(wù)的服務(wù)順序，如圖2所示。

解碼過(guò)程中，車(chē)輛對(duì)客戶(hù)點(diǎn)服務(wù)執(zhí)行先送后裝原則。解碼分為兩階段，第一階段從左到右將客戶(hù)點(diǎn)的任務(wù)劃分給車(chē)輛，按照貪婪原則，車(chē)輛滿(mǎn)足送貨任務(wù)后盡可能多地取貨，并進(jìn)行車(chē)輛約束檢驗(yàn)，直到車(chē)輛沒(méi)有待配送貨物且待運(yùn)回貨物滿(mǎn)載時(shí)，車(chē)輛退出路徑分配階段，等待返回配送中心，派出新車(chē)對(duì)剩余任務(wù)進(jìn)行服務(wù)；第二階段根據(jù)每輛車(chē)服務(wù)首尾客戶(hù)點(diǎn)到配送中心的距離最短原則確定每輛車(chē)的始末配送中心。

以圖2為例進(jìn)行求解，假設(shè)車(chē)輛k1滿(mǎn)足客戶(hù)點(diǎn)4的全部任務(wù)，訪(fǎng)問(wèn)客戶(hù)點(diǎn)3時(shí)滿(mǎn)足送貨任務(wù)和一部分取貨任務(wù)，訪(fǎng)問(wèn)客戶(hù)點(diǎn)5時(shí)滿(mǎn)足部分送貨任務(wù)和全部取貨任務(wù)，此時(shí)車(chē)輛k1沒(méi)有待配送貨物且已滿(mǎn)載，則退出路徑分配。派出車(chē)輛k2對(duì)剩余任務(wù)服務(wù)，k2先服務(wù)客戶(hù)點(diǎn)5的送貨任務(wù)和客戶(hù)點(diǎn)3的取貨任務(wù)，再去服務(wù)客戶(hù)點(diǎn)2和1，假設(shè)k2滿(mǎn)足客戶(hù)點(diǎn)1、2的任務(wù)，則k1的分配過(guò)程和k1、k2的最后路徑如圖3所示，最后依據(jù)車(chē)輛服務(wù)首尾客戶(hù)點(diǎn)到配送中心距離最小來(lái)確定車(chē)輛的始末配送中心，6、7為配送中心。

可以看出，在后續(xù)操作時(shí)只對(duì)pop_Pnum信息的第一段進(jìn)行迭代操作，操作完成后依據(jù)配送車(chē)輛的載重約束重新為每輛車(chē)分配客戶(hù)點(diǎn)，得到每個(gè)車(chē)輛的運(yùn)行路徑，再對(duì)車(chē)輛的首尾客戶(hù)點(diǎn)進(jìn)行解碼操作就可以獲得最終路徑。只要pop_Pnum第一階段正確，則后面由它產(chǎn)生的最終路徑也一定是正確的，即pop_Pnum的第一階段編碼決定了后續(xù)編碼。通過(guò)此編碼方式，不僅實(shí)現(xiàn)了對(duì)客戶(hù)點(diǎn)需求的拆分，而且使得后續(xù)擾動(dòng)操作總能產(chǎn)生可行解，提高了算法效率。

3.2適應(yīng)度函數(shù)

適應(yīng)度函數(shù)通常由目標(biāo)函數(shù)式（1）確定，由于構(gòu)建距離最小化的目標(biāo)函數(shù)，則染色體S的適應(yīng)度函數(shù)fs如下：

fs=1Gs（9）

其中：Gs為染色體S的目標(biāo)函數(shù)值。

3.3選擇交叉操作

本文選擇操作采用輪盤(pán)賭與精英保留策略相結(jié)合的方式。輪盤(pán)賭是個(gè)體以一定概率被選中，概率大小根據(jù)個(gè)體的適應(yīng)度函數(shù)值大小確定，個(gè)體適應(yīng)度函數(shù)值高的被選中的概率則大，反之則小。精英保留策略是適應(yīng)度函數(shù)值最高的父代

代替適應(yīng)度函數(shù)值最低的子代。采取這兩種策略有助于加強(qiáng)所有個(gè)體間基因充分交流以及快速形成穩(wěn)定的下一代。

交叉操作則是采用順序交叉算子。對(duì)個(gè)體pop_1順序交叉時(shí)，從種群中隨機(jī)選取pop_2個(gè)體，分別隨機(jī)選取pop_1、pop_2中四個(gè)基因g11、g12、g21和g22，pop_1中的g11、g12之間的基因作為newpop_1個(gè)體的第一段，消除pop_2中g(shù)11、g12之間的客戶(hù)點(diǎn)，保持剩下客戶(hù)點(diǎn)位置不變，作為newpop_1的第二段，此時(shí)newpop_1個(gè)體生產(chǎn)完畢，newpop_2同理。順序交叉示意如圖4所示。

3.4大變異操作

傳統(tǒng)遺傳算法容易早熟，為了讓種群擺脫早熟，采取大變異策略彌補(bǔ)這一缺陷。大變異策略具體是[22]先設(shè)定一個(gè)合適的變異率搜索，并記錄每一代種群的最高適應(yīng)度f(wàn)max和平均適應(yīng)度f(wàn)avg，當(dāng)滿(mǎn)足α×fmaxlt;favg，表示該代種群具有高度集中的表現(xiàn)，隨后以普通變異率大5倍以上的概率對(duì)該代種群進(jìn)行一次變異操作。其中，0.5lt;αlt;1，α為密集因子，表示種群的集中程度。

變異操作采用了三種鄰域結(jié)構(gòu)來(lái)增強(qiáng)算法的局部搜索，分別是插入、交換、2-opt。設(shè)置鄰域結(jié)構(gòu)的最優(yōu)解次數(shù)Se和最大搜索次數(shù)max_Se，當(dāng)個(gè)體進(jìn)行第一個(gè)鄰域操作時(shí)，在Se次最優(yōu)解不變時(shí)進(jìn)入下一個(gè)鄰域操作或當(dāng)個(gè)體循環(huán)次數(shù)達(dá)到max_Se時(shí)進(jìn)入下一個(gè)鄰域操作。直至循環(huán)到最后一個(gè)鄰域操作，搜索終止輸出最優(yōu)解。

a）插入規(guī)則如圖5（a）所示，將個(gè)體中的客戶(hù)點(diǎn)3移動(dòng)到客戶(hù)點(diǎn)6后產(chǎn)生新的個(gè)體。

b）交換規(guī)則如圖5（b）所示，將個(gè)體中的客戶(hù)點(diǎn)3與6進(jìn)行交換產(chǎn)生新的個(gè)體。

c）2-opt規(guī)則如圖5（c）所示，將個(gè)體中客戶(hù)點(diǎn)3與6之間的客戶(hù)逆序排列，客戶(hù)點(diǎn)3保持不變，客戶(hù)點(diǎn)5、2、6逆序排列，從而產(chǎn)生新的個(gè)體。

使用以上三種策略產(chǎn)生新個(gè)體能大大提高個(gè)體的適應(yīng)度，進(jìn)而提升GAMVNS算法的局部搜索能力，提高算法運(yùn)算效率。算法流程如圖6所示。

4實(shí)驗(yàn)與結(jié)果分析

本文依次選取MDVRP、MDHOSVRPPD與SVRPPD算例驗(yàn)證本文算法的有效性。其中SVRPPD算例不僅證明了本文算法的有效性，而且證明了聯(lián)合配送下多中心半開(kāi)放送取需求可拆分的配送模式優(yōu)于單中心下送取需求可拆分的配送模式。為了測(cè)試GAMVNS算法的性能，對(duì)算例進(jìn)行大量實(shí)驗(yàn)驗(yàn)證。本文在MATLAB2016B中編程，并使用Intel CoreTM i5-1035G1 CPU 2.19 GHz計(jì)算機(jī)系統(tǒng)在Windows 10上執(zhí)行，該系統(tǒng)內(nèi)存為16 GB。實(shí)驗(yàn)基本參數(shù)設(shè)置如表2所示，n、N、G、Pc、Pm、Se、Max_Se分別為客戶(hù)規(guī)模、種群規(guī)模、最大迭代次數(shù)、交叉概率、變異概率、最優(yōu)解次數(shù)、最大鄰域搜索次數(shù)。

4.1MDVRP算例驗(yàn)證

實(shí)驗(yàn)1為了驗(yàn)證本文算法的有效性，選取文獻(xiàn)[23～25]中的MDVRP算例進(jìn)行驗(yàn)證。該算例包括30個(gè)客戶(hù)點(diǎn)（編號(hào)為1～30），3個(gè)配送中心（編號(hào)為31～33），配送車(chē)輛的最大容量為10 t及最大行駛距離為50 km，所有客戶(hù)點(diǎn)需求都在2 t及以下。表3給出狼群算法（WPA）[23]、競(jìng)爭(zhēng)決策算法（CDA）[24]以及禁忌搜索算法（TS）[25]、量子遺傳算法（QGA）[25]與本文提出的GAMVNS算法運(yùn)行10次的結(jié)果對(duì)比。表中KOS表示已知最優(yōu)解，best、worst、avg分別表示算法運(yùn)行10次得到的最優(yōu)解、最差解以及平均解，%dev、CPU為最優(yōu)解偏差與算法平均運(yùn)行時(shí)間。配送車(chē)輛行駛路徑如表4所示。

由表3可以看出，本文算法求得最優(yōu)解與已知最優(yōu)解相同，均是116.01，而求得的最差解及平均解均優(yōu)于其他算法所求。從求解時(shí)間方面來(lái)看，本文算法運(yùn)行10次的平均時(shí)間為7.84 s，運(yùn)行時(shí)間比其他算法有顯著降低，且具有較強(qiáng)的優(yōu)勢(shì)。

4.2MDHOSVRPPD算例驗(yàn)證

實(shí)驗(yàn)2MDHOSVRPPD的相關(guān)約束較多，有多個(gè)配送中心、多個(gè)客戶(hù)點(diǎn)、客戶(hù)點(diǎn)具有送取需求等特點(diǎn)。目前沒(méi)有通用的算例集，本文選用標(biāo)準(zhǔn)算例庫(kù)中的MDVRP算例P02（算例集來(lái)源https：//neo.lcc.uma.es/vrp/vrpinstances/multiple-depot-vrp-instances/），并按MDHOSVRPPD的特點(diǎn)修改后進(jìn)行驗(yàn)證。P02算例包括50個(gè)客戶(hù)點(diǎn)（編號(hào)為1～50），4個(gè)配送中心（編號(hào)為 51～54），車(chē)輛容量為160。客戶(hù)的送取需求由文獻(xiàn)[26]提出的需求分離規(guī)則產(chǎn)生：xi、yi為客戶(hù)點(diǎn)的坐標(biāo)，di、pi為客戶(hù)點(diǎn)送貨、取貨需求，qi為客戶(hù)點(diǎn)原始需求，ri=min（xi/yi，yi/xi）計(jì)算每個(gè)客戶(hù)比率，由di=qiri和pi=qi（1-ri）計(jì)算得出各個(gè)客戶(hù)點(diǎn)的送取需求，算例具體信息如表5所示。

與傳統(tǒng)遺傳算法（genetic algorithm，GA）、傳統(tǒng)蟻群算法（ant colony optimization，ACO）、傳統(tǒng)大變異遺傳算法（genetic algorithm based on big mutation，GAM）、傳統(tǒng)變鄰域搜索算法（variable neighborhood search，VNS）作對(duì)比，結(jié)果如表6、7所示。best、num為算法運(yùn)行20次的最優(yōu)解和車(chē)輛數(shù)，%dev、CPU為最優(yōu)解偏差與算法平均運(yùn)行時(shí)間。

由表6可以看出，傳統(tǒng)GA、GAM、ACO以及VNS算法搜索策略單一，容易出現(xiàn)早熟現(xiàn)象，在求解質(zhì)量上表現(xiàn)較差。本文提出的GAMVNS算法與四種算法相比，在配送總距離方面分別優(yōu)化了5.66％、6.88％、12.83%、16.46％，求解質(zhì)量方面均優(yōu)于傳統(tǒng)算法。從求解時(shí)間上看，本文算法的平均時(shí)間為7.2 s，計(jì)算時(shí)間比較理想。最優(yōu)解偏差為0.8％，能夠有效地求解出最優(yōu)解。表7為配送車(chē)輛行駛路徑。由圖7的最優(yōu)路徑的迭代圖可以看出，本文的GAMVNS算法能夠以較少的迭代次數(shù)快速地進(jìn)行收斂，具有較強(qiáng)的尋優(yōu)能力。

4.3配送模式對(duì)比驗(yàn)證

實(shí)驗(yàn)3為驗(yàn)證聯(lián)合配送模式下多中心半開(kāi)放式送取需求可拆分配送模式優(yōu)于獨(dú)立配送模式下單中心送取需求可拆分配送模式（SVRPPD），選取了MDVRP標(biāo)準(zhǔn)算例庫(kù)中的P01、P02、P03、P04、P05、P06進(jìn)行半開(kāi)放式送取需求可拆分的多中心與單中心對(duì)比研究。多中心的配送中心坐標(biāo)取算例中的數(shù)據(jù)，單中心的配送中心坐標(biāo)如表8所示，客戶(hù)點(diǎn)送取需求數(shù)據(jù)的處理按照實(shí)驗(yàn)2的標(biāo)準(zhǔn)執(zhí)行。結(jié)果如表8、9所示。表9中的best、worst、avg分別為算法運(yùn)行20次得到的最優(yōu)解、最差解以及平均解；%dev為最優(yōu)解偏差，num為車(chē)輛數(shù)，CPU為算法運(yùn)行20次的平均時(shí)間。

由表9看出，聯(lián)合配送模式與獨(dú)立配送模式下各算例求解結(jié)果中，最優(yōu)解偏差最大為8.9%，最小為0.5%，求解時(shí)間均在8 s內(nèi)。可以看出，本文算法的優(yōu)化結(jié)果求解速度較快，可以穩(wěn)定地收斂到較優(yōu)解。

對(duì)比聯(lián)合配送模式下多中心半開(kāi)放式送取需求可拆分的配送模式與獨(dú)立配送模式下單中心送取需求可拆分的配送模式可以看出，配送距離對(duì)應(yīng)縮短為31.86%、13.0%、25.57%、9.89%、27.95%和6.55%。從表9和圖8可以得出，聯(lián)合配送下多中心半開(kāi)放式送取需求可拆分的配送模式，相對(duì)于獨(dú)立配送下單中心送取需求可拆分模式，前者大幅度減少了車(chē)輛頻繁往返配送中心產(chǎn)生的配送路徑，進(jìn)而降低車(chē)輛的配送成本。

5結(jié)束語(yǔ)

本文針對(duì)聯(lián)合配送下多中心半開(kāi)放式送取需求可拆分的車(chē)輛路徑問(wèn)題進(jìn)行了以下研究：a）構(gòu)建了總配送距離最短的多中心半開(kāi)放式送取需求可拆分的車(chē)輛路徑數(shù)學(xué)模型；b）設(shè)計(jì)了大變異鄰域遺傳算法對(duì)其求解，大變異策略和鄰域搜索策略擺脫了算法早熟問(wèn)題并提高了搜索效率，通過(guò)三組算例對(duì)模型和算法進(jìn)行了驗(yàn)證分析。結(jié)果表明，本文建立的模型和算法能夠有效地解決MDHOSVRPPD，且搜索穩(wěn)定，具有較為明顯的優(yōu)勢(shì)。

此外，MDHOSVRPPD適用于電商聯(lián)盟，為了給電商企業(yè)提供更貼合現(xiàn)實(shí)的配送路徑，不僅要考慮配送距離最小化，還要考慮客戶(hù)滿(mǎn)意度問(wèn)題，因此，在時(shí)間窗約束下求解多中心半開(kāi)放式送取需求可拆分的車(chē)輛路徑問(wèn)題是下一步的研究方向。

參考文獻(xiàn)：

［1］楊翔，范厚明，徐振林，等.模糊需求下多中心開(kāi)放式車(chē)輛路徑優(yōu)化[J].計(jì)算機(jī)集成制造系統(tǒng)，2019，25（2）：469-479.（Yang Xiang，F(xiàn)an Houming，Xu Zhenlin， et al.Optimization of open multi-depot vehicle routing problem with fuzzy demand[J].Computer Integrated Manufacturing Systems，2019，25（2）：469-479.）

[2]劉冉，江志斌，耿娜，等.半開(kāi)放式多車(chē)場(chǎng)車(chē)輛路徑問(wèn)題[J].上海交通大學(xué)學(xué)報(bào)，2010，44（11）：1539-1545.（Liu Ran，Jiang Zhibin，Geng Na，et al.Half open multi-depot vehicle routing problem[J].Journal of Shanghai Jiaotong University，2010，44（11）：1539-1545.）

[3]Hornstra R P，Silva A，Bergen K J R，et al.The vehicle routing problem with simultaneous pickup and delivery and handling costs[J].Computers and Operations Research，2020，115（3）：305-408.

[4]Wang Kefeng，Ye Chunming，Ning Aibing.Achieving better solutions for vehicle routing problem involving split deliveries and pickups using a competitive decision algorithm[J].Asia Pacific Journal of Operational Research，2015，32（4）：155-177.

[5]Mitra S.An algorithm for the generalized vehicle routing problem with backhauling[J].Asia Pacific Journal of Operational Research，2005，22（2）：153-169.

[6]Archetti C，Savelsbergh M，Speranza M G.To split or not to split：that is the question[J].Transportation Research Part E Logistics amp; Transportation Review，2008，44（1）：114-123.

[7]Tang Guochun，Ning Aibing，Wang Kefeng，et al.A practical split vehicle routing problem with simultaneous pickup and delivery[C]//Proc of the 16th International Conference on Industrial Engineering and Engineering Management.Piscataway，NJ：IEEE Press，2009：26-30.

[8]Nagy G，Wassan N A，Speranza M G，et al.The vehicle routing problem with divisible deliveries and pickups[J].Transportation Science，2015，49（2）：271-294.

[9]Cordeau J F，Laporte G，Mercier A.A unified tabu search heuristic for vehicle routing problems with time windows[J].Journal of the Operational Research Society，2001，52（8）：928-936.

[10]Ting C J，Chen C H.Combination of multiple ant colony system and simulated annealing for the multi-depot vehicle-routing problem with time windows[J].Transportation Research Record，2008，2089（1）：85-92.

[11]辜勇，袁源乙，張列，等.帶時(shí)間窗的多中心半開(kāi)放式車(chē)輛路徑問(wèn)題[J].中國(guó)機(jī)械工程，2020，31（14）：1733-1740.（Gu Yong，Yuan Yuanyi，Zhang Lie，et al.Multi-depot half open vehicle routing problem with time windows[J].China Mechanical Engineering，2020，31（14）：1733-1740.）

[12]范厚明，楊翔，李蕩，等.基于生鮮品多中心聯(lián)合配送的半開(kāi)放式車(chē)輛路徑問(wèn)題[J].計(jì)算機(jī)集成制造系統(tǒng)，2019，25（1）：256-266.（Fan Houming，Yang Xiang，Li Dang，et al.Half-open multi-depot vehicle routing problem based on joint distribution mode of fresh food[J].Computer Integrated Manufacturing Systems，2019，25（1）：256-266.）

[13]王勇，任音吉，劉永，等.基于多中心車(chē)輛路徑問(wèn)題的收益分配優(yōu)化研究[J].交通運(yùn)輸系統(tǒng)工程與信息，2018，18（3）：210-217.（Wang Yong，Ren Yinji，Liu Yong，et al.Profit allocation optimization based on multi-center vehicle routing problem[J].Journal of Transportation Systems Engineering and Information Technology，2018，18（3）：210-217.）

[14]范厚明，劉鵬程，劉浩，等.多中心聯(lián)合配送模式下集貨需求隨機(jī)的VRPSDP問(wèn)題[J].自動(dòng)化學(xué)報(bào)，2021，47（7）：1646-1660.（Fan Houming，Liu Pengcheng，Liu Hao，et al.The multi-depot vehicle routing problem with simultaneous deterministic delivery and stochastic pickup based on joint distribution[J].Acta Automatica Sinica，2021，47（7）：1646-1660.）

[15]Brandao J.A new tabu search algorithm for the vehicle routing problem with backhauls[J].European Journal Operational Research，2006，173（2）：540-555.

[16]Wade A C，Salhi S.An investigation into a new class of vehicle routing problem with backhauls[J].Omega，2002，30（6）：479-487.

[17]Zhu Lin，Sheu J B.Failure-specific cooperative recourse strategy for simultaneous pickup and delivery problem with stochastic demands[J].European Journal of Operational Research，2018，271（3）：896-912.

[18]Shi Yong，Boudouh T，Grunder O，et al.Modeling and solving simultaneous delivery and pick-up problem with stochastic travel and service times in home health care[J].Expert Systems with Applications，2018，102（7）：218-233.

[19]Dror M，Trudeau P.Savings by split delivery routing[J].Transportation Science，1989，23（2）：141-145.

[20]范厚明，張軒，任曉雪，等.多中心開(kāi)放且需求可拆分的VRPSDP問(wèn)題優(yōu)化[J].系統(tǒng)工程理論與實(shí)踐，2021，41（6）：1521-1534.（Fan Houming，Zhang Xuan，Ren Xiaoxue，et al.Optimization of multi-depot open split delivery vehicle routing problem with simultaneous delivery and pick-up[J].Systems Engineering-Theory amp; Practice，2021，41（6）：1521-1534.）

[21]徐倩，熊俊，楊珍花，等.基于自適應(yīng)大鄰域搜索算法的外賣(mài)配送車(chē)輛路徑優(yōu)化[J].工業(yè)工程與管理，2021，26（3）：115-122.（Xu Qian，Xiong Jun，Yang Zhenhua，et al.Route optimization of takeout delivery vehicles based on adaptive large neighborhood search algorithm[J].Industrial Engineering and Management，2021，26（3）：115-122.）

[22]張華慶，張喜.改進(jìn)遺傳算法在車(chē)輛路徑問(wèn)題中的應(yīng)用[J].交通信息與安全，2012，30（5）：81-86.（Zhang Huaqing，Zhang Xi.Application of improved genetic algorithm in vehicle routing problem[J].Journal of Transport Information and Safety，2012，30（5）：81-86.）

[23]葉勇，張惠珍.多配送中心車(chē)輛路徑問(wèn)題的狼群算法[J].計(jì)算機(jī)應(yīng)用研究，2017，34（9）：2590-2593.（Ye Yong，Zhang Huizhen.Wolf pack algorithm for multi-depot vehicle routing problem[J].Application Research of Computers，2017，34（9）：2590-2593.）

[24]殷脂，葉春明.多配送中心物流配送車(chē)輛調(diào)度問(wèn)題的分層算法模型[J].系統(tǒng)管理學(xué)報(bào)，2014，23（4）：602-606.（Yin Zhi，Ye Chunming.Study on the hierarchical model for multi-depot logistic vehicle scheduling problem[J].Journal of Systems amp; Management，2014，23（4）：602-606.）

[25]葛顯龍，許茂增，王偉鑫.基于聯(lián)合配送的城市物流配送路徑優(yōu)化[J].控制與決策，2016，31（3）：503-512.（Ge Xianlong，Xu Maozeng，Wang Weixin.Route optimization of urban logistics in joint distribution[J].Control and Decision，2016，31（3）：503-512.）

[26]Salhi S，Nagy G.A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling[J].Journal of the Operational Research Society，1999，50（10）：1034-1042.

收稿日期：2022-01-05；修回日期：2022-03-02基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（51674102）；NSFC-河南聯(lián)合基金重點(diǎn)資助項(xiàng)目（U1904210）； 河南省高校基本科研業(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資金資助項(xiàng)目（NSFRF180104）

作者簡(jiǎn)介：張穎鈺（1997-），女，山東淄博人，碩士研究生，主要研究方向?yàn)楝F(xiàn)代物流與供應(yīng)鏈管理；吳立云（1973-），女（通信作者），河北石家莊人，教授，碩導(dǎo)，博士，主要研究方向?yàn)楝F(xiàn)代物流與供應(yīng)鏈管理等（jitwly@hpu.edu.cn）.