同時(shí)取送貨配送路徑優(yōu)化的兩階段混合策略搜索算法

徐 寧，胡義秋，姚 康（南京審計(jì)大學(xué) 商學(xué)院，江蘇 南京 210029）

0 引言

車(chē)輛同時(shí)取送貨是物流企業(yè)在配送環(huán)節(jié)提高運(yùn)作效率所需要采用的重要模式，通過(guò)將集貨與配貨結(jié)合起來(lái)可以合理利用配送途中車(chē)輛剩余載荷。配送中實(shí)現(xiàn)同時(shí)取貨與送貨作業(yè)可以有效結(jié)合再制造與資源的回收利用，降低企業(yè)的配送成本。該模式下的路徑優(yōu)化問(wèn)題具有高復(fù)雜度和難以求解的特點(diǎn)，同時(shí)求解過(guò)程需要面臨時(shí)間效率、運(yùn)作成本的兼顧。

同時(shí)取送貨問(wèn)題是傳統(tǒng)車(chē)輛路徑問(wèn)題的延伸，擴(kuò)展了車(chē)輛路徑問(wèn)題的使用場(chǎng)景，近些年越來(lái)越多的學(xué)者對(duì)其展開(kāi)研究。Hu 等考慮了動(dòng)態(tài)且取貨與送貨不相容的VRPSPD 問(wèn)題[1]，為管理者解決貨物不相容的取送貨問(wèn)題提供了定量的依據(jù)；Wang 等考慮了時(shí)間窗[2]，構(gòu)建了多目標(biāo)優(yōu)化模型，并以實(shí)際業(yè)務(wù)數(shù)據(jù)證明了所設(shè)計(jì)的多目標(biāo)鄰域搜索算法的有效性；馬艷芳等考慮了運(yùn)行環(huán)境的不確定性構(gòu)建了不確定VRPSPD 數(shù)學(xué)模型[3]，引入模糊隨機(jī)理論描述決策環(huán)境中的不確定性；Hornstra 等研究了考慮貨物裝卸后進(jìn)先出原則的同時(shí)取送貨車(chē)輛路徑問(wèn)題[4]；Zhang 等研究了新加坡快時(shí)尚商品的多種類(lèi)商品需求的同時(shí)取送貨問(wèn)題[5]，并通過(guò)自適應(yīng)內(nèi)存優(yōu)化策略求解超過(guò)10 000 個(gè)節(jié)點(diǎn)的大規(guī)模實(shí)際問(wèn)題；Büsta 等以最小化燃油消耗為目標(biāo)[6]，建立了綠色取送貨車(chē)輛路徑問(wèn)題的整數(shù)線性規(guī)劃模型，并設(shè)計(jì)了超啟發(fā)式算法對(duì)其進(jìn)行求解；Golsefidi 等針對(duì)生產(chǎn)-庫(kù)存的同時(shí)取送貨問(wèn)題提出了一種魯棒的混合整數(shù)線性規(guī)劃模型[7]，并設(shè)計(jì)了兩種啟發(fā)式算法用于求解該線性模型；Foroutan 等研究了同時(shí)考慮多車(chē)型與碳排放的同時(shí)取送貨路徑規(guī)劃問(wèn)題[8]，建立了以最小化成本和碳排放的多目標(biāo)整數(shù)線性規(guī)劃模型。

