網(wǎng)絡(luò)貨運(yùn)平臺運(yùn)力優(yōu)化調(diào)度研究

文/吳國游

為優(yōu)化網(wǎng)絡(luò)貨運(yùn)平臺運(yùn)力調(diào)度，本文建立了雙層規(guī)劃模型，并采用基于精英選擇策略的遺傳算法對模型進(jìn)行求解。算例結(jié)果表明，相較于單層規(guī)劃模型而言，采用雙層規(guī)劃模型求解網(wǎng)絡(luò)貨運(yùn)平臺運(yùn)力資源調(diào)度優(yōu)化問題，能夠顯著提高運(yùn)力調(diào)度均衡性，并實(shí)現(xiàn)總成本41.31%~64.20%的節(jié)約。

一、引言：

網(wǎng)絡(luò)貨運(yùn)是指公路貨運(yùn)市場以承運(yùn)人的名義承攬貨源，與托運(yùn)人簽訂運(yùn)輸合同，承擔(dān)承運(yùn)人的責(zé)任和義務(wù)，然后將貨源外包給實(shí)際承運(yùn)人完成運(yùn)輸任務(wù)的道路貨物運(yùn)輸經(jīng)營者[1]。在網(wǎng)絡(luò)貨運(yùn)平臺中，大部分運(yùn)輸資源來自加入平臺的運(yùn)輸企業(yè)或運(yùn)輸個(gè)體，平臺通過利用網(wǎng)絡(luò)中所有可用的資源形成最終物流解決方案，將多個(gè)運(yùn)輸任務(wù)合并到幾個(gè)車輛中，以實(shí)現(xiàn)規(guī)模經(jīng)濟(jì)。目前針對運(yùn)力優(yōu)化調(diào)度問題，大多數(shù)文獻(xiàn)多從單一決策主體的角度進(jìn)行研究，如李麗瀅等[2]從物流集成商的角度，針對整車物流服務(wù)供應(yīng)鏈的運(yùn)力優(yōu)化調(diào)度問題，提出以準(zhǔn)時(shí)送達(dá)及最小化物流采購成本為目標(biāo)的雙層運(yùn)力優(yōu)化調(diào)度模型。Jiawei等[3]從承運(yùn)人角度，構(gòu)建了O2O平臺運(yùn)力優(yōu)化調(diào)度模型。楊東林等[4]從O2O平臺角度，構(gòu)建了中央集中分配O2O訂單的VRPSDP運(yùn)力優(yōu)化調(diào)度模型。此外，還有部分文獻(xiàn)從平臺和承運(yùn)人兩個(gè)決策主體進(jìn)行了研究，如常連玉等[5]以平臺收益最大化為目標(biāo)，承運(yùn)人能夠接受的利潤水平為約束條件。綜上，總結(jié)近幾年相關(guān)研究，可以得到現(xiàn)有文獻(xiàn)主要從平臺或承運(yùn)人角度對車輛進(jìn)行調(diào)度和路線安排，缺少對多方參與主體的分類研究。而在網(wǎng)絡(luò)貨運(yùn)平臺運(yùn)力資源優(yōu)化調(diào)度問題中，托運(yùn)人、網(wǎng)絡(luò)貨運(yùn)平臺、實(shí)際承運(yùn)人三者之間的關(guān)系是一種不穩(wěn)定的合作關(guān)系，必須考慮多方參與主體之間的協(xié)同關(guān)系，才能取得較好的決策結(jié)果。雙層規(guī)劃是一種建立分散決策模型的工具，與網(wǎng)絡(luò)貨運(yùn)平臺運(yùn)力資源優(yōu)化調(diào)度問題的特點(diǎn)相符，因此，本文可采用雙層規(guī)劃模型來研究網(wǎng)絡(luò)貨運(yùn)平臺運(yùn)力資源優(yōu)化調(diào)度問題。

二、問題描述

本文問題描述如下：考慮某網(wǎng)絡(luò)貨運(yùn)平臺有若干運(yùn)輸任務(wù)處于待分配狀態(tài)，且實(shí)際承運(yùn)人原有若干未完成的運(yùn)輸任務(wù)。從平臺角度需考慮不同的運(yùn)輸分配，實(shí)現(xiàn)調(diào)度前后變動(dòng)成本最小化。實(shí)際承運(yùn)人除了考慮運(yùn)輸成本，運(yùn)輸過程中的空載距離也是考慮因素之一。

三、數(shù)學(xué)模型

（一）模型假設(shè)及符號說明

