陸心航 徐宗露 劉文

摘? 要： 在商品供應(yīng)鏈中，生鮮配送成本過高是亟需解決的問題。本文考慮疫情的感染風(fēng)險對生鮮配送路徑優(yōu)化問題展開研究，以最小化物流成本和最小化感染風(fēng)險為目標(biāo)構(gòu)建模型，設(shè)計優(yōu)先級三層編碼方法，使用NSGA-Ⅱ求解問題。在此基礎(chǔ)上，增加逆序鄰域策略改進NSGA-Ⅱ，提高算法的收斂性。最后進行數(shù)值實驗，驗證了模型的可行性以及改進算法的優(yōu)越性。

關(guān)鍵詞： 后疫情時代； 生鮮電商； 車輛路徑問題； NSGA-Ⅱ； 客戶滿意度

中圖分類號：C93;TP18? ? ? ? ? 文獻標(biāo)識碼：A? ? ?文章編號：1006-8228（2023）09-59-05

Research on vehicle routing problem considering the infection risk of

terminal distribution mode and consumer satisfaction

Lu Xinhang1， Xu Zonglu1， Liu Wen2

（1. Business School， Jiangnan University， Wuxi， Jiangsu 214122， China;

2. School of Mechanical Engineering， Nanjing University of Science and Technology）

Abstract： In the commodity supply chain， the high cost of fresh food distribution is an urgent problem. In this paper， considering the infection risk of the epidemic， the optimization of fresh food distribution route is studied. A model with the objectives of minimizing logistics cost and infection risk is constructed. A priority three-layer coding method is designed and NSGA-Ⅱ is used to solve the problem. On this basis， the inversion neighborhood strategy is added to improve the convergence of NSGA-Ⅱ. The feasibility of the model and the superiority of the improved algorithm are verified by numerical experiments.

Key words： post-epidemic era; fresh e-commerce; vehicle routing problem; NSGA- Ⅱ; customer satisfaction

0 引言

后疫情時代，居民使用生鮮電商app頻次增加，但配送成本過高一直都是亟需解決的問題，末端配送路徑優(yōu)化是降低成本的重要手段[1]。除成本問題外，滿意度也是十分重要的問題，它影響著客戶重復(fù)購買的意愿[2]?？蛻魸M意度大多體現(xiàn)在時間窗上[3]，運輸時間過長也會影響生鮮食品的貨損程度。在時間滿意度、食品貨損程度等約束條件下，適當(dāng)?shù)囊?guī)劃行車路線，實現(xiàn)成本控制，這是車輛路徑問題的重要研究內(nèi)容。

在生鮮配送的路徑問題研究中，余海燕等以配送距離最小為目標(biāo)，構(gòu)建生鮮外賣即時配送路徑優(yōu)化模型[4]。物流成本最小化也是生鮮配送的重要問題[5]。在生鮮配送的多目標(biāo)問題中，詹紅鑫等人以配送成本最小，路徑風(fēng)險最小為目標(biāo)構(gòu)建路徑優(yōu)化模型[6]。

由于感染風(fēng)險是疫情背景下所特有的，因此本文在考慮末端配送方式滿足客戶滿意度前提下，以最小化物流成本和最小化感染風(fēng)險為目標(biāo)構(gòu)建模型，運用改進的NSGA-Ⅱ算法求解該問題，通過算例實驗來驗證算法的有效性與可行性。

1 問題描述及模型構(gòu)建

1.1 問題描述

本文研究后疫情時代生鮮配送車輛路徑優(yōu)化問題，定義[G=（V，E）]為一個完備的無向圖，配送中心用[{0}]表示，客戶集合用[N={1，2，…，n}]表示，[V=N∪{0}]表示圖中節(jié)點集合，配送員與配送車輛集合用[K={1，2，…，m}]表示，[E={i，j，i，j∈V，i≠j}]表示各節(jié)點間的弧集合。具體描述為：一個配送中心有[k]個配送員和[k]輛車執(zhí)行送貨任務(wù)，將貨物送往[n]個客戶點。每個客戶點都有三種交付方式可以選擇：快遞柜、物業(yè)和送貨上門。