對(duì)于求解同時(shí)取送貨問(wèn)題，根據(jù)問(wèn)題的業(yè)務(wù)場(chǎng)景與客戶(hù)規(guī)模的不同，學(xué)者提出了諸多的策略。Soylu 在研究多旅行商問(wèn)題時(shí)設(shè)計(jì)了變鄰域搜索算法[9]，并通過(guò)仿真試驗(yàn)驗(yàn)證了算法具有良好的收斂效果；Mu 等設(shè)計(jì)了并行模擬退火算法用于求解同時(shí)取送貨車(chē)輛路徑問(wèn)題[10]，并通過(guò)不同規(guī)模算例驗(yàn)證了算法的有效性；Belgin 等設(shè)計(jì)了變鄰域下降與鄰域搜索算法求解帶同時(shí)取送貨的兩級(jí)車(chē)輛路徑問(wèn)題[11]，并構(gòu)建中大規(guī)模算例驗(yàn)證算法有效性，通過(guò)實(shí)例表明文中算法能夠有效應(yīng)用于現(xiàn)實(shí)配送場(chǎng)景；裴頌文等采用了一種融合拓展性K-Means++算法和遺傳算法的路徑動(dòng)態(tài)規(guī)劃模型（KMG）[12]，實(shí)現(xiàn)包含逆向物流的無(wú)人機(jī)調(diào)度策略；Majidi 等設(shè)計(jì)了自適應(yīng)大鄰域搜索算法用于求解帶同時(shí)取送貨的污染路徑問(wèn)題[13]；Lagos 等設(shè)計(jì)了改進(jìn)的粒子群算法對(duì)帶同時(shí)取送貨和時(shí)間窗的車(chē)輛路徑問(wèn)題進(jìn)行了求解[14]；Chentli 等設(shè)計(jì)了自適應(yīng)大鄰域算法用于求解同時(shí)取送貨的車(chē)輛路徑問(wèn)題[15]，并通過(guò)多個(gè)算例證明了算法的有效性；Qiu 等采用了分支定界的方法求解考慮逆向物流的路徑問(wèn)題[16]，算法在取貨量相對(duì)較大時(shí)更加高效；Zhao 等設(shè)計(jì)了一種超啟發(fā)式算法框架用于求解帶同時(shí)取送貨的選址-路徑問(wèn)題[17]，該算法框架在求解質(zhì)量和速度上均優(yōu)于傳統(tǒng)的算法框架；Ma 等采用基于模糊邏輯控制器和模糊隨機(jī)仿真的混合優(yōu)先級(jí)嵌套遺傳算法求解逆向物流環(huán)境下帶時(shí)間窗和同時(shí)取送貨的車(chē)輛路徑問(wèn)題[18]，并用多個(gè)規(guī)模算例對(duì)算法有效性進(jìn)行驗(yàn)證；Afra 等在求解取送貨問(wèn)題時(shí)考慮了啟動(dòng)成本和環(huán)保因素[19]，設(shè)計(jì)了拉格朗日松弛算法（LR）對(duì)其進(jìn)行求解?？蛻?hù)規(guī)模是路徑優(yōu)化問(wèn)題的重要影響因素之一，隨著客戶(hù)節(jié)點(diǎn)的規(guī)模增大，精確求解法和傳統(tǒng)啟發(fā)式算法的計(jì)算時(shí)間呈指數(shù)級(jí)增長(zhǎng)，難以求得較優(yōu)解。

本文研究較大規(guī)模帶同時(shí)取送貨的車(chē)輛路徑問(wèn)題，針對(duì)規(guī)模較大的同時(shí)取送貨物流配送問(wèn)題提出了基于“先分解，再求解”思想的兩階段策略，通過(guò)聚類(lèi)方法將規(guī)模較大的問(wèn)題分解為多個(gè)小規(guī)模的問(wèn)題，并將每個(gè)子問(wèn)題的規(guī)模約束在一輛運(yùn)輸車(chē)能滿(mǎn)足規(guī)模內(nèi)所有客戶(hù)需求的范圍內(nèi)，即將子問(wèn)題轉(zhuǎn)化為求解旅行商問(wèn)題，再設(shè)計(jì)混合變鄰域搜索算法提高對(duì)子問(wèn)題搜索能力的適應(yīng)，提高對(duì)該類(lèi)較大規(guī)模配送路徑問(wèn)題的求解能力。本文通過(guò)不同規(guī)模的算例計(jì)算，并與同類(lèi)算法進(jìn)行對(duì)比，驗(yàn)證兩階段的算法能夠有效求解同時(shí)取送貨物流配送問(wèn)題，為企業(yè)在整合取貨與送貨時(shí)合理調(diào)配車(chē)輛提供方法理論支持。

