多類包裹協(xié)同配送下的城市物流選址-路徑問題研究

趙泉午 張會芳 譚克維

(1.重慶大學 經(jīng)濟與工商管理學院, 重慶 400030; 2.重慶大學 現(xiàn)代物流重慶市重點實驗室, 重慶 400030)

0 引言

隨著現(xiàn)代物流網(wǎng)絡的逐步完善,物流配送品類越來越多,由信函、日用品、電子產(chǎn)品逐步覆蓋到家電家居等大件商品。物流包裹的形狀和重量等發(fā)生變化,城市物流企業(yè)主要將其分為大件包裹和標準包裹。大件包裹,又稱重貨包裹,指重量或體積超過一定閾值的包裹。根據(jù)易觀《中國大件白皮書2018》,2025年大件市場規(guī)模將達到4100億元。典型大件包裹包括面向終端消費者的家電家居等電商大件、面向線下各類實體門店的補貨大件以及面向搬遷群體的搬家大件。海爾日日順、蘇寧物流等是較早涉足大件物流的自營物流企業(yè),德邦、安能、遠成等是較早涉足大件物流的第三方物流企業(yè)。隨著電商大件需求的快速增長,以順豐、中通、韻達為代表的快遞企業(yè)紛紛進入大件物流領域。目前業(yè)內(nèi)對大件包裹的閾值并沒有統(tǒng)一標準,不同企業(yè)之間存在差異。德邦和安能等快運企業(yè)的閾值較低,如德邦閾值為3kg,安能物流閾值為5kg;順豐和韻達等快遞企業(yè)閾值較高,如中通快運閾值為10kg,順豐速運重貨包裹閾值為20kg以及韻達電商大件閾值為30kg。大件包裹閾值設置影響城市物流選址和路徑規(guī)劃。

典型城市物流網(wǎng)絡包括位于城市邊緣的分撥中心、城區(qū)內(nèi)的中轉中心和分散在城區(qū)的末端需求點。即日達、次日達、隔日達等標準產(chǎn)品,規(guī)格標準,重量和體積較小,磨損率低,對分揀設施、搬運工具和物流場地等要求較低;而大件包裹的體積或重量較大,且包裝形狀不規(guī)則,包裹價值較高,易磨損,對分揀設施、搬運工具和物流場地等要求較高。大件包裹中轉中心和標準快遞包裹中轉中心在容量配置、分揀設施和搬運裝卸工具方面存在明顯差異。大件和標準包裹中轉中心選址同樣影響城市物流選址和路徑規(guī)劃。

當前城市物流企業(yè)對標準包裹和大件包裹主要采用分網(wǎng)獨立配送策略(獨立配送模式),資源利用率低,配送成本高,多類包裹協(xié)同配送是綜合型物流企業(yè)解決城市配送的有效策略。協(xié)同配送指集中調度物流設施、中轉中心、末端網(wǎng)點、配送車輛和一線員工等物流資源,滿足多類物流包裹的攬收及派送需求。根據(jù)各類包裹需求特征,聯(lián)合優(yōu)化大件包裹閾值設置、中轉中心選址和末端需求點分配(中轉中心覆蓋范圍)是實施協(xié)同配送的關鍵。

論文研究城市物流企業(yè)實施多產(chǎn)品(包裹)協(xié)同配送下大件包裹閾值設置、多功能中轉中心選址以及末端需求點分配的聯(lián)合優(yōu)化問題,是城市物流選址-路徑問題的新拓展。經(jīng)典選址-路徑問題是在末端需求點需求量及位置、中轉中心等設施備選集合給定下,以整個物流系統(tǒng)總成本最小為目標,研究戰(zhàn)略層面的設施選址和末端需求點分配,以及運營層面的設施到末端需求點配送路徑的聯(lián)合優(yōu)化決策問題。Maranzana最早對該問題進行了研究[1];近年來大量文獻對選址-路徑問題進行了深入拓展研究,如考慮設施容量限制(Laporte等[2],Schwengerer等[3]和Boccia等[4])、多車型影響(Winkenbach等[5]和Zhao等[6])、時間窗(Nikbakhsh等[7]、Govindan等[8]和劉必爭等[9])、庫存成本(Hiassat等[10]、 Zhalechian等[11]和戢守峰等[12])、碳排放(Ko?等[13]、唐金環(huán)等[14]和常征等[15])、兩層及多層選址-路徑問題(Govindan等[16]、Dondo等[17]、Zhuo等[18]、鄭稱德等[19]和張會芳[20])等。Prodhon等[21], Schneider[22]以及 Cuda等[23]對該問題進行了詳細綜述。

