時變交通下社區(qū)團購生鮮配送多目標優(yōu)化

楊習杰，馬云峰,2 YANG Xijie,MA Yunfeng,2

（1.武漢科技大學 恒大管理學院，湖北 武漢 430065；2.武漢科技大學 服務(wù)科學與工程研究中心，湖北 武漢 430065）

0 引 言

社區(qū)團購是一種以生鮮類商品作為切入點，依托于本地社區(qū)和團長的個人資源在小范圍區(qū)域內(nèi)進行團購的新型電商零售模式。用戶當日線上下單，次日在社區(qū)團長處自提，由專門的平臺提供采購、物流倉儲及售后。受疫情影響，自2020年以來，社區(qū)團購訂單量出現(xiàn)井噴式增長，社區(qū)團購市場發(fā)展迅猛，隨之而來的生鮮配送問題受到諸多學者關(guān)注。

社區(qū)團購生鮮配送問題可以看作車輛路徑問題的一種變體，與傳統(tǒng)電商不同，社區(qū)團購一般屬于小范圍配送，并且對于配送的時效性要求更高。目前關(guān)于社區(qū)團購的研究主要聚焦在其運營模式上，對訂單配送展開研究的較少，一般都是基于靜態(tài)路網(wǎng)，以成本、滿意度等為目標，加入了時間窗等約束。然而，社區(qū)團購的配送是面向城市道路，在實際配送過程中，必須要考慮到時變交通路網(wǎng)對于車速的影響。近年來，在時變路網(wǎng)的車輛路徑問題研究中，常見的優(yōu)化目標諸如成本、行程時間、碳排放量、車輛使用數(shù)量、顧客價值和顧客滿意度等。由于該問題屬于NP-hard，在模型求解上也以一些元啟發(fā)式算法為主，包括遺傳算法、蟻群算法、粒子群算法、模擬退火和禁忌搜索算法等。趙志學和李夏苗綜合考慮了最低新鮮度約束，車載限制和電動車電量約束，利用設(shè)計的自適應(yīng)的蟻群算法求出了最低配送成本。王寧等以客戶價值和滿意度為優(yōu)化目標，假設(shè)車速在同一時段內(nèi)保持恒定，考慮了時間窗和車輛載重等約束，利用線性加權(quán)法將雙目標轉(zhuǎn)化為單目標，并設(shè)計了單親遺傳算法進行求解。

本文以配送成本最小和配送時間最短為目標，建立了時變交通下社區(qū)團購生鮮配送雙目標優(yōu)化模型，在傳統(tǒng)的遺傳算法基礎(chǔ)上先后引入了進化逆轉(zhuǎn)操作和改進的精英保留策略，用于提高遺傳算法的局部尋優(yōu)能力，最后通過具體算例對模型和算法進行驗證。

1 問題描述與模型建立

1.1 問題描述

本文研究的時變交通下社區(qū)團購生鮮配送多目標優(yōu)化問題可以被描述為：以單個配送中心作為配送車輛的起止點，由一組同質(zhì)車隊為多個社區(qū)團長點配送貨物，考慮時變路網(wǎng)對車輛速度的影響，并以總配送成本最少和總配送時間最短為目標，對車輛的配送路徑進行規(guī)劃。該問題的示意圖如圖1所示。

圖1 時變交通下社區(qū)團購生鮮配送多目標優(yōu)化模型示意圖

針對問題的可操作性，本文做出以下基本假設(shè)，使用的符號及參數(shù)說明如表1所示。

表1 符號及變量說明

（1）配送中心可以滿足所有客戶點的需求，車輛從配送中心出發(fā)，最終回到配送中心，并且車輛載重不能超過其最大載重量；

（2）每個社區(qū)團長點僅由一輛車服務(wù)，所有的社區(qū)團長點都要被服務(wù)，服務(wù)時間相同；所有社區(qū)團長點的需求量、地理位置等信息已知，所有車輛最早8點從配送中心出發(fā)，在16:00前完成所有需求點的配送任務(wù)；

（3）假設(shè)交通狀態(tài)對車輛速度的影響是基于時間段的，車輛在每個時間段內(nèi)的速度保持不變。

1.2 配送成本計算

1.2.1 固定成本與運輸成本

本文中的車輛是同質(zhì)的，固定成本一般只與使用的車輛數(shù)量有關(guān)，車輛在配送過程中產(chǎn)生的運輸成本一般與行駛距離呈正比。因此，固定成本和運輸成本的表達式如公式（1）和公式（2）所示。

1.2.2 貨損成本

生鮮在配送過程中往往會因為配送時間過長造成物品腐敗、變質(zhì)等，從而形成了貨損成本。假設(shè)生鮮配送過程中，車內(nèi)的溫度恒定，那么生鮮產(chǎn)品到達社區(qū)團長點i處的新鮮度表達式為：

