文/吳國游

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

一、引言：

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

二、問題描述

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

三、數學模型

（一）模型假設及符號說明

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

（二）上層決策模型

上層從平臺的整個物流網絡角度出發(fā)，以調度前后變動成本最小化為目標，建立任務分配決策模型如下：

目標函數（1）表示最小化平臺調度前后變動成本，即新增任務報價與調度成本之和，其中M為無窮大。約束條件（2）表示所有新任務都要被分配。

（三）下層決策模型

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

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

四、模型求解

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

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

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

Step3：下層將運算結果反饋給上層。

Step4：計算適應值。本文為雙層成本函數，參考文獻[6]的處理方式，選取上下層目標函數之和（minβ+minωk）作為適應度函數。

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

Step6：變異操作。本文運算過程中采用2點互異進行變異操作，改變其中部分基因的位置后，將產生的新個體加入子代。

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

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

五、算例分析

（一）算例結果分析

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

（二）模型分析

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

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

參考文獻[6]的求解思路，對上述單層雙目標模型做如下處理，其中（λ，η）為權重參數。

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

表1 不同權重下單層模型運行結果

表2 不同權重下單層模型運輸任務組合

六、結論：

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