李 娜

（西安財經(jīng)大學 管理學院，陜西 西安 710100）

1 問題描述及變量定義

1.1 問題描述

新零售背景下，多功能生鮮超市應運而生，人們越來越注重生鮮產(chǎn)品的新鮮度以及配送時間的長短，本文總結(jié)相關路徑優(yōu)化研究現(xiàn)狀如下，張倩等[1]在研究配送路徑時，建立以配送成本，產(chǎn)品新鮮度，碳排放量為主的目標函數(shù)，并利用果蠅算法進行求解；肖建華[2]用變鄰域算法求解多車輛多配送中心的路徑優(yōu)化問題；王超[3]設置軟時間窗約束研究即時配送的效果，并采用了布谷鳥進化算法求解PDVRP 問題。何美玲等[4]利用蟻群算法求解軟時間窗的路徑問題。姚臻等[5]以客戶時間窗、客戶滿意度、碳排放為約束條件，建立以碳排放量為基礎的總成本最小目標函數(shù)，并應用遺傳算法求解數(shù)學模型，得出考慮碳排放成本對于物流配送成本的重要影響。楊霞等[6]考慮生鮮產(chǎn)品新鮮度在軟時間窗約束的條件下對車輛路徑優(yōu)化問題的影響，并用插點分段的方式計算兩需求點的距離，建立成本最小模型。秦馨等[7]根據(jù)當前訂單分批模式從訂單挑選搬運次數(shù)方面比較四種聚類算法的差別，最后得出相應結(jié)論。Fahimeh 等[8]針對訂單揀選和交付計劃這兩個重要且相互關聯(lián)的環(huán)節(jié)，從訂單批次揀貨處理以及向配送車輛分配訂單、規(guī)劃路線入手，以系統(tǒng)成本最小化為目標進行了充分研究，最終有效降低了系統(tǒng)成本并提高了揀選效率。Mar 等[9]也從訂單揀選和交付流程著手，對存在多個揀選配送位置的揀配問題進行研究，最終不僅減少了揀選和交付成本，還避免了閑置資源的浪費。實際生活中，訂單的產(chǎn)生是動態(tài)且具有規(guī)模性，需要考慮訂單分揀造成的時間差異對于消費者體驗度的影響，因此，考慮訂單分揀過程中造成的懲罰成本、新鮮度成本以及運輸過程中的運輸成本非常重要。

1.2 問題分析

即時配送的貨物主要為小型且分散，且不同入口訂單來源的需求要滿足多元化需求，整體呈現(xiàn)出一個動態(tài)的變化過程，現(xiàn)實中即時配送訂單分配未按照一定的規(guī)范標準，同類型以及需求點相近的產(chǎn)品或有特殊需求的產(chǎn)品用戶，比如有時間窗要求或要求增值服務的，未被合理分配在一起。即時配送的貨物大多為三公里之內(nèi)的貨物，在智能化配送未完全普及的背景下，人工配送是主要的配送方式，而人工配送的路徑并未完全運用智能化算法來分析配送路徑的選擇以及順序，大多依賴于配送員主觀上的認知，這些在很大程度上影響即時配送效率。

1.3 模型假設

1.3.1 問題假設

生鮮產(chǎn)品不區(qū)分種類，按照訂單分配；假設生鮮產(chǎn)品初始配送新鮮度以及耐腐性能無差別；配送地點產(chǎn)品充足，不存在因產(chǎn)品短缺而引起的時間浪費；挑揀人員熟悉門店環(huán)境，可以及時挑揀；配送車輛統(tǒng)一出發(fā)，不考慮多時段車輛配送；配送過程中始終勻速行駛，不考慮行駛路程中突發(fā)因素對車輛速度的影響；假設配送過程中不發(fā)生堵車、車禍等意外情況；配送過程中的行駛速度是恒定的，不隨路況發(fā)生變化；配送過程中配送車輛溫度恒定，不受其他因素影響。

1.3.2 約束條件

配送車輛從生鮮產(chǎn)品配送中心出發(fā)，完成配送后返回配送中心；配送中心貨物充足，能滿足一切訂單需求；每輛車輛載重量大于當車訂單需求量；配送車輛實現(xiàn)眾包配送，但訂單需求方只能由一個配送車輛完成。