1.2 參數(shù)設(shè)置

[N={1，2，…，n}]：表示客戶集合；

[K={1，2，…，m}]：表示車輛與配送員的集合；

[Ck]：表示第[k]輛車及第[k]個配送員的固定成本；

[Cl]：表示使用第[l]種交付方式所需要的單位時間成本；

[C'l]：表示使用第[l]種交付方式所需要的固定成本；

[Cg1]：表示使用快遞柜的固定成本；

[dij]：表示從點[i]到[j]之間的距離；

[A]：表示配送過程中單位距離重量成本；

[qj]：表示第[j]個客戶的貨物需求量；

[tj]：表示到達第[j]個客戶點的時間；

[V]：表示車輛行駛速度；

[?tjl]：表示配送員配送生鮮的服務(wù)時間，包括交付時間及等待時間；

[t1，t2]：表示客戶的期望時間窗；

[T1，t1）]，[t2，T2]：表示客戶可接受時間窗；

[α]：表示商品提前送達時客戶對時間的敏感系數(shù)；

[β]：表示商品延遲送達時客戶對時間的敏感系數(shù)；

[μ]：表示客戶滿意度的最低要求水平；

[yj']：表示客戶可容忍的最高貨損率；

[Sjl]：表示客戶[j]對第[l]種末端配送方式的滿意度；

[Y]：表示單位時間貨損系數(shù)；

[Q]：表示配送車輛的最大裝載量；

[N+]：表示區(qū)域內(nèi)的感染人數(shù)；

[N]：表示區(qū)域內(nèi)的總?cè)藬?shù)；

[φl]：第[l]種末端配送方式下，客戶受到配送者感染風(fēng)險的概率系數(shù)；

[ωl]：第[l]種末端配送方式下，配送者受到客戶感染風(fēng)險的概率系數(shù)；

[l]：表示末端配送方式，當(dāng)[l=g1]時，表示將貨物放在快遞柜作為末端配送方式；當(dāng)[l=g2]時，表示將貨物放在物業(yè)作為末端配送方式；當(dāng)[l=g3]時，表示將送貨上門作為末端配送方式；

[xijk]：[xijk=1]表示從點[i]到[j]由第[k]個配送員配送，[xijk=0]表示從點[i]到[j]不由第[k]個配送員配送。

1.3 模型構(gòu)建

物流成本模型：由配送車輛及配送員人力的固定成本[CA]、配送車輛的配送成本[CB]、以及末端配送方式的交付成本和交付過程中配送員的等待成本[CC]構(gòu)成。具體公式如下所示：

[CA=k=1mCk]? ⑴

[CB=i=0nj=1nk=1mdij?xijk?A?qj] ⑵

[CC=j=1n（C'l+Cl??tjl）]? ⑶

其中，

[C'l=Cg1 ，? l∈g1? 0，? ? ?l∈g2，g3]? ⑷

[?tjl=1，? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?l∈g1，g212π?σ?exp-x-μ22σ2 ，l∈g3]? ⑸

末端配送方式感染風(fēng)險模型：本文假設(shè)城市總?cè)藬?shù)為[N]，城市中尚未采取隔離措施的新冠疫情肺炎病毒攜帶者人數(shù)為[N+]，人們在城市中的感染概率為[P]?？蛻襞c配送員的感染概率如下所示：

[Pkstart=N+N]? ⑹

[Pjstart=N+N]? ⑺

[Pjend=Pjstart+φl?Pki?1-Pjstart?xijk]? ⑻

[Pkj=Pki+ωl?Pjstart?1-Pki?xijk]? ⑼

[P*=k=1mPk0+j=1nPjend]? ⑽