但遺憾的是,選址-路徑問題相關文獻大多基于單產(chǎn)品場景,較少文獻研究多產(chǎn)品場景。經(jīng)典多產(chǎn)品選址-路徑問題解決不同需求點產(chǎn)品需求和不同供應點產(chǎn)品供應均存在差異下,聯(lián)合優(yōu)化中轉中心選址、供應點及需求點分配、以及車輛訪問供應點和需求點的路徑規(guī)劃等問題。Rieck等基于木材加工行業(yè)供應點和需求點可以采用直接配送模式或中轉分撥模式(軸輻式網(wǎng)絡)的現(xiàn)實,允許中轉中心間轉運,對中轉中心數(shù)量、位置以及服務產(chǎn)品種類、服務的供應點和需求點聯(lián)合優(yōu)化問題進行了研究[24]。Winkenbach等考慮包裹大小差異,給定包裹規(guī)格劃分的閾值,基于大型包裹采用兩級物流網(wǎng)絡配送、小型包裹采用三級物流網(wǎng)絡配送,構建了兩種快遞包裹下考慮車型選擇和設施容量約束的選址-路徑集成優(yōu)化模型,并提出末端配送成本近似估計公式 (Augmented Routing Cost Estimation Formula,ARCE) 簡化模型計算,最后以法國兩個典型城市的郵政包裹為例,驗證了模型及算法的有效性[5]。Giannessi等在不同城市物流門戶(樞紐)負責單一產(chǎn)品的流入和流出,不同產(chǎn)品通過環(huán)形連接的中轉中心間轉運,末端需求點的配送和攬收由相應中轉中心完成的城市物流場景下,研究了中轉中心選址、末端需求點和車輛補給站路徑規(guī)劃的聯(lián)合決策問題,該文的取貨和送貨是獨立運行的,并未實現(xiàn)取送貨一體化[25]。Younes等集成考慮多產(chǎn)品、攬收派送一體化和中轉中心轉運,采用聚類分析方法簡化路徑規(guī)劃問題,研究末端需求點需要多個中轉中心服務下的多產(chǎn)品配送一體化的選址-路徑集成優(yōu)化問題[26]。Boccia等考慮多類型產(chǎn)品(或包裹)流經(jīng)的市內(nèi)中轉中心存在差異,以某類產(chǎn)品(或包裹)市內(nèi)配送過程中經(jīng)過的部分站點作為該產(chǎn)品(或包裹)的候選中轉中心,產(chǎn)品(或包裹)配送起點到中轉中心采用直接配送模式,中轉中心到末端需求點采用循環(huán)配送模式 (Milk Run) ,采用流量截取方法 (Flow Intercepting Approach) 構建線性整數(shù)規(guī)劃模型,并設計分支-切割法求解模型,環(huán)形、半環(huán)形以及網(wǎng)格狀3種網(wǎng)絡拓撲結構的運算結果驗證了該文模型及方法的有效性[27]。

綜上,現(xiàn)有多產(chǎn)品選址-路徑問題的研究假定產(chǎn)品品類外生。而現(xiàn)實中城市物流企業(yè)的包裹品類是根據(jù)市場競爭情況及物流成本進行優(yōu)化調整的,可以設置重量或體積閾值劃分包裹品類。此外,現(xiàn)有研究多根據(jù)需求及供應的時空分布特征進行研究,未考慮不同產(chǎn)品(包裹)在配送環(huán)節(jié)或攬收過程的差異,尚無綜合考慮不同包裹在搬運、分揀等處理環(huán)節(jié)相關設施配置需求及成本差異的研究。

本文基于大件包裹和標準包裹的城市配送實踐,考慮中轉中心容量約束,以及包裹在規(guī)格(重量或體積)、處理成本、設施配置等要求不同,構建了大件包裹和標準包裹協(xié)同配送下的大件包裹和標準包裹閾值設置、多功能中轉中心選址、以及末端需求點分配的聯(lián)合優(yōu)化模型,設計混合拉格朗日算法求解模型,并以SF重慶主城區(qū)核心區(qū)域為例,采用實際數(shù)據(jù)驗證本文模型及方法的有效性,并提出管理啟示和建議。

1 模型構建

1.1 問題描述

典型城市物流網(wǎng)絡包括城郊分撥中心、城區(qū)中轉中心以及接近客戶的末端需求點。城市分撥中心負責城市貨物(或包裹)的流入和流出;中轉中心連接分撥中心和末端需求點,負責中轉處理;末端需求點一般位于小區(qū)、學校、商圈等位置,負責片區(qū)內(nèi)包裹的派送和攬收。標準包裹和大件包裹協(xié)同配送時,按照功能差異,中轉中心可分為大件型中轉中心、標準型中轉中心和混合型中轉中心三類。

實踐中分撥中心和中轉中心間大多采用點對點的直接配送模式,中轉中心和末端需求點間采用循環(huán)配送模式。中轉中心到末端需求點,標準包裹和大件包裹獨立進行配送和攬收,圖1中末端需求點間的實線代表標準包裹行駛路線,末端需求點間的虛線代表大件包裹行駛路線。當末端需求點同時有標準包裹和大件包裹配送或攬收需求時,則需要被分開訪問2次,如圖1中的點a和點b。

圖1 標準包裹和大件包裹協(xié)同配送下的城市物流網(wǎng)絡Figure 1Urban logistics network under the coordinated distribution for standard and large items

城市物流企業(yè)實施多類包裹協(xié)同配送時面臨如下決策問題:

(1)大件包裹和標準包裹的閾值設置;

(2)大件型、標準型和混合型三類中轉中心的數(shù)量和位置;

(3)不同功能類型中轉中心的覆蓋范圍,即末端需求點分配。

1.2 模型構建

