零擔(dān)物流線路組合選擇策略研究

閆 芳，郭 俊，陳 凱

(重慶交通大學(xué) 經(jīng)濟與管理學(xué)院，400074 重慶)

0 引 言

隨著物流業(yè)的不斷發(fā)展，公路物流貨運量保持著強勁的增長勢頭。在GDP不斷增長與社會生產(chǎn)柔性化發(fā)展的雙重推動下，零擔(dān)物流得到了越來越廣泛的關(guān)注。那么在零擔(dān)物流中，承運人如何在已有運載資源配置的情況下，根據(jù)托運任務(wù)間的協(xié)同效應(yīng)選擇最佳運輸任務(wù)組合是一個關(guān)鍵問題。

目前，關(guān)于運輸任務(wù)選擇的研究主要從整車運輸(truck load,TL)承運人的視角出發(fā)。從建立模型的角度來看，C.G.LEE等[1]建立了非線性整數(shù)規(guī)劃模型，并采用基于列生成和拉格朗日的啟發(fā)式算法求解，使承運人得到組合拍賣中的最優(yōu)任務(wù)組合；X.H.QIAN等[2]針對第4方物流供應(yīng)商通過組合逆向拍賣購買運輸服務(wù)情況，將防御策略、保留策略和外部期權(quán)策略相結(jié)合，構(gòu)建了兩階段隨機競勝標(biāo)確定模型；Y.FANG等[3]討論了包含承運人、托運人以及第3方承運人的運輸服務(wù)采購競勝標(biāo)問題，針對傳統(tǒng)混合整數(shù)線性規(guī)劃模型求解易陷入分枝樹和定界樹不平衡的問題，構(gòu)建了一個確定模型；C.TRIKI等[4]將運輸服務(wù)采購拍賣和生產(chǎn)調(diào)度決策問題相結(jié)合，構(gòu)建競勝標(biāo)確定問題模型，并開發(fā)了2種啟發(fā)式算法對模型求解；G.KUYZU等[5]建立了隨機投標(biāo)價格優(yōu)化模型，以選出承運人滿意的任務(wù)組合方案；閆芳等[6-7]則考慮承運人與托運人的合作與競爭關(guān)系，建立了雙層規(guī)劃模型以解決承運人選包問題。從考慮任務(wù)組合的協(xié)同效應(yīng)的角度來看，E.OLCAYTU等[8]提出了一種基于任務(wù)之間協(xié)同的競價方法，并模擬實驗證明其有效性；F.YAN等[9]考慮了已有任務(wù)和新任務(wù)間的協(xié)同效應(yīng)，構(gòu)建了運輸服務(wù)競價問題模型，并設(shè)計了一種基于粒子群優(yōu)化的智能算法對模型求解;C.TRIKI等[10]利用基于位置技術(shù)的優(yōu)化方法評估托運任務(wù)間的協(xié)同作用，使承運人減少空車移動距離從而增加收益。

在零擔(dān)物流(less than truckload,LTL)中如何快速有效地選擇運輸任務(wù)的研究相對較少。文獻[11]從零擔(dān)物流的角度出發(fā)，提出了一種混合整數(shù)規(guī)劃方法以解決運輸服務(wù)采購?fù)稑?biāo)問題。文獻[12]為了解決小規(guī)模的零配件運輸問題，提出了一種迭代請求交換機制，證明組合包多輪交換機制能有效提高承運人收益。以上研究都是利用智能算法求解承運人選包問題，運算耗時長、求解結(jié)果不穩(wěn)定。筆者基于承運人的視角，建立可搭載零擔(dān)物流選包和車輛路徑優(yōu)化模型，提出了一種基于托運任務(wù)間協(xié)同效應(yīng)的零擔(dān)物流選包策略，以解決承運人選包和路徑優(yōu)化問題，并選取2個算例對其有效性和可行性進行驗證分析。

1 問題描述及建模

1.1 問題描述

假設(shè)在可達區(qū)域內(nèi)有V個節(jié)點，節(jié)點間的距離已知。某承運人已承運任務(wù)集為M0，M表示現(xiàn)貨市場待選任務(wù)集，且托運任務(wù)的起止點、物流量和運輸費用等信息已知。那么該承運人需要考慮2個問題：①如何在已有任務(wù)M0的基礎(chǔ)上選擇M的任務(wù)子集，使其運輸決策最優(yōu)；②如何規(guī)劃車輛行駛路線，運輸完成M的任務(wù)子集和M0，以達到收益最大。

1.2 模型假設(shè)

模型存在以下假設(shè)：

1)假定不同托運人的貨物可以混裝，但不可拆分；

