考慮動(dòng)態(tài)需求的多中心沿途補(bǔ)貨冷鏈物流配送路徑優(yōu)化

譚曉偉 王雪韻 胡大偉

為提升冷鏈物流配送效率、降低物流成本，本文在綜合考慮多配送中心、客戶動(dòng)態(tài)需求、沿途補(bǔ)貨策略的前提下，建立以總配送成本和客戶滿意度最優(yōu)為目標(biāo)的冷鏈物流配送模型.模型采用主目標(biāo)法處理客戶滿意度和成本之間的背反關(guān)系，將動(dòng)態(tài)問題按照時(shí)間軸依次分解為一系列的靜態(tài)調(diào)度子問題并考慮了5種配送成本.本文提出自適應(yīng)大鄰域搜索算法求解該模型，設(shè)計(jì)了三種破壞算子和三種修復(fù)算子，對(duì)小中大三種不同規(guī)模的算例進(jìn)行測(cè)算.結(jié)果表明該算法在速度、精度和穩(wěn)定性上表現(xiàn)良好，對(duì)求解此類問題有較好的適應(yīng)性和準(zhǔn)確性.與不考慮沿途補(bǔ)貨策略的動(dòng)態(tài)配送方案相比，沿途補(bǔ)貨策略可使成本降低23.06%、客戶滿意度提升8.69%.結(jié)果表明提出的配送方案可很好地節(jié)約企業(yè)的配送資源、減少配送成本、增強(qiáng)競爭力.

物流工程； 冷鏈物流； 自適應(yīng)大鄰域搜索算法； 配送路徑優(yōu)化； 動(dòng)態(tài)需求； 沿途補(bǔ)貨

U492.3A2023.022002

收稿日期： 2022-08-31

基金項(xiàng)目： 陜西省自然科學(xué)基金項(xiàng)目（2021JZ-20）

作者簡介： 譚曉偉（1985-）， 男， 內(nèi)蒙赤峰人， 工程師， 博士生， 主要研究方向?yàn)槲锪鲀?yōu)化. E-mail： tanxw@chd.edu.cn

通訊作者： 胡大偉. E-mail： dwhu@chd.edu.cn

Research on distribution routing optimization of multi-center cold chain logistics for replenishment along the way considering dynamic demand

TAN Xiao-Wei1， WANG Xue-Yun2，? HU Da-Wei3

（1. School of Automobile， Changan University， Xian 710018，? China；? 2. Daqing Water Affairs Bureau， Daqing 163311， China;

3. School of Transportation Engineering， Changan University， Xian 710064， China）

To improve the efficiency of cold chain logistics distribution and reduce logistics cost， a cold chain logistics distribution model is established to optimize both total distribution cost and customer satisfaction on the premise of comprehensively considering multiple distribution centers， customers dynamic demand and strategy of replenishment along the way. A principal objective method is used to deal with the inverse relationship between customer satisfaction and cost， and the dynamic problem is decomposed into a series of static scheduling sub-problems according to the time axis with five kinds of distribution cost considered. An adaptive large neighborhood search algorithm is designed to solve the peoposed model with three kinds of damage operators and three repair operators. Small， medium and large-scale examples are calculated respectively， the results show that the algorithm performs well in terms of speed， accuracy and stability， and moreover， is adaptable and accurate in solving such problems. Compared with the dynamic distribution scheme without considering strategy of replenishment along the way， the cost is reduced by 23.06% and the customer satisfaction is improved by 8.69% by the strategy of replenishment along the way， this? confirms the proposed distribution scheme can save distribution resources， reduce distribution cost and enhance the competitiveness of enterprises.

Logistics engineering; Cold chain logistics; Adaptive large neighborhood search algorithm; Distribution routing optimization; Dynamic demand; Replenishment along the way

1 引 言

隨著人們對(duì)生活品質(zhì)的要求不斷提高，生鮮電商迅猛發(fā)展、冷藏食品消費(fèi)量不斷升級(jí)，冷鏈物流配送問題日益凸顯.生鮮產(chǎn)品保質(zhì)期短、易損耗，需要冷鏈物流具有較高的時(shí)效性.因此，合理規(guī)劃配送路徑，提高客戶滿意度的同時(shí)，降低配送成本，成為冷鏈物流的關(guān)鍵問題.

在基于動(dòng)態(tài)冷鏈物流配送問題的研究方面，Mustafa等［1］建立了綜合考慮車輛行駛速度變動(dòng)和碳排放的數(shù)學(xué)模型，并設(shè)計(jì)了遺傳算法對(duì)其求解，結(jié)果發(fā)現(xiàn)所提出的模型和求解方法適用于可持續(xù)物流決策過程中的許多實(shí)際應(yīng)用場景；王淑云等［2］針對(duì)研究的動(dòng)態(tài)蓄冷式多溫共配問題，構(gòu)建了考慮隨機(jī)需求的以成本最小為目標(biāo)的數(shù)學(xué)模型，模型考慮了正向配送和反向補(bǔ)貨兩種情況；Rajeev等［3］考慮服務(wù)訂單和服務(wù)時(shí)間呈概率彈性變化的特點(diǎn)，建立了以運(yùn)輸成本最小和客戶滿意度最高為目標(biāo)的數(shù)學(xué)模型；Reza等［4］研究綠色交通條件下易腐產(chǎn)品的動(dòng)態(tài)綠色車輛路徑問題，優(yōu)化了動(dòng)態(tài)交通網(wǎng)絡(luò)的總成本，有效減少了環(huán)境影響，提高了顧客滿意度；林明錦等［5］研究考慮客戶需求動(dòng)態(tài)變化和軟時(shí)間窗的兩級(jí)路徑優(yōu)化問題，設(shè)置合適的概率閾值來調(diào)整客戶動(dòng)態(tài)度，動(dòng)態(tài)包括客戶點(diǎn)新增和需求量變動(dòng)兩種.