上述聯(lián)合優(yōu)化問題是有容量限制兩級選址-路徑問題的拓展,該問題是定義在一個完全加權有向網(wǎng)絡G=(V,A),其中V=(V0,V1)表示物流節(jié)點集合,V0表示城市分撥中心,V1=(M∪N),M和N分別表示中轉中心候選點的集合和末端需求點的集合?；〖螦定義為A=(A1∪A2),A1={(0,m):0∈V0,m∈M},A2={(i,j):i,j∈V1,i≠j,(i∪j)∩N≠?}。從城市分撥中心到中轉中心采用車型v1,中轉中心服務末端需求點的標準包裹和大件包裹分別采用車型v2和v3。

為構建聯(lián)合優(yōu)化模型,設置如下參數(shù)和決策變量:

模型參數(shù):

V0:城市分撥中心

M:中轉中心候選點集合;

N:末端需求點集合;

P:包裹類型集合;

fs:標準型中轉中心固定成本,如場地費用、分揀、裝卸及搬運配套設施成本等;

fL:大件型中轉中心固定成本,如場地費用、分揀、裝卸及搬運配套設施成本等;

fMIX:混合型中轉中心固定成本,如場地費用、分揀、裝卸及搬運配套設施成本等;

Qm:中轉中心候選點m的最大容量,用包裹個數(shù)表示,和包裹的大小有關,并隨著閾值的不同而相應變化,m∈M;

dom:城市分撥中心到備選中轉中心m的距離,m∈M;

cv1,cv2,cv3:分別表示車型v1/v2/v3的單位運輸成本;

capv1,capv2,capv3:分別表示車型v1/v2/v3的最大裝載能力,用包裹個數(shù)表示,對于同一車型,不同大件包裹閾值選擇下的包裹個數(shù)是不同的;

qp:p類型包裹的重量,對于體積較大的輕拋貨,轉化為體積重量測算;

Cs:標準包裹的單位處理成本,包括在中轉中心的搬運裝卸成本和分揀成本、末端需求點的裝卸成本等,主要取決于標準包裹的平均重量,受大件包裹閾值設置影響;

Cl:大件包裹的單位處理成本,包括在中轉中心的搬運裝卸成本和分揀成本、末端需求點的裝卸成本等,主要取決于大件包裹的平均重量,受大件包裹閾值設置影響;

K,g:分別表示生成標準包裹超級顧客、大件包裹超級顧客(算法部分涉及);

dmk,dmg:分別表示中轉中心m服務超級顧客k或g的往返距離,m∈M;

,,,:分別表示末端需求點標準包裹攬收和配送的總數(shù)量,大件包裹攬收和配送的總數(shù)量,不同大件包裹閾值選取下也是不同的;

,,,:分別表示組成標準包裹超級顧客k的所有末端需求點的攬收和配送的包裹數(shù)量、組成大件包裹超級顧客g的所有末端需求點的攬收和配送的包裹數(shù)量;

: 車輛v2從節(jié)點i到節(jié)點j裝載的標準包裹量,包括攬收和配送量,i,j∈V1,i≠j,(i∪j)∩N≠?;

: 車輛v3從節(jié)點i到節(jié)點j裝載的大件包裹量,包括攬收和配送量,i,j∈V1,i≠j,(i∪j)∩N≠?;

:表示由中轉中心m處理的標準包裹總投遞量,m∈M;

:表示由中轉中心m處理的標準包裹總攬收量,m∈M;

:表示由中轉中心m處理的大件包裹總投遞量,m∈M;

:表示由中轉中心m處理的大件包裹總攬收量,m∈M;

:表示車輛v2從中轉中心出發(fā),到達節(jié)點i時所使用的總時間;

:表示車輛v3從中轉中心出發(fā),到達節(jié)點i時所使用的總時間;

:車輛v2在節(jié)點i的服務停留時間以及從節(jié)點i到節(jié)點j的行駛時間;

:車輛v3在節(jié)點i的服務停留時間以及從節(jié)點i到節(jié)點j的行駛時間;

Tv2,Tv3:車輛v2,v3單個工作周期最大工作時間。工作周期和快遞企業(yè)集散頻次(攬投頻次)有關,每天總工作時長一定的情況下,單個工作周期時長隨著集散頻次增加而減少;

決策變量:

qa:閾值,即qp≥qa,則p類型包裹歸為大件,否則歸為標準包裹。

xtm:候選中轉中心m是否被選作t型中轉中心,其中t=1,2,3分別表示標準型中轉中心、大件型中轉中心以及混合型中轉中心,xtm∈{0,1},m∈M;

:節(jié)點i和節(jié)點j之間運輸標準包裹時,車輛v2經(jīng)過弧(i,j),(i,j)∈A2;

:節(jié)i和節(jié)點j之間運輸大件包裹時,車輛v3經(jīng)過弧(i,j),(i,j)∈A2;

：末端需求點i的大件包裹需求分配給中轉中心m來服務時為1,否則為0;

:末端需求點i的標準包裹需求分配給中轉中心m來服務時為1,否則為0;

ymk:標準包裹超級顧客k由中轉中心m來服務時為1,否則為0;

zmg:大件包裹超級顧客g由中轉中心m來服務時為1,否則為0;

由于末端需求點的布局取決于終端用戶郵寄及接收包裹的偏好、用戶密度以及競爭對手等因素,是外生變量,本文將其視為既定條件。此外,由于城市內(nèi)部的物流配送,不同于干線運輸,分撥中心和中轉中心、中轉中心和末端需求點間距離均有限,一般不超過100公里?？爝f企業(yè)城市配送常用車型如金杯車、依維柯、面包車等,不存在里程約束,時間約束是快遞企業(yè)考慮的關鍵因素。因此,論文采用時間約束而非車輛里程約束。

