基于客戶分流策略的電商促銷下車輛路徑問題研究

呂俊杰 馮 謙

(北京工商大學商學院 北京 100048)

0 引 言

近年來電子商務在中國迅速崛起，各電商企業為了吸引客戶競相開展促銷活動，使客戶的需求發生井噴式增長，這對電商的線下物流配送活動提出了巨大的挑戰。即使電商物流部門全負荷工作，仍然有很多商品無法按時送到，影響客戶的購物體驗。物流配送效率直接影響客戶對電商促銷活動的滿意程度，因此如何優化配送路線既能有效控制成本增加又能滿足客戶的時間要求，已經成為電商促銷下物流服務亟需解決的重要問題。

現有國內外文獻對電商配送路徑優化問題主要從成本或時間這兩個角度展開研究。如Prins[1]研究了以最小行駛路徑成本為目標的多車型車輛路徑問題；Kown等[2]研究了不同車型排放量同類型車輛排放成本的車輛路徑問題；馬秋卓等[3]以最小化碳排放成本為目標，探討了市區小范圍配送網絡內最優車輛路徑問題決策；Lin Zhou等[4]以最小化運輸成本為目標，研究了最后一公里客戶不同收貨方式的車輛路徑問題；符卓等[5]研究了以成本為目標的客戶需求可按商品拆分的車輛路徑問題；李妍峰等[6]研究了最小化車輛行駛時間為目標的動態網絡車輛路徑派送問題；王旭坪等[7]以最小化總時間為目標，研究了揀選與配送聯合調度問題。劉家利等[8]以系統車輛總成本為目標，研究了一種具有多個配送中心、存在車輛租賃、有時間窗限制的開環車輛路徑問題；王旭坪等[9]以最大客戶滿意度為目標，研究了模糊時間窗下的車輛路徑問題；張源凱等[10]以最小化運輸成本為目標研究了一地多倉環境下商品分配和配送聯合優化問題；陳萍等[11]以最大化客戶時間滿意度為目標，研究了一類外賣配送模型。

上述研究可以規劃出特定情境下的最佳行駛路徑，但綜合分析，上述研究不適用于需求井噴情況下的配送路徑問題，研究內容仍有局限性。電商配送服務需要滿足客戶的時間要求，不能以節省自身成本為目標，但同時電商促銷時客戶的商品需求量急劇增加，配送服務無法滿足所有客戶的時間要求。因此，針對電商促銷時客戶時間敏感性不同的特點，本文將客戶分為時間敏感型和時間延遲型兩類，把集中的配送需求分散化，既能滿足敏感型客戶對配送時間的要求，又能控制總成本的增加。同時，構建了井噴需求場景的多周期多車程車輛路徑優化模型，并通過數值實驗與最小成本、最短時間目標路徑模型進行對比。

1 問題描述與模型建立

1.1 問題描述

本文問題可以用圖G=(N,A)描述，其中N表示節點的集合，i或j表示節點編號，包括1個配送中心和n-1個末端網點，A={(i,j|i∈N,j∈N)} 為弧的集合。用K表示配送中心的車輛集合，在一定周期內配送完Q個商品。在單位周期的工作時間Dk內車輛多次往返配送中心和網點之間，用T表示周期數，h表示車輛配送車次，用sikhT表示在第T個單位周期內車輛k第h次配送過程到達節點i的時間，在第一個單位周期內車輛k第一次從配送中心出發的時間sik11=0；tij表示從網點i到j的行駛時間。車輛不允許超載，最大載量均為q。單位周期內車輛加班時間為tkT，單位時間加班成本為ck，末端網點i的商品單數為Qi，gikhT表示在第T個單位周期內車輛k第h次配送到網點i的商品數量。

決策變量：

xijkhT：第T個周期內車輛k第h次配送從網點i行駛至j時為1，否則為0；

yikhT：第T個周期內點i的商品配送任務由車輛k第h次配送時完成為1，否則為0。

1.2 數學模型

本文提出一種客戶分流策略并建立多周期多車程車輛路徑優化模型，同時建立以最小成本和最短時間為目標的多周期多車程車輛路徑優化模型進行對比，下面展開介紹三種模型的構造過程。

客戶分流策略根據客戶時間敏感度的不同，將客戶分為時間敏感型和時間延遲型。時間敏感型客戶對配送時間要求高，電商物流配送服務必須在其期望時間范圍內完成商品配送；時間延遲型客戶愿意接受超出一定時間范圍的延遲配送服務，因此需要對其給予一定程度的補償。如圖1所示，車輛優先配送三個有敏感型客戶商品的網點，然后再配送其余只有延遲型客戶商品的網點。