模型假設(shè)如下：1）車輛運(yùn)輸能力能夠滿足客戶的運(yùn)輸需求；2）假定車輛當(dāng)前位置為已取貨但未配送運(yùn)輸任務(wù)的取貨地，且為車輛的起點(diǎn)；3）車輛最初都是從車場出發(fā)，完成所有任務(wù)后直接空車回到車場。符號及參數(shù)表達(dá)：S代表車場，點(diǎn)集合為V，所有任務(wù)集合為R，新任務(wù)集合L，所有可能的新任務(wù)分配組合?γ∈{γn}，任務(wù)r的起點(diǎn)終點(diǎn)分別為Or、Dr，K實(shí)際承運(yùn)人集合，β網(wǎng)絡(luò)貨運(yùn)平臺調(diào)度前后變動(dòng)成本，ωk實(shí)際承運(yùn)人k運(yùn)輸成本增量，Ck未接受新任務(wù)時(shí)實(shí)際承運(yùn)人k計(jì)劃路線行駛的運(yùn)輸成本，Pk，實(shí)際承運(yùn)人k對新增運(yùn)輸組合的報(bào)價(jià)，ρ實(shí)際承運(yùn)人運(yùn)輸利潤率，c單位運(yùn)輸成本，dij表示地點(diǎn)到地點(diǎn)j的距離，c1車輛調(diào)度成本，tik實(shí)際承運(yùn)人k到達(dá)點(diǎn)i的時(shí)刻，si地點(diǎn)i的服務(wù)時(shí)間，tij地點(diǎn)i到地點(diǎn)j的行駛時(shí)間，Q配送車輛最大載重，qik實(shí)際承運(yùn)人k在地點(diǎn)i的取貨量（配送量），Qki實(shí)際承運(yùn)人k在離開點(diǎn)i時(shí)車輛的載重，dijk實(shí)際承運(yùn)人k的空載距離，Dkmax實(shí)際承運(yùn)人k能接受的最大空載距離，xyk將任務(wù)組γ分配給實(shí)際承運(yùn)人k為1否則為0，實(shí)際承運(yùn)人從點(diǎn)行駛到點(diǎn)為1否則為0，實(shí)際承運(yùn)人接受任務(wù)組為1否則為0。

（二）上層決策模型

上層從平臺的整個(gè)物流網(wǎng)絡(luò)角度出發(fā)，以調(diào)度前后變動(dòng)成本最小化為目標(biāo)，建立任務(wù)分配決策模型如下：

目標(biāo)函數(shù)（1）表示最小化平臺調(diào)度前后變動(dòng)成本，即新增任務(wù)報(bào)價(jià)與調(diào)度成本之和，其中M為無窮大。約束條件（2）表示所有新任務(wù)都要被分配。

（三）下層決策模型

最小化運(yùn)輸成本增量作為下層模型目標(biāo)，空載距離為決策重要因素，建立下層決策模型如下：

目標(biāo)函數(shù)（3）表示最小化實(shí)際承運(yùn)人運(yùn)輸成本增量；約束條件式（4）、（5）和式（6）表示若實(shí)際承運(yùn)人接受任務(wù)組分配，則組內(nèi)任務(wù)一定會(huì)被該實(shí)際承運(yùn)人服務(wù)；式（7）表示上層決策變量與下層決策變量間的關(guān)系；式（8）表示車輛裝載不超過最大負(fù)載；式（9）表示車輛最后都要回到車場；式（10）表示每筆訂單都是先取貨再送貨；式（11）表示流量平衡；式（12）表示車輛空載距離不能超過實(shí)際承運(yùn)人能接受的最大空載距離；式（13）表示實(shí)際承運(yùn)人對新增任務(wù)向網(wǎng)絡(luò)貨運(yùn)平臺的報(bào)價(jià)。

四、模型求解

針對本文雙層規(guī)劃問題，設(shè)計(jì)了基于精英選擇策略的遺傳算法對上述模型進(jìn)行求解，基本思路：首先根據(jù)上層規(guī)劃生成初始種群，然后下層進(jìn)行路徑優(yōu)化，將下層運(yùn)算結(jié)果傳遞給上層，最后通過選擇、交叉、變異操作進(jìn)行優(yōu)化。算法流程如下所示。

Step1：初始化，根據(jù)上層規(guī)劃生成初始種群，設(shè)置交叉概率Pc，突變概率Pm，種群規(guī)模為g，最大迭代數(shù)Maxgen，初始迭代數(shù)gen=0。

Step2：將染色體傳遞給下層進(jìn)行路徑優(yōu)化。

Step3：下層將運(yùn)算結(jié)果反饋給上層。

Step4：計(jì)算適應(yīng)值。本文為雙層成本函數(shù)，參考文獻(xiàn)[6]的處理方式，選取上下層目標(biāo)函數(shù)之和（minβ+minωk）作為適應(yīng)度函數(shù)。

Step5：交叉操作。父代中的每一條染色體根據(jù)交叉概率Pc與不同染色體進(jìn)行交叉產(chǎn)生新的染色體加入子代。