在基于沿途補(bǔ)貨冷鏈物流配送問題的研究方面，李延暉等［6］研究了考慮沿途補(bǔ)貨的多配送中心車輛路徑問題，建立了以運(yùn)輸成本最小為目標(biāo)的數(shù)學(xué)模型，設(shè)計(jì)了帶補(bǔ)貨控制因子的蟻群算法對(duì)問題進(jìn)行求解，表明沿途補(bǔ)貨策略能更有效地利用車輛資源；張景玲等［7］考慮沿途補(bǔ)貨的動(dòng)態(tài)路徑優(yōu)化問題，采用自適應(yīng)免疫量子進(jìn)化算法，證明了動(dòng)態(tài)條件下沿途補(bǔ)貨策略的實(shí)用性；Luca等［8］研究了考慮補(bǔ)貨的車輛路徑問題，當(dāng)車輛的剩余載重不足以支撐后續(xù)服務(wù)計(jì)劃時(shí)，車輛選擇去倉庫補(bǔ)貨，通過后續(xù)測(cè)試發(fā)現(xiàn)，選擇補(bǔ)貨策略的配送方案能提高運(yùn)輸總效率；李國明等［9］研究了客戶需求和服務(wù)時(shí)間都隨機(jī)改變的車輛路徑問題，同時(shí)在配送方案中加入補(bǔ)貨策略，設(shè)計(jì)了改進(jìn)的禁忌搜索算法對(duì)問題進(jìn)行求解，并用6種不同實(shí)驗(yàn)對(duì)算法進(jìn)行評(píng)估.

在基于多配送中心的物流配送問題的研究方面，Lahyani等［10］使用自適應(yīng)大鄰域搜索算法求解多車場開放式問題，采用多組不同規(guī)模數(shù)據(jù)進(jìn)行測(cè)試，最大為6個(gè)配送中心288個(gè)客戶點(diǎn)，證明了自適應(yīng)大鄰域搜索算法對(duì)于求解此類問題的適應(yīng)性和優(yōu)越性；Husakou等［11］研究了多車場異構(gòu)車隊(duì)開放式路徑問題，不同車隊(duì)的單位運(yùn)輸成本和載重容量不同，模型以最小的運(yùn)輸成本為目標(biāo)，文章使用標(biāo)準(zhǔn)的混合整數(shù)規(guī)劃求解器求解實(shí)例并獲得最優(yōu)解；Sadati等［12］研究多車場綠色路徑優(yōu)化問題，建立了以運(yùn)輸總路徑最短為目標(biāo)的數(shù)學(xué)模型，設(shè)計(jì)了禁忌搜索算法和廣義變鄰域搜索算法相結(jié)合的算法，通過測(cè)算小規(guī)模算例證明了該算法具有較強(qiáng)的魯棒性；范厚明等［13］研究多配送中心同時(shí)配集貨路徑優(yōu)化問題，模型考慮包括理貨成本在內(nèi)的三種成本，并設(shè)計(jì)混合遺傳算法對(duì)算例進(jìn)行求解.

通過上述分析可知，目前冷鏈物流研究文獻(xiàn)雖多，但大部分集中于傳統(tǒng)靜態(tài)車輛路徑問題和單配送中心固定區(qū)域范圍配送問題，綜合考慮多配送中心和客戶動(dòng)態(tài)需求的冷鏈物流研究較少，考慮沿途補(bǔ)貨的文獻(xiàn)亦不多.綜合考慮客戶需求變化情況和多配送中心的配送條件更加貼合冷鏈物流企業(yè)配送的現(xiàn)實(shí)場景，同時(shí)，考慮沿途補(bǔ)貨策略能夠節(jié)約企業(yè)資源，提高冷鏈物流配送的快速響應(yīng)能力和配送效率.因此，本文構(gòu)建了考慮動(dòng)態(tài)需求和沿途補(bǔ)貨的多配送中心冷鏈物流配送模型并設(shè)計(jì)了相應(yīng)的自適應(yīng)大鄰域搜索算法對(duì)其給予有效求解，旨在提高冷鏈物流企業(yè)的服務(wù)能力，提高客戶的滿意程度.對(duì)冷鏈物流企業(yè)控制成本的同時(shí)，保持企業(yè)核心競爭力有著很大的現(xiàn)實(shí)意義和應(yīng)用價(jià)值.

2 問題描述及模型建立

2.1 問題描述

在規(guī)定的時(shí)間段內(nèi)，某區(qū)域的多個(gè)配送中心共同服務(wù)一定數(shù)量的客戶，配送產(chǎn)品為單一的冷鏈產(chǎn)品，通過對(duì)車輛配送路線的合理規(guī)劃從而滿足求解目標(biāo).其中客戶分為靜態(tài)客戶和動(dòng)態(tài)客戶，靜態(tài)客戶指配送開始前一天下單的客戶，動(dòng)態(tài)客戶指配送開始后，實(shí)時(shí)出現(xiàn)的新增訂單客戶.由于可能存在動(dòng)態(tài)客戶大量出現(xiàn)后車輛載重不足或原始配送中心缺貨等現(xiàn)實(shí)情況，車輛允許中途去區(qū)域內(nèi)的任一個(gè)配送中心補(bǔ)貨.所研究問題的示意圖如圖1所示.