根據(jù)以上分析,構建如下混合整數(shù)規(guī)劃模型:

其中:

s.t.

目標函數(shù)(1)最小化物流總成本,包括開放中轉中心的固定成本、城市分撥中心到中轉中心的運輸成本、中轉中心到末端需求點的運輸成本、包裹的處理成本。約束條件(4) ~ (5)確保每個末端需求點的標準包裹和大件包裹在一個周期內(nèi)只被服務一次,且每個末端需求點的車輛駛入數(shù)量等于駛出車輛,都等于1。(6) ~ (7)表明任一路徑上的行駛時間不超過車輛單個工作周期內(nèi)的工作時間。(8) ~ (9) 確保服務末端需求點j時,車輛的剩余裝載量要大于本節(jié)點的待取件量。(10) ~ (11)確保在任一路徑上,車輛包裹裝載量不能超過其最大承載力。(12) ~ (13)確保從任一中轉中心發(fā)出的大件或標準包裹總投遞量分別等于分配給該中轉中心末端需求點的大件或標準包裹的待配送包裹量之和。(14) ~ (15)表明所有配送車輛返回中轉中心m,且其所裝載包裹量等于分配給該中轉中心的大件或標準包裹總攬收量。(16)保證分配給中轉中心m的包裹量不能超過其容量。(17)~(18)分別表示每個末端需求點的標準包裹或大件包裹分別有且僅有一個中轉中心為其服務。(19)~(22)保證所有路徑起點和終點為同一中轉中心,其中(21)~(22)表示如果節(jié)點i由中轉中心m服務,那么訪問i之后的下一節(jié)點j也必須由同一中轉中心m服務。(23) ~ (24)保證末端需求點的大件或標準包裹只能分配給相應開放的中轉中心。最后(25) ~ (27)保證變量的整數(shù)性和非負性。

2 求解算法

選址-路徑問題的求解算法可分為兩類。一是精確算法,如分支定界、分支定價、列生成以及切平面算法等(Contardo 等[28]和Santos等[29]),精確算法通常適用于中小規(guī)模問題;二是采用啟發(fā)式算法或元啟發(fā)式算法或混合啟發(fā)式算法,如禁忌搜索、貪婪算法、大規(guī)模領域算法、模擬退火、禁忌搜索、拉格朗日松弛等,該類算法適用于中等規(guī)模和較大規(guī)模問題(Vincent等[30],肖建華等[31]和Hemmelmayr等[32],Prins等[33])。此外,不少研究采用機器學習及統(tǒng)計分析等構建配送距離或配送成本的近似逼近模型,基于近似估算模型求解選址-路徑問題(如Winkenbach等[5],Zhao等[6])。該方法綜合考慮需求等相關因素的時空變化特征,在降低計算復雜度的同時能夠給出選址-路徑問題的穩(wěn)健解決方案,是解決選址-路徑問題有效方法?；谏鲜龇治?本文采用近似估算和拉格朗日松弛方法結合的混合算法求解模型。本文算法包括閾值設置(ThresholdSetting)、超級顧客群生成(Super-customerGeneration)、距離估算(DistanceEstimation)、中轉中心選址及末端需求點分配 (拉格朗日啟發(fā)式算法,Lagrangianrelaxation)等主要步驟,簡稱TSDL混合算法。以下詳細介紹算法各個步驟。

2.1 包裹閾值設置(Threshold Setting)

城市物流企業(yè)根據(jù)競爭對手現(xiàn)有服務產(chǎn)品,以及包裹重量、體積和時效性等特征,面向客戶提供不同包裹服務產(chǎn)品,如順豐的順豐即日、順豐標快、順豐次晨、物流普運等產(chǎn)品。同時物流企業(yè)根據(jù)不同包裹服務產(chǎn)品的要求,以物流系統(tǒng)總成本最小為目標,優(yōu)化設計多產(chǎn)品的物流運作模式和流程。本文根據(jù)包裹產(chǎn)品的重量分布(體積換算為對應重量),將區(qū)分大件包裹和標準包裹的閾值設置為有限離散數(shù)值,如3kg、5kg、10kg等,對閾值設置進行簡化處理。當閾值為3kg時,把小于3kg的包裹歸為標準包裹,大于等于3kg的包裹歸為大件包裹,其他依次類推。

2.2 超級顧客生成(Super-customer Generation)

根據(jù)末端需求點的標準包裹和大件包裹派送和攬收數(shù)量,采用Prins等[33]提出的最近鄰域法,將末端需求點分別按照標準包裹和大件包裹進行聚類,生成超級顧客群K和G。聚類同時考慮車輛容量以及車輛工作時間約束。生成超級顧客時,初始點選擇方法有隨機選取和最大選取(選取包裹量最大的點作為起始點)兩種,隨機選取能夠保證生成超級顧客的多樣性,大多論文采用隨機選取方法。具體就是在生成標準包裹超級顧客時,在末端需求點中隨機選取一個點作為起始點A,再找距離A最近點B,再找距離B最近點C,依次進行下去,直到再加入一個末端需求點時所有點的標準包裹量之和超過車輛最大裝載量或者所有點的車輛?？繒r間之和超過TS(車輛最長工作時間)時停止,此時所有點形成一個標準包裹超級客戶,之后再隨機選取剩余點中一個點作為起始點,按此方法進行,直到所有標準包裹末端需求點都組建成超級顧客。大件包裹超級顧客生成采用同樣的方法。采用車型v2服務標準包裹超級顧客k,車型v3服務大件包裹超級顧客g。需要說明的是,同時考慮取貨和配貨,在生成超級客戶的過程中,每個末端需求點的包裹量取待取包裹量和配送包裹量兩者中的最大值。