圖1 客戶分流策略下單位周期內車輛k配送示意圖

其中將所有節點集合N分為0、N+和N-三個部分，0代表配送中心，N+代表網點(敏感型客戶)，N-代表網點(延遲型客戶)，車輛單位距離運輸成本為cij，延遲配送商品的單位補償成本為b，末端網點i需要的商品商品數為Qi。

根據以上問題的描述和界定，客戶分流策略的車輛路徑優化模型建立如下：

(1)

(2)

式(2)表示單位周期T內配送中心單次出發車輛數至多有K輛。

(3)

式(3)表示車輛不允許超載。

(4)

式(4)表示車輛每次從配送中心出發并返回配送中心。

(5)

式(5)表示所有網點商品都被配送。

?k∈K,T=1,2，…

(6)

式(6)表示某一車輛駛出點必是該車輛駛入點。

(7)

式(7)表示單位周期T內車輛k第h次和第h-1次配送行駛時間的連續性。

(8)

式(8)表示單位周期T內車輛第h次配送到末端網點j的時間。

先說學術權力行政化。我國社會的“官本位”意識濃厚，這種“官本位”觀念也滲透到了高校的學術管理中，影響到了學術管理中的行政權力的正當行使。在學術管理中，許多行政人員唯官是從，習慣于按照官的指示辦事，而很少考慮學術發展的客觀規律。隨之而來的是服務意識淡薄，行政人員自身定位不準，對學術管理中學術人員應有的主體地位和學術權力的主導地位認識有限，服務不到位。各種委員會的設置缺乏明確的章程，任務不明，職責不清，這說明我國許多高校的學術機構在人員構成上具有明顯的行政化傾向。

s0khT+UkM≤Dk?h∈H,?k∈K,T=1,2,…

(9)

(10)

式(9)和式(10)表示車輛k單位周期工作時間限制，若第h+1次配送時間超出工作時間限制，則第h次配送回到配送中心后停止工作。

?i∈N+,?h∈H,?k∈K

(11)

式(11)表示時間敏感型客戶的商品要求在一定時間內送至末端網點。

sjkhT≤sikhT?i∈N-,?j∈N+,?h∈H,?k∈K

(12)

式(12)表示時間敏感型客戶商品配送結束后開始送延遲型客戶的商品。

為了對比客戶分流策略下配送時效性，本文構建常規配送方式下以最小成本為目標的車輛路徑模型，如圖2所示該車輛路徑模型選擇的是路徑成本最低的配送方案，網點間的配送順序沒有優先級。

圖2 最小成本策略下單位周期內車輛k配送示意圖

故最小成本目標的車輛路徑模型目標函數為：

(13)

式(13)計算了所有周期內全部車輛的運輸成本之和，該模型的約束條件取式(2)-式(10)。

圖3 最短時間策略下單位周期內車輛k配送示意圖

Tdeadline為所有客戶允許的最晚收貨周期，在Tdeadline結束前電商物流部門必須將商品全部送達，最短時間目標的車輛路徑優化模型目標函數為：

(14)

該模型約束條件取式(2)-式(8)，并在此基礎上增加如下約束：

s0khT+UkM≤Dk+tkT?h∈H,?k∈K,T=1,2,…

(15)

(16)

?j∈N,?h∈H,?k∈K

(17)

式(14)為模型的成本目標函數，計算了所有周期內所有車輛運輸成本和加班成本的和；式(15)和式(16)表示每天車輛工作時間限制, 當車輛k第h+1次配送時間超出當天工作時間，則在第h次配送結束回到配送中心后停止工作；式(17)表示最后一個回到配送中心的車輛所花費的所有時間不超過Tdeadline與單位周期內總的工作時間Dk+tkT的積。

2 改進的遺傳算法

根據上文可知，該問題是多車程的車輛路徑優化問題，屬于NP難問題，適合使用啟發式算法求解。在各類啟發式算法中，遺傳算法的優點是有很強的魯棒性和全局搜索能力，適合求解復雜多極值優化和組合問題。

目前遺傳算法主要有基于行駛路徑編碼方式和基于需求點編碼方式兩種，這兩種編碼方式只適合單次車程的車輛路徑優化。根據研究問題中車輛多次從配送中心出發并返回的特點，而且存在時間敏感型客戶商品和時間延遲型客戶商品的區分，本文提出一種新的染色體表示方式——基于車輛和需求點分類的混合編碼方式。

2.1 染色體編碼和種群初始化