1 同時(shí)取送貨物流配送問(wèn)題描述與數(shù)學(xué)模型的構(gòu)建

1.1 同時(shí)取送貨物流配送問(wèn)題描述

帶同時(shí)取送貨物流配送規(guī)劃問(wèn)題是傳統(tǒng)VRP 問(wèn)題的延展，指配送車(chē)輛在對(duì)客戶(hù)執(zhí)行送貨任務(wù)時(shí)，同時(shí)可能有取貨需求，這要求車(chē)輛需要有效利用配送任務(wù)中產(chǎn)生的剩余載荷，在滿(mǎn)足容量約束的條件下，規(guī)劃配送路線，最小化配送成本。同時(shí)取送貨物流配送問(wèn)題可以被描述為在歐式平面內(nèi)的一個(gè)全連通圖G=｛V,A ｝，頂點(diǎn)集V=｛0,1 ,…,N ｝，其中：0 為配送中心，i（i≠ 0）為客戶(hù)節(jié)點(diǎn)。弧集為A，車(chē)輛沿?。╥,j）∈A 的行駛距離為dij。配送中心負(fù)責(zé)滿(mǎn)足N 個(gè)客戶(hù)的送貨需求di和取貨需求pi，設(shè)所有客戶(hù)的送貨與取貨需求由配送中心的M 輛運(yùn)輸車(chē)負(fù)責(zé)，運(yùn)輸車(chē)完全相同，其固定啟動(dòng)成本為c1，單位距離的運(yùn)輸成本為c2，載荷量為Q，車(chē)輛從配送中心出發(fā)，負(fù)責(zé)服務(wù)一批客戶(hù)后回到配送中心，每個(gè)客戶(hù)僅被訪問(wèn)一次，且每個(gè)客戶(hù)的需求都被滿(mǎn)足。所有距離都用平面上的歐式距離表示，假設(shè)所有車(chē)輛的速度為勻速，且嚴(yán)禁超載。同時(shí)取送貨物流配送問(wèn)題就是為每輛車(chē)找到滿(mǎn)足約束且成本最小的路徑。同時(shí)取送貨物流配送網(wǎng)絡(luò)如圖1 所示。

圖1 同時(shí)取送貨物流配送問(wèn)題示意圖

構(gòu)建模型需滿(mǎn)足以下約束：載荷約束，在任何時(shí)刻，車(chē)輛的載重量不超過(guò)車(chē)輛的最大載荷；行駛路線，約束車(chē)輛從配送中心出發(fā)，完成配送任務(wù)后返回配送中心；服務(wù)次數(shù)約束，一個(gè)客戶(hù)節(jié)點(diǎn)只能被一輛車(chē)服務(wù)，一輛車(chē)可服務(wù)多個(gè)客戶(hù)節(jié)點(diǎn)；節(jié)點(diǎn)約束，車(chē)輛從某個(gè)客戶(hù)節(jié)點(diǎn)進(jìn)入則必須從該節(jié)點(diǎn)離開(kāi)。

1.2 建立同時(shí)取送貨物流配送問(wèn)題的數(shù)學(xué)模型

基于上述問(wèn)題描述，構(gòu)建以成本最小化為目標(biāo)函數(shù)的同時(shí)取送貨物流配送模型：

目標(biāo)函數(shù)式（1）表示最小化配送總成本，第一項(xiàng)為車(chē)輛固定啟動(dòng)成本，第二項(xiàng)為車(chē)輛的旅行成本；式（2）表示每個(gè)客戶(hù)僅被訪問(wèn)一次，式（3）表示車(chē)輛駛?cè)肽彻?jié)點(diǎn)后一定從該點(diǎn)駛出；式（4）表示每輛車(chē)最多只被使用一次；式（5）表示每條弧上的取貨和送貨載荷不超過(guò)車(chē)輛的額定載荷；式（6）和式（7）表示取貨與送貨的流量守恒；式（8）表示每條弧上的載荷都大于等于0；式（9）表示若車(chē)輛k 經(jīng)過(guò)?。╥,j） ∈A，則為1，否則為0。模型所有的符號(hào)定義如表1 所示。