1.3.3 變量設置表

訂單聚類中心I，配送中心O，需求點集合M={i},i=1,2,3,…,n，配送點集合N={J},J=1,2,3,…,n，運輸車輛的集合K={k},k=1,2,3,…,n，需求點i 到配送點j 的距離dij，訂單i 的需求量Ri，車輛k 載重量Zk，客戶可接受配送時間[Ei,Li]，時間滿意度程度M（t），生鮮產(chǎn)品在t 時間的新鮮度H（t），生鮮農(nóng)產(chǎn)品的變質(zhì)率α。

2 數(shù)學模型構(gòu)建

2.1 相似性函數(shù)

由于新零售模式的影響，更多的消費者傾向于通過線上購買物品，因此產(chǎn)生訂單的位置是多樣性的，配送端需要盡可能用最少的人力、物力、財力實現(xiàn)即時配送。K-means 聚類算法以需求點相距距離作為相似性的評價指標，以多個配送中心和分散需求點進行聚類，其結(jié)果受到K 值選取的影響，容易超出劃定的配送范圍，增加尋優(yōu)的復雜過程。此算法契合于即時配送確定范圍內(nèi)的尋優(yōu)問題。

Step1：計算各需求點，配送中心，聚類中心之間相互的距離，diI表示需求點與聚類中心的距離，dij表示需求點到配送中心的距離，dIj表示配送中心到聚類中心的距離，（Xi,Yi）表示需求點坐標，（XI,YI）表示聚類中心坐標，（Xj,Yj）表示配送中心位置坐標。

Step3：更新訂單位置，重新計算Step1，Step2，直至訂單穩(wěn)定，結(jié)束迭代。

2.2 懲罰成本

由于配送時間的限制性而產(chǎn)生一種懲罰成本，懲罰成本大小表示顧客對于即時配送時間的滿意程度，兩者之間的關系是此消彼長，密不可分的，CC表示懲罰成本，ε1,ε2表示早到或晚到客戶點的時間懲罰系數(shù)，因此懲罰成本可表示為：

2.3 貨損成本

產(chǎn)品新鮮度對于顧客的回頭率具有非常重要的作用，本文引入新鮮度函數(shù)來體現(xiàn)生鮮農(nóng)產(chǎn)品的貨損成本，生鮮產(chǎn)品的新鮮度會隨著配送時間和溫度的變化而變化，假設生鮮超市農(nóng)產(chǎn)品物流配送過程中可以保證產(chǎn)品恒溫運輸，α 為變質(zhì)率，且為固定常數(shù)，H（t）表示生鮮農(nóng)產(chǎn)品從配送中心O 到需求點i 中即時配送過程中發(fā)生的新鮮度變化。

當t=0 時，H（t）=1，此時生鮮農(nóng)產(chǎn)品從配送點開始裝車出發(fā)，假定新鮮度為1，經(jīng)過運輸過程中耗費的時間t，新鮮度逐漸下降，由此表現(xiàn)出遞減的指數(shù)函數(shù)。

根據(jù)生鮮農(nóng)產(chǎn)品需求量與下降的新鮮度成線性關系的假設，只考慮訂單運輸過程中的貨損成本，P 為貨物單價，α 表示生鮮產(chǎn)品貨損率，ti表示配送車輛Ki行駛到訂單i 的時間，t0表示配送車輛Ki從配送中心出發(fā)的時間，則貨損成本為：

2.4 運輸成本

生鮮產(chǎn)品從集中生產(chǎn)場所流入分散需求點主要通過物流配送來實現(xiàn)，在配送過程中成本支出最大的部分就是運輸成本，運輸成本始終貫穿配送的每一時刻，在企業(yè)經(jīng)濟效益中占據(jù)重要地位，受物流運輸距離，車輛行駛速度等主要因素影響。忽略供應商到配送中心的距離，考慮從配送中心到需求點再到配送點的距離下的固定成本和車輛運輸成本。

因此，建立目標函數(shù)模型：

目標函數(shù)表示以總配送成本最小，具體又包括以訂單分類影響的訂單分類標準和配送時間，運輸過程中產(chǎn)生的運輸費用，貨損費用，懲罰費用。