本文經(jīng)過多次循環(huán)迭代確定最終的超級顧客,采用平均距離作為評價超級顧客優(yōu)劣的指標,以標準包裹超級顧客k為例,平均距離定義如下:

其中Dk表示從超級顧客k內(nèi)的一個末端需求點出發(fā),訪問該超級顧客內(nèi)所有的需求點所經(jīng)過的距離,本文采用Beardwood等[34]提出的連續(xù)逼近法進行估算。n表示所有末端需求點的個數(shù)。選取最小的超級顧客。其中:

A為超級顧客k覆蓋面積,可通過Datamap獲取(或者通過找到超級顧客內(nèi)兩點間最大距離作為矩形對角線),nk為超級顧客k內(nèi)的末端需求點的個數(shù)。

2.3 距離估算(Distance Estimation)

根據(jù)Beardwood等[34]提出的連續(xù)逼近法,基于網(wǎng)點分布的空間密度來測算配送車輛的行駛距離。則中轉中心m服務標準包裹超級顧客k的配送距離近似估算公式如下:

其中,r代表中轉中心到超級顧客的平均距離。同理,可求得dmg。

以生成的超級顧客代替原來的末端需求點,近似估算代替路徑規(guī)劃,則模型簡化為:

s.t:

式(32)表示中轉中心只能開放為一種類型的中轉中心或者不開放;(33) ~ (34)確保超級顧客只能分配給一個中轉中心;(35) ~ (36)保證超級顧客只能分配給開放的中轉中心;(37)保證分配給中轉中心m的包裹量不超過其最大容量;(38) ~ (40)表示參數(shù)的整數(shù)性和非負性。

2.4 拉格朗日啟發(fā)式算法(Lagrangian Relaxation)

拉格朗日啟發(fā)式算法由拉格朗日松弛、改進下界解以及次梯度優(yōu)化算法三個步驟組成。在拉格朗日松弛階段,將重要的約束條件進行松弛得到下界解(LB),下界解(LB)中可能違背約束條件,改進下界解得到上界解(UB)。次梯度算法通過循環(huán)調整拉格朗日乘子,使下界解和上界解逐步靠近。當?shù)螖?shù)達到一定數(shù)量或者上界解和下界解的差距滿足一定范圍,終止循環(huán)給出最終解。

求解過程中,首先分別研究標準包裹中轉中心和大件包裹中轉中心的開放方案,如果有中轉中心m同時開放為大件和標準包裹中轉中心,則將m開放為混合型中轉中心。據(jù)此進一步簡化模型為:

s.t:(33)~(40)

Step1:尋找下界

據(jù)Prins[33]的松弛方法,放松單一分配限制,令λk,k∈K,λk,∈R;μg,g∈G,μg∈R作為拉格朗日乘子,松弛后的拉格朗日對偶模型如下:

該線性規(guī)劃可被拆分為一個個獨立的子問題,每個子問題對應一個候選中轉中心m,子問題可表達為:

(1)當中轉中心開放為標準包裹中轉中心時,大件包裹的成本項Cm(μ)為0,則子問題簡化為:

當x1m=1時上述問題為背包問題,模型簡化為:

約束條件為:

給定λk的值,可用經(jīng)典動態(tài)規(guī)劃來解決背包問題。然后利用如下條件判斷中轉中心m是否開放為標準包裹中轉中心:

如果中轉中心m不開放,則令ymk=0,k∈K。

(2)當中轉中心m開放為大件包裹中轉中心時,標準包裹的成本項Cm(λ)=0,則子問題為:

若x2m=1時上述問題為背包問題,模型簡化為:

約束條件為:

同樣地,給定μg的值,可以用經(jīng)典動態(tài)規(guī)劃來解決背包問題。再用如下條件判斷中轉中心m是否開放為大件包裹中轉中心:

如果中轉中心m不開放,則ymg=0,g∈G。

Step2:尋找上界

分別用PDK和PDg表示超級顧客k、g對應中轉中心集合表示數(shù)量。根據(jù)PDK和PDg,可將超級顧客k、g分成三類。以標準包裹超級顧客k為例:表示沒有中轉中心為超級顧客k服務;,表示有且僅有一個中轉中心為超級顧客k服務;,表示有多個中轉中心為超級顧客k服務。同理劃分大件包裹超級顧客g。

對于第一種情況,把超級顧客k分配給PDk∩NS≠?中,cv2dmk-λk最小且有足夠容量剩余的中轉中心。對于第二種情況,選擇PDk∩NMIX中,cv2dmk-λk最小且有容量剩余的中轉中心m。第三種情況下,把PDk中,cv2dmk-λk最小的中轉點m加入NS型集合。對于第四種情況,則把超級顧客k分配給(PDK∩NS)∪(PDK∩NMIX)中有容量剩余且cv2dmk-λk最小的中轉中心m。對的大件包裹超級顧客g做同樣處理。

