陸心航 徐宗露 劉文

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

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

中圖分類號(hào)：C93;TP18? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ?文章編號(hào)：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 引言

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

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

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

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

1.1 問(wèn)題描述

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

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

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

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

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

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

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

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

[dij]：表示從點(diǎn)[i]到[j]之間的距離；

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

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

[tj]：表示到達(dá)第[j]個(gè)客戶點(diǎn)的時(shí)間；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[xijk]：[xijk=1]表示從點(diǎn)[i]到[j]由第[k]個(gè)配送員配送，[xijk=0]表示從點(diǎn)[i]到[j]不由第[k]個(gè)配送員配送。

1.3 模型構(gòu)建

物流成本模型：由配送車輛及配送員人力的固定成本[CA]、配送車輛的配送成本[CB]、以及末端配送方式的交付成本和交付過(guò)程中配送員的等待成本[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)險(xiǎn)模型：本文假設(shè)城市總?cè)藬?shù)為[N]，城市中尚未采取隔離措施的新冠疫情肺炎病毒攜帶者人數(shù)為[N+]，人們?cè)诔鞘兄械母腥靖怕蕿閇P]?？蛻襞c配送員的感染概率如下所示：

[Pkstart=N+N]? ⑹

[Pjstart=N+N]? ⑺

[Pjend=Pjstart+φl(shuí)?Pki?1-Pjstart?xijk]? ⑻

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

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

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

客戶滿意度模型：客戶的滿意度會(huì)收到收貨方式的影響。具體交付方式滿意度和時(shí)間滿意度設(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)險(xiǎn)模型和客戶滿意度模型，以客戶滿意度作為約束條件，以最小化物流成本和最小化感染風(fēng)險(xiǎn)為目標(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)險(xiǎn)最小化；式⒂是客戶滿意度約束；式⒃是車載容量約束；式⒄是生鮮貨損率約束；式⒅表示配送車輛始于配送中心，終于配送中心；式⒆表示每個(gè)消費(fèi)者僅被一個(gè)配送員服務(wù)；式⒇是保證路線的連貫性。

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

目前，遺傳算法已經(jīng)有了較為成熟的研究。NSGA-Ⅱ與NSGA相比，復(fù)雜度更低，求解速度更快，收斂性越好。因?yàn)楸疚氖褂昧薔SGA-Ⅱ求解感染風(fēng)險(xiǎn)和成本最小化的雙目標(biāo)問(wèn)題，圖1為NSGA-Ⅱ改進(jìn)算法流程。

2.1 基于優(yōu)先級(jí)編碼方法簡(jiǎn)介

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

2.2 三重編碼方法簡(jiǎn)介

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

第一層編碼：[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)策略

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

3 算例實(shí)驗(yàn)

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

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

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

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

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

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

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

參考文獻(xiàn)（References）：

[1] 蔣俊，申貴成，王詩(shī)佳，等.基于強(qiáng)化學(xué)習(xí)的物流配送路徑優(yōu)化[J].統(tǒng)計(jì)與決策，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] 詹紅鑫，王旭坪，孫自來(lái)，等.基于鄰域搜索的成品油多艙多目標(biāo)配送路徑優(yōu)化算法研究[J].系統(tǒng)工程理論與實(shí)踐，2019，39（10）：2660-2675.

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