約束條件：

約束（13）表示多個訂單需求量小于配送車輛載重量；約束（14）表示每個客戶只被一個配送車輛配送；約束（15）表示車輛從配送中心出發(fā)到完成配送，并返回配送中心；約束（16）表示第k 輛配送車輛從第i 個需求點到第j 個配送點的概率，或0，1 代表配送，0 代表不配送；約束（17）Yki表示第k 輛車到第i 個需求點的概率，Yki=1 或0，1 代表配送，0 代表不配送。

3 粒子群算法模型

物流配送路徑優(yōu)化問題屬于多變量、多目標的復雜線性問題，物流配送路徑優(yōu)化方法主要有精確算法和啟發(fā)式算法兩類。這兩類方法又包含蟻群算法、遺傳算法、粒子群算法、模擬退火算法以及禁忌搜索算法等，蟻群算法適用于多目標的優(yōu)化問題，遺傳算法適用于更復雜類型的優(yōu)化問題，粒子群算法參數(shù)設置較簡單，更適用于多峰高維的復雜計算問題[10-12]。但他們本身又具有一定的局限性，比如在粒子群算法全局搜索過程中易早熟收斂、陷入局部最優(yōu)，需提出改進后的粒子群算法，克服粒子群算法的不足，能更好地解決配送路徑問題。

3.1 粒子編碼方式

在粒子群算法尋優(yōu)過程中，每個粒子都代表著需求點被選的隨機性，假設粒子維度v 與需求點數(shù)量n 相等，每個維度數(shù)代表相應待選擇的需求點，Xi表示粒子i 的第一維編碼原始值，原始值在[1,n] 內(nèi)變化，相同的整數(shù)部分表示同一車輛配送，小數(shù)部分的數(shù)值大小表示配送的先后順序，Ki表示粒子i 的第二維編碼值，代表需求點選取的車輛編號，本文選取盒馬生鮮12個需求點的實際位置坐標，按照數(shù)值越小越先配送的原則，進行編碼排序，以配送中心作為初始聚類，則初始種群的配送方案（粒子）的編碼和解碼如表1 所示。

表1 配送中心與粒子間的映射關系

粒子從多個配送中心出發(fā)，逐步訪問各需求點位置、時間窗要求、商品新鮮度接受程度及配送車輛最大承載量，各需求點僅被訪問一次，訪問結(jié)束后返回配送中心。根據(jù)粒子形成的位置記憶，對需求點訂單進行順序編碼和解碼，如12 個需求點和3輛配送車輛的順序解碼后形成的配送順序分別為車輛k1配送O1-3-O1；車輛k2配送O2-2-4-5-1-10-O2；車輛k3配送O3-7-8-12-11-O3,車輛k4配送O4-9-6-O4。如圖1 所示。

圖1 多配送中心配送方案

3.2 改進粒子群算法

3.2.1 自適應慣性權(quán)重

根據(jù)K-means 把多個配送中心轉(zhuǎn)化為單個配送中心求解，需求點i 到聚類中心I 的距離很大程度上是由距離慣性權(quán)重來決定的，粒子設置相應的適應度值，調(diào)整權(quán)重大小，對于路徑優(yōu)化有重要作用，因此適應度函數(shù)如式（18）所示：

其中：w1,w2表示權(quán)重因子，且因即時配送的生鮮產(chǎn)品大部分為三公里之內(nèi)的訂單，則有w1+w2=1,w1＞w2,Daverage表示需求點i 的平均配送距離，Dmin表示各需求點i 最低配送距離，Dmax表示最長配送距離，Dtotal表示各需求點i 總配送距離。

3.2.2 粒子位置，速度更新

實時更新粒子位置，速度粒子的位置和速度對于粒子群算法的選優(yōu)過程占有重要地位，他們不僅能解決粒子陷入局部最優(yōu)的局面，而且快速縮短尋優(yōu)過程的時間以及準確度的提高，本文在更新粒子位置和速度時把訂單產(chǎn)生的隨機性考慮在內(nèi)，不同的時間段會有新的訂單取消和產(chǎn)生，更加準確設置合理的路徑。