表1 模型中的符號(hào)說(shuō)明

2 求解同時(shí)取送貨物流配送問(wèn)題的兩階段策略設(shè)計(jì)

2.1 區(qū)域劃分聚類(lèi)算法

客戶(hù)節(jié)點(diǎn)都為離散的點(diǎn)，本文基于k 均值聚類(lèi)算法設(shè)計(jì)區(qū)域劃分算法（RPC）將配送范圍劃分為多個(gè)區(qū)域。聚類(lèi)屬于無(wú)監(jiān)督學(xué)習(xí)，聚類(lèi)過(guò)程不受限制，由于車(chē)輛有載荷約束，因此需對(duì)聚類(lèi)算法增加約束使得每個(gè)類(lèi)中配送需求或取貨需求總量都不超過(guò)一輛車(chē)的載荷能力。算法將客戶(hù)節(jié)點(diǎn)劃分為M 個(gè)區(qū)域，每個(gè)區(qū)域內(nèi)的客戶(hù)滿(mǎn)足一輛運(yùn)輸車(chē)即可負(fù)責(zé)服務(wù)，從而在每個(gè)區(qū)域內(nèi)的路徑規(guī)劃可轉(zhuǎn)化為求解旅行商路徑問(wèn)題。

計(jì)算客戶(hù)的送貨總量D 與取貨總量P，通過(guò)單輛運(yùn)輸車(chē)的容量Q，估算滿(mǎn)足全部客戶(hù)需求所需的車(chē)輛總數(shù)M。式（10）為需要的車(chē)輛數(shù)即劃分的區(qū)域數(shù)量。

隨機(jī)選取配送范圍內(nèi)M 個(gè)坐標(biāo)點(diǎn)作為M 個(gè)區(qū)域的中心點(diǎn)，對(duì)于每個(gè)客戶(hù)，計(jì)算其與各個(gè)中心點(diǎn)的距離，選擇與其距離最近的中心點(diǎn)且該區(qū)域內(nèi)的配送總量滿(mǎn)足車(chē)輛容量約束時(shí)加入該區(qū)域內(nèi)，若不滿(mǎn)足則將其加入到距離次近的區(qū)域內(nèi)，直至所有客戶(hù)節(jié)點(diǎn)都加入到某個(gè)區(qū)域中。

計(jì)算每個(gè)區(qū)域的重心μj，并將重心作為新的區(qū)域中心重新劃分客戶(hù)，重復(fù)迭代上述劃分的過(guò)程，算法的終止條件為達(dá)到區(qū)域內(nèi)平方和最小化：

2.2 混合變鄰域搜索算法

通過(guò)第一階段的區(qū)域劃分聚類(lèi)算法將配送范圍劃分成M 個(gè)區(qū)域，從而將求解大規(guī)模問(wèn)題轉(zhuǎn)化為求解多個(gè)小規(guī)模的子問(wèn)題，分別對(duì)每個(gè)區(qū)域的物流配送服務(wù)使用混合變鄰域搜索算法（HVNS）求解。HVNS 可以被描述為，設(shè)s 為一個(gè)可行解，Nk（s） 是關(guān)于s 的一個(gè)鄰域結(jié)構(gòu)的解集，其中：k=1,…,kmax。HVNS 算法通過(guò)變鄰域下降法（VND）拓展局部搜索，并混合模擬退火接受準(zhǔn)則判斷是否接受新解。混合變鄰域算法的組成包括初始化參數(shù)、一組鄰域結(jié)構(gòu)、模擬退火接受準(zhǔn)則和算法終止條件。