圖3 TSDL算法流程Figure 3Solution approach of the TSDL algorithm

Step3:次梯度優(yōu)化

在初始化拉格朗日乘子時,離中轉中心最近的需求點會被優(yōu)先考慮,故其表達式如下:

根據(jù)獲得的上界解和下界解,使用以下公式調整拉格朗日乘子。以λk為例:

θt是次梯度算法中第t次迭代的步長,根據(jù)Prins等[33],βt初始值設為1.5,當每三次連續(xù)迭代的結果沒有改善時,將其值減少為一半,當其值小于預先設定參數(shù)值或者上界解得到改進時,重設其初始值。當出現(xiàn)LB=UB或者‖dt‖=0時,次梯度優(yōu)化停止,此時中轉中心位置和超級顧客分配方案均已得到;或者當?shù)螖?shù)達到預先設定值時,次梯度優(yōu)化停止,此時得到的上界解為最終解。同理對μg進行相同的操作處理。

2.5 混合算法的有效性檢驗

為驗證本文算法的有效性,設計不同數(shù)據(jù)集,對比本文算法與CPLEX運行結果。結果如表1所示。

表1 本文算法與CPLEX結果對比Table 1Result comparison between the proposed algorithm and CPLEX

由表1可知本文算法與CPLEX相比,在運算結果差值不超過4%的前提下,在時間效率方面優(yōu)于CPLEX。特別是當末端需求點的數(shù)量超過15時,本文算法的時間效率明顯優(yōu)于CPLEX的時間效率,且能得到較好的運算結果。

3 實例分析

3.1 實例描述與結果分析

本文以SF重慶公司為例分析城市物流選址-路徑優(yōu)化問題。SF重慶公司城市物流網(wǎng)絡分為城市分撥中心、點部和末端需求點,點部等同于本文模型中的中轉中心。點部有3-50個配送員不等,配送員固定配送分區(qū),配送分區(qū)覆蓋若干末端需求點。末端需求點包括自營服務點、自提柜和外部合作點等類型。SF重慶公司在主城區(qū)目前有766個末端需求點,標準包裹中轉中心39個、大件包裹中轉中心16個、2個城市分撥中心,其中城市分撥中心分別負責空運和陸運。圖4 為SF重慶公司現(xiàn)有中轉中心布局圖。學校和住宅小區(qū)以標準包裹為主,工廠、工業(yè)園區(qū)和商圈以大件包裹為主。

圖4 SF重慶公司現(xiàn)有中轉中心分布圖Figure 4Current transfer center distribution of SF Chongqing company

SF重慶公司的車型包括依維柯、面包車、貨車以及電動三輪車、兩輪車。末端需求點分布的高度密集性以及較高的集散頻率,多采用小容量、機動性強的物流車型。城市分撥中心到中轉中心采用3.5噸貨車,中轉中心到末端需求點標準包裹選用電動三輪車配送,大件包裹選用面包車。根據(jù)SF重慶公司現(xiàn)有的點部和潛在的可選點,生成144個中轉中心候選點,采集766個末端需求點的派送和攬收包裹量,節(jié)點間距離通過Datamap獲得,相關參數(shù)設置如表2所示。

表2 SF重慶的參數(shù)設置Table 2Parameter setting of SF Chongqing

根據(jù)上表數(shù)據(jù),本文采用Python 3.7.3編程語言實現(xiàn)上述混合算法,運行平臺為:AMD,A8-7650K,Radeon,R7,10Compute Cores 4C+6 G@3.3 GHZ, Win10 PC。本文提出TSDL混合算法,得到各個閾值下的三種中轉中心開放方案以及成本情況(見表3)。

表3 協(xié)同配送模式下的優(yōu)化結果Table 3Result of optimization under collaborative delivery

圖5為SF重慶公司優(yōu)化后的中轉中心布局圖。優(yōu)化方案的閾值為10kg,不同于和SF重慶公司現(xiàn)有20kg的閾值。優(yōu)化方案共開放41個中轉中心,其中混合型13個、標準型25個、大件型3個。優(yōu)化方案總成本為86996.01元,包裹單均成本為4.61元,和SF現(xiàn)有城市物流網(wǎng)絡相比,物流總成本和單均成本均降低6.5%。

圖5 SF重慶公司優(yōu)化后的中轉中心分布示意圖Figure 5Optimized transfer center distribution of SF Chongqing company

3.2 獨立配送和協(xié)同配送對比分析

獨立配送指多類包裹分網(wǎng)獨立配送,各類包裹之間的派送和攬收是分離的。協(xié)同配送指集中調度物流設施、中轉中心、末端網(wǎng)點、配送車輛和一線員工等物流資源,滿足多類物流包裹的攬收及派送需求。理論上協(xié)同配送能夠通過共享城市物流資源,降低物流成本,提高物流運作效率。以下通過SF重慶公司現(xiàn)有數(shù)據(jù),對兩種配送模式進行對比分析,見表4。

表4 協(xié)同配送和獨立配送成本對比表Table 4Cost comparison of collaborative delivery and independent delivery

