呂俊杰 馮 謙
(北京工商大學(xué)商學(xué)院 北京 100048)
近年來電子商務(wù)在中國(guó)迅速崛起,各電商企業(yè)為了吸引客戶競(jìng)相開展促銷活動(dòng),使客戶的需求發(fā)生井噴式增長(zhǎng),這對(duì)電商的線下物流配送活動(dòng)提出了巨大的挑戰(zhàn)。即使電商物流部門全負(fù)荷工作,仍然有很多商品無(wú)法按時(shí)送到,影響客戶的購(gòu)物體驗(yàn)。物流配送效率直接影響客戶對(duì)電商促銷活動(dòng)的滿意程度,因此如何優(yōu)化配送路線既能有效控制成本增加又能滿足客戶的時(shí)間要求,已經(jīng)成為電商促銷下物流服務(wù)亟需解決的重要問題。
現(xiàn)有國(guó)內(nèi)外文獻(xiàn)對(duì)電商配送路徑優(yōu)化問題主要從成本或時(shí)間這兩個(gè)角度展開研究。如Prins[1]研究了以最小行駛路徑成本為目標(biāo)的多車型車輛路徑問題;Kown等[2]研究了不同車型排放量同類型車輛排放成本的車輛路徑問題;馬秋卓等[3]以最小化碳排放成本為目標(biāo),探討了市區(qū)小范圍配送網(wǎng)絡(luò)內(nèi)最優(yōu)車輛路徑問題決策;Lin Zhou等[4]以最小化運(yùn)輸成本為目標(biāo),研究了最后一公里客戶不同收貨方式的車輛路徑問題;符卓等[5]研究了以成本為目標(biāo)的客戶需求可按商品拆分的車輛路徑問題;李妍峰等[6]研究了最小化車輛行駛時(shí)間為目標(biāo)的動(dòng)態(tài)網(wǎng)絡(luò)車輛路徑派送問題;王旭坪等[7]以最小化總時(shí)間為目標(biāo),研究了揀選與配送聯(lián)合調(diào)度問題。劉家利等[8]以系統(tǒng)車輛總成本為目標(biāo),研究了一種具有多個(gè)配送中心、存在車輛租賃、有時(shí)間窗限制的開環(huán)車輛路徑問題;王旭坪等[9]以最大客戶滿意度為目標(biāo),研究了模糊時(shí)間窗下的車輛路徑問題;張?jiān)磩P等[10]以最小化運(yùn)輸成本為目標(biāo)研究了一地多倉(cāng)環(huán)境下商品分配和配送聯(lián)合優(yōu)化問題;陳萍等[11]以最大化客戶時(shí)間滿意度為目標(biāo),研究了一類外賣配送模型。
上述研究可以規(guī)劃出特定情境下的最佳行駛路徑,但綜合分析,上述研究不適用于需求井噴情況下的配送路徑問題,研究?jī)?nèi)容仍有局限性。電商配送服務(wù)需要滿足客戶的時(shí)間要求,不能以節(jié)省自身成本為目標(biāo),但同時(shí)電商促銷時(shí)客戶的商品需求量急劇增加,配送服務(wù)無(wú)法滿足所有客戶的時(shí)間要求。因此,針對(duì)電商促銷時(shí)客戶時(shí)間敏感性不同的特點(diǎn),本文將客戶分為時(shí)間敏感型和時(shí)間延遲型兩類,把集中的配送需求分散化,既能滿足敏感型客戶對(duì)配送時(shí)間的要求,又能控制總成本的增加。同時(shí),構(gòu)建了井噴需求場(chǎng)景的多周期多車程車輛路徑優(yōu)化模型,并通過數(shù)值實(shí)驗(yàn)與最小成本、最短時(shí)間目標(biāo)路徑模型進(jìn)行對(duì)比。
本文問題可以用圖G=(N,A)描述,其中N表示節(jié)點(diǎn)的集合,i或j表示節(jié)點(diǎn)編號(hào),包括1個(gè)配送中心和n-1個(gè)末端網(wǎng)點(diǎn),A={(i,j|i∈N,j∈N)} 為弧的集合。用K表示配送中心的車輛集合,在一定周期內(nèi)配送完Q個(gè)商品。在單位周期的工作時(shí)間Dk內(nèi)車輛多次往返配送中心和網(wǎng)點(diǎn)之間,用T表示周期數(shù),h表示車輛配送車次,用sikhT表示在第T個(gè)單位周期內(nèi)車輛k第h次配送過程到達(dá)節(jié)點(diǎn)i的時(shí)間,在第一個(gè)單位周期內(nèi)車輛k第一次從配送中心出發(fā)的時(shí)間sik11=0;tij表示從網(wǎng)點(diǎn)i到j(luò)的行駛時(shí)間。車輛不允許超載,最大載量均為q。單位周期內(nèi)車輛加班時(shí)間為tkT,單位時(shí)間加班成本為ck,末端網(wǎng)點(diǎn)i的商品單數(shù)為Qi,gikhT表示在第T個(gè)單位周期內(nèi)車輛k第h次配送到網(wǎng)點(diǎn)i的商品數(shù)量。
決策變量:
xijkhT:第T個(gè)周期內(nèi)車輛k第h次配送從網(wǎng)點(diǎn)i行駛至j時(shí)為1,否則為0;
yikhT:第T個(gè)周期內(nèi)點(diǎn)i的商品配送任務(wù)由車輛k第h次配送時(shí)完成為1,否則為0。
本文提出一種客戶分流策略并建立多周期多車程車輛路徑優(yōu)化模型,同時(shí)建立以最小成本和最短時(shí)間為目標(biāo)的多周期多車程車輛路徑優(yōu)化模型進(jìn)行對(duì)比,下面展開介紹三種模型的構(gòu)造過程。
客戶分流策略根據(jù)客戶時(shí)間敏感度的不同,將客戶分為時(shí)間敏感型和時(shí)間延遲型。時(shí)間敏感型客戶對(duì)配送時(shí)間要求高,電商物流配送服務(wù)必須在其期望時(shí)間范圍內(nèi)完成商品配送;時(shí)間延遲型客戶愿意接受超出一定時(shí)間范圍的延遲配送服務(wù),因此需要對(duì)其給予一定程度的補(bǔ)償。如圖1所示,車輛優(yōu)先配送三個(gè)有敏感型客戶商品的網(wǎng)點(diǎn),然后再配送其余只有延遲型客戶商品的網(wǎng)點(diǎn)。
圖1 客戶分流策略下單位周期內(nèi)車輛k配送示意圖
其中將所有節(jié)點(diǎn)集合N分為0、N+和N-三個(gè)部分,0代表配送中心,N+代表網(wǎng)點(diǎn)(敏感型客戶),N-代表網(wǎng)點(diǎn)(延遲型客戶),車輛單位距離運(yùn)輸成本為cij,延遲配送商品的單位補(bǔ)償成本為b,末端網(wǎng)點(diǎn)i需要的商品商品數(shù)為Qi。
根據(jù)以上問題的描述和界定,客戶分流策略的車輛路徑優(yōu)化模型建立如下:
(1)
(2)
式(2)表示單位周期T內(nèi)配送中心單次出發(fā)車輛數(shù)至多有K輛。
(3)
式(3)表示車輛不允許超載。
(4)
式(4)表示車輛每次從配送中心出發(fā)并返回配送中心。
(5)
式(5)表示所有網(wǎng)點(diǎn)商品都被配送。
?k∈K,T=1,2,…
(6)
式(6)表示某一車輛駛出點(diǎn)必是該車輛駛?cè)朦c(diǎn)。
(7)
式(7)表示單位周期T內(nèi)車輛k第h次和第h-1次配送行駛時(shí)間的連續(xù)性。
(8)
式(8)表示單位周期T內(nèi)車輛第h次配送到末端網(wǎng)點(diǎn)j的時(shí)間。
先說學(xué)術(shù)權(quán)力行政化。我國(guó)社會(huì)的“官本位”意識(shí)濃厚,這種“官本位”觀念也滲透到了高校的學(xué)術(shù)管理中,影響到了學(xué)術(shù)管理中的行政權(quán)力的正當(dāng)行使。在學(xué)術(shù)管理中,許多行政人員唯官是從,習(xí)慣于按照官的指示辦事,而很少考慮學(xué)術(shù)發(fā)展的客觀規(guī)律。隨之而來的是服務(wù)意識(shí)淡薄,行政人員自身定位不準(zhǔn),對(duì)學(xué)術(shù)管理中學(xué)術(shù)人員應(yīng)有的主體地位和學(xué)術(shù)權(quán)力的主導(dǎo)地位認(rèn)識(shí)有限,服務(wù)不到位。各種委員會(huì)的設(shè)置缺乏明確的章程,任務(wù)不明,職責(zé)不清,這說明我國(guó)許多高校的學(xué)術(shù)機(jī)構(gòu)在人員構(gòu)成上具有明顯的行政化傾向。
s0khT+UkM≤Dk?h∈H,?k∈K,T=1,2,…
(9)
(10)
式(9)和式(10)表示車輛k單位周期工作時(shí)間限制,若第h+1次配送時(shí)間超出工作時(shí)間限制,則第h次配送回到配送中心后停止工作。
?i∈N+,?h∈H,?k∈K
(11)
式(11)表示時(shí)間敏感型客戶的商品要求在一定時(shí)間內(nèi)送至末端網(wǎng)點(diǎn)。
sjkhT≤sikhT?i∈N-,?j∈N+,?h∈H,?k∈K
(12)
式(12)表示時(shí)間敏感型客戶商品配送結(jié)束后開始送延遲型客戶的商品。
為了對(duì)比客戶分流策略下配送時(shí)效性,本文構(gòu)建常規(guī)配送方式下以最小成本為目標(biāo)的車輛路徑模型,如圖2所示該車輛路徑模型選擇的是路徑成本最低的配送方案,網(wǎng)點(diǎn)間的配送順序沒有優(yōu)先級(jí)。
圖2 最小成本策略下單位周期內(nèi)車輛k配送示意圖
故最小成本目標(biāo)的車輛路徑模型目標(biāo)函數(shù)為:
(13)
式(13)計(jì)算了所有周期內(nèi)全部車輛的運(yùn)輸成本之和,該模型的約束條件取式(2)-式(10)。
圖3 最短時(shí)間策略下單位周期內(nèi)車輛k配送示意圖
Tdeadline為所有客戶允許的最晚收貨周期,在Tdeadline結(jié)束前電商物流部門必須將商品全部送達(dá),最短時(shí)間目標(biāo)的車輛路徑優(yōu)化模型目標(biāo)函數(shù)為:
(14)
該模型約束條件取式(2)-式(8),并在此基礎(chǔ)上增加如下約束:
s0khT+UkM≤Dk+tkT?h∈H,?k∈K,T=1,2,…
(15)
(16)
?j∈N,?h∈H,?k∈K
(17)
式(14)為模型的成本目標(biāo)函數(shù),計(jì)算了所有周期內(nèi)所有車輛運(yùn)輸成本和加班成本的和;式(15)和式(16)表示每天車輛工作時(shí)間限制, 當(dāng)車輛k第h+1次配送時(shí)間超出當(dāng)天工作時(shí)間,則在第h次配送結(jié)束回到配送中心后停止工作;式(17)表示最后一個(gè)回到配送中心的車輛所花費(fèi)的所有時(shí)間不超過Tdeadline與單位周期內(nèi)總的工作時(shí)間Dk+tkT的積。
根據(jù)上文可知,該問題是多車程的車輛路徑優(yōu)化問題,屬于NP難問題,適合使用啟發(fā)式算法求解。在各類啟發(fā)式算法中,遺傳算法的優(yōu)點(diǎn)是有很強(qiáng)的魯棒性和全局搜索能力,適合求解復(fù)雜多極值優(yōu)化和組合問題。
目前遺傳算法主要有基于行駛路徑編碼方式和基于需求點(diǎn)編碼方式兩種,這兩種編碼方式只適合單次車程的車輛路徑優(yōu)化。根據(jù)研究問題中車輛多次從配送中心出發(fā)并返回的特點(diǎn),而且存在時(shí)間敏感型客戶商品和時(shí)間延遲型客戶商品的區(qū)分,本文提出一種新的染色體表示方式——基于車輛和需求點(diǎn)分類的混合編碼方式。
將所有節(jié)點(diǎn)編為一條大的TSP路徑進(jìn)行編碼,在網(wǎng)點(diǎn)編碼后加入配送中心編碼,然后在所有節(jié)點(diǎn)編碼后加入車輛編碼,用于切割大TSP路徑。用配送中心編碼、末端網(wǎng)點(diǎn)編碼和車輛編碼三部分構(gòu)成每條染色體。其中客戶分流策略中,編碼構(gòu)成為配送中心編碼+網(wǎng)點(diǎn)(敏感型客戶)編碼+網(wǎng)點(diǎn)(延遲型客戶)編碼+配送中心編碼+車輛編碼,表示為:(1) 網(wǎng)點(diǎn)(敏感型客戶)編碼1,2,…,N1;網(wǎng)點(diǎn)(延遲型客戶)編碼N1+1,N1+2,…,N;配送中心編碼為0。(2) 車輛編碼N+1,N+2,…,N+K。旅行商路徑切割流程如下:
步驟1:按節(jié)點(diǎn)編碼順序從左到右累計(jì)網(wǎng)點(diǎn)編碼,直到超過車輛負(fù)載q的前一個(gè)編碼,將這些網(wǎng)點(diǎn)加入到第一輛車輛行駛計(jì)劃中,依次類推直到所有車輛都有任務(wù)。
步驟2:若有剩余末端網(wǎng)點(diǎn)沒有分配到車輛行駛計(jì)劃中,則重復(fù)步驟1,直到所有末端網(wǎng)點(diǎn)編碼都有對(duì)應(yīng)的車輛編碼。
適應(yīng)度用于評(píng)價(jià)每個(gè)配送方案的優(yōu)劣程度,每個(gè)配送方案可以用一個(gè)染色體來表示,染色體適應(yīng)度越大,該方案被選擇的幾率也越大。
令目標(biāo)函數(shù)倒數(shù)為適應(yīng)度函數(shù),zi表示第i條染色體對(duì)應(yīng)的目標(biāo)函數(shù),該染色體的適應(yīng)度為fi=1/zi。判斷染色體是否滿足約束條件,滿足則保留,反之則舍棄;將適應(yīng)度f(wàn)i≥favg的染色體保留到子代;對(duì)全部染色體進(jìn)行交叉和變異操作,按適應(yīng)度大小再選出N-L條染色體,與保留的L條染色體組合構(gòu)成下一代種群。
每代種群個(gè)體以交叉概率交叉重組,pc表示染色體個(gè)體i1和i2的交叉概率,pavg表示基礎(chǔ)概率,pmax表示適應(yīng)度值大于平均值的染色體個(gè)體交叉概率,f表示i1和i2中適應(yīng)度值大的個(gè)體適應(yīng)度值,favg表示平均適應(yīng)度值,fmax表示最大適應(yīng)度值。交叉概率公示為:
采用兩點(diǎn)交叉算法,隨機(jī)在染色體個(gè)體編碼串中設(shè)置了兩個(gè)交叉點(diǎn),兩點(diǎn)之間區(qū)域?yàn)槠ヅ鋮^(qū)域,并在[0,1]之間產(chǎn)生一個(gè)隨機(jī)數(shù)r,若pc≥r,則進(jìn)行交換部分基因,否則不交叉。其中,客戶分流配送策略編碼的兩條染色體在交叉區(qū)域的基因位對(duì)應(yīng)可能存在下列三種情形(見圖4),分別為:對(duì)應(yīng)基因位為“網(wǎng)點(diǎn)(敏感型客戶)編碼-網(wǎng)點(diǎn)(延遲型客戶)編碼”,如交叉區(qū)域[A,E]、[D,B],此時(shí)不進(jìn)行交叉;對(duì)應(yīng)基因位為“網(wǎng)點(diǎn)(敏感型客戶)編碼/網(wǎng)點(diǎn)(延遲型客戶)編碼-車輛編碼”,如交叉區(qū)域[A,F]、[B,F]、[D,C]、[E,C],此時(shí)也不能進(jìn)行交叉;對(duì)應(yīng)基因位為“網(wǎng)點(diǎn)(敏感型客戶)編碼-網(wǎng)點(diǎn)(敏感型客戶)編碼”、“網(wǎng)點(diǎn)(延遲型客戶)編碼-網(wǎng)點(diǎn)(延遲型客戶)編碼”、“車輛編碼-車輛編碼”,如交叉區(qū)域[A,D]、[B,E]、[C,F],此時(shí)采用部分匹配交叉的方式進(jìn)行交叉。
圖4 交叉區(qū)域基因位對(duì)應(yīng)情形圖
變異概率是染色體中某些基因改變的概率,pm表示染色體個(gè)體的變異概率,pmavg表示基礎(chǔ)變異概率,pmmax表示適應(yīng)度值大于平均值個(gè)體所采用的變異概率,fm表示個(gè)體i1的適應(yīng)度值,fmavg表示平均適應(yīng)度值,fmmax表示染色體個(gè)體中最大適應(yīng)度值。變異概率的公式為:
在[0,1]之間產(chǎn)生一個(gè)隨機(jī)數(shù)e,若pm 最后檢查交叉和變異產(chǎn)生的染色體是否滿足約束條件,不滿足則舍棄,反之則保留。 控制參數(shù)的選取不同,遺傳算法的收斂性就會(huì)有所改變,這些控制參數(shù)主要有種群的大小、終止代數(shù)、變異概率、交叉概率等。判斷是否達(dá)到停止進(jìn)化條件,如達(dá)到代數(shù)要求,則停止迭代,否則繼續(xù)迭代。 本文設(shè)置最大進(jìn)化代數(shù)作為判斷算法終止條件,當(dāng)算法迭代到MAX代時(shí)計(jì)算終止,此時(shí)選擇適應(yīng)度值最大的染色體對(duì)應(yīng)的路徑集合作為最優(yōu)解。 為了驗(yàn)證本文改進(jìn)的遺傳算法的有效性和優(yōu)越性,針對(duì)Solomn算例庫(kù)中RC110算例分別采用基本遺傳算法和改進(jìn)的遺傳算法模擬仿真求解10次進(jìn)行比較,10次運(yùn)算的平均結(jié)果如表1所示。 表1 算法運(yùn)行性能比較 由表1可以看出,針對(duì)求解多車程多周期車輛路徑問題,改進(jìn)遺傳算法在收斂最優(yōu)解次數(shù)和計(jì)算時(shí)間方面均優(yōu)于基本遺傳算法,顯示出良好的穩(wěn)定性和尋優(yōu)性能,同時(shí)在計(jì)算效率方面也有所提升。 本文設(shè)計(jì)的改進(jìn)遺傳算法與基本遺傳算法的迭代收斂情況比較如圖5所示,圖中虛線顯示了基本遺傳算法求解過程的收斂情況,實(shí)線顯示了改進(jìn)遺傳算法求解過程的收斂情況。由圖5可知,改進(jìn)遺傳算法具有更好的收斂性。 圖5 兩種遺傳算法的迭代收斂圖 本文以Solomn算例庫(kù)中20個(gè)算例數(shù)據(jù)為基礎(chǔ)進(jìn)行擴(kuò)建,構(gòu)建1個(gè)配送中心與100個(gè)網(wǎng)點(diǎn)的電商促銷下商品配送的算例并進(jìn)行仿真實(shí)驗(yàn),最后比較三種策略在成本和配送時(shí)效性方面的優(yōu)化結(jié)果。 配送中心有待處理商品60 000單,擁有10輛車載能力為500單的貨車,單位距離運(yùn)輸成本1元,單位周期是1天,車輛單位周期工作時(shí)間為12 h。最短時(shí)間目標(biāo)下車輛加班時(shí)間為6 h,加班成本為25元/h,要求48小時(shí)內(nèi)配送完商品。客戶分流策略下隨機(jī)選取時(shí)間敏感型客戶商品16 413單,延遲型客戶商品43 587單,延遲型客戶商品每單補(bǔ)償0.1元。 本文實(shí)驗(yàn)數(shù)據(jù)中設(shè)置1個(gè)配送中心(用坐標(biāo)源點(diǎn)表示配送中心,序號(hào)為0)和100個(gè)末端網(wǎng)點(diǎn),本文限于篇幅,僅展示100個(gè)網(wǎng)點(diǎn)中前20個(gè)網(wǎng)點(diǎn)的數(shù)據(jù),如表2所示,其中X、Y表示網(wǎng)點(diǎn)坐標(biāo),R表示各網(wǎng)點(diǎn)商品的總需求量。 表2 測(cè)試算例相關(guān)數(shù)據(jù)信息 結(jié)合算例規(guī)模,設(shè)定算法參數(shù)如下:種群規(guī)模為100,迭代次數(shù)為200次,交叉概率Px=0.7,變異概率Pm=0.05。使用MATLABR2014a運(yùn)行遺傳算法。 實(shí)驗(yàn)結(jié)果顯示,以最小成本為目標(biāo)的常規(guī)配送模式總成本為36 038.66元。該實(shí)驗(yàn)數(shù)據(jù)包括10輛車4天內(nèi)的行駛路徑,限于篇幅本文展示其中部分車輛的路徑情況(下文模型路徑結(jié)果也只進(jìn)行部分展示),如表3所示。 表3 最小成本配送策略的部分車輛路徑安排 以最短時(shí)間為目標(biāo)的常規(guī)配送模式總成本為46 523.39元,部分車輛路徑安排情況如表4所示。 表4 最短時(shí)間配送策略下部分車輛路徑安排 客戶分流配送策略下總成本為41 550.23元。該策略下部分車輛路徑安排情況如表5所示。其中車輛在第四天完成所有配送任務(wù),超出最晚配送周期2天,但車輛在敏感型客戶允許的最晚配送周期前完成對(duì)其的配送任務(wù),如車輛1在第2天完成所有敏感型客戶商品的配送任務(wù),車輛2在第一天完成所有敏感型客戶商品的配送任務(wù)。 表5 客戶分流策略下部分車輛路徑安排 為了分析三種配送模型在成本與時(shí)效性方面的優(yōu)劣性,本文比較了它們的最優(yōu)解,結(jié)果如表6和表7所示。 表6 實(shí)驗(yàn)結(jié)果對(duì)比分析 表7 三種策略成本對(duì)比分析 從表6中可以看出,客戶分流策略總成本比最短時(shí)間配送模式總成本減少4 973.16元,減少約10.7%,但滿足時(shí)效性的商品比例與最短時(shí)間配送模式相同為100%。客戶分流策略總成本比最小成本目標(biāo)總成本增加5 511.57元,增加了約15.3%,但滿足時(shí)效性的商品比例比最小成本配送模式增加了36.7%。 由表7可知,客戶分流策略與最短時(shí)間配送模式相比,運(yùn)輸成本減少量約占總成本減少量的84.5%;客戶分流策略與最小成本配送模式相比,運(yùn)輸成本增加量約占總成本增加量的50.5%;客戶分流策略的補(bǔ)償成本與最短時(shí)間配送模式的加班成本相比減少約22%。 可以看出,與最短時(shí)間配送模式相比,客戶分流策略按照客戶商品優(yōu)先級(jí)配送,把集中的配送需求分散化,減少了單位周期內(nèi)車輛的工作時(shí)間和配送車次,從而減少運(yùn)輸成本,節(jié)約加班成本。并且,客戶分流策略可以根據(jù)節(jié)省的加班成本給予時(shí)間償延遲型客戶一定程度的補(bǔ)償,這樣既能使敏感型客戶商品的時(shí)效滿足率達(dá)到100%,同時(shí)也盡可能地減少延遲型客戶的抱怨,降低退貨的概率。與最小成本配送模式相比,客戶分流策略提高了滿足時(shí)效性的商品比例,并有效控制了成本的增幅。 本文考慮成本和客戶時(shí)間敏感度對(duì)配送過程的影響,基于客戶分流配送策略,建立了更加符合大規(guī)模需求場(chǎng)景的多周期多車程車輛路徑優(yōu)化模型,通過算例驗(yàn)證了三種配送方式的優(yōu)缺點(diǎn)。未來,在本文的基礎(chǔ)上,可以進(jìn)一步深化研究的方向有需求井噴場(chǎng)景下多車場(chǎng)多車型的配送問題,還可以通過加入不同貨物交付方式,結(jié)合配送中心到網(wǎng)點(diǎn)的配送環(huán)節(jié)進(jìn)行聯(lián)合優(yōu)化。2.4 控制參數(shù)以及確定循環(huán)終止條件
2.5 算法性能分析
3 實(shí)驗(yàn)結(jié)果與分析
3.1 算例構(gòu)建
3.2 實(shí)驗(yàn)結(jié)果
4 結(jié) 語(yǔ)