考慮電商超市多倉多品類訂單拆分與整合的車輛路徑優化

孫一凡，高更君

（上海海事大學 物流研究中心，上海 201306）

0 引言

2021年雙11電商產業實現穩健增長，折射出消費活力和經濟韌性。國家郵政局檢測數據顯示，全國郵政、快遞企業11月11日當天共處理快件6.96億件，再創歷史新高，未來訂單量的增長是常態化的。電商超市布局多倉存儲貨物可服務區域更廣，但客戶訂單的差異化以及收貨時間、服務次數的限制使得電商訂單配送的研究受到廣泛關注，如何有效減少物流成本，提高客戶服務水平是本文的優化目標。

林昌輝[1]針對電商企業在配送訂單時面臨的訂單拆分需求，提出考慮訂單拆分的多倉庫車輛路徑優化問題，以最小化配送距離為目標，同時決策訂單的分配和車輛路徑的規劃。喻銳[2]設計醫藥物流多倉聯動的雙層配送模式，將區域內車輛調度問題與物流中心庫存問題相結合，實現多倉聯動模式的創新。劉鵬程[3]針對多中心集貨需求隨機的同時配集貨車輛路徑問題展開研究，構建了兩階段優化模型。范厚明等[4]研究多中心開放式同時配集貨需求可拆分車輛路徑問題，建立以車輛派遣成本、理貨成本以及運輸成本之和最小為目標的車輛路徑優化模型，設計混合遺傳算法進行求解，研究成果拓展了車輛路徑問題的相關理論。Imen Harbaoui Dridi等[5]研究多車、多倉庫、帶時間窗口的提貨和交貨問題，滿足客戶和供應商之間的運輸要求，優先級、容量和時間限制，找到最小化總旅行距離的最佳路線。盛虎宜[6]綜合考慮區域內多配送中心、客戶居住地較分散、同時具有集貨和送貨雙重需求、集貨量與需求量都比較小等因素，以總配送費用最少為目標構建農村電商基于共同配送策略的集送貨一體化車輛路徑問題數學模型。WANG Yong等[7]提出基于時間窗分配的多中心協同取貨配送問題，并將其化為兩階段優化問題進行求解，通過時間窗口分配策略，將一組候選時間窗口分配給相應的客戶，以提高物流網絡的運行效率，目標為最小化車輛數量和總運行成本。符卓等[8]綜合考慮客戶需求依訂單拆分和客戶有被服務時間的要求，研究帶軟時間窗的需求依訂單拆分車輛路徑問題。李寒梅[9]結合企業實踐提出同時具有多品種運輸物品、多車場、多時間窗、需求可拆分集送貨車輛路徑問題。張維智[10]考慮車輛裝載量、運行距離限制、網點服務時間限制對同時取送貨車輛路徑的影響，構建以系統總成本最小為優化目標包括調用成本、運行成本、裝卸成本及時間窗偏離懲罰成本的同時取送貨車輛路徑優化模型。章園園[11]通過分析電子商務訂單的特點，針對“一地多倉”型自營電子商務平臺的訂單拆分與分配進行研究，提出以提高客戶滿意度、降低履約成本為目標的新拆單原則，并將訂單拆分與配送相結合，在保證客戶滿意度的情況下最小化訂單履約成本。楊明星[12]分析電子商務環境下在線零售商客戶訂單的特點，研究“一地多倉”模式下在線零售商的訂單拆分及在各倉庫間的分配問題，考慮品類拆單與數量拆單同時存在的情形，最小化總配送成本，構建以“最小拆單數”作為訂單拆分規則的在線零售商訂單分配與車輛路徑的聯合優化模型。ZHU Shan等[13]提出了一種基于多商品訂單配送的啟發式k鏈接聚類算法來優化多倉庫之間的產品類別分配，以最小化訂單拆分的總次數，減少多商品的客戶訂單因需要分成多個發貨導致的更高的運輸成本。郭瓊[14]針對網上超市的高拆單率問題，提出利用多供應商間的橫向轉運策略，以最小化訂單履行總成本為目標，將拆分訂單合并運輸優化問題分為完全合并和部分合并兩種方式，可針對客戶的需求選取適合的拆分訂單合并優化方法。ZHANG Yuankai等[15]討論在線零售最后一英里配送中出現的多個貨物被多次交付給同一客戶問題，提出一種訂單合并方法，將相同客戶的貨物在派送站合并，以更少的配送距離完成配送。建立一個在分裝和合并貨物之間進行成本權衡的整數規劃模型。黃敏芳等[16]以減少大型網上超市拆分子訂單的包裹在分撥中心的合并成本為目標，針對多分撥中心之間通過循環發車對拆分訂單子包裹進行橫向轉載與合并這一作業流程，建立了大型網上超市拆分子訂單的包裹合并配送的優化模型，提出采用分段整數編碼的遺傳算法優化訂單合并次序。

