楊習(xí)杰，馬云峰,2 YANG Xijie,MA Yunfeng,2

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

0 引 言

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

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

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

1 問題描述與模型建立

1.1 問題描述

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

圖1 時變交通下社區(qū)團購生鮮配送多目標(biāo)優(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ù)分為暢通、緩行、擁堵和嚴(yán)重?fù)矶滤膫€等級，暢通（1～1.5）、緩行（1.5～1.8）、擁堵（1.8～2）和嚴(yán)重?fù)矶拢?以上）。本文中的TPI表示為車輛實際行程時間與暢通行程時間的比值，TPI的值越大也代表著道路的擁堵程度越高。因此，車輛的實際速度與車速限制和TPI的關(guān)系表示為：

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

1.4 模型構(gòu)建

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

約束條件為：

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

2 算法設(shè)計

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

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

其中：C為該目標(biāo)函數(shù)的最小值，C為目標(biāo)函數(shù)的一個極大值。根據(jù)本文所建立的模型以及設(shè)計的算法只能求出目標(biāo)函數(shù)的極大值，其次單目標(biāo)的最大值在本文的求解過程中意義不大。線性加權(quán)后的單目標(biāo)函數(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：交叉后的染色體中可能存在著重復(fù)的片段，對于重復(fù)的片段按照交叉片段中的映射關(guān)系進行處理。

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

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

加入進化逆轉(zhuǎn)操作的目的是為了提高遺傳算法的局部尋優(yōu)能力，進化體現(xiàn)在僅當(dāng)逆轉(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è)計

本文中的部分?jǐn)?shù)據(jù)來源于文獻[5]，包括各社區(qū)團長點的位置坐標(biāo)、需求量和距離等數(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)算子的遺傳算法和本文中改進的遺傳算法分別求解單目標(biāo)下的配送成本最小值，每種算法下均進行20次計算，取20次中的最優(yōu)值作為配送成本的最小值，三種算法的優(yōu)化過程如圖4所示。由圖4可以看出，改進的遺傳算法相比于另外兩種算法具有更快的收斂速度，同時也更不容易陷入局部最優(yōu)。

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

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

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

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

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

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

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

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

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

4 結(jié)論

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