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

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

0 引 言

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

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

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

1 問(wèn)題描述與模型建立

1.1 問(wèn)題描述

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

圖1 時(shí)變交通下社區(qū)團(tuán)購(gòu)生鮮配送多目標(biāo)優(yōu)化模型示意圖

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

表1 符號(hào)及變量說(shuō)明

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

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

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

1.2 配送成本計(jì)算

1.2.1 固定成本與運(yùn)輸成本

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

1.2.2 貨損成本

生鮮在配送過(guò)程中往往會(huì)因?yàn)榕渌蜁r(shí)間過(guò)長(zhǎng)造成物品腐敗、變質(zhì)等，從而形成了貨損成本。假設(shè)生鮮配送過(guò)程中，車(chē)內(nèi)的溫度恒定，那么生鮮產(chǎn)品到達(dá)社區(qū)團(tuán)長(zhǎng)點(diǎn)i處的新鮮度表達(dá)式為：

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

1.3 配送時(shí)間的計(jì)算

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

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

1.4 模型構(gòu)建

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

約束條件為：

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

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

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

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

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

2.2 遺傳算法

2.2.1 編碼操作

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

2.2.2 選擇、交叉與變異操作

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

交叉操作采用雙點(diǎn)交叉算子，交叉操作的步驟如下：

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

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

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

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

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

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

圖2 交叉操作示例

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

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

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

2.2.4 改進(jìn)的精英保留策略

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

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

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

3 數(shù)值實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)計(jì)

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

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

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

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

3.2 算例求解

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

圖4 改進(jìn)遺傳算法的配送成本迭代過(guò)程

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

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

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

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

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

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

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

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

4 結(jié)論

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