目前電商配送研究多為車輛路徑優化、車輛調度方面的研究，使得貨物配送在便捷性、實用性和經濟性方面有了質的飛躍，更好的滿足客戶的個性化需求，但僅研究訂單的拆分或者整合，僅考慮配送沒有考慮車輛回程等環節對成本的影響。本課題從客戶下訂單開始，按照倉庫庫存拆分訂單，通過設置轉運倉庫整合訂單等一系列物流活動的閉環服務，從而在提高客戶服務質量的前提下降低物流配送成本。

1 模型構建

1.1 問題描述

電商超市在一個地區設置多個品類倉，由于商品具有互斥性，倉庫內存放多種商品，商品種類有差異且有部分重合；每個倉庫有多輛車，保證每個倉庫車輛進出平衡。考慮距離、包裹數、客戶及倉庫的時間窗選擇轉運倉庫，通過橫向轉運的方式集齊訂單所需商品后訪問客戶一次；轉運或配送任務完成后，車輛就近返回倉庫，通過轉運、儲存、配送、車輛回程等物流活動過程中的成本，研究多倉多品類訂單先拆分后整合的車輛路徑優化問題如圖1所示，確定合適的訂單分配和客戶服務方案，提高電商訂單整體處理效率。

圖1 多倉多品類訂單先拆分后整合的車輛路徑優化問題圖

1.2 假設條件

作出假設如下：

1）電商超市在一個區域的多個倉庫為分類倉，即每個倉庫所儲存商品種類有重合；

2）滿足每個客戶點的需求，且只能被服務一次，每個客戶的送貨需求量都小于車輛最大載容量限制；

3）每個倉庫有充足的同類型的配送車輛，車輛完成配送任務后，按照就近原則返回任一倉庫，且每個倉庫的車輛進出平衡；

4）卡車以平均速度行駛，車輛成本與單位運行成本有關；

5）倉庫裝貨成本、客戶點卸貨成本與包裹數有關，含在包裹的配送成本中；

6）客戶、倉庫對配送服務有期望接收服務的時間窗；

7）不宜混裝貨物在多倉庫分開存儲，配送時可在卡車混裝。

1.3 符號說明

符號說明如表1所示。

表1 符號說明表

1.4 建立模型

根據本文提出的多倉多品類訂單先拆分后整合的車輛路徑優化問題，以成本作為目標函數，構建模型如下：

其中，式(1)按客戶所購種類劃分客戶歸屬倉庫；式(2)表示該地區的倉庫備貨充足，不存在缺貨情況；目標函數式(3)為總成本最小化，總成本包括轉運成本，儲存成本，車輛單位運行成本及與包裹數有關的配送成本，客戶及倉庫的時間懲罰成本，客戶到倉庫的空車分配成本、轉運倉庫到倉庫的空車分配成本；式(4)某配送車輛k在客戶點i的時間懲罰成本；式(5)某配送車輛k在倉庫n的時間懲罰成本；式(6)計算車輛到達客戶點i的時間；式(7)計算車輛到達倉庫n的時間；式(8)表示當車輛到達客戶點i的時間點比規定的時間窗口稍早時，需要等待一會；式(9)表示當車輛到達倉庫n的時間點比規定的時間窗口稍早時，需要等待一會；式(10)表示從第1個倉庫開始裝貨的初始時間設為零；式(11)保證每個客戶點由一輛車提供服務；式(12)表示每個節點流入的車輛數和流出的車輛數相等；式(13)表示節點自己內部流量為零；式(14)表示某卡車從某倉庫出發時，所載貨物量等于該倉庫服務客戶點的送貨量之和；式(15)指從倉庫出發的車輛上的貨物不能大于最大車載能力；式(16)表示車輛從轉運倉庫出發，并且回到任一倉庫；式(17)表示當倉庫n中含有客戶i中的某種商品時，該倉庫與該客戶才有可能匹配；式(18)表示客戶i備選倉庫中商品r的數量需滿足訂單需求；式(19)表示每一個訂單至少被一個倉庫滿足，即必須被匹配完成；式(20)表示一個訂單在一個轉運倉庫合并；式(21)表示訂單合并完成時間取決于轉運時間最長的子訂單的轉運時間；式(22)表示客戶i的訂單分配在j倉庫開始轉運的時間；式(23)表示倉庫的庫存量不能超過倉庫最大容量；式(24)表示所有訂單開始轉運的時間一致。

2 遺傳算法

2.1 算法選擇及概述