初始化參數(shù)包括初始可行解、初始溫度、退火速率和最終溫度，本文使用貪婪算法生成初始解。

鄰域Nk-1（s）的局部最優(yōu)s 優(yōu)于Nk（s）的局部最優(yōu)s'時(shí)以概率）接受新解，使得變鄰域算法以一定概率進(jìn)入下一個(gè)鄰域，避免只在前幾個(gè)鄰域中搜索，擴(kuò)大算法的搜索范圍。

HVNS 的關(guān)鍵步驟是使用合適的鄰域搜索方案，鄰域結(jié)構(gòu)的選擇與鄰域搜索方案的順序都影響著HVNS 性能。本文采用了五種（lmax=5）鄰域結(jié)構(gòu)方案，包括插入法，2-opt，3-opt，cross-exchange 和大鄰域搜索。插入法從路徑中刪除一個(gè)節(jié)點(diǎn)，并將其插入到路徑的其他位置上得到一條新的路徑，選擇使得目標(biāo)函數(shù)最小的插入方案；two-opt 將路徑中的一段進(jìn)行反轉(zhuǎn)操作得到一條新的路徑，若目標(biāo)函數(shù)減小即進(jìn)行反轉(zhuǎn)，否則不反轉(zhuǎn)；three-opt 首先刪除路徑中3 條邊，生成3 條子路徑，從而產(chǎn)生了7 種不同的重連方式，并找出其中最優(yōu)的重連方法；cross-exchange 隨機(jī)選取路徑中兩條子路徑，且兩條子路徑?jīng)]有重復(fù)的節(jié)點(diǎn)，交換兩條子路徑的訪問(wèn)順序，生成新的路徑；大鄰域搜索包括destroy 和repair 兩個(gè)算子。本文采用貪婪的思想設(shè)計(jì)摧毀和修復(fù)算子，計(jì)算摧毀節(jié)點(diǎn)后的節(jié)約值，將路徑中對(duì)目標(biāo)函數(shù)影響最大的節(jié)點(diǎn)摧毀。修復(fù)算子將被摧毀的節(jié)點(diǎn)插入到路徑中對(duì)目標(biāo)函數(shù)影響最小的位置。

變鄰域下降（VND）是HVNS 最關(guān)鍵的部分，VND 的原理基于一個(gè)事實(shí)：一個(gè)鄰域結(jié)構(gòu)的局部最小值對(duì)于另一個(gè)鄰域結(jié)構(gòu)未必如此。VND 拓展了局部搜索，當(dāng)在一個(gè)鄰域結(jié)構(gòu)內(nèi)陷入局部最優(yōu)時(shí)跳出該鄰域結(jié)構(gòu)重新尋找另一鄰域結(jié)構(gòu)內(nèi)的局部最優(yōu)，全局最優(yōu)是關(guān)于所有可能的鄰域結(jié)構(gòu)的局部最優(yōu)。

在遍歷一個(gè)鄰域后，通過(guò)退火速率更新當(dāng)前溫度，算法終止條件為溫度達(dá)到設(shè)定的最終溫度。

表2 給出了兩階段算法RPCHVNS 的偽代碼。

表2 兩階段算法的偽代碼

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

針對(duì)提出的兩階段策略，本文通過(guò)隨機(jī)生成的方法生成數(shù)據(jù)進(jìn)行數(shù)值實(shí)驗(yàn)。通過(guò)多組實(shí)驗(yàn)對(duì)比，得出本文算法在求解較大規(guī)模的同時(shí)取送貨問(wèn)題時(shí)優(yōu)于其他同類(lèi)算法。

3.1 算例構(gòu)建與有效性驗(yàn)證