SF重慶公司選取不同大件閾值時,協(xié)同配送下的固定成本以及運輸成本均低于獨立配送,總成本相應降低,總成本節(jié)約最高達17.2%。協(xié)同配送下大件包裹和標準包裹在混合型中轉中心實現(xiàn)分揀設施和場地的共享,以及分撥中心到混合型中轉中心車輛共享,對大件包裹和標準包裹實施協(xié)同配送,配送次數(shù)減少,裝載率提高,運輸成本降低。當大件閾值為10kg時,協(xié)同配送總成本從105097.58元降低到86996.01元,單均包裹成本從5.56元降到4.61元。

值得注意的是,協(xié)同配送的運營組織難度大于獨立配送,對企業(yè)管理水平和信息系統(tǒng)等要求更高;此外不同類型包裹配送時效也會影響協(xié)同配送成本。因此城市物流企業(yè)實施協(xié)同配送需要根據(jù)自身需求及狀況進行綜合評估。

3.3 包裹派送及攬收量影響分析

包裹派送及攬收量包括數(shù)量規(guī)模和結構分布兩個方面:數(shù)量規(guī)模指在不改變各類包裹派送及攬收比例,增減包裹總數(shù)量;結構分布指改變各類包裹派送及攬收占比。針對本文研究,數(shù)量規(guī)模指不改變6類包裹的派送及攬收比例,結構分布指改變本文6類包裹的派送及攬收占比。本文設計以下4個實驗分析包裹派送及攬收量變動對協(xié)同配送模式的影響,驗證本文設計物流網(wǎng)絡的穩(wěn)健性。

表5 派送及攬收包裹量變動實驗設計Table 5Experimental design for the volume change of packages delivered and received

實驗1用來模擬包裹業(yè)務結構接近、包裹量更大的城市物流企業(yè)。當各類包裹攬收及派送量整數(shù)倍增加時,中轉中心容量及固定成本同比例增加。由表6可知,包裹派送及攬收量對大件閾值及中轉中心開放方案沒有顯著影響。包裹派送及攬收量越大,單個包裹平均成本越低,符合規(guī)模經(jīng)濟原理,也符合SF重慶公司現(xiàn)實。

表6 實驗1中轉中心開放方案對比Table 6Comparison of open schemes of transfer center in experiment 1

實驗2用來模擬末端需求點包裹派送及攬收量的日常隨機變動。運算結果表明對大件閾值及中轉中心開放方案沒有顯著影響,且單個包裹的平均成本變化不顯著,如圖6所示。說明本文模型和算法給出優(yōu)化方案具有穩(wěn)健性,能夠應對日常需求變動。綜合實驗1和實驗2,本文模型和算法給出優(yōu)化方案具有穩(wěn)健性,既能滿足不同規(guī)模城市物流企業(yè)需求,又能適用同類型城市物流企業(yè)包裹派送及攬收量日常波動的情形。

圖6 實驗2中單均成本變動Figure 6Average unit cost change in experiment 2

實驗3來模擬多類包裹派送及攬收比例差異較大的城市物流企業(yè)。分別將10kg及20kg以上的包裹派送及攬收量分別增至10倍和20倍。由表7可見,多類包裹派送及攬收比例會影響大件閾值設置。經(jīng)營多類包裹的城市物流企業(yè),大件閾值的選擇沒有固定標準,城市物流企業(yè)需要根據(jù)包裹派送及攬收結構分布,綜合考慮相關因素,合理選擇大件閾值。

表7 實驗3中轉中心開放方案對比Table 7Comparison of open schemes of transfer center in experiment 3

實驗4模擬大件包裹增長對物流成本的影響,適用于進入大件物流領域的快遞企業(yè)。進入大件物流的快遞企業(yè),標準包裹市場規(guī)模穩(wěn)步增長,大件包裹快速增長。由于大件包裹派送及攬收需求集中在工業(yè)園區(qū)、商圈及學校,實驗4增加以上各類末端需求點10kg以上的大件包裹派送及攬收量,同時相應增加大件包裹車輛容量及單位運輸成本,模擬進入大件物流領域快遞企業(yè)的現(xiàn)實狀況,運算結果如表8所示。

表8 實驗4中轉中心開放方案及相關成本Table 8Open scheme of transfer center and related costs in experiment 4

當各類末端需求點10kg以上的大件包裹派送及攬收量增加到原來的2倍、4倍時,中轉中心開放方案是基本不變的,運輸成本和處理成本增加。當增加到原來的6倍、8倍、10倍時,大件包裹中轉中心開放數(shù)量增加,標準包裹中轉中心開放數(shù)量無明顯變化。對于進入大件物流領域的快遞企業(yè),在大件包裹增長的前期,可以通過增加大件車輛容量應對需求增加,但當需求增加至一定量時,還需要增設相應的中轉中心。此外大件包裹數(shù)量增加越多,單個包裹平均成本越高,原因在于大件包裹成本相對較高,與實踐吻合。

3.4 服務時效影響分析

服務時效指城市物流公司承諾的遞送時間;如蘇寧易購推出的急速達(2小時內(nèi)送達)、半日達、次日達等包裹服務。服務時效越短,城市物流企業(yè)單日內(nèi)需要進行集散處理的頻次越高,如間隔2個小時集散、間隔3個小時集散等。集散間隔時間越短,間隔內(nèi)的包裹派送和攬收量越少。根據(jù)本文模型和算法,包裹派送和攬收量決定超級顧客的生成,進而影響運輸成本、固定成本、處理成本以及物流總成本。以下對比分析集散間隔時間分別為2 h、3 h、4 h、6 h時的中轉中心開放方案以及日均物流成本。