其中，[Pkstart]表示配送員初始感染概率，[Pjstart]表示客戶初始感染概率，[Pk0]表示配送員回到配送中心感染概率，[Pjend]表示客戶[j]拿到貨物后的感染概率，[Pki]表示配送員在點[i]的感染概率，[Pkj]表示配送員在點[j]感染概率。

客戶滿意度模型：客戶的滿意度會收到收貨方式的影響。具體交付方式滿意度和時間滿意度設(shè)置表示如下：

[Sjl=b，? ? ? ? ? ? ? l∈g1b-δc，? ? l∈g2a ，? ? ? ? ? ? ? l∈g3]? ⑾

[Sj（tj）=tj-T1t1-T1α， tj∈T1，t11，? ? ? ? ? ? ? ? ? tj∈t1，t2T2-tjT2-t2β， tj∈t2，T20，? ? ? ? ? ? ? ? ?else]? ⑿

VRPTW模型：根據(jù)物流成本模型、感染風(fēng)險模型和客戶滿意度模型，以客戶滿意度作為約束條件，以最小化物流成本和最小化感染風(fēng)險為目標(biāo)構(gòu)建模型如下：

[F1=MinCA+CB+CC]? ⒀

[F2=Min（k=1mPk0+j=1nPjendm+n）]? ⒁

s.t.：

[S=j=1nSj（tj）+j=1nSjl2n>μ]? ⒂

[j=1nxijk.qj≤Q ，?k∈1，2，…，m]? ⒃