2.2 問題假設(shè)

為了簡化問題并保證解決方案的可操作性，假設(shè)：（1） 運(yùn)輸時(shí)忽略貨物的體積、形狀等因素，只考慮貨物重量對(duì)車輛載重的影響；（2） 除了配送中出現(xiàn)的動(dòng)態(tài)訂單，其余初始訂單的全部信息都是已知的，當(dāng)動(dòng)態(tài)訂單出現(xiàn)時(shí)該訂單的全部信息隨即已知；（3） 車輛是同質(zhì)車輛；（4） 整個(gè)配送體系包含若干配送中心，所有配送中心庫的位置已知，所有車輛從配送中心出發(fā)，完成配送任務(wù)后返回各自的配送中心；（5） 忽略上級(jí)向配送中心配備貨物的過程，整個(gè)配送過程忽略貨物在配送中心內(nèi)的損耗，只計(jì)算在車輛運(yùn)送過程中的貨損成本；（6） 每個(gè)客戶點(diǎn)只被服務(wù)一次，客戶點(diǎn)的需求不可拆分；（7） 車輛在運(yùn)行過程中始終處于勻速行駛；（8） 在配送中心補(bǔ)貨需要的時(shí)間與客戶點(diǎn)服務(wù)時(shí)間一致；（9） 每個(gè)配送中心的車輛都是足夠的，不存在無法發(fā)車的情況.涉及的符號(hào)說明如表1所示.

3 算法設(shè)計(jì)

3.1 求解思路

采用自適應(yīng)大鄰域搜索算法（Adaptive Large Neighborhood Search， ALNS）對(duì)該模型求解，具體的算法流程如圖2所示.

對(duì)于分布在某個(gè)區(qū)域的多家配送中心而言，首先依據(jù)靜態(tài)客戶規(guī)劃初始路徑.在實(shí)時(shí)服務(wù)時(shí)間窗口開放時(shí)，配送中心將處理陸續(xù)接到的新增客戶訂單需求.考慮到動(dòng)態(tài)問題的復(fù)雜性，首先將動(dòng)態(tài)問題分成若干個(gè)靜態(tài)子問題進(jìn)行簡化，本文選擇將配送時(shí)間窗劃分成多個(gè)時(shí)間片段，每到時(shí)間片段的節(jié)點(diǎn)時(shí)統(tǒng)計(jì)一次動(dòng)態(tài)信息，將上一個(gè)時(shí)間片段內(nèi)出現(xiàn)的新增客戶進(jìn)行處理，此時(shí)整個(gè)系統(tǒng)中待服務(wù)的客戶有初始路徑中未完成配送的客戶和新增客戶兩類，如圖1所示，配送策略分三種類型.

（1） 路徑中某個(gè)正在執(zhí)行配送任務(wù)車輛的剩余載重量足以為待服務(wù)的客戶服務(wù)，路徑中插入新增客戶后全部待服務(wù)客戶點(diǎn)的時(shí)間窗仍然滿足，且配送成本低于重新發(fā)車的成本，則將新增客戶分配給該車輛，車輛更新路徑，按照新路徑規(guī)劃依次服務(wù).

（2） 路徑中某個(gè)正在執(zhí)行配送任務(wù)車輛的剩余載貨量不足以為待服務(wù)的客戶服務(wù) ，此時(shí)車輛可以選擇去臨近的配送中心補(bǔ)貨，當(dāng)補(bǔ)貨完成后足以為待服務(wù)客戶配送并且仍滿足路徑中所有待服務(wù)客戶的時(shí)間窗要求且配送成本比重新發(fā)車低，則將新增客戶分配給該車輛，車輛更新路徑，按照新路徑規(guī)劃依次服務(wù).

（3） 路徑中任意車輛剩余載貨量不足以為待服務(wù)的客戶服務(wù)，且任意車輛去臨近配送中心補(bǔ)貨后無法滿足后續(xù)待服務(wù)客戶時(shí)間窗要求，或者任意車輛給新增客戶服務(wù)的成本都高于配送中心單獨(dú)發(fā)車給新增客戶服務(wù)的成本，此時(shí)配送中心新派車輛對(duì)新增客戶進(jìn)行服務(wù)，已出發(fā)的車輛按照原規(guī)劃路徑進(jìn)行配送.

3.2 初始解的構(gòu)造

使用構(gòu)造方法產(chǎn)生初始解.首先對(duì)客戶點(diǎn)進(jìn)行隨機(jī)排序，然后在滿足載重約束、時(shí)間窗約束的情況下當(dāng)遇到可行插入的位置時(shí)將客戶點(diǎn)插入，隨即產(chǎn)生問題的初始解Sinitial，然后在該初始解的基礎(chǔ)上進(jìn)行固定次數(shù)的迭代，迭代過程中使用破壞和修復(fù)算子進(jìn)行鄰域搜索.初始解構(gòu)造的基本流程如下.

Step1：將待安排的客戶進(jìn)行隨機(jī)排序得到客戶集合B，輸入當(dāng)前的線路數(shù)據(jù)，當(dāng)沒有進(jìn)行動(dòng)態(tài)更新時(shí)當(dāng)前線路為空集，開始更新時(shí)，當(dāng)前線路數(shù)據(jù)為上一個(gè)周期優(yōu)化結(jié)束后線路去除可重新安排的客戶點(diǎn)的剩余線路；

Step2：為客戶集合B中的第一個(gè)客戶i尋找當(dāng)前周期新增車輛中滿足所有約束的插入位置，若存在，將客戶點(diǎn)插入后更新線路并進(jìn)入Step5，反之進(jìn)入Step3；