由表9可知,集散間隔時間不影響閾值設置,包裹單均固定成本及處理成本沒有明顯改變,但單均運輸成本隨著集散間隔時間的增加而顯著降低,也就是說物流總成本下降主要是來自運輸成本的降低。當集散間隔時間由2小時增加到3小時,總成本降低20.8%,成本下降最為顯著。SF重慶公司為保證服務時效,每天集散頻次達到4次,在北上廣深等城市,甚至達到了7次或8次,遠高于同行業(yè)企業(yè)。較高的集散頻率使得單個集散批次的包裹派送及攬收量減少,不能充分發(fā)揮規(guī)模經(jīng)濟,中轉中心設施等物流資源利用率降低,單個包裹平均成本較高。

表9 不同集散間隔時間下的成本構成表Table 9Cost composition for various time intervals

由圖7可知,延長集散間隔時間,大件包裹車輛裝載率逐步提高,但標準包裹車輛裝載率沒有明顯變化,且維持在較高水平。表明SF重慶公司標準包裹業(yè)務已經(jīng)相當成熟,車輛配置合理;與SF重慶公司以快遞業(yè)務起家,逐步涉足大件物流的現(xiàn)實吻合。大件包裹車輛裝載率偏低,主要是因為大件包裹較難搬運導致車輛在末端需求點停留時間較長,集散間隔時間約束車輛能夠訪問的末端需求點個數(shù);現(xiàn)有大件包裹車輛車型容量偏大,應選取容量稍小的車型運輸大件包裹。

圖7 集散間隔時間與車輛裝載率(中轉中心到末端點)Figure 7Distribution interval and vehicle loading rate (transfer center to terminal)

4 結語

論文研究城市物流企業(yè)實施多產(chǎn)品(包裹)協(xié)同配送下大件包裹閾值設置、多功能中轉中心選址以及末端需求點分配的聯(lián)合優(yōu)化問題,是城市物流選址-路徑問題的新拓展。論文首次引入大件包裹閾值設置,綜合考慮大件包裹和標準包裹在搬運、分揀等處理環(huán)節(jié)以及相關設施場地配置差異,構造多功能中轉中心類型變量,以物流系統(tǒng)總成本最小為目標構建整數(shù)規(guī)劃模型;集成拉格朗日松弛和近似估算模型,針對多包裹協(xié)同配送特征提出求解模型TSDL混合算法,并通過與CPLEX運算結果對比,驗證TSDL混合算法的有效性?；趪鴥?nèi)典型快遞企業(yè)SF重慶公司的運營數(shù)據(jù),得出大件包裹閾值、多功能中轉中心選址布局、末端需求點分配的優(yōu)化結果;并分析配送模式、派送及攬收包裹量、服務時效對結果的影響。

結果表明:SF重慶公司優(yōu)化后的大件閾值為10kg,不同于現(xiàn)有20kg的閾值。優(yōu)化方案總成本SF現(xiàn)有狀況對比,物流總成本和單均成本均降低6.5%。協(xié)同配送模式下的固定成本以及運輸成本均低于獨立配送模式,總成本相應降低。本文模型和算法給出優(yōu)化方案具有穩(wěn)健性,既能滿足不同包裹規(guī)模城市物流企業(yè)需求,又能適用同類型城市物流企業(yè)包裹派送及攬收量日常波動的情形。經(jīng)營多類包裹的城市物流企業(yè),大件閾值的選擇沒有固定標準,城市物流企業(yè)需要根據(jù)包裹派送及攬收結構分布,綜合考慮相關因素,合理選擇大件閾值。包裹集散間隔時間不影響閾值設置,對包裹單均固定成本及處理成本沒有明顯影響,但單均運輸成本隨著集散間隔時間的增加而顯著降低,也就是說物流總成本下降主要是來自運輸成本的降低。

綜合本文的研究結論以及當前物流領域內(nèi)的大件業(yè)務發(fā)展現(xiàn)狀,本文提出以下建議:一是進入大件領域的快遞企業(yè)應根據(jù)自身狀況,合理選擇閾值。閾值的選擇與包裹派送及攬收規(guī)模、結構有關。二是合理確定服務時效。服務時效越高,集散頻次越高;較高的集散頻次使得單個集散批次的包裹派送及攬收量減少,不能充分發(fā)揮規(guī)模經(jīng)濟,中轉中心設施等物流資源利用率降低,車輛裝載率低,單個包裹平均成本較高?，F(xiàn)實中需要明確客戶時效需求,綜合物流成本和服務體驗,合理確定服務時效。三是對于進入大件物流領域的快遞企業(yè),在大件包裹增長的前期,可以通過增加大件車輛容量應對需求增加,但當需求增加至一定量時,還需要增設相應的中轉中心。四是協(xié)同配送的運營組織難度大于獨立配送,對企業(yè)管理水平和信息系統(tǒng)等要求更高。此外不同類型包裹配送時效也會影響協(xié)同配送成本。因此城市物流企業(yè)實施協(xié)同配送需要根據(jù)自身需求及狀況進行綜合評估。