本文采用隨機(jī)生成的方法構(gòu)建算例，構(gòu)建一個(gè)大小為30km×30km 的歐氏平面，配送中心的坐標(biāo)為（15,15），客戶(hù)規(guī)模為200個(gè)，客戶(hù)的配送需求滿(mǎn)足均值為5，標(biāo)準(zhǔn)差為2 的高斯分布，設(shè)定25%的節(jié)點(diǎn)有取貨要求，5%既有送貨也有取貨需求的客戶(hù)節(jié)點(diǎn)，詳細(xì)的客戶(hù)信息見(jiàn)表3。設(shè)定運(yùn)輸車(chē)的載荷為150kg，車(chē)輛的固定啟動(dòng)成本c1為600 元，車(chē)輛平均行駛速度為50km/h，單位距離的行駛成本c2為5 元，運(yùn)輸車(chē)從配送中心出發(fā)，完成規(guī)劃的配送任務(wù)后返回配送中心。算法使用Python3.8 編程，在主頻2.1GHz，8GB 內(nèi)存的PC 上運(yùn)行。

表3 配送信息

算法第一階段RPC 算法是將問(wèn)題按規(guī)模劃分為多個(gè)子問(wèn)題，使得每個(gè)子問(wèn)題的規(guī)模為一輛運(yùn)輸車(chē)即可完成全部服務(wù)，計(jì)算總送貨量為755kg，總?cè)∝浟繛?90kg，通過(guò)式（10）計(jì)算得出M 值為6。通過(guò)區(qū)域劃分聚類(lèi)算法對(duì)所有點(diǎn)進(jìn)行劃分，聚類(lèi)的結(jié)果如圖2 所示。

圖2 客戶(hù)節(jié)點(diǎn)聚類(lèi)結(jié)果圖

通過(guò)第一階段的分解后，使用HVNS 分別求解子問(wèn)題，設(shè)置初始溫度為50 000，退火速率為0.98，最終溫度為15，返回迭代過(guò)程中出現(xiàn)的最優(yōu)解。算法求得6 條配送子路徑。使用兩階段算法生成的配送方案路線圖如圖3 所示，每一個(gè)閉環(huán)代表一輛運(yùn)輸車(chē)的配送路徑。

圖3 配送方案路徑

生成的配送子路徑中，路徑中服務(wù)的客戶(hù)數(shù)量有的區(qū)別較大，但配送的里程接近，如路徑6 的客戶(hù)服務(wù)數(shù)量為21，配送里程為62.3，路徑3 的客戶(hù)服務(wù)數(shù)量為40，配送里程為68.1，與路徑6 的里程接近，在平均速度近似的情況下，每輛運(yùn)輸車(chē)的配送時(shí)間也接近。由于RPC 算法僅有地理坐標(biāo)與車(chē)輛載荷維度的約束，因此若考慮到配送中的裝卸貨的需求，會(huì)有任務(wù)分配不均勻的情況發(fā)生。

3.2 算法對(duì)比與分析

針對(duì)3.1 構(gòu)建的算例，本文對(duì)比了文獻(xiàn)[9]中提出的變鄰域搜索算法（GVNS）和文獻(xiàn)[20]中提出的的改進(jìn)遺傳算法（GA）。分別使用各算法求解10 次，得到計(jì)算結(jié)果的平均值與標(biāo)準(zhǔn)差，算法對(duì)比結(jié)果如表4 所示。結(jié)果顯示，本文所提出的兩階段策略在處理較大規(guī)模的算例上具有優(yōu)勢(shì)，對(duì)比文獻(xiàn)[9]的GVNS，車(chē)輛行駛距離減少了17.8%，成本節(jié)約了8.6%，時(shí)間節(jié)省了77.9%；對(duì)比文獻(xiàn)[20]的GA，車(chē)輛行駛距離減少了82.8%，成本節(jié)約了66.6%，時(shí)間節(jié)省了73.8%。兩階段算法在規(guī)模較大時(shí)解的質(zhì)量與求解時(shí)間均優(yōu)于傳統(tǒng)啟發(fā)式算法，這是由于當(dāng)算例規(guī)模增大時(shí)，解空間呈指數(shù)級(jí)增長(zhǎng)，傳統(tǒng)啟發(fā)式算法每次迭代都需要花較長(zhǎng)時(shí)間，難以收斂，兩階段的策略將大規(guī)模問(wèn)題劃分為多個(gè)小規(guī)模的子問(wèn)題，減少了計(jì)算時(shí)間，同時(shí)提高了算法的尋優(yōu)效果。