Step3：為客戶i尋找上周期使用的車輛中滿足所有約束的插入位置，若存在，將客戶點(diǎn)i插入后更新線路并進(jìn)入Step5，反之進(jìn)入Step4；

Step4：找到距離客戶i最近的配送中心發(fā)車形成新的線路，并進(jìn)入Step5；

Step5：依次對(duì)客戶集合B中其他客戶點(diǎn)進(jìn)行Step2～Step4操作，直到所有客戶點(diǎn)均被服務(wù)，

輸出完整線路，輸出初始解.

3.3 破壞和修復(fù)策略設(shè)計(jì)

3.3.1 破壞算子 破壞算子對(duì)當(dāng)前解中的客戶點(diǎn)做出部分移除處理，目的是為移除的客戶在后續(xù)安排更合理的路線，本文選用了三種破壞算子.

（1） 隨機(jī)破壞算子：隨機(jī)破壞是最常用的破壞方法，表示在當(dāng)前解中隨機(jī)移除一定個(gè)數(shù)的客戶點(diǎn)，這樣的方法有助于增加搜索的多樣性，不易陷入局部最優(yōu).隨機(jī)破壞是在當(dāng)前解的客戶集B中隨機(jī)刪除q個(gè)客戶點(diǎn)，產(chǎn)生一個(gè)缺少q個(gè)客戶點(diǎn)的部分解決方案和q個(gè)后續(xù)待插入的零散客戶.

（2） 相關(guān)破壞算子：相關(guān)破壞算子的基本思想是將某些特征相似的點(diǎn)刪除，原因是具有相關(guān)性的客戶點(diǎn)在空間上往往呈現(xiàn)聚集的狀態(tài)，刪除這類客戶點(diǎn)可在盡量少破壞已經(jīng)較合理的規(guī)劃線路前提下探尋更優(yōu)的解.設(shè)置了兩種相關(guān)性刪除：① 距離相關(guān)破壞算子：這種刪除基于點(diǎn)與點(diǎn)之間距離相關(guān)性，首先根據(jù)刪除數(shù)量q生成待刪除客戶的空集列表A，從當(dāng)前解Scurr的客戶點(diǎn)集中隨機(jī)選擇一個(gè)客戶點(diǎn)i，將它放入刪除列表A中，然后計(jì)算Scurr中剩余點(diǎn)和i的距離，選擇最近的點(diǎn)依次移入刪除列表A中，直到A中的數(shù)量達(dá)到q.算子的相關(guān)性函數(shù)R1為：R1=dij；② 時(shí)間相關(guān)破壞算子：這種算子的破壞基于時(shí)間窗的相關(guān)性，同距離相關(guān)破壞算子操作一致，不同之處在于基于時(shí)間窗的相關(guān)性函數(shù)R2為：R2=ETi-ETj+LTi-LTj.

（3） 匯集度破壞算子：匯集度破壞算子就是優(yōu)先破壞當(dāng)前解的路徑中服務(wù)客戶數(shù)較少的那些路徑，目的在于盡量刪除短路徑，減少發(fā)車數(shù)量.首先判斷所有路徑服務(wù)客戶數(shù)量，選擇在服務(wù)客戶數(shù)量最少的路徑中隨機(jī)刪除客戶點(diǎn)，重復(fù)判斷過程和刪除過程直到刪除數(shù)量達(dá)到q.

3.3.2 修復(fù)算子 修復(fù)算子是將破壞過程移除的客戶點(diǎn)以更優(yōu)的方式插入到當(dāng)前解中，本文選用三種修復(fù)算子.

（1） 貪婪修復(fù)算子：貪婪修復(fù)算子的基本思想指將被移除的客戶點(diǎn)逐個(gè)以最小插入成本的方式插回到路徑中，貪婪插入比較的成本是插入客戶點(diǎn)后總配送成本的大小，避免了插入成本和總配送成本變化不一致的情況.假設(shè)L表示所有可插入的路徑的集合，L包括已發(fā)出車輛所在的路徑和配送中心待發(fā)出車輛的路徑，算子的核心思想就是找到使插入成本達(dá)到最小的路徑和位置，然后將客戶插入該位置.

（2） 最短距離修復(fù)算子：最短距離修復(fù)算子是根據(jù)客戶點(diǎn)距離成本的大小來進(jìn)行插入的，因?yàn)檫\(yùn)輸成本在成本內(nèi)占比往往較高，所以以距離成本最小為插入的衡量標(biāo)準(zhǔn)有更高的概率找到最優(yōu)方案.在每次迭代中，計(jì)算待插入客戶點(diǎn)與路徑中所有客戶點(diǎn)的距離，選取距離最短路徑及位置插入.

（3） 匯集度修復(fù)算子：匯集度修復(fù)算子的目的在于盡量少產(chǎn)生新的路徑，減少發(fā)車數(shù)量.首先判斷是否存在滿足配送要求的已出發(fā)路徑，如果存在按最小成本插入路徑，如果不存在，選擇距離客戶點(diǎn)最近配送中心新派車配送.

3.4 算子選擇策略和自適應(yīng)權(quán)重調(diào)整機(jī)制

