考慮電商超市多倉(cāng)多品類訂單拆分與整合的車輛路徑優(yōu)化

孫一凡，高更君

（上海海事大學(xué) 物流研究中心，上海 201306）

0 引言

2021年雙11電商產(chǎn)業(yè)實(shí)現(xiàn)穩(wěn)健增長(zhǎng)，折射出消費(fèi)活力和經(jīng)濟(jì)韌性。國(guó)家郵政局檢測(cè)數(shù)據(jù)顯示，全國(guó)郵政、快遞企業(yè)11月11日當(dāng)天共處理快件6.96億件，再創(chuàng)歷史新高，未來(lái)訂單量的增長(zhǎng)是常態(tài)化的。電商超市布局多倉(cāng)存儲(chǔ)貨物可服務(wù)區(qū)域更廣，但客戶訂單的差異化以及收貨時(shí)間、服務(wù)次數(shù)的限制使得電商訂單配送的研究受到廣泛關(guān)注，如何有效減少物流成本，提高客戶服務(wù)水平是本文的優(yōu)化目標(biāo)。

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

目前電商配送研究多為車輛路徑優(yōu)化、車輛調(diào)度方面的研究，使得貨物配送在便捷性、實(shí)用性和經(jīng)濟(jì)性方面有了質(zhì)的飛躍，更好的滿足客戶的個(gè)性化需求，但僅研究訂單的拆分或者整合，僅考慮配送沒(méi)有考慮車輛回程等環(huán)節(jié)對(duì)成本的影響。本課題從客戶下訂單開(kāi)始，按照倉(cāng)庫(kù)庫(kù)存拆分訂單，通過(guò)設(shè)置轉(zhuǎn)運(yùn)倉(cāng)庫(kù)整合訂單等一系列物流活動(dòng)的閉環(huán)服務(wù)，從而在提高客戶服務(wù)質(zhì)量的前提下降低物流配送成本。

1 模型構(gòu)建

1.1 問(wèn)題描述

電商超市在一個(gè)地區(qū)設(shè)置多個(gè)品類倉(cāng)，由于商品具有互斥性，倉(cāng)庫(kù)內(nèi)存放多種商品，商品種類有差異且有部分重合；每個(gè)倉(cāng)庫(kù)有多輛車，保證每個(gè)倉(cāng)庫(kù)車輛進(jìn)出平衡?？紤]距離、包裹數(shù)、客戶及倉(cāng)庫(kù)的時(shí)間窗選擇轉(zhuǎn)運(yùn)倉(cāng)庫(kù)，通過(guò)橫向轉(zhuǎn)運(yùn)的方式集齊訂單所需商品后訪問(wèn)客戶一次；轉(zhuǎn)運(yùn)或配送任務(wù)完成后，車輛就近返回倉(cāng)庫(kù)，通過(guò)轉(zhuǎn)運(yùn)、儲(chǔ)存、配送、車輛回程等物流活動(dòng)過(guò)程中的成本，研究多倉(cāng)多品類訂單先拆分后整合的車輛路徑優(yōu)化問(wèn)題如圖1所示，確定合適的訂單分配和客戶服務(wù)方案，提高電商訂單整體處理效率。

圖1 多倉(cāng)多品類訂單先拆分后整合的車輛路徑優(yōu)化問(wèn)題圖

1.2 假設(shè)條件

作出假設(shè)如下：

1）電商超市在一個(gè)區(qū)域的多個(gè)倉(cāng)庫(kù)為分類倉(cāng)，即每個(gè)倉(cāng)庫(kù)所儲(chǔ)存商品種類有重合；

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

3）每個(gè)倉(cāng)庫(kù)有充足的同類型的配送車輛，車輛完成配送任務(wù)后，按照就近原則返回任一倉(cāng)庫(kù)，且每個(gè)倉(cāng)庫(kù)的車輛進(jìn)出平衡；

4）卡車以平均速度行駛，車輛成本與單位運(yùn)行成本有關(guān)；

5）倉(cāng)庫(kù)裝貨成本、客戶點(diǎn)卸貨成本與包裹數(shù)有關(guān)，含在包裹的配送成本中；

6）客戶、倉(cāng)庫(kù)對(duì)配送服務(wù)有期望接收服務(wù)的時(shí)間窗；

7）不宜混裝貨物在多倉(cāng)庫(kù)分開(kāi)存儲(chǔ)，配送時(shí)可在卡車混裝。

