閆 芳,郭 俊,陳 凱
(重慶交通大學(xué) 經(jīng)濟與管理學(xué)院,400074 重慶)
隨著物流業(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)建了兩階段隨機競勝標確定模型;Y.FANG等[3]討論了包含承運人、托運人以及第3方承運人的運輸服務(wù)采購競勝標問題,針對傳統(tǒng)混合整數(shù)線性規(guī)劃模型求解易陷入分枝樹和定界樹不平衡的問題,構(gòu)建了一個確定模型;C.TRIKI等[4]將運輸服務(wù)采購拍賣和生產(chǎn)調(diào)度決策問題相結(jié)合,構(gòu)建競勝標確定問題模型,并開發(fā)了2種啟發(fā)式算法對模型求解;G.KUYZU等[5]建立了隨機投標價格優(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ù)稑藛栴}。文獻[12]為了解決小規(guī)模的零配件運輸問題,提出了一種迭代請求交換機制,證明組合包多輪交換機制能有效提高承運人收益。以上研究都是利用智能算法求解承運人選包問題,運算耗時長、求解結(jié)果不穩(wěn)定。筆者基于承運人的視角,建立可搭載零擔(dān)物流選包和車輛路徑優(yōu)化模型,提出了一種基于托運任務(wù)間協(xié)同效應(yīng)的零擔(dān)物流選包策略,以解決承運人選包和路徑優(yōu)化問題,并選取2個算例對其有效性和可行性進行驗證分析。
假設(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,以達到收益最大。
模型存在以下假設(shè):
1)假定不同托運人的貨物可以混裝,但不可拆分;
2)每個托運任務(wù)的信息已知;
3)油耗與車輛的負載率成線性相關(guān)[13];
4)車輛折舊系數(shù)根據(jù)工作量法計算;
5)車輛類別相同,高速收費系數(shù)唯一;
參數(shù)定義如表1:
表1 參數(shù)定義Table 1 Parameter definition
決策變量有:
承運人零擔(dān)物流選包和車輛路徑問題模型為:
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
目標函數(shù)式(1)表示承運人收益最大化;式(2)表示流量平衡;式(3)表示車輛經(jīng)過邊(i,j)時貨物裝載總量;式(4)表示車輛經(jīng)過邊(i,j)時貨物裝載率;式(5)表示車輛容量限制;式(6)表示車輛最大行駛距離約束;式(7)表示車輛在邊(i,j)上的單位油耗成本;式(8)、式(9)表示接受的任務(wù)必須全部完成;式(10)、式(11)表示二進制變量的取值范圍。
在零擔(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.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é)同程度的重要指標。換言之,單位成本距離越小,任務(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)的重要指標。跳躍點數(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.1 任務(wù)選擇
采用協(xié)同效益策略對現(xiàn)貨市場任務(wù)進行選擇。首先,計算承運人已有任務(wù)與所有現(xiàn)貨市場任務(wù)組合的協(xié)同值;其次,將最大協(xié)同值所對應(yīng)的組合作為承運人在現(xiàn)貨市場上的選擇。
2.2.2 車輛路徑規(guī)劃
針對標準粒子群優(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)標記P-D操作。
(a)按照優(yōu)先順序,尋找未拆分時相同任務(wù)編號的位置;
(b)將位置較小者標記為該任務(wù)的pickup點,較大者標記為delivery點。
4)規(guī)劃路徑。
(a)根據(jù)操作優(yōu)先順序,確定車輛首個任務(wù);
(b)將當前節(jié)點加入到路徑集合,并更新車輛剩余運力;
(c)根據(jù)順序確定下一任務(wù);
(d)判斷該任務(wù)的操作性質(zhì),若為pickup點則進入步驟(e),若為delivery點則進入步驟(f);
(e)判斷車輛剩余運力與任務(wù)量的大小關(guān)系。若剩余運力小于任務(wù)量,則將該任務(wù)標記后拋棄,并返回步驟(c);否則進入步驟(f);
(f)完成任務(wù)相應(yīng)的裝卸操作,更新車輛剩余運力和路徑集合;
(g)判斷未標記任務(wù)是否已經(jīng)完成。若還存在未完成的任務(wù),則返回步驟(c)。若不存在則進入步驟(h);
(h)根據(jù)原有優(yōu)先順序,完成標記任務(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
為驗證協(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
算例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)勢。
為了進一步驗證模型、協(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%。因此當承運人放棄現(xiàn)貨市場任務(wù)N1和N5時,其車輛行駛總里程和空載距離均不同程度的減少,且收益從-528.3元增加到943.7元。
表10 結(jié)果對比Table 10 Comparison of results
綜上可知,當不考慮線路間的協(xié)同效應(yīng)而盲目選擇增加托運任務(wù),可能會增加承運人的運輸成本,形成不合理的運輸方案。因此,筆者所提模型和基于托運任務(wù)協(xié)同效應(yīng)的求解策略可以幫助承運人在現(xiàn)貨市場選擇合適的托運任務(wù),以實現(xiàn)承運人收益最大化。
筆者以承運人收益最大化為目標,以車輛最大裝載貨運量和最大行駛距離為約束條件,構(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)用價值。