算子選擇策略為賦予算子不同的權(quán)重值，通過算子權(quán)重的變化改變算子被選擇的概率大小.本文算法在初始化階段給予每個(gè)算子相同的權(quán)重值1，后期算子權(quán)重的調(diào)整有賴于算法自適應(yīng)的過程，自適應(yīng)過程其實(shí)就是計(jì)算并記錄每個(gè)算子在迭代過程中的得分，用得分衡量該算子的表現(xiàn)，算子的表現(xiàn)越好得分越高，得分越高則在下一輪被選擇的概率越大.預(yù)先為算法設(shè)置三種打分的分?jǐn)?shù)σ1、σ2、σ3（σ1>σ2>σ3），算法根據(jù)新解可能出現(xiàn)的三種情況進(jìn)行迭代過程中算子的評(píng)分過程：（1） 新解是一個(gè)新的全局最優(yōu)解，評(píng)分增加σ1； （2）? 新解優(yōu)于當(dāng)前解，評(píng)分增加σ2； （3）? 新解差于當(dāng)前解但仍被算法的接受準(zhǔn)則接納，評(píng)分增加σ3.對(duì)于某一個(gè)算子k而言，假設(shè)mk為在該片段中使用算子k的次數(shù)，πk為算子在該片段的得分，更新權(quán)重ρk如下式：

ρk=ρk， mk=0

ρk（1-ζ）+ρkπkmk， mk>0（36）

式中，ζ用于調(diào)整權(quán)重對(duì)于算子有效性的影響，取值在（0，1）之間.當(dāng)ζ=0時(shí)，評(píng)分對(duì)權(quán)重?zé)o影響，當(dāng)ζ=1時(shí)，權(quán)重的取值完全由評(píng)分決定.當(dāng)0<ζ<1時(shí)，權(quán)重的取值同時(shí)考慮最近得分與過去的表現(xiàn).

3.5 客戶移除數(shù)量選擇機(jī)制和終止條件

在每次進(jìn)行破壞算子操作時(shí)都要明確需要移除的客戶數(shù)量q，參考算子選擇策略和自適應(yīng)權(quán)重調(diào)整機(jī)制的評(píng)分過程，在每次破壞和修復(fù)操作前對(duì)移除客戶數(shù)量q進(jìn)行評(píng)分，設(shè)置了三種移除數(shù)量比例參數(shù)的選擇q1、q2、q3，移除客戶點(diǎn)的具體數(shù)量根據(jù)算例節(jié)點(diǎn)規(guī)模不同而變化.當(dāng)算例中客戶的數(shù)量為U時(shí)，假設(shè)此時(shí)選中的客戶移除數(shù)量比例參數(shù)為q1，則實(shí)際移除的客戶數(shù)量q為：q=Uq1.給三種移除數(shù)量比例參數(shù)每種一個(gè)初始權(quán)重1，后期權(quán)重根據(jù)移除數(shù)量參數(shù)的表現(xiàn)而變化.首先隨機(jī)選擇一種移除數(shù)量比例參數(shù)，每段迭代結(jié)束后會(huì)給該移除數(shù)量比例參數(shù)打分并根據(jù)分?jǐn)?shù)修改該移除數(shù)量比例參數(shù)的權(quán)重，采用和破壞、修復(fù)算子一致的三種評(píng)分的分?jǐn)?shù)σ1、σ2、σ3（σ1>σ2>σ3），算法依然根據(jù)新解可能出現(xiàn)的三種情況進(jìn)行迭代中移除數(shù)量的評(píng)分過程.采用迭代次數(shù)終止規(guī)則，此規(guī)則通過設(shè)定最大迭代次數(shù)，一旦算法迭代搜索次數(shù)達(dá)到最大迭代次數(shù)則終止運(yùn)行.

4 算例試驗(yàn)與結(jié)果分析

通過使用三種不同規(guī)模的數(shù)據(jù)對(duì)構(gòu)建模型和提出的算法進(jìn)行有效性測(cè)試，同時(shí)對(duì)算例結(jié)果進(jìn)行分析，全部測(cè)試是在運(yùn)行環(huán)境為2.4 GHZ Intel COREi5 CPU、內(nèi)存4 GB的Windows10系統(tǒng)的Dell電腦上進(jìn)行的，編程和運(yùn)行軟件為MATLAB R2018a.

4.1 算法參數(shù)分析

選擇合適的評(píng)分機(jī)制更有助于算法整體效果的提升，因此對(duì)算法評(píng)分參數(shù)σ1、σ2、σ3、ζ進(jìn)行分析，通過文獻(xiàn)［10］找到五組已被驗(yàn)證有良好效果的評(píng)分機(jī)制，篩選出適合的一組評(píng)分機(jī)制，為后續(xù)的算例結(jié)果分析提供依據(jù).分別用五組評(píng)分機(jī)制測(cè)算本文的小規(guī)模算例和中規(guī)模算例，為了盡量減少誤差對(duì)求解結(jié)果的影響，每個(gè)算例測(cè)試三次，用S表示小規(guī)模算例，用M表示中規(guī)模算例，S-1表示小規(guī)模第一次測(cè)試、M-1表示中規(guī)模第一次測(cè)試，其余同理.小規(guī)模、中規(guī)模算例的測(cè)試結(jié)果見表2.

通過算例測(cè)試發(fā)現(xiàn)，幾組評(píng)分分?jǐn)?shù)在測(cè)試小規(guī)模算例時(shí)得到的結(jié)果相差不大，但是當(dāng)測(cè)試中規(guī)模算例時(shí)差距開始顯現(xiàn)，其中［1，0.4，0.25，0.25］這組分?jǐn)?shù)的表現(xiàn)優(yōu)于其余幾組評(píng)分分?jǐn)?shù)，更適合所研究的問題，因此選擇這組參數(shù)進(jìn)行后續(xù)的數(shù)據(jù)分析，客戶數(shù)量移除比例參數(shù)通過測(cè)試調(diào)整得到，q1、q2、q3分別為1%、15%、30%.