將所有節點編為一條大的TSP路徑進行編碼，在網點編碼后加入配送中心編碼，然后在所有節點編碼后加入車輛編碼，用于切割大TSP路徑。用配送中心編碼、末端網點編碼和車輛編碼三部分構成每條染色體。其中客戶分流策略中，編碼構成為配送中心編碼+網點(敏感型客戶)編碼+網點(延遲型客戶)編碼+配送中心編碼+車輛編碼，表示為：(1) 網點(敏感型客戶)編碼1，2，…，N1；網點(延遲型客戶)編碼N1+1,N1+2,…，N；配送中心編碼為0。(2) 車輛編碼N+1，N+2，…，N+K。旅行商路徑切割流程如下：

步驟1：按節點編碼順序從左到右累計網點編碼，直到超過車輛負載q的前一個編碼，將這些網點加入到第一輛車輛行駛計劃中，依次類推直到所有車輛都有任務。

步驟2：若有剩余末端網點沒有分配到車輛行駛計劃中，則重復步驟1，直到所有末端網點編碼都有對應的車輛編碼。

2.2 適應度函數和選擇操作

適應度用于評價每個配送方案的優劣程度，每個配送方案可以用一個染色體來表示，染色體適應度越大，該方案被選擇的幾率也越大。

令目標函數倒數為適應度函數，zi表示第i條染色體對應的目標函數，該染色體的適應度為fi=1/zi。判斷染色體是否滿足約束條件，滿足則保留，反之則舍棄；將適應度fi≥favg的染色體保留到子代；對全部染色體進行交叉和變異操作，按適應度大小再選出N-L條染色體，與保留的L條染色體組合構成下一代種群。

2.3 交叉和變異操作

每代種群個體以交叉概率交叉重組，pc表示染色體個體i1和i2的交叉概率，pavg表示基礎概率，pmax表示適應度值大于平均值的染色體個體交叉概率，f表示i1和i2中適應度值大的個體適應度值，favg表示平均適應度值，fmax表示最大適應度值。交叉概率公示為：

采用兩點交叉算法，隨機在染色體個體編碼串中設置了兩個交叉點，兩點之間區域為匹配區域，并在[0，1]之間產生一個隨機數r，若pc≥r，則進行交換部分基因，否則不交叉。其中，客戶分流配送策略編碼的兩條染色體在交叉區域的基因位對應可能存在下列三種情形(見圖4)，分別為：對應基因位為“網點(敏感型客戶)編碼-網點(延遲型客戶)編碼”，如交叉區域[A,E]、[D,B],此時不進行交叉；對應基因位為“網點(敏感型客戶)編碼/網點(延遲型客戶)編碼-車輛編碼”，如交叉區域[A,F]、[B,F]、[D,C]、[E,C],此時也不能進行交叉；對應基因位為“網點(敏感型客戶)編碼-網點(敏感型客戶)編碼”、“網點(延遲型客戶)編碼-網點(延遲型客戶)編碼”、“車輛編碼-車輛編碼”，如交叉區域[A,D]、[B,E]、[C,F],此時采用部分匹配交叉的方式進行交叉。

圖4 交叉區域基因位對應情形圖

變異概率是染色體中某些基因改變的概率，pm表示染色體個體的變異概率，pmavg表示基礎變異概率，pmmax表示適應度值大于平均值個體所采用的變異概率，fm表示個體i1的適應度值，fmavg表示平均適應度值，fmmax表示染色體個體中最大適應度值。變異概率的公式為：

在[0，1]之間產生一個隨機數e，若pm

最后檢查交叉和變異產生的染色體是否滿足約束條件，不滿足則舍棄，反之則保留。

2.4 控制參數以及確定循環終止條件

控制參數的選取不同，遺傳算法的收斂性就會有所改變，這些控制參數主要有種群的大小、終止代數、變異概率、交叉概率等。判斷是否達到停止進化條件，如達到代數要求，則停止迭代，否則繼續迭代。 本文設置最大進化代數作為判斷算法終止條件，當算法迭代到MAX代時計算終止，此時選擇適應度值最大的染色體對應的路徑集合作為最優解。

2.5 算法性能分析

為了驗證本文改進的遺傳算法的有效性和優越性，針對Solomn算例庫中RC110算例分別采用基本遺傳算法和改進的遺傳算法模擬仿真求解10次進行比較，10次運算的平均結果如表1所示。

表1 算法運行性能比較

由表1可以看出，針對求解多車程多周期車輛路徑問題，改進遺傳算法在收斂最優解次數和計算時間方面均優于基本遺傳算法，顯示出良好的穩定性和尋優性能，同時在計算效率方面也有所提升。