假設(shè)貨損成本只與生鮮產(chǎn)品的數(shù)量、單價以及產(chǎn)品的新鮮度有關(guān)，那么貨損成本為：

1.3 配送時間的計算

在實際的交通路網(wǎng)中，配送車輛的實際速度與車流量和車速限制有關(guān)。道路交通擁堵指數(shù)（Traffic Performance Index,TPI）是用來反映道路交通擁擠程度的一種數(shù)字化表現(xiàn)，本文按照百度地圖道路交通擁堵指數(shù)分為暢通、緩行、擁堵和嚴重擁堵四個等級，暢通（1～1.5）、緩行（1.5～1.8）、擁堵（1.8～2）和嚴重擁堵（2以上）。本文中的TPI表示為車輛實際行程時間與暢通行程時間的比值，TPI的值越大也代表著道路的擁堵程度越高。因此，車輛的實際速度與車速限制和TPI的關(guān)系表示為：

在本文中，假設(shè)每天的配送時間被分為p個時間段，車輛從社區(qū)團長點i處出發(fā)，到社區(qū)團長點處完成配送并離開，配送時間由車輛行駛時間和服務(wù)時間兩部分組成。根據(jù)各時間段的交通擁堵指數(shù)，設(shè)計了配送時間的計算方法，步驟如下：

1.4 模型構(gòu)建

本文建立總配送成本和配送時間最小的時變交通下社區(qū)團購生鮮配送雙目標優(yōu)化模型如下：

約束條件為：

公式（6）和公式（7）分別表示目標函數(shù)為總配送成本最小和總配送時間最短，公式（8）表示每個社區(qū)團長點有且只有一輛車提供服務(wù)，公式（9）、公式（10）表示所有車輛只能從配送中心出發(fā)一次，最終并回到配送中心，公式（11）為最低新鮮度約束，公式（12）、公式（13）和公式（14）分別為車輛的載重、里程約束和車輛數(shù)量約束，公式（15）、公式（16）為到達社區(qū)團長點的時間及軟時間窗約束，公式（17）為決策變量。

2 算法設(shè)計

2.1 雙目標優(yōu)化的求解思想

本文通過線性加權(quán)的方法將雙目標轉(zhuǎn)化為單目標進行求解。配送成本與配送時間兩個目標函數(shù)具有不同量綱和數(shù)量級大小，直接進行線性加權(quán)得出的結(jié)果顯然是不合理的，因此首先對兩個目標函數(shù)進行歸一化處理，歸一化的方法如公式（18）：

其中：C為該目標函數(shù)的最小值，C為目標函數(shù)的一個極大值。根據(jù)本文所建立的模型以及設(shè)計的算法只能求出目標函數(shù)的極大值，其次單目標的最大值在本文的求解過程中意義不大。線性加權(quán)后的單目標函數(shù)為：

2.2 遺傳算法

2.2.1 編碼操作

本文采用整數(shù)排列的方式進行編碼，染色體的長度等于需求點的數(shù)量，染色體的每一段對應(yīng)著需求點的編號，如{8,10,9,6,1,2,5,4,3,7}就是一個正常的染色體。

2.2.2 選擇、交叉與變異操作

選擇算子采用輪盤賭的方式，每個個體被選中的概率與其適應(yīng)度的值有關(guān)。適應(yīng)度的值越大，被選中的概率越大，本文設(shè)置適應(yīng)度函數(shù)如公式（20）所示。

交叉操作采用雙點交叉算子，交叉操作的步驟如下：

Step1：將父代種群兩兩分為一組，按照交叉概率對每一組進行交叉操作；

Step2：產(chǎn)生兩個客戶編號范圍內(nèi)的隨機整數(shù)a和b，交換兩個父代a到b范圍內(nèi)的染色體片段；

Step3：交叉后的染色體中可能存在著重復的片段，對于重復的片段按照交叉片段中的映射關(guān)系進行處理。

變異操作的方法是，隨機選擇染色體的兩個基本位，按照變異概率交換其對應(yīng)片段，如圖3（a）所示。

2.2.3 進化逆轉(zhuǎn)操作

加入進化逆轉(zhuǎn)操作的目的是為了提高遺傳算法的局部尋優(yōu)能力，進化體現(xiàn)在僅當逆轉(zhuǎn)后適應(yīng)度值提高才接受逆轉(zhuǎn)，否則逆轉(zhuǎn)無效。換句話說，進化逆轉(zhuǎn)是為了使得每個個體朝著適應(yīng)度值高的方向逆轉(zhuǎn)。進化逆轉(zhuǎn)操作的步驟如下：

圖2 交叉操作示例

Step1：產(chǎn)生兩個客戶編號范圍內(nèi)的隨機整數(shù)a和b，將父代a到b范圍內(nèi)的染色體片段按照相反順序排列后插入至原位置，如圖3（b）所示；