表4 與算法結(jié)果對(duì)比

3.3 構(gòu)建多個(gè)規(guī)模算例

本文將RPCHVNS 算法應(yīng)用于幾個(gè)不同規(guī)模的算例，并與GVNS 和GA 的計(jì)算結(jié)果進(jìn)行對(duì)比分析。構(gòu)建客戶(hù)規(guī)模分別為20、50、100 和200 的隨機(jī)算例，算例的構(gòu)建方法與3.1 中采取的方法相同。分別對(duì)每個(gè)規(guī)模求解10 次，獲得其配送成本的最優(yōu)解、平均值與標(biāo)準(zhǔn)差。不同算法在不同規(guī)模算例下的數(shù)值結(jié)果如表5 所示。

表5 不同算法在不同規(guī)模算例下的數(shù)值結(jié)果

計(jì)算結(jié)果顯示本文提出的RPCHVNS 算法在求解不同規(guī)模問(wèn)題上都有良好的性能表現(xiàn)。在客戶(hù)規(guī)模為20 的算例中，RPCHVNS 與GA 和GVNS 的效果區(qū)別并不明顯，從標(biāo)準(zhǔn)差上看，GA 與GVNS 能夠得出比本文算法更加穩(wěn)定的結(jié)果；當(dāng)規(guī)模達(dá)到50 時(shí)，由于GA 的局部搜索性能較差，求解質(zhì)量較差，GVNS 和RPCHVNS 的表現(xiàn)良好；當(dāng)規(guī)模超過(guò)100 時(shí)，可以看出RPCHVNS 能夠得出的解更加優(yōu)秀，且穩(wěn)定性表現(xiàn)良好。因此，本文提出的RPCHVNS 更加適合規(guī)模較大的問(wèn)題，解的質(zhì)量和穩(wěn)定性都表現(xiàn)良好。

4 結(jié)論與展望

本文考慮了實(shí)際物流配送中常見(jiàn)的同時(shí)取送貨的情景，構(gòu)建了帶同時(shí)取送貨的物流配送數(shù)學(xué)模型，采用了兩階段算法RPCHVNS 求解該類(lèi)問(wèn)題，首先通過(guò)區(qū)域劃分聚類(lèi)算法將問(wèn)題分解為多個(gè)小規(guī)模的子問(wèn)題，對(duì)于每個(gè)子問(wèn)題，設(shè)計(jì)了混合變鄰域搜索算法求解配送路徑。通過(guò)數(shù)值實(shí)驗(yàn)證明了RPCHVNS 在求解不同規(guī)模同時(shí)取送貨物流配送問(wèn)題的有效性，對(duì)比傳統(tǒng)啟發(fā)式算法，RPCHVNS 在客戶(hù)規(guī)模較小時(shí)優(yōu)越性并不明顯，當(dāng)規(guī)模增大到數(shù)百個(gè)時(shí)，本文算法在求解時(shí)間和數(shù)值結(jié)果上都有良好的表現(xiàn)，這為企業(yè)在開(kāi)展同時(shí)取送貨業(yè)務(wù)時(shí)提供了參考意義。

本文在第一階段的聚類(lèi)過(guò)程中，僅考慮了地理位置與車(chē)輛載荷約束，而實(shí)際配送過(guò)程中可能會(huì)有裝卸貨與時(shí)間窗約束，而當(dāng)約束增多時(shí)，不可行解的數(shù)量也增多，算法的尋優(yōu)能力難以保證。因此下一步的工作將對(duì)考慮時(shí)間窗和裝卸貨的同時(shí)取送貨問(wèn)題展開(kāi)研究，并不斷改進(jìn)RPCHVNS 的尋優(yōu)性能。