本文設計的改進遺傳算法與基本遺傳算法的迭代收斂情況比較如圖5所示，圖中虛線顯示了基本遺傳算法求解過程的收斂情況，實線顯示了改進遺傳算法求解過程的收斂情況。由圖5可知，改進遺傳算法具有更好的收斂性。

圖5 兩種遺傳算法的迭代收斂圖

3 實驗結果與分析

本文以Solomn算例庫中20個算例數據為基礎進行擴建，構建1個配送中心與100個網點的電商促銷下商品配送的算例并進行仿真實驗，最后比較三種策略在成本和配送時效性方面的優化結果。

3.1 算例構建

配送中心有待處理商品60 000單，擁有10輛車載能力為500單的貨車，單位距離運輸成本1元，單位周期是1天，車輛單位周期工作時間為12 h。最短時間目標下車輛加班時間為6 h，加班成本為25元/h，要求48小時內配送完商品。客戶分流策略下隨機選取時間敏感型客戶商品16 413單，延遲型客戶商品43 587單，延遲型客戶商品每單補償0.1元。

本文實驗數據中設置1個配送中心(用坐標源點表示配送中心，序號為0)和100個末端網點，本文限于篇幅，僅展示100個網點中前20個網點的數據，如表2所示，其中X、Y表示網點坐標，R表示各網點商品的總需求量。

表2 測試算例相關數據信息

3.2 實驗結果

結合算例規模，設定算法參數如下：種群規模為100，迭代次數為200次，交叉概率Px=0.7，變異概率Pm=0.05。使用MATLABR2014a運行遺傳算法。

實驗結果顯示，以最小成本為目標的常規配送模式總成本為36 038.66元。該實驗數據包括10輛車4天內的行駛路徑，限于篇幅本文展示其中部分車輛的路徑情況(下文模型路徑結果也只進行部分展示)，如表3所示。

表3 最小成本配送策略的部分車輛路徑安排

以最短時間為目標的常規配送模式總成本為46 523.39元，部分車輛路徑安排情況如表4所示。

表4 最短時間配送策略下部分車輛路徑安排

客戶分流配送策略下總成本為41 550.23元。該策略下部分車輛路徑安排情況如表5所示。其中車輛在第四天完成所有配送任務，超出最晚配送周期2天，但車輛在敏感型客戶允許的最晚配送周期前完成對其的配送任務，如車輛1在第2天完成所有敏感型客戶商品的配送任務，車輛2在第一天完成所有敏感型客戶商品的配送任務。

表5 客戶分流策略下部分車輛路徑安排

為了分析三種配送模型在成本與時效性方面的優劣性，本文比較了它們的最優解，結果如表6和表7所示。

表6 實驗結果對比分析

表7 三種策略成本對比分析

從表6中可以看出，客戶分流策略總成本比最短時間配送模式總成本減少4 973.16元，減少約10.7%，但滿足時效性的商品比例與最短時間配送模式相同為100%。客戶分流策略總成本比最小成本目標總成本增加5 511.57元，增加了約15.3%，但滿足時效性的商品比例比最小成本配送模式增加了36.7%。

由表7可知，客戶分流策略與最短時間配送模式相比，運輸成本減少量約占總成本減少量的84.5%；客戶分流策略與最小成本配送模式相比，運輸成本增加量約占總成本增加量的50.5%；客戶分流策略的補償成本與最短時間配送模式的加班成本相比減少約22%。

可以看出，與最短時間配送模式相比，客戶分流策略按照客戶商品優先級配送，把集中的配送需求分散化，減少了單位周期內車輛的工作時間和配送車次，從而減少運輸成本，節約加班成本。并且，客戶分流策略可以根據節省的加班成本給予時間償延遲型客戶一定程度的補償，這樣既能使敏感型客戶商品的時效滿足率達到100%，同時也盡可能地減少延遲型客戶的抱怨，降低退貨的概率。與最小成本配送模式相比，客戶分流策略提高了滿足時效性的商品比例，并有效控制了成本的增幅。

4 結 語

本文考慮成本和客戶時間敏感度對配送過程的影響，基于客戶分流配送策略，建立了更加符合大規模需求場景的多周期多車程車輛路徑優化模型，通過算例驗證了三種配送方式的優缺點。未來,在本文的基礎上，可以進一步深化研究的方向有需求井噴場景下多車場多車型的配送問題，還可以通過加入不同貨物交付方式，結合配送中心到網點的配送環節進行聯合優化。