1.3 符號(hào)說(shuō)明

符號(hào)說(shuō)明如表1所示。

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

1.4 建立模型

根據(jù)本文提出的多倉(cāng)多品類訂單先拆分后整合的車輛路徑優(yōu)化問(wèn)題，以成本作為目標(biāo)函數(shù)，構(gòu)建模型如下：

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

2 遺傳算法

2.1 算法選擇及概述

遺傳算法是一種基于生物進(jìn)化的啟發(fā)式搜索算法，遺傳算法構(gòu)造的問(wèn)題初始解不是單個(gè)解，在同一時(shí)間一起處理種群中的多個(gè)個(gè)體，因此迭代過(guò)程中不易陷入局部最優(yōu)解；適應(yīng)度函數(shù)是遺傳算法進(jìn)行個(gè)體評(píng)判的唯一標(biāo)準(zhǔn)，不需要額外輔助信息；搜素方向上沒(méi)有確定的規(guī)則，根據(jù)進(jìn)化過(guò)程中獲得的信息直接組織搜索，更容易快速收斂于最優(yōu)解。

2.2 遺傳算法流程

遺傳算法求解流程如下：

Step1 染色體編碼設(shè)計(jì)：采用實(shí)數(shù)編碼，每一個(gè)GENE都表示一個(gè)轉(zhuǎn)運(yùn)倉(cāng)庫(kù)編號(hào)，每一條染色體表示一種轉(zhuǎn)運(yùn)方案，每個(gè)個(gè)體染色體總長(zhǎng)為客戶數(shù)50。其中，客戶數(shù)=訂單數(shù)=基因長(zhǎng)度。染色體的結(jié)構(gòu)如下：

Step2 種群初始化：隨機(jī)產(chǎn)生多組亂序的1～n序列作為遺傳算法的初始種群，種群數(shù)量設(shè)置為300；

Step3 適應(yīng)度函數(shù)：計(jì)算轉(zhuǎn)運(yùn)成本，儲(chǔ)存成本，車輛單位運(yùn)行成本及與包裹數(shù)有關(guān)的配送成本，客戶及倉(cāng)庫(kù)的時(shí)間懲罰成本，客戶到倉(cāng)庫(kù)的空車分配成本、轉(zhuǎn)運(yùn)倉(cāng)庫(kù)到倉(cāng)庫(kù)的空車分配成本之和，作為適應(yīng)度函數(shù)，適應(yīng)度函數(shù)值越低，個(gè)體越優(yōu)；

Step4 判斷迭代次數(shù)是否超過(guò)最大迭代次數(shù)，若是，跳轉(zhuǎn)至step8；若否，則進(jìn)行下一步；

Step5 選擇：采用輪盤賭選擇法。對(duì)所有個(gè)體按適應(yīng)度函數(shù)進(jìn)行升序排列后取倒數(shù)，各個(gè)個(gè)體被選中的概率與其大小成正比；

Step6 交叉：采用經(jīng)營(yíng)保留策略+單點(diǎn)交叉法。保留排序最優(yōu)的個(gè)體染色體，隨機(jī)選擇298個(gè)父代染色體進(jìn)行單點(diǎn)交叉，對(duì)應(yīng)位置的基因進(jìn)行互換；

Step7 變異：采用隨機(jī)單點(diǎn)變異法。隨機(jī)選取兩個(gè)變異點(diǎn)，交換相應(yīng)的基因，返回Step3；

Step8 終止條件：迭代1000次，提取種群中最優(yōu)個(gè)體，算法結(jié)束。

3 算例分析

3.1 背景描述

假設(shè)上海市9個(gè)電商倉(cāng)庫(kù)給隨機(jī)選取的50個(gè)客戶配送商品，將電商訂單商品分為以下15類，食品類：1食品酒飲2生鮮食品3醫(yī)療保?。浑娮宇悾?手機(jī)數(shù)碼5電腦、辦公6家電7母嬰、玩具、樂(lè)器8個(gè)護(hù)化妝9圖書、音像10服飾、鞋帽；高價(jià)值類：11鐘表、珠寶12禮品箱包13工業(yè)品14汽車用品15家具、家裝、廚具。品類13、14、15不宜混裝貨物在多倉(cāng)庫(kù)分開(kāi)存儲(chǔ)，配送時(shí)可在卡車混裝。