4.2 算例求解與分析

文獻(xiàn)［20］等采取了Solomon數(shù)據(jù)集中R102數(shù)據(jù)，但算例沒有區(qū)分動(dòng)態(tài)和靜態(tài)客戶.本文在其算例基礎(chǔ)上進(jìn)行改造，將算例中的客戶分成靜

態(tài)客戶和動(dòng)態(tài)客戶，其中，小規(guī)模算例的客戶點(diǎn)相關(guān)信息如表3所示，算例其他相關(guān)參數(shù)如表4所示，中、大規(guī)模算例客戶點(diǎn)數(shù)據(jù)來源自文獻(xiàn)［21］.將劃分的時(shí)間片段即配送的時(shí)間間隔設(shè)置為1小時(shí)，客戶滿意度最小值為0.7，9∶00后開始處理［8∶00～9∶00］之間出現(xiàn)的動(dòng)態(tài)客戶信息.①②表示配送中心編號(hào)，1～5表示靜態(tài)客戶編號(hào)，6、7表示動(dòng)態(tài)客戶編號(hào).

使用LINGO求解器求解小規(guī)模算例，驗(yàn)證模型的準(zhǔn)確性，并和本文設(shè)計(jì)的ALNS算法求解結(jié)果進(jìn)行對(duì)比，如表5所示. ALNS算法獲得了和LINGO相同的最優(yōu)解，而求解時(shí)間明顯少于LINGO的求解時(shí)間.中規(guī)模算例有52個(gè)點(diǎn)，其中2個(gè)為配送中心點(diǎn)，30個(gè)靜態(tài)客戶點(diǎn)，20個(gè)動(dòng)態(tài)客戶點(diǎn).編號(hào)1～30為靜態(tài)客戶，編號(hào)31～50為動(dòng)態(tài)客戶，動(dòng)態(tài)更新4次，迭代次數(shù)設(shè)置為200次.大規(guī)模算例有103個(gè)節(jié)點(diǎn)，其中3個(gè)為配送中心點(diǎn)，60個(gè)靜態(tài)客戶點(diǎn)，40個(gè)動(dòng)態(tài)客戶點(diǎn).編號(hào)1～60為靜態(tài)客戶，編號(hào)61～100為動(dòng)態(tài)客戶，動(dòng)態(tài)更新6次，迭代次數(shù)設(shè)置為200次.兩種規(guī)模運(yùn)行結(jié)果如表6所示.靜態(tài)客戶的初始配送路徑和動(dòng)態(tài)結(jié)束后最終配送路徑如表7所示.其中①（補(bǔ)）、②（補(bǔ)）、③（補(bǔ)）表示車輛去到某個(gè)配送中心補(bǔ)貨.

由表6可以看出，中規(guī)模算例的總成本為2246.8821元，客戶滿意度的平均值0.9409，計(jì)算運(yùn)行時(shí)間為363.24 s；大規(guī)模算例的總成本為4056.1413元，客戶滿意度的平均值為0.9412，計(jì)算運(yùn)行時(shí)間為1751.21 s.可以發(fā)現(xiàn)，隨著節(jié)點(diǎn)規(guī)模增大，更新次數(shù)增加，更新算法搜索范圍變大，求得最優(yōu)解的速度變緩，計(jì)算運(yùn)行時(shí)間增加，但在可接受范圍內(nèi).

4.3 對(duì)比分析

為了體現(xiàn)考慮動(dòng)態(tài)需求的多配送中心沿途補(bǔ)貨的冷鏈物流配送方案的優(yōu)越性，將本文的方案與不允許沿途補(bǔ)貨的考慮動(dòng)態(tài)需求的多配送中心物流配送方案進(jìn)行對(duì)比.由于不允許車輛沿途補(bǔ)貨，當(dāng)車輛服務(wù)下一個(gè)客戶i的載重不足時(shí)，客戶i的需求只能由路徑中其他負(fù)載充足且滿足所有約束條件的車輛服務(wù)或配送中心新派出車輛服務(wù).選擇中規(guī)模算例作為對(duì)比數(shù)據(jù)觀察其對(duì)比效果，考慮沿途補(bǔ)貨的配送方案和不考慮沿途補(bǔ)貨的配送方案運(yùn)行成本如表8所示.

由表8可以看出，相同客戶規(guī)模下，不考慮沿途補(bǔ)貨策略的配送方案對(duì)客戶服務(wù)的成本要高于考慮沿途補(bǔ)貨策略為客戶服務(wù)的成本，高出了23.06%.同時(shí)，在客戶滿意度上，不考慮沿途補(bǔ)貨策略配送模式的客戶滿意度也比考慮沿途補(bǔ)貨策略配送模式的客戶滿意度要低8.69%.造成不考慮沿途補(bǔ)貨策略成本高的主要原因是發(fā)車數(shù)量增加，雖然配送中心發(fā)出了更多的車輛為客戶服務(wù)，但是客戶的滿意度沒有因此提高，反而低于考慮沿途補(bǔ)貨配送方案的客戶滿意度.

以上結(jié)果說明了考慮沿途補(bǔ)貨策略的配送方案具有一定的優(yōu)越性.本文的配送方案可以減少發(fā)車數(shù)量、減少企業(yè)的配送成本，同時(shí)不會(huì)犧牲客戶的滿意程度.

4.4 靈敏度分析

