閆 芳,郭 俊,陳 凱
(重慶交通大學 經濟與管理學院,400074 重慶)
隨著物流業(yè)的不斷發(fā)展,公路物流貨運量保持著強勁的增長勢頭。在GDP不斷增長與社會生產柔性化發(fā)展的雙重推動下,零擔物流得到了越來越廣泛的關注。那么在零擔物流中,承運人如何在已有運載資源配置的情況下,根據托運任務間的協(xié)同效應選擇最佳運輸任務組合是一個關鍵問題。
目前,關于運輸任務選擇的研究主要從整車運輸(truck load,TL)承運人的視角出發(fā)。從建立模型的角度來看,C.G.LEE等[1]建立了非線性整數規(guī)劃模型,并采用基于列生成和拉格朗日的啟發(fā)式算法求解,使承運人得到組合拍賣中的最優(yōu)任務組合;X.H.QIAN等[2]針對第4方物流供應商通過組合逆向拍賣購買運輸服務情況,將防御策略、保留策略和外部期權策略相結合,構建了兩階段隨機競勝標確定模型;Y.FANG等[3]討論了包含承運人、托運人以及第3方承運人的運輸服務采購競勝標問題,針對傳統(tǒng)混合整數線性規(guī)劃模型求解易陷入分枝樹和定界樹不平衡的問題,構建了一個確定模型;C.TRIKI等[4]將運輸服務采購拍賣和生產調度決策問題相結合,構建競勝標確定問題模型,并開發(fā)了2種啟發(fā)式算法對模型求解;G.KUYZU等[5]建立了隨機投標價格優(yōu)化模型,以選出承運人滿意的任務組合方案;閆芳等[6-7]則考慮承運人與托運人的合作與競爭關系,建立了雙層規(guī)劃模型以解決承運人選包問題。從考慮任務組合的協(xié)同效應的角度來看,E.OLCAYTU等[8]提出了一種基于任務之間協(xié)同的競價方法,并模擬實驗證明其有效性;F.YAN等[9]考慮了已有任務和新任務間的協(xié)同效應,構建了運輸服務競價問題模型,并設計了一種基于粒子群優(yōu)化的智能算法對模型求解;C.TRIKI等[10]利用基于位置技術的優(yōu)化方法評估托運任務間的協(xié)同作用,使承運人減少空車移動距離從而增加收益。
在零擔物流(less than truckload,LTL)中如何快速有效地選擇運輸任務的研究相對較少。文獻[11]從零擔物流的角度出發(fā),提出了一種混合整數規(guī)劃方法以解決運輸服務采購投標問題。文獻[12]為了解決小規(guī)模的零配件運輸問題,提出了一種迭代請求交換機制,證明組合包多輪交換機制能有效提高承運人收益。以上研究都是利用智能算法求解承運人選包問題,運算耗時長、求解結果不穩(wěn)定。筆者基于承運人的視角,建立可搭載零擔物流選包和車輛路徑優(yōu)化模型,提出了一種基于托運任務間協(xié)同效應的零擔物流選包策略,以解決承運人選包和路徑優(yōu)化問題,并選取2個算例對其有效性和可行性進行驗證分析。
假設在可達區(qū)域內有V個節(jié)點,節(jié)點間的距離已知。某承運人已承運任務集為M0,M表示現(xiàn)貨市場待選任務集,且托運任務的起止點、物流量和運輸費用等信息已知。那么該承運人需要考慮2個問題:①如何在已有任務M0的基礎上選擇M的任務子集,使其運輸決策最優(yōu);②如何規(guī)劃車輛行駛路線,運輸完成M的任務子集和M0,以達到收益最大。
模型存在以下假設:
1)假定不同托運人的貨物可以混裝,但不可拆分;
2)每個托運任務的信息已知;
3)油耗與車輛的負載率成線性相關[13];
4)車輛折舊系數根據工作量法計算;
5)車輛類別相同,高速收費系數唯一;
參數定義如表1:
表1 參數定義Table 1 Parameter definition
決策變量有:
承運人零擔物流選包和車輛路徑問題模型為:
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
目標函數式(1)表示承運人收益最大化;式(2)表示流量平衡;式(3)表示車輛經過邊(i,j)時貨物裝載總量;式(4)表示車輛經過邊(i,j)時貨物裝載率;式(5)表示車輛容量限制;式(6)表示車輛最大行駛距離約束;式(7)表示車輛在邊(i,j)上的單位油耗成本;式(8)、式(9)表示接受的任務必須全部完成;式(10)、式(11)表示二進制變量的取值范圍。
在零擔物流中,無論是選擇任務組合還是規(guī)劃路徑都屬于NP-Hard問題[14-15],求解過程較為復雜。因此,筆者提出了一種基于托運任務間協(xié)同效應策略的2階段算法,并通過其對模型求解。第1階段采用協(xié)同效應策略完成現(xiàn)貨市場任務選擇;第2階段規(guī)劃車輛路徑。
2.1.1 協(xié)同效應影響因子
為衡量現(xiàn)貨市場可選任務組合S與承運人已有任務間的協(xié)同效應,將協(xié)同效應顯著的組合作為承運人的最優(yōu)選擇,筆者綜合選取了7個能夠集中體現(xiàn)2者協(xié)同程度的影響因子作為研究對象。
1)任務組合S運輸成本與車輛行駛距離
文獻[8]提出,承運人為完成任務而付出的單位距離成本是衡量任務間協(xié)同程度的重要指標。換言之,單位成本距離越小,任務間的協(xié)同效益更高。由此,可將運輸成本C(S)與車輛行駛距離d(S)的協(xié)同值定義如式(13):
(13)
2)報價與行駛距離
在報價既定的情況下,更小的運輸距離代表任務間擁有更高的協(xié)同。承運人單獨承運任務組合S時,其報價P(S)與行駛距離d(S)之間的協(xié)同值計算如式(14):
(14)
3)起點節(jié)點與行駛路線
r3表述為:車輛行駛距離與任務組合S中各任務的起點節(jié)點到只承運M0時運輸路線各節(jié)點的最短距離之和的比值。筆者在文獻[10]的基礎上,提出了一種新的求解r3的方法。首先,將任務組合S包含任務數記為nS;其次,利用EOPSO[16]計算承運人只承運M0時,其行駛路線R(M0)和行駛距離d(M0);最后,計算第i個任務的起點與R(M0)各節(jié)點距離的最小值dM0(i)。對數據進行歸一化處理后計算如式(15):
(15)
4)終點節(jié)點與行駛路線
(16)
5)起點節(jié)點與各節(jié)點的跳躍點數量
待選任務起點與M0運輸路線節(jié)點間的可達性是體現(xiàn)其協(xié)同效應的重要指標。跳躍點數量越少,表明協(xié)同程度更高。將任務i的起點到R(M0)各節(jié)點的跳躍點最小值記為ZM0(i),運輸網絡中任意2節(jié)點之間跳躍點個數的最大值記為nmax。協(xié)同值r5的計算如式(17):
(17)
6)終點節(jié)點與各節(jié)點的跳躍點數量
(18)
7)在承運M0時,組合S可搭載的概率
筆者從零擔運輸的角度來研究線路組合選擇,因此還需考慮待選任務與車輛可用載重之間的協(xié)同。首先,將任務i的運量q(i)依次插入到R(M0)后的量記為g(R),R(M0)包含的節(jié)點個數記為nR(M0);然后,將g(R)的元素與車輛最大載重Q比較,若大于Q,則說明任務i在R(M0)的此節(jié)點不能搭載,反之,則可搭載;最后,將可搭載的節(jié)點個數記為H(i)。協(xié)同值r7的計算如式(19):
(19)
2.1.2 影響因子權重
BP神經網絡具有自我學習能力、自適應能力、強大的非線性映射能力以及高容錯性,適合求解具有多因素的綜合評價權重確定問題[18]。筆者選取BP神經網絡解決因子權重確定問題。權重ωi的計算步驟如下:
步 驟 1:建立神經網絡。將七個因子的值作為BP神經網絡的輸入層神經元,建立一個3層的BP神經網絡。
步 驟 2:確定隱含層。采用文獻[19]提出的試湊法確定其個數。
步 驟 3:計算承運人收益。采用EOPSO計算現(xiàn)貨市場所有任務組合S與已有任務M0合并后的收益。
步 驟 4:確定輸出層。將步驟3計算的結果進行歸一化處理,并將結果作為輸出層神經元。
步 驟 5:訓練。利用BP神經網絡工具箱進行訓練,從而得到各因子的權重。
2.2.1 任務選擇
采用協(xié)同效益策略對現(xiàn)貨市場任務進行選擇。首先,計算承運人已有任務與所有現(xiàn)貨市場任務組合的協(xié)同值;其次,將最大協(xié)同值所對應的組合作為承運人在現(xiàn)貨市場上的選擇。
2.2.2 車輛路徑規(guī)劃
針對標準粒子群優(yōu)化算法易陷入局部最優(yōu)、進化后期收斂速度慢和收斂精度低等缺點,筆者采用精英反向學習的粒子群優(yōu)化算法對車輛路徑規(guī)劃求解。具體步驟如下:
步 驟 1:初始化,隨機生成各粒子位置和速度。vi和pi都是一個N·2R的矩陣,其中R為任務個數,N為粒子個數。
步 驟 2:車輛運輸路徑規(guī)劃。
1)將每個任務拆分為pickup任務和delivery任務,并重新編號;
2)根據pi前2R列,進行升序操作,確定任務拆分后的操作先后順序;
3)標記P-D操作。
(a)按照優(yōu)先順序,尋找未拆分時相同任務編號的位置;
(b)將位置較小者標記為該任務的pickup點,較大者標記為delivery點。
4)規(guī)劃路徑。
(a)根據操作優(yōu)先順序,確定車輛首個任務;
(b)將當前節(jié)點加入到路徑集合,并更新車輛剩余運力;
(c)根據順序確定下一任務;
(d)判斷該任務的操作性質,若為pickup點則進入步驟(e),若為delivery點則進入步驟(f);
(e)判斷車輛剩余運力與任務量的大小關系。若剩余運力小于任務量,則將該任務標記后拋棄,并返回步驟(c);否則進入步驟(f);
(f)完成任務相應的裝卸操作,更新車輛剩余運力和路徑集合;
(g)判斷未標記任務是否已經完成。若還存在未完成的任務,則返回步驟(c)。若不存在則進入步驟(h);
(h)根據原有優(yōu)先順序,完成標記任務的路徑規(guī)劃;
(i)采用插入法確定最優(yōu)的路線拆分位置,滿足車輛行駛里程約束;
步 驟 3:求解路線載重、車輛載重率,計算運輸成本,記錄最優(yōu)值。
步 驟 4:更新粒子。
1)判斷每個粒子的上下界;
2)根據上下界和個體最優(yōu)生成反向精英粒子,并規(guī)定其上下界;
3)判斷反向精英粒子與各粒子上下界的大小關系。若反向精英粒子大于上界或者小于下界,則反向精英粒子為上下界之間的隨機數。
步 驟 5:利用差分演化策略,更新全局最優(yōu)解。
步 驟 6:判斷是否達到最大迭代次數。若未達到則返回步驟4;反之,則進入步驟7。
步 驟 7:結束。
整體算法流程如圖1。
圖1 算法流程Fig. 1 Algorithm flowchart
為驗證協(xié)同效應策略的有效性和可行性,筆者采用間協(xié)同效應策略和EOPSO[15]對兩個算例進行分析討論。
首先,計算現(xiàn)貨市場所有任務組合與M0合并后的各因子的協(xié)同值;其次,利用EOPSO計算任務合并后承運人的收益(粒子群參數設置為:種群規(guī)模為20,迭代次數為200,學習因子c1=1.5,c2=0.3,ωmax=0.4);最后,將協(xié)同值最大的組合包的收益與承運人的最大收益對比,如果二者相近,則證明協(xié)同效應策略在解決零擔物流承運人選擇任務組合時有較好的可行性和有效性。
車型和油耗資料來源于文獻[12],表2和表3中任務節(jié)點的距離和跳躍點數量來源于360地圖,貨物運輸費用1.0元/kg。算例1和算例2任務數據都來源于互比物流網站(www.hubiwl.com)。
表2 節(jié)點間的距離Table 2 Distance between nodes km
表3 節(jié)點間的跳躍點的數量信息Table 3 Number information of jump points between nodes
算例1任務信息如表4,現(xiàn)貨市場托運任務M有24-1=15種組合,包含的任務如表5。首先,將所有任務組合S的收益歸一化處理;然后,將15種任務組合中的70%(11種任務組合)作為訓練樣本,15%(2種任務組合)作為驗證樣本,剩下的15%作為檢測樣本,調用BP神經網絡工具箱進行訓練,訓練結果如圖2;最后,根據訓練的結果求各因子的權重,其結果為:r1=0.36、r2=r3=0.18、r4=0.02、r5=0.03、r6=0.12和r7=0.13。
表4 算例1任務信息Table 4 Task information of example 1
表5 組合包S所包含的任務Table 5 Tasks included in the package S
圖2 BP神經網絡訓練結果Fig. 2 BP neural network training results
承運人只選擇任務N2時,協(xié)同效應值最大為0.89,利用EOPSO計算承運人的收益最大為1 108元,如表6。將承運人已有任務集合M與新增任務N2合并,得到承運人的運輸任務集合。在允許搭載的情況下,對其運輸線路進行合理規(guī)劃, 計算結果如表7。其中,第1列表示車輛的運 輸路徑,如車輛 1的路線為2-5-8-9-6,表示車輛從節(jié)點2出發(fā),途徑節(jié)點 5、8和 9,之后到達節(jié)點 6; 第2列表示在該節(jié)點相關運輸任務的裝貨操作,第3行表示在該節(jié)點相關運輸任務的卸貨操作。如車輛2的行駛路線為3-1-3,表示車輛在節(jié)點3裝載任務E2,行駛到節(jié)點 1后,卸載E2并裝載新任務E1,最后返回到節(jié)點3,卸載任務E1。通過分析 發(fā)現(xiàn),任務E4與任務E3存在相同節(jié)點。因此,綜 合考慮各節(jié)點間的距離后,在搭載任務E4的同時,完成任務E3和任務N2能夠最大程度上節(jié)約成本。因此,在此決策方案下,承運人總體收益最優(yōu),為1 108元。
表6 算例1計算結果Table 6 Calculation results of example 1
表7 承運人車輛行駛路線信息Table 7 Carrier vehicle driving route information
算例1中分別采用協(xié)同效應策略與EOPSO求解,2者最優(yōu)方案相同,均選擇N2作為承運人的新增線路,因此,協(xié)同效應策略與EOPSO在計算結果質量方面表現(xiàn)相同,但是在計算時間上,采用協(xié)同效應策略選擇任務僅需120.6 s,而采用反向精英粒子群算法則需要1 895.7 s,前者節(jié)約了近93.64%的運算時間。在時間計算方面,采用協(xié)同效應策略選擇現(xiàn)貨市場任務組合更具有優(yōu)勢。
為了進一步驗證模型、協(xié)同效應策略的適用性,算例2擴大了任務規(guī)模,包含31種任務組合,包含的任務如表8。通過計算,承運人在M0的基礎上選擇承運任務N2、N3和N4時,其協(xié)同效應值最大為0.927;利用EOPSO計算在此情況下承運人的收益為943.7元,其收益在所有任務組合里依然最大。因此,基于托運任務間協(xié)同效應的求解策略與EOPSO求解質量相同。
表8 算例2任務信息Table 8 Task information of example 2
選擇任務N2、N3和N4作為新任務時,路徑規(guī)劃結果如表9。需要2輛車完成承運的8個任務,行駛路線分別為1-3-4-5-2-3和8-9-12-10-11。對路線分析可知,任務E1和E2在節(jié)點1同時被裝載,所以將任務E1和E2進行了合并運輸。綜合考慮各節(jié)點間的距離、裝載和卸載情況,通過計算可知,在搭載任務E1的同時,完成任務E2、E3和E5能夠最大程度上節(jié)約運輸成本。算例2在考慮承運人收益最大化的前提下,選擇N2、N3和N4的任務組合作為新增任務,得出最大收益為943.7元。與算例1結果相似,兩者在解的質量方面表現(xiàn)相同。但EOPSO耗時4 125.9 s,協(xié)同效應策略僅耗時148.6 s,節(jié)約了96.4%的運算時間。
表9 承運人車輛行駛路線信息Table 9 Carrier vehicle driving route information
為說明算例2結果的有效性和合理性,將選擇全部任務的收益與協(xié)同效應策略得到的最優(yōu)解進行對比。如表10,后者車輛行駛的總距離比前者減少33.63%,且空載距離減少46.51%。因此當承運人放棄現(xiàn)貨市場任務N1和N5時,其車輛行駛總里程和空載距離均不同程度的減少,且收益從-528.3元增加到943.7元。
表10 結果對比Table 10 Comparison of results
綜上可知,當不考慮線路間的協(xié)同效應而盲目選擇增加托運任務,可能會增加承運人的運輸成本,形成不合理的運輸方案。因此,筆者所提模型和基于托運任務協(xié)同效應的求解策略可以幫助承運人在現(xiàn)貨市場選擇合適的托運任務,以實現(xiàn)承運人收益最大化。
筆者以承運人收益最大化為目標,以車輛最大裝載貨運量和最大行駛距離為約束條件,構建了零擔物流選包和車輛路徑優(yōu)化的數學模型,提出了一種解決承運人選擇市場上托運任務組合包的協(xié)同效應策略,并用2個算例驗證了所建立模型及基于托運任務協(xié)同效應的求解方法的有效性和可行性。算例1中協(xié)同效應策略與反向精英粒子群算法求解方案相同,但協(xié)同效應策略運算時間僅需120.6 s,較后者減少1 775.1 s,求解時間縮短93.64%。擴大算例規(guī)模后,二者求解時間增加。在求解質量相同情況下,協(xié)同效應策略耗時148.6 s,反向精英粒子群算法則需4 125.9 s,后者運算時間增加96.4%。
通過計算結果可知,筆者提出的協(xié)同效應策略,不但可以快速的幫助承運人找到滿意的現(xiàn)貨市場托運任務組合,而且在求解結果相同的情況下,計算時間更少。所以本文研究成果求解可搭載零擔物流組合包的選取問題具有一定的理論和應用價值。