圖3 變異操作與進化逆轉(zhuǎn)操作示例

Step2：計算逆轉(zhuǎn)后的個體適應(yīng)度，若適應(yīng)度值提高，則保留逆轉(zhuǎn)操作，否則逆轉(zhuǎn)無效。

2.2.4 改進的精英保留策略

本文采用改進的精英保留策略主要有以下三點原因：（1）保證子代種群中的最優(yōu)個體永遠不會比父代的差；（2）同時也防止父代中適應(yīng)度高的個體由于交叉、變異等操作而丟失；（3）增加隨機保留策略，在一定程度上避免了算法陷入局部最優(yōu)。精英保留策略的具體操作步驟如下：

Step1：計算父代中個體適應(yīng)度值的集合Fit，計算經(jīng)過選擇、交叉、變異和進化逆轉(zhuǎn)等操作后的個體適應(yīng)度值的集合Fit；

Step2：將Fit和Fit放在一起，按照適應(yīng)度值由高到低排序，根據(jù)精英保留比例先選出一定比例的子代個體，將這部分個體替代Fit種群中適應(yīng)度值較差的個體，從而形成新的子代種群進入下一步迭代。

3 數(shù)值實驗

3.1 實驗設(shè)計

本文中的部分數(shù)據(jù)來源于文獻[5]，包括各社區(qū)團長點的位置坐標、需求量和距離等數(shù)據(jù)，其中各節(jié)點間的距離是通過高德地圖得到的實際最小距離。各時間段的交通擁堵指數(shù)及其他相關(guān)參數(shù)如表2和表3所示。

表2 各時間段的交通擁堵指數(shù)

表3 其他相關(guān)參數(shù)

車輛從配送中心的出發(fā)時間為8:00，改進遺傳算法的初始種群規(guī)模為150，迭代次數(shù)為1 000，交叉概率為0.9，變異概率為0.1，精英保留比例為0.3，算法采用MATLAB 2018a軟件編寫。

3.2 算例求解

采用簡單的遺傳算法、加入進化逆轉(zhuǎn)算子的遺傳算法和本文中改進的遺傳算法分別求解單目標下的配送成本最小值，每種算法下均進行20次計算，取20次中的最優(yōu)值作為配送成本的最小值，三種算法的優(yōu)化過程如圖4所示。由圖4可以看出，改進的遺傳算法相比于另外兩種算法具有更快的收斂速度，同時也更不容易陷入局部最優(yōu)。

圖4 改進遺傳算法的配送成本迭代過程

根據(jù)上述所給參數(shù)計算單目標下的極大值和最小值，總配送成本和配送時間的極大值與最小值分別為：2 460.65元、18.9558小時、1 447.62元、7.9235小時。

將上述結(jié)果代入公式（18）和公式（19），λ取值集合為0.1到0.9，步長為0.1，不同λ取值下的仿真結(jié)果如表4所示。

表4中所求出的解均可以作為雙目標優(yōu)化的帕累托最優(yōu)解，當λ取值在0.2到0.7時，求得的雙目標優(yōu)化的解是相同的，因此本文取配送成本為1 457.01元，配送時間為7.9576小時作為最終的解，對應(yīng)的配送路徑的可視化如圖5所示。

表4 不同λ取值下的仿真結(jié)果

圖5 雙目標優(yōu)化下的具體配送路徑

為了進一步分析交通狀況的變化對生鮮配送過程的影響，λ取0.5，在其他條件不變的情況下，設(shè)置不同的車輛出發(fā)時間，利用改進的遺傳算法進行求解，仿真結(jié)果如表5所示。

由表5可以看出，車輛的出發(fā)時間主要對貨損成本和總配送時間的影響較大，主要原因在于，當配送時間段內(nèi)的道路交通擁堵指數(shù)較低時，車輛以更高的車速完成配送，各個客戶也能更早地收到貨物，從而降低了貨損成本、縮短了配送時間。

表5 不同車輛出發(fā)時間下的仿真結(jié)果

4 結(jié)論

本文在綜合考慮生鮮最低新鮮度、軟時間窗和車載限制等約束的情況下，建立了以總配送成本最小和配送時間最短為目標的時變交通下社區(qū)團購生鮮配送雙目標優(yōu)化模型。采用分段求解的方法計算時變路網(wǎng)下車輛行駛時間，通過極大極小歸一化和線性加權(quán)處理，將雙目標轉(zhuǎn)化為單目標，并設(shè)計了改進的遺傳算法進行求解。實驗結(jié)果表明，社區(qū)團購企業(yè)在生鮮配送調(diào)度過程中，要充分考慮到交通狀況對生鮮配送的影響，合理規(guī)劃配送路線，在可能的情況下，盡量避免擁堵時段，從而達到降低配送成本、縮短配送時間和提高客戶滿意度的目的。