4.4.1 動(dòng)態(tài)更新時(shí)間的靈敏度分析 對(duì)于動(dòng)態(tài)需求配送模型來說，動(dòng)態(tài)更新時(shí)間決定了配送的及時(shí)性，動(dòng)態(tài)更新時(shí)間的長短極大地影響了車輛對(duì)動(dòng)態(tài)客戶服務(wù)的時(shí)間和路徑安排，也會(huì)改變路徑最終的配送成本.選擇對(duì)更新次數(shù)較多的大規(guī)模算例進(jìn)行測(cè)試，設(shè)置了四種更新時(shí)間，并對(duì)四種更新時(shí)間造成的配送成本變化和運(yùn)行時(shí)間變化做出對(duì)比分析.更新時(shí)間及運(yùn)行結(jié)果如表9所示.

由表9可知，隨著動(dòng)態(tài)更新次數(shù)的增加，配送的總成本逐漸增加，動(dòng)態(tài)更新次數(shù)增加后算法的計(jì)算運(yùn)行時(shí)間也增加了.這是因?yàn)楦聲r(shí)間間隔縮短時(shí)，系統(tǒng)更新路線的次數(shù)增加，動(dòng)態(tài)客戶大部分都能得到及時(shí)響應(yīng)，無需積累到一定數(shù)量后才被處理，系統(tǒng)路線重疊次數(shù)增加，運(yùn)輸成本提高明顯，因此總成本增加，算法計(jì)算時(shí)間也隨之增加.雖然動(dòng)態(tài)更新時(shí)間間隔縮短導(dǎo)致成本增加，但是客戶的平均滿意度卻隨著動(dòng)態(tài)更新次數(shù)的增加而增加.這是因?yàn)閯?dòng)態(tài)客戶需求得到及時(shí)響應(yīng)，客戶的等待時(shí)間變短，因此滿意度提高.冷鏈物流企業(yè)可以根據(jù)自己的實(shí)際需求，衡量客戶滿意度和成本對(duì)自身企業(yè)的影響，動(dòng)態(tài)調(diào)整更新時(shí)間間隔以達(dá)到利益最大化.

4.4.2 動(dòng)態(tài)客戶數(shù)的靈敏度分析 動(dòng)態(tài)客戶的數(shù)量對(duì)動(dòng)態(tài)需求配送存在較大的影響.此處主要分析動(dòng)態(tài)客戶數(shù)量對(duì)配送路徑的影響.采用動(dòng)態(tài)度來表示動(dòng)態(tài)客戶的數(shù)量.動(dòng)態(tài)度的表示方法為動(dòng)態(tài)客戶的數(shù)量除以全部客戶數(shù).動(dòng)態(tài)客戶數(shù)量越多，動(dòng)態(tài)度越大.選擇對(duì)中規(guī)模算例進(jìn)行操作.中規(guī)模算例共20個(gè)動(dòng)態(tài)客戶，30個(gè)靜態(tài)客戶，因此動(dòng)態(tài)度為0.4.改變中規(guī)模算例中的動(dòng)態(tài)客戶數(shù)量，對(duì)不同動(dòng)態(tài)度的算例進(jìn)行求解，運(yùn)行結(jié)果如表10所示.

由表10可知，隨著動(dòng)態(tài)客戶數(shù)量增加，路徑的總配送成本增大.這是因?yàn)閯?dòng)態(tài)客戶增多，路徑的重新規(guī)劃次數(shù)增多.除此之外，動(dòng)態(tài)客戶數(shù)量的增加也會(huì)使車輛的補(bǔ)貨次數(shù)或新發(fā)車次數(shù)增加.因此配送的總成本不可避免的增大.同時(shí)，動(dòng)態(tài)客戶數(shù)量增加時(shí)，算法的計(jì)算運(yùn)行時(shí)間也隨之增加.這是因?yàn)樵趧?dòng)態(tài)客戶較少時(shí)，路徑中的大部分客戶為靜態(tài)客戶，在動(dòng)態(tài)更新之前已經(jīng)找到了較好的路徑方案.因此少量動(dòng)態(tài)客戶重新加入路徑時(shí)路徑的改動(dòng)相對(duì)較少，而動(dòng)態(tài)客戶數(shù)量很多時(shí)，路徑的更新次數(shù)頻繁，需要更久的計(jì)算時(shí)間才能實(shí)現(xiàn)路徑的重新規(guī)劃.

5 結(jié) 論

本文考慮動(dòng)態(tài)客戶需求和沿途補(bǔ)貨的多配送中心冷鏈物流配送模型，更能滿足當(dāng)今市場客戶對(duì)冷鏈配送更快速更準(zhǔn)時(shí)的需求.采用主目標(biāo)法對(duì)多目標(biāo)問題進(jìn)行處理轉(zhuǎn)化為單目標(biāo)問題，保證客戶的滿意程度在較高的范圍內(nèi)而不是一味追求成本低，這樣更有助于企業(yè)的長期發(fā)展，增加企業(yè)的競爭力.