[yj=Y?tj-t0<yj']? ⒄

[j=1nx0jk=i=1nxi0k=1，? ?k∈1，2，…，m]? ⒅

[j=1nxijk=i=1nxijk=1，? ?k∈1，2，…，m]? ⒆

[i=1nxihk-j=1nxhjk=0，? h∈n，? ?k∈1，2，…，m]? ⒇

式⒀表示物流成本最小化；式⒁表示感染風(fēng)險最小化；式⒂是客戶滿意度約束；式⒃是車載容量約束；式⒄是生鮮貨損率約束；式⒅表示配送車輛始于配送中心，終于配送中心；式⒆表示每個消費者僅被一個配送員服務(wù)；式⒇是保證路線的連貫性。

2 基于優(yōu)先級三層編碼改進的NSGA-Ⅱ算法

目前，遺傳算法已經(jīng)有了較為成熟的研究。NSGA-Ⅱ與NSGA相比，復(fù)雜度更低，求解速度更快，收斂性越好。因為本文使用了NSGA-Ⅱ求解感染風(fēng)險和成本最小化的雙目標(biāo)問題，圖1為NSGA-Ⅱ改進算法流程。

2.1 基于優(yōu)先級編碼方法簡介

基于優(yōu)先級編碼方法相較于傳統(tǒng)編碼方式有如下優(yōu)點：①相對傳統(tǒng)的編碼方式，該方法降低了決策變量維度，提高了求解效率；②通過解碼獲得的路徑均為從起點到終點的完整路徑。具體編碼過程如表1所示。

2.2 三重編碼方法簡介

本文具體案例：某個配送員將物資以某種配送方式送給某個客戶。為此設(shè)計了三層實數(shù)編碼。第一層，客戶點優(yōu)先級編碼，第二層，車輛路徑選擇編碼，第三層，末端配送方式選擇編碼。

第一層編碼：[1，3，2，4，6，5，7，10，8，9]；

第二層編碼：[（0-1-5-9-0）（0-2-4-7-0）（0-3-6-8-10-0）]；

第三層編碼：[1.0，1.0，1.0，3.0，2.0，2.0，2.0，1.0，1.0，2.0]。

2.3 局部尋優(yōu)策略

逆序策略：在染色體的基因中，隨機選擇兩個不同的位置生成[n1]、[n2]兩個點，對[n1]、[n2]兩點之間的基因（包括基因的優(yōu)先級、配送車輛和順序、交付方式）進行逆序排列，形成新的編碼序列。如圖2所示，[n1]、[n2]分別為客戶點3與客戶點10，采用逆序策略后，路徑3為[0→10→8→6→3→0]?？蛻酎c處的基因全部逆序。

3 算例實驗

假設(shè)平臺接到20個訂單，配送中心有10輛配送車輛，配送車輛速度為300m/min，最大車載重量為30kg，每輛車和每個配送員固定成本為50元。單位距離重量成本為0.001元/m*kg；快遞柜的固定成本為0.5元/次，交付的單位時間成本為1元；單位時間貨損系數(shù)為0.005貨損，客戶對送達時間的敏感系數(shù)為0.2。配送過程中生鮮貨損率小于0.6，客戶滿意度閾值為0.6，直接接觸的感染風(fēng)險概率系數(shù)為0.31，間接接觸的感染風(fēng)險概率系數(shù)為0.20。算例實驗數(shù)據(jù)如表2所示。直接接觸的感染風(fēng)險概率系數(shù)為0.31，間接接觸的感染風(fēng)險概率系數(shù)為0.20。

根據(jù)以上數(shù)據(jù)，在python中運用基于優(yōu)先級三層編碼的NSGA-Ⅱ原始算法和NSGA-Ⅱ改進算法進行數(shù)值實驗，如圖3所示，一個點即代表了一個配送方案，F(xiàn)1為物流成本目標(biāo)，F(xiàn)2為感染風(fēng)險目標(biāo)。帕累托點所代表的具體方案如表3所示。

表3中交付方式1.0對應(yīng)送貨到快遞柜的末端配送方式，2.0對應(yīng)送貨到物業(yè)的配送方式，交付方式3.0對應(yīng)送貨上門的配送方式。其中送貨上門和送貨到快遞的末端配送方式較為常用，送貨上門為末端配送方式次數(shù)最少?？梢暬囕v路徑選擇圖如圖4所示。

研究結(jié)果發(fā)現(xiàn)，NSGA-Ⅱ改進算法與NSGA-Ⅱ原始算法在感染風(fēng)險均為0.1449時，成本從580.50降到了500.74，降低了13.6%；NSGA-Ⅱ改進算法得到的方案3與方案4在和NSGA-Ⅱ原始算法的方案相比，改進算法的方案能得到更小的物流成本和更低的感染風(fēng)險。

4 結(jié)束語

在后疫情時代，送貨上門和送貨到快遞柜應(yīng)為生鮮電商平臺較為常用的末端配送方式，送貨上門既增加成本又增加感染風(fēng)險并不提倡。生鮮電商平臺必須根據(jù)實際情況平衡配送過程中物流成本、客戶滿意度和感染風(fēng)險。

此外，算例實驗證明了模型及算法的有效性，也證明了改進算法的優(yōu)越性。

參考文獻（References）：

[1] 蔣俊，申貴成，王詩佳，等.基于強化學(xué)習(xí)的物流配送路徑優(yōu)化[J].統(tǒng)計與決策，2021，37（18）：185-188.

[2] Wu J， Li YY， Zhang W. ReRec： A Divide-and-ConquerApproach to Recommendation Based on Repeat Purchase Behaviors of Users in Community E-Commerce[J]. Mathematics，2022，10（2）：208.

[3] Wang DQ， Yang YT， Wang YH. Optimization of?Distribution Path considering Cost and Customer Satisfaction under New Retail Modes[J]. Journal of Advanced Transportation，2021：9426659.

[4] Su JF， Zhang FT， Chen S. Path Optimization of Fresh?Products Logistics Distribution under New Retail Mode[J].International Journal of Innovative Computing Information and Control，2022，18（2）：511-523.

[5] 詹紅鑫，王旭坪，孫自來，等.基于鄰域搜索的成品油多艙多目標(biāo)配送路徑優(yōu)化算法研究[J].系統(tǒng)工程理論與實踐，2019，39（10）：2660-2675.

[6] 賴志柱，王錚，戈冬梅，等.多目標(biāo)應(yīng)急物流中心選址的魯棒優(yōu)化模型[J].運籌與管理，2020，29（5）：74-83.