粒子位置更新：

粒子速度更新：

3.3 改進算法步驟

設置參數(shù)，輸入需求點時間窗，位置坐標，假設車輛個數(shù)為n，求解的最大迭代次數(shù)為imax，本文取值200，當前迭代次數(shù)t=0，首先，初始化粒子的速度和位置，即明確需求點位置，根據(jù)K-means 聚類算法和訂單相似性對訂單進行合理劃分，其次，按照上述得出的目標函數(shù)計算粒子的適應值，降低即時物流配送總成本。在相應的約束條件下得出單個粒子最優(yōu)值pbest和群體最優(yōu)值gbest，確定粒子初始最優(yōu)解，逐步迭代，同時改進智能算法，直至迭代次數(shù)最大，完成路徑優(yōu)化。具體算法過程如圖2所示。

圖2 算法過程

首先，對訂單開始聚類分析：

Step1：輸入客戶基本信息，比如位置信息、時間窗要求等；

Step2：隨機選取多個配送中心和聚類中心；

Step3：利用K-means 算法解鎖粒子編碼，根據(jù)訂單相似性分配車輛，完成分批配送劃分，并按照孰近原則劃分先后順序，持續(xù)更新需求點訂單，直至訂單相對趨于穩(wěn)定，得出配送車輛和配送順序的合理分配，否則返回Step2，重新迭代；

Step4：初始化種群，選擇客戶，引入算法，設置種群規(guī)模N，最大迭代次數(shù)imax，權(quán)重因子w1,w2等；

Step5：按照即時配送數(shù)學模型，計算每個粒子的適應度值，尋找種群粒子個體最優(yōu)位置bpest和群體全局最優(yōu)位置pbest；

Step6：更新粒子位置、速度、慣性權(quán)重，產(chǎn)生的個體最優(yōu)和全局最優(yōu)替代原來產(chǎn)生的個體和全局最優(yōu)；

Step7：滿足迭代次數(shù)，若是，則輸出結(jié)果，若否，則Step6，重新執(zhí)行粒子優(yōu)化策略，直至迭代結(jié)束，得到全局最優(yōu)解。

4 案例分析—盒馬生鮮

4.1 案例基本情況

以某市某區(qū)域盒馬生鮮即時物流配送為例，研究改進后的智能算法對物流即時配送的成本影響和效率影響，并提出相應意見，具體案例相關數(shù)據(jù)設置如表2、表3 所示。

表2 用戶點位置和時間窗要求

表3 相關參數(shù)設置

4.2 模型求解

本文將多個配送中心配送轉(zhuǎn)化成多個單配送中心出發(fā)，再利用K-means 算法選取其中一個需求點i 為聚類中心，粒子從聚類中心I 配送出發(fā)，逐步訪問各需求點位置、時間窗要求、商品新鮮度接受程度以及配送車輛最大承載量，各需求點僅被訪問一次，訪問結(jié)束后更新需求點信息直至穩(wěn)定形成位置記憶，最后返回配送中心。以需求點1 作為更新的聚類中心，解碼結(jié)果如表4 所示：

表4 聚類中心與粒子間的映射關系

根據(jù)粒子形成的位置記憶，對需求點訂單進行順序編碼和解碼，形成的配送順序分別為車輛k1配送1-5-4-3-2-10-1；車輛k2配送1-6-9-1；車輛k3配送1-8-12-11-7-1，由圖3 所示。

圖3 聚類中心配送方式

4.3 算法比較

表5 改進算法對目標函數(shù)的影響

表6 改進算法與傳統(tǒng)算法對比

5 結(jié)論

由此可知，注重物流運輸效率、加強管理上的模式，提高物流服務質(zhì)量，優(yōu)化粒子適應度值，改變粒子慣性權(quán)重，更新粒子位置和速度對于粒子的尋優(yōu)過程至關重要，不僅有效避免粒子陷入局部最優(yōu)，同時又能保證整個尋優(yōu)過程高速、準確進行，提升客戶滿意度，高效完成訂單配送。優(yōu)化訂單的劃分標準，注重訂單的個性化服務，以及特殊需求，提高客戶滿意度，最終降低536 元配送總成本，提高12%的配送效率。