設(shè)計(jì)的自適應(yīng)大鄰域搜索算法可求解所構(gòu)建模型，自適應(yīng)評(píng)分機(jī)制可提高算法對(duì)本文問題的求解能力.通過小、中、大三種規(guī)模算例驗(yàn)證了本文算法的有效性.以中規(guī)模算例為例對(duì)比分析考慮沿途補(bǔ)貨策略的和不考慮沿途補(bǔ)貨策略的兩種配送方案，發(fā)現(xiàn)考慮沿途補(bǔ)貨策略后配送總成本可減少23.06%，發(fā)車數(shù)量減少3輛，滿意度提高8.69%.這說明動(dòng)態(tài)需求條件下考慮沿途補(bǔ)貨策略的方案具有突出的優(yōu)勢(shì).對(duì)動(dòng)態(tài)更新時(shí)間間隔和動(dòng)態(tài)客戶數(shù)量的靈敏度分析結(jié)果表明：所有客戶為完全動(dòng)態(tài)客戶時(shí)的配送成本要比所有客戶為純靜態(tài)客戶時(shí)的配送成本高出約65.14%，算法計(jì)算運(yùn)行時(shí)間多出約66.28%；當(dāng)動(dòng)態(tài)更新時(shí)間間隔縮短時(shí)，動(dòng)態(tài)更新次數(shù)增加，配送總成本增加，計(jì)算時(shí)間增加；當(dāng)動(dòng)態(tài)客戶數(shù)量增加時(shí)，路徑的總配送成本增大，計(jì)算時(shí)間增加.

未來此類問題仍需進(jìn)行更深層次的研究，如適用場景變化，多分布不同數(shù)據(jù)集的測(cè)試，算法穩(wěn)定性分析，多種車型共同配送等情況.

參考文獻(xiàn)：

［1］ Cimen M， Soysal M. Time-dependent green vehicle routing problem with stochastic vehicle speeds： an approximate dynamic programming algorithm［J］. Transport Res D-Tr， 2017， 54： 82.

［2］ 王淑云， 孫虹， 牟進(jìn)進(jìn). 隨機(jī)需求下蓄冷式多溫共配優(yōu)化模型［J］. 系統(tǒng)管理學(xué)報(bào)， 2018， 27： 712.

［3］ Goel R， Maini R， Bansal S. Vehicle routing problem with time windows having stochasticcustomers demands and stochastic service times： Modelling and Solution ［J］. J Comput Sci-Neth， 2019， 34： 1.

［4］ Talouki R Z， Javadian N， Movahedi M M. Optimization and incorporating of green traffic for dynamic vehicle routing problem with perishable products［J］. Environ Sci Pollut R， 2021， 28： 36415.

［5］ 林明錦， 王建新， 王超. 考慮動(dòng)態(tài)度和時(shí)間窗的兩級(jí)車輛路徑問題［J］. 計(jì)算機(jī)集成制造系統(tǒng)， 2021， 25： 1870.

［6］ 李延暉， 劉向. 沿途補(bǔ)貨的多車場開放式車輛路徑問題及蟻群算法［J］. 計(jì)算機(jī)集成制造系統(tǒng)， 2008， 14： 557.

［7］ 張景玲， 王萬良， 趙燕偉. 基于沿途補(bǔ)貨的多配送中心動(dòng)態(tài)需求VRP建模及優(yōu)化［J］.計(jì)算機(jī)集成制造系統(tǒng)， 2013， 19： 869.

［8］ Luca B， Nicola S. Faster rollout search for the vehicle routing problem with stochastic demands and restocking ［J］.Eur J Oper Res， 2018， 270： 1.

［9］ 李國明， 李軍華. 基于混合禁忌搜索算法的隨機(jī)車輛路徑問題［J］. 控制與決策， 2021， 36： 2161.

［10］ Lahyani R， Gouguenheim A L， Coelho L C. A hybrid adaptive large neighbourhood search for multi-depot open vehicle routing problems ［J］. Int J Prod Res， 2019， 57： 6963.

［11］ Husakou A， Hvattum L M， Danielsen K， et al. An application of the multi-depot heterogeneous fixed fleet open vehicle routing problem ［J］. Int J Adv Oper Manag， 2020， 12： 142.

［12］ Sadati M， Atay B. A hybrid variable neighborhood search approach for the multi-depot green vehicle routing problem ［J］. Transport Res E-Log， 2021， 149： 102293.

［13］ 范厚明， 張軒， 任曉雪， 等. 多中心開放且需求可拆分的VRPSDP問題優(yōu)化［J］. 系統(tǒng)工程理論與實(shí)踐， 2021， 41： 1521.

［14］ 張冬青， 郭釗俠， 張殷杰.考慮時(shí)空相關(guān)隨機(jī)行駛時(shí)間的車輛路徑問題模型與算法［J］. 四川大學(xué)學(xué)報(bào)： 自然科學(xué)版， 2021， 58： 067001.

［15］ 劉志碩， 李秋雨， 董子琦， 等. 帶軟時(shí)間窗的冷鏈電動(dòng)車輛路徑問題研究［J］. 北京交通大學(xué)學(xué)報(bào)， 2022， 46： 57.

［16］ 安健. 基于ALNS算法的城市商品配送車輛路徑問題研究［D］. 南京： 南京大學(xué)， 2020.

［17］ Ropke S， Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows［J］. Transport Sci， 2006， 40： 1.

［18］ 李蕩. 時(shí)變路網(wǎng)條件下模糊需求車輛路徑優(yōu)化研究［D］. 大連： 大連海事大學(xué)， 2020.

［19］ 南麗君， 陳彥如， 張宗成. 改進(jìn)的自適應(yīng)大規(guī)模鄰域搜索算法求解動(dòng)態(tài)需求的混合車輛路徑問題［J］. 計(jì)算機(jī)應(yīng)用研究， 2021， 38： 2926.

［20］ 王寧， 胡大偉， 徐杰， 等. 基于客戶價(jià)值和滿意度的城市冷鏈物流時(shí)變路徑問題［J］. 中國公路學(xué)報(bào)， 2021， 34： 297.

［21］ 段詩遠(yuǎn). 考慮碳交易的生鮮農(nóng)產(chǎn)品冷鏈配送選址-路徑研究［D］.北京： 北京交通大學(xué)， 2019.