2)每個托運任務(wù)的信息已知；

3)油耗與車輛的負(fù)載率成線性相關(guān)[13]；

4)車輛折舊系數(shù)根據(jù)工作量法計算；

5)車輛類別相同，高速收費系數(shù)唯一；

1.3 參數(shù)定義及數(shù)學(xué)模型

參數(shù)定義如表1：

表1 參數(shù)定義Table 1 Parameter definition

決策變量有：

承運人零擔(dān)物流選包和車輛路徑問題模型為：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

目標(biāo)函數(shù)式(1)表示承運人收益最大化；式(2)表示流量平衡；式(3)表示車輛經(jīng)過邊(i,j)時貨物裝載總量；式(4)表示車輛經(jīng)過邊(i,j)時貨物裝載率；式(5)表示車輛容量限制；式(6)表示車輛最大行駛距離約束；式(7)表示車輛在邊(i,j)上的單位油耗成本；式(8)、式(9)表示接受的任務(wù)必須全部完成；式(10)、式(11)表示二進制變量的取值范圍。

2 模型求解

在零擔(dān)物流中，無論是選擇任務(wù)組合還是規(guī)劃路徑都屬于NP-Hard問題[14-15]，求解過程較為復(fù)雜。因此，筆者提出了一種基于托運任務(wù)間協(xié)同效應(yīng)策略的2階段算法，并通過其對模型求解。第1階段采用協(xié)同效應(yīng)策略完成現(xiàn)貨市場任務(wù)選擇；第2階段規(guī)劃車輛路徑。

2.1 協(xié)同效應(yīng)策略

2.1.1 協(xié)同效應(yīng)影響因子

為衡量現(xiàn)貨市場可選任務(wù)組合S與承運人已有任務(wù)間的協(xié)同效應(yīng)，將協(xié)同效應(yīng)顯著的組合作為承運人的最優(yōu)選擇，筆者綜合選取了7個能夠集中體現(xiàn)2者協(xié)同程度的影響因子作為研究對象。

1)任務(wù)組合S運輸成本與車輛行駛距離

文獻[8]提出，承運人為完成任務(wù)而付出的單位距離成本是衡量任務(wù)間協(xié)同程度的重要指標(biāo)。換言之，單位成本距離越小，任務(wù)間的協(xié)同效益更高。由此，可將運輸成本C(S)與車輛行駛距離d(S)的協(xié)同值定義如式(13)：

(13)

2)報價與行駛距離

在報價既定的情況下，更小的運輸距離代表任務(wù)間擁有更高的協(xié)同。承運人單獨承運任務(wù)組合S時，其報價P(S)與行駛距離d(S)之間的協(xié)同值計算如式(14)：

(14)

3)起點節(jié)點與行駛路線

r3表述為：車輛行駛距離與任務(wù)組合S中各任務(wù)的起點節(jié)點到只承運M0時運輸路線各節(jié)點的最短距離之和的比值。筆者在文獻[10]的基礎(chǔ)上，提出了一種新的求解r3的方法。首先，將任務(wù)組合S包含任務(wù)數(shù)記為nS；其次，利用EOPSO[16]計算承運人只承運M0時，其行駛路線R(M0)和行駛距離d(M0)；最后，計算第i個任務(wù)的起點與R(M0)各節(jié)點距離的最小值dM0(i)。對數(shù)據(jù)進行歸一化處理后計算如式(15)：

(15)

4)終點節(jié)點與行駛路線

(16)

5)起點節(jié)點與各節(jié)點的跳躍點數(shù)量

待選任務(wù)起點與M0運輸路線節(jié)點間的可達性是體現(xiàn)其協(xié)同效應(yīng)的重要指標(biāo)。跳躍點數(shù)量越少，表明協(xié)同程度更高。將任務(wù)i的起點到R(M0)各節(jié)點的跳躍點最小值記為ZM0(i)，運輸網(wǎng)絡(luò)中任意2節(jié)點之間跳躍點個數(shù)的最大值記為nmax。協(xié)同值r5的計算如式(17)：

(17)

6)終點節(jié)點與各節(jié)點的跳躍點數(shù)量

(18)

7)在承運M0時，組合S可搭載的概率

筆者從零擔(dān)運輸?shù)慕嵌葋硌芯烤€路組合選擇，因此還需考慮待選任務(wù)與車輛可用載重之間的協(xié)同。首先，將任務(wù)i的運量q(i)依次插入到R(M0)后的量記為g(R)，R(M0)包含的節(jié)點個數(shù)記為nR(M0)；然后，將g(R)的元素與車輛最大載重Q比較，若大于Q，則說明任務(wù)i在R(M0)的此節(jié)點不能搭載，反之，則可搭載；最后，將可搭載的節(jié)點個數(shù)記為H(i)。協(xié)同值r7的計算如式(19)：