3.2 參數(shù)設(shè)置

假設(shè)各倉(cāng)庫(kù)、客戶點(diǎn)之間道路互通，位置如表2所示，客戶需求及倉(cāng)庫(kù)、客戶時(shí)間窗參數(shù)如表3所示，倉(cāng)庫(kù)商品的庫(kù)存供應(yīng)量如表4所示，相關(guān)參數(shù)如表5所示。

表2 倉(cāng)庫(kù)及客戶點(diǎn)位置表

表3 客戶需求及倉(cāng)庫(kù)、客戶時(shí)間窗參數(shù)表

表4 倉(cāng)庫(kù)商品的庫(kù)存供應(yīng)量表

表4 倉(cāng)庫(kù)商品的庫(kù)存供應(yīng)量表

表5 相關(guān)參數(shù)表

結(jié)合算例數(shù)據(jù)得到目標(biāo)函數(shù)如下：

3.3 算例結(jié)果

Python運(yùn)行8min27s，得到50個(gè)客戶訂單對(duì)應(yīng)9個(gè)轉(zhuǎn)運(yùn)倉(cāng)庫(kù)，分別為1，2，6，4，7，3，9，8，5，總成本最小為2783.59元。適應(yīng)度函數(shù)與迭代次數(shù)圖如圖2所示。

圖2 適應(yīng)度函數(shù)與迭代次數(shù)圖

轉(zhuǎn)運(yùn)及配送情況如表6所示。所有倉(cāng)庫(kù)均作為轉(zhuǎn)運(yùn)倉(cāng)庫(kù)，倉(cāng)庫(kù)6轉(zhuǎn)運(yùn)商品次數(shù)最多為6次，倉(cāng)庫(kù)5轉(zhuǎn)運(yùn)商品次數(shù)為5次，倉(cāng)庫(kù)3、4、7轉(zhuǎn)運(yùn)商品次數(shù)為3次，倉(cāng)庫(kù)1、2、8、9轉(zhuǎn)運(yùn)商品次數(shù)最少為1次；轉(zhuǎn)運(yùn)倉(cāng)庫(kù)1服務(wù)客戶數(shù)最多為14，轉(zhuǎn)運(yùn)倉(cāng)庫(kù)5服務(wù)客戶數(shù)最少為1。

表6 轉(zhuǎn)運(yùn)及配送情況表

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

表7 客戶所需商品品類轉(zhuǎn)運(yùn)情況表

電商超市訂單多倉(cāng)拆分及訂單整合的轉(zhuǎn)運(yùn)、配送過(guò)程如圖3所示?？傓D(zhuǎn)運(yùn)里程：451.09km，轉(zhuǎn)運(yùn)倉(cāng)庫(kù)總存儲(chǔ)時(shí)間：205.26h，違反倉(cāng)庫(kù)時(shí)間：0，違反客戶時(shí)間：54.32h，客戶到倉(cāng)庫(kù)空車?yán)锍蹋?025.14km，倉(cāng)庫(kù)間轉(zhuǎn)運(yùn)空車?yán)锍蹋?8.92km。

4 結(jié)語(yǔ)

電商超市呈現(xiàn)多倉(cāng)服務(wù)一個(gè)區(qū)域的形式，電商訂單以多品類為主，客戶需求的差異化制約訂單快速響應(yīng)，及時(shí)完成配送。本文建立模型通過(guò)轉(zhuǎn)運(yùn)倉(cāng)庫(kù)實(shí)現(xiàn)訂單的拆分與整合，滿足客戶一次配送的需求，尋找成本最低的車輛路徑。運(yùn)用算例驗(yàn)證設(shè)計(jì)的遺傳算法能求得最優(yōu)解。結(jié)果表明，依據(jù)倉(cāng)庫(kù)及客戶位置考慮轉(zhuǎn)運(yùn)、倉(cāng)庫(kù)存儲(chǔ)成本、車輛回程成本，結(jié)合配送包裹數(shù)，時(shí)間窗等選擇物流總成本最低的轉(zhuǎn)運(yùn)倉(cāng)庫(kù)，從而得出配送車輛路徑，為電商訂單配送問(wèn)題提供從轉(zhuǎn)運(yùn)、倉(cāng)儲(chǔ)、配送等多環(huán)節(jié)整體優(yōu)化的研究方向。