遺傳算法是一種基于生物進化的啟發式搜索算法，遺傳算法構造的問題初始解不是單個解，在同一時間一起處理種群中的多個個體，因此迭代過程中不易陷入局部最優解；適應度函數是遺傳算法進行個體評判的唯一標準，不需要額外輔助信息；搜素方向上沒有確定的規則，根據進化過程中獲得的信息直接組織搜索，更容易快速收斂于最優解。

2.2 遺傳算法流程

遺傳算法求解流程如下：

Step1 染色體編碼設計：采用實數編碼，每一個GENE都表示一個轉運倉庫編號，每一條染色體表示一種轉運方案，每個個體染色體總長為客戶數50。其中，客戶數=訂單數=基因長度。染色體的結構如下：

Step2 種群初始化：隨機產生多組亂序的1～n序列作為遺傳算法的初始種群，種群數量設置為300；

Step3 適應度函數：計算轉運成本，儲存成本，車輛單位運行成本及與包裹數有關的配送成本，客戶及倉庫的時間懲罰成本，客戶到倉庫的空車分配成本、轉運倉庫到倉庫的空車分配成本之和，作為適應度函數，適應度函數值越低，個體越優；

Step4 判斷迭代次數是否超過最大迭代次數，若是，跳轉至step8；若否，則進行下一步；

Step5 選擇：采用輪盤賭選擇法。對所有個體按適應度函數進行升序排列后取倒數，各個個體被選中的概率與其大小成正比；

Step6 交叉：采用經營保留策略+單點交叉法。保留排序最優的個體染色體，隨機選擇298個父代染色體進行單點交叉，對應位置的基因進行互換；

Step7 變異：采用隨機單點變異法。隨機選取兩個變異點，交換相應的基因，返回Step3；

Step8 終止條件：迭代1000次，提取種群中最優個體，算法結束。

3 算例分析

3.1 背景描述

假設上海市9個電商倉庫給隨機選取的50個客戶配送商品，將電商訂單商品分為以下15類，食品類：1食品酒飲2生鮮食品3醫療保健；電子類：4手機數碼5電腦、辦公6家電7母嬰、玩具、樂器8個護化妝9圖書、音像10服飾、鞋帽；高價值類：11鐘表、珠寶12禮品箱包13工業品14汽車用品15家具、家裝、廚具。品類13、14、15不宜混裝貨物在多倉庫分開存儲，配送時可在卡車混裝。

3.2 參數設置

假設各倉庫、客戶點之間道路互通，位置如表2所示，客戶需求及倉庫、客戶時間窗參數如表3所示，倉庫商品的庫存供應量如表4所示，相關參數如表5所示。

表2 倉庫及客戶點位置表

表3 客戶需求及倉庫、客戶時間窗參數表

表4 倉庫商品的庫存供應量表

表4 倉庫商品的庫存供應量表

表5 相關參數表

結合算例數據得到目標函數如下：

3.3 算例結果

Python運行8min27s，得到50個客戶訂單對應9個轉運倉庫，分別為1，2，6，4，7，3，9，8，5，總成本最小為2783.59元。適應度函數與迭代次數圖如圖2所示。

圖2 適應度函數與迭代次數圖

轉運及配送情況如表6所示。所有倉庫均作為轉運倉庫，倉庫6轉運商品次數最多為6次，倉庫5轉運商品次數為5次，倉庫3、4、7轉運商品次數為3次，倉庫1、2、8、9轉運商品次數最少為1次；轉運倉庫1服務客戶數最多為14，轉運倉庫5服務客戶數最少為1。

表6 轉運及配送情況表

客戶所需商品品類轉運情況如表7所示。其中，8位客戶所需商品全部需要轉運，在總客戶數中占比16%，70%的客戶有一半商品需要轉運，2位客戶訂單的轉運率最低為20%。

表7 客戶所需商品品類轉運情況表

電商超市訂單多倉拆分及訂單整合的轉運、配送過程如圖3所示。總轉運里程：451.09km，轉運倉庫總存儲時間：205.26h，違反倉庫時間：0，違反客戶時間：54.32h，客戶到倉庫空車里程：1025.14km，倉庫間轉運空車里程：38.92km。

4 結語

電商超市呈現多倉服務一個區域的形式，電商訂單以多品類為主，客戶需求的差異化制約訂單快速響應，及時完成配送。本文建立模型通過轉運倉庫實現訂單的拆分與整合，滿足客戶一次配送的需求，尋找成本最低的車輛路徑。運用算例驗證設計的遺傳算法能求得最優解。結果表明，依據倉庫及客戶位置考慮轉運、倉庫存儲成本、車輛回程成本，結合配送包裹數，時間窗等選擇物流總成本最低的轉運倉庫，從而得出配送車輛路徑，為電商訂單配送問題提供從轉運、倉儲、配送等多環節整體優化的研究方向。