(19)

2.1.2 影響因子權(quán)重

BP神經(jīng)網(wǎng)絡(luò)具有自我學(xué)習(xí)能力、自適應(yīng)能力、強大的非線性映射能力以及高容錯性，適合求解具有多因素的綜合評價權(quán)重確定問題[18]。筆者選取BP神經(jīng)網(wǎng)絡(luò)解決因子權(quán)重確定問題。權(quán)重ωi的計算步驟如下：

步 驟 1：建立神經(jīng)網(wǎng)絡(luò)。將七個因子的值作為BP神經(jīng)網(wǎng)絡(luò)的輸入層神經(jīng)元，建立一個3層的BP神經(jīng)網(wǎng)絡(luò)。

步 驟 2：確定隱含層。采用文獻[19]提出的試湊法確定其個數(shù)。

步 驟 3：計算承運人收益。采用EOPSO計算現(xiàn)貨市場所有任務(wù)組合S與已有任務(wù)M0合并后的收益。

步 驟 4：確定輸出層。將步驟3計算的結(jié)果進行歸一化處理，并將結(jié)果作為輸出層神經(jīng)元。

步 驟 5：訓(xùn)練。利用BP神經(jīng)網(wǎng)絡(luò)工具箱進行訓(xùn)練，從而得到各因子的權(quán)重。

2.2 算法設(shè)計

2.2.1 任務(wù)選擇

采用協(xié)同效益策略對現(xiàn)貨市場任務(wù)進行選擇。首先，計算承運人已有任務(wù)與所有現(xiàn)貨市場任務(wù)組合的協(xié)同值；其次，將最大協(xié)同值所對應(yīng)的組合作為承運人在現(xiàn)貨市場上的選擇。

2.2.2 車輛路徑規(guī)劃

針對標(biāo)準(zhǔn)粒子群優(yōu)化算法易陷入局部最優(yōu)、進化后期收斂速度慢和收斂精度低等缺點,筆者采用精英反向?qū)W習(xí)的粒子群優(yōu)化算法對車輛路徑規(guī)劃求解。具體步驟如下：

步 驟 1：初始化，隨機生成各粒子位置和速度。vi和pi都是一個N·2R的矩陣，其中R為任務(wù)個數(shù)，N為粒子個數(shù)。

步 驟 2：車輛運輸路徑規(guī)劃。

1)將每個任務(wù)拆分為pickup任務(wù)和delivery任務(wù)，并重新編號；

2)根據(jù)pi前2R列，進行升序操作，確定任務(wù)拆分后的操作先后順序；

3)標(biāo)記P-D操作。

(a)按照優(yōu)先順序，尋找未拆分時相同任務(wù)編號的位置；

(b)將位置較小者標(biāo)記為該任務(wù)的pickup點，較大者標(biāo)記為delivery點。

4)規(guī)劃路徑。

(a)根據(jù)操作優(yōu)先順序，確定車輛首個任務(wù)；

(b)將當(dāng)前節(jié)點加入到路徑集合，并更新車輛剩余運力；

(c)根據(jù)順序確定下一任務(wù)；

(d)判斷該任務(wù)的操作性質(zhì)，若為pickup點則進入步驟(e)，若為delivery點則進入步驟(f)；

(e)判斷車輛剩余運力與任務(wù)量的大小關(guān)系。若剩余運力小于任務(wù)量，則將該任務(wù)標(biāo)記后拋棄，并返回步驟(c)；否則進入步驟(f)；

(f)完成任務(wù)相應(yīng)的裝卸操作，更新車輛剩余運力和路徑集合；

(g)判斷未標(biāo)記任務(wù)是否已經(jīng)完成。若還存在未完成的任務(wù)，則返回步驟(c)。若不存在則進入步驟(h)；

(h)根據(jù)原有優(yōu)先順序，完成標(biāo)記任務(wù)的路徑規(guī)劃；

(i)采用插入法確定最優(yōu)的路線拆分位置，滿足車輛行駛里程約束；

步 驟 3：求解路線載重、車輛載重率，計算運輸成本，記錄最優(yōu)值。

步 驟 4：更新粒子。

1)判斷每個粒子的上下界；

2)根據(jù)上下界和個體最優(yōu)生成反向精英粒子，并規(guī)定其上下界；