Step6：變異操作。本文運(yùn)算過程中采用2點(diǎn)互異進(jìn)行變異操作，改變其中部分基因的位置后，將產(chǎn)生的新個(gè)體加入子代。

Step7：選擇操作，采用精英選擇策略。第t代產(chǎn)生g'個(gè)子代，為保持種群規(guī)模大小不變，對子代群體適應(yīng)值升序排列，選擇前g個(gè)個(gè)體，再將新種群加入父代種群，通過同樣選擇策略生成新的父代。

Step8：重復(fù)執(zhí)行Step2~Step7，直到算法運(yùn)行次數(shù)達(dá)到Maxgen時(shí)，終止運(yùn)行并輸出最優(yōu)方案。

五、算例分析

（一）算例結(jié)果分析

本算例部分信息來源于文獻(xiàn)[7]，5個(gè)實(shí)際承運(yùn)人已有運(yùn)輸任務(wù)數(shù)量分別為4、6、4、5、5?，F(xiàn)有10個(gè)新運(yùn)輸任務(wù)需分配。實(shí)際承運(yùn)人新增運(yùn)輸線路能產(chǎn)生20%的利潤，單位運(yùn)輸成本2元/公里，調(diào)度成本5元/輛，車輛最大載重10t。利用本文算法對算例進(jìn)行求解，算法參數(shù)設(shè)置如下：種群大小為30，交叉概率為0.8，變異概率為0.3，最大迭代數(shù)為20，由MatlabR2019a進(jìn)行計(jì)算，得出實(shí)驗(yàn)最優(yōu)結(jié)果運(yùn)行時(shí)間為77s，最優(yōu)總成本為217.84元。即將任務(wù)10分配給實(shí)際承運(yùn)人，任務(wù)4/5分配給實(shí)際承運(yùn)人，任務(wù)3/7/8分配給實(shí)際承運(yùn)人k3，任務(wù)9分配給實(shí)際承運(yùn)人k4，任務(wù)1/2/6分配給實(shí)際承運(yùn)人k5，使得平臺調(diào)度前后變動(dòng)成本最小且能夠與實(shí)際承運(yùn)人合作。

（二）模型分析

非線性雙層規(guī)劃問題對應(yīng)的多目標(biāo)規(guī)劃問題的最優(yōu)解，已被證明不是非線性雙層規(guī)劃問題的最優(yōu)解，因此為了驗(yàn)證雙層規(guī)劃能有效地解決該問題，則構(gòu)建對應(yīng)的單層雙目標(biāo)模型來進(jìn)行結(jié)果比較。對應(yīng)單層雙目標(biāo)模型如下：

式（14）的約束條件為，式（2）和式（4）~（14）。

參考文獻(xiàn)[6]的求解思路，對上述單層雙目標(biāo)模型做如下處理，其中（λ，η）為權(quán)重參數(shù)。

單層模型同樣采用本文遺傳算法進(jìn)行求解，運(yùn)行結(jié)果如表1表2所示。通過表1、表2與雙層模型實(shí)驗(yàn)結(jié)果相比較，可得到從總成本角度，雙層規(guī)劃的解均比處理后的單層規(guī)劃的解要優(yōu)，總成本降低了41.31%~64.20%。在單層模型中，不同加權(quán)比值下實(shí)際承運(yùn)人間運(yùn)輸任務(wù)數(shù)量最大差值分別為3/6/6，運(yùn)輸任務(wù)量標(biāo)準(zhǔn)差分別為1.04/2.29/2.14。雙層規(guī)劃下，實(shí)際承運(yùn)人間運(yùn)輸任務(wù)數(shù)量最大差值為3，標(biāo)準(zhǔn)差為1.17?？芍?，相比于雙層規(guī)劃模型而言，單層模型下加權(quán)比值為1和10時(shí)，運(yùn)輸任務(wù)分配兩極分化嚴(yán)重，均衡性較差，加權(quán)比值為0.1時(shí)，盡管均衡性得到了改善，但其總成本與雙層規(guī)劃模型相比增加了64.20%。

表1 不同權(quán)重下單層模型運(yùn)行結(jié)果

表2 不同權(quán)重下單層模型運(yùn)輸任務(wù)組合

六、結(jié)論：

本文綜合考慮了平臺與實(shí)際承運(yùn)人之間的相互關(guān)系，建立雙層規(guī)劃模型對上述問題進(jìn)行研究，并采用基于精英選擇策略的遺傳算法對所建立模型進(jìn)行求解。算例分析結(jié)果表明，雙層規(guī)劃模型與單層模型相比，無論在總成本抑或在運(yùn)力分配均衡性方面，均具備顯著優(yōu)勢。因此，對網(wǎng)絡(luò)貨運(yùn)平臺而言，本文所提出的雙層規(guī)劃模型在節(jié)約成本、均衡運(yùn)力及維持穩(wěn)定合作關(guān)系方面均具有一定的參考意義。