3)判斷反向精英粒子與各粒子上下界的大小關(guān)系。若反向精英粒子大于上界或者小于下界，則反向精英粒子為上下界之間的隨機數(shù)。

步 驟 5：利用差分演化策略，更新全局最優(yōu)解。

步 驟 6：判斷是否達到最大迭代次數(shù)。若未達到則返回步驟4；反之，則進入步驟7。

步 驟 7：結(jié)束。

整體算法流程如圖1。

圖1 算法流程Fig. 1 Algorithm flowchart

3 算例分析

為驗證協(xié)同效應(yīng)策略的有效性和可行性，筆者采用間協(xié)同效應(yīng)策略和EOPSO[15]對兩個算例進行分析討論。

首先，計算現(xiàn)貨市場所有任務(wù)組合與M0合并后的各因子的協(xié)同值；其次，利用EOPSO計算任務(wù)合并后承運人的收益(粒子群參數(shù)設(shè)置為：種群規(guī)模為20，迭代次數(shù)為200，學(xué)習(xí)因子c1=1.5，c2=0.3，ωmax=0.4)；最后，將協(xié)同值最大的組合包的收益與承運人的最大收益對比，如果二者相近，則證明協(xié)同效應(yīng)策略在解決零擔(dān)物流承運人選擇任務(wù)組合時有較好的可行性和有效性。

車型和油耗資料來源于文獻[12]，表2和表3中任務(wù)節(jié)點的距離和跳躍點數(shù)量來源于360地圖，貨物運輸費用1.0元/kg。算例1和算例2任務(wù)數(shù)據(jù)都來源于互比物流網(wǎng)站(www.hubiwl.com)。

表2 節(jié)點間的距離Table 2 Distance between nodes km

表3 節(jié)點間的跳躍點的數(shù)量信息Table 3 Number information of jump points between nodes

3.1 算例1

算例1任務(wù)信息如表4，現(xiàn)貨市場托運任務(wù)M有24-1=15種組合，包含的任務(wù)如表5。首先，將所有任務(wù)組合S的收益歸一化處理；然后，將15種任務(wù)組合中的70%(11種任務(wù)組合)作為訓(xùn)練樣本，15%(2種任務(wù)組合)作為驗證樣本，剩下的15%作為檢測樣本，調(diào)用BP神經(jīng)網(wǎng)絡(luò)工具箱進行訓(xùn)練，訓(xùn)練結(jié)果如圖2；最后，根據(jù)訓(xùn)練的結(jié)果求各因子的權(quán)重，其結(jié)果為：r1=0.36、r2=r3=0.18、r4=0.02、r5=0.03、r6=0.12和r7=0.13。

表4 算例1任務(wù)信息Table 4 Task information of example 1

表5 組合包S所包含的任務(wù)Table 5 Tasks included in the package S

圖2 BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練結(jié)果Fig. 2 BP neural network training results

承運人只選擇任務(wù)N2時，協(xié)同效應(yīng)值最大為0.89，利用EOPSO計算承運人的收益最大為1 108元，如表6。將承運人已有任務(wù)集合M與新增任務(wù)N2合并，得到承運人的運輸任務(wù)集合。在允許搭載的情況下，對其運輸線路進行合理規(guī)劃， 計算結(jié)果如表7。其中，第1列表示車輛的運 輸路徑，如車輛 1的路線為2-5-8-9-6，表示車輛從節(jié)點2出發(fā)，途徑節(jié)點 5、8和 9，之后到達節(jié)點 6； 第2列表示在該節(jié)點相關(guān)運輸任務(wù)的裝貨操作，第3行表示在該節(jié)點相關(guān)運輸任務(wù)的卸貨操作。如車輛2的行駛路線為3-1-3，表示車輛在節(jié)點3裝載任務(wù)E2，行駛到節(jié)點 1后，卸載E2并裝載新任務(wù)E1，最后返回到節(jié)點3，卸載任務(wù)E1。通過分析 發(fā)現(xiàn)，任務(wù)E4與任務(wù)E3存在相同節(jié)點。因此，綜 合考慮各節(jié)點間的距離后，在搭載任務(wù)E4的同時，完成任務(wù)E3和任務(wù)N2能夠最大程度上節(jié)約成本。因此，在此決策方案下，承運人總體收益最優(yōu)，為1 108元。

表6 算例1計算結(jié)果Table 6 Calculation results of example 1

表7 承運人車輛行駛路線信息Table 7 Carrier vehicle driving route information

算例1中分別采用協(xié)同效應(yīng)策略與EOPSO求解，2者最優(yōu)方案相同，均選擇N2作為承運人的新增線路，因此，協(xié)同效應(yīng)策略與EOPSO在計算結(jié)果質(zhì)量方面表現(xiàn)相同，但是在計算時間上，采用協(xié)同效應(yīng)策略選擇任務(wù)僅需120.6 s，而采用反向精英粒子群算法則需要1 895.7 s，前者節(jié)約了近93.64%的運算時間。在時間計算方面，采用協(xié)同效應(yīng)策略選擇現(xiàn)貨市場任務(wù)組合更具有優(yōu)勢。

3.2 算例2

為了進一步驗證模型、協(xié)同效應(yīng)策略的適用性，算例2擴大了任務(wù)規(guī)模，包含31種任務(wù)組合，包含的任務(wù)如表8。通過計算，承運人在M0的基礎(chǔ)上選擇承運任務(wù)N2、N3和N4時，其協(xié)同效應(yīng)值最大為0.927；利用EOPSO計算在此情況下承運人的收益為943.7元，其收益在所有任務(wù)組合里依然最大。因此，基于托運任務(wù)間協(xié)同效應(yīng)的求解策略與EOPSO求解質(zhì)量相同。

表8 算例2任務(wù)信息Table 8 Task information of example 2

選擇任務(wù)N2、N3和N4作為新任務(wù)時，路徑規(guī)劃結(jié)果如表9。需要2輛車完成承運的8個任務(wù)，行駛路線分別為1-3-4-5-2-3和8-9-12-10-11。對路線分析可知，任務(wù)E1和E2在節(jié)點1同時被裝載，所以將任務(wù)E1和E2進行了合并運輸。綜合考慮各節(jié)點間的距離、裝載和卸載情況，通過計算可知，在搭載任務(wù)E1的同時，完成任務(wù)E2、E3和E5能夠最大程度上節(jié)約運輸成本。算例2在考慮承運人收益最大化的前提下，選擇N2、N3和N4的任務(wù)組合作為新增任務(wù)，得出最大收益為943.7元。與算例1結(jié)果相似，兩者在解的質(zhì)量方面表現(xiàn)相同。但EOPSO耗時4 125.9 s，協(xié)同效應(yīng)策略僅耗時148.6 s，節(jié)約了96.4%的運算時間。

表9 承運人車輛行駛路線信息Table 9 Carrier vehicle driving route information

為說明算例2結(jié)果的有效性和合理性，將選擇全部任務(wù)的收益與協(xié)同效應(yīng)策略得到的最優(yōu)解進行對比。如表10，后者車輛行駛的總距離比前者減少33.63%，且空載距離減少46.51%。因此當(dāng)承運人放棄現(xiàn)貨市場任務(wù)N1和N5時，其車輛行駛總里程和空載距離均不同程度的減少，且收益從-528.3元增加到943.7元。

表10 結(jié)果對比Table 10 Comparison of results

綜上可知，當(dāng)不考慮線路間的協(xié)同效應(yīng)而盲目選擇增加托運任務(wù)，可能會增加承運人的運輸成本，形成不合理的運輸方案。因此，筆者所提模型和基于托運任務(wù)協(xié)同效應(yīng)的求解策略可以幫助承運人在現(xiàn)貨市場選擇合適的托運任務(wù)，以實現(xiàn)承運人收益最大化。

4 結(jié) 語

筆者以承運人收益最大化為目標(biāo)，以車輛最大裝載貨運量和最大行駛距離為約束條件，構(gòu)建了零擔(dān)物流選包和車輛路徑優(yōu)化的數(shù)學(xué)模型，提出了一種解決承運人選擇市場上托運任務(wù)組合包的協(xié)同效應(yīng)策略，并用2個算例驗證了所建立模型及基于托運任務(wù)協(xié)同效應(yīng)的求解方法的有效性和可行性。算例1中協(xié)同效應(yīng)策略與反向精英粒子群算法求解方案相同，但協(xié)同效應(yīng)策略運算時間僅需120.6 s，較后者減少1 775.1 s，求解時間縮短93.64%。擴大算例規(guī)模后，二者求解時間增加。在求解質(zhì)量相同情況下，協(xié)同效應(yīng)策略耗時148.6 s，反向精英粒子群算法則需4 125.9 s，后者運算時間增加96.4%。

通過計算結(jié)果可知，筆者提出的協(xié)同效應(yīng)策略，不但可以快速的幫助承運人找到滿意的現(xiàn)貨市場托運任務(wù)組合，而且在求解結(jié)果相同的情況下，計算時間更少。所以本文研究成果求解可搭載零擔(dān)物流組合包的選取問題具有一定的理論和應(yīng)用價值。