□ 劉美玲，孟博冉，胡文杰

(華東交通大學(xué) 交通運輸與物流學(xué)院，江西 南昌 330013)

貨運O2O平臺致力于解決的貨運訂單匹配問題，是車輛路徑規(guī)劃(Vehicle Routing Problem，簡稱VRP)這一NP-hard難題在貨運行業(yè)的實際應(yīng)用。近年來，理論界對于車輛路徑規(guī)劃問題的研究從變換車輛容量、服務(wù)時間窗、訂單特殊需求等約束條件出發(fā)，衍生出了帶時間窗的、需求可拆分的、多車場的、半開放式車輛路徑規(guī)劃問題等多種貼合實際需求的VRP分支。學(xué)者們的研究也從對于尋求改進各類VRP優(yōu)化算法的理論探討，不斷向衍生車貨匹配數(shù)智化平臺的實際運用深化。

優(yōu)化算法求解方面：何小鋒等[1]同時運用量子蟻群算法、蟻群算法、改進遺傳算法和改進粒子群算法對帶有時間窗的車輛路徑規(guī)劃問題進行了求解，結(jié)果表明量子蟻群算法和改進的遺傳算法求解結(jié)果最優(yōu)，但在運行時間上量子蟻群算法有明顯優(yōu)勢；劉冉等[2]利用節(jié)約算法、順序插入算法、并行后悔插入算法三種啟發(fā)式算法對半開放式多車場車輛路徑問題進行了求解；楊鵬等[3]在帶有時間窗約束的基礎(chǔ)上，又增加了貨主需求可以被拆分的假設(shè)，利用改進的蟻群算法求解最優(yōu)路線配送方案；韓亞娟等[4]針對傳統(tǒng)軟時間窗的車輛路徑問題，提出了折現(xiàn)軟時間窗概念，利用超啟發(fā)式算法對于構(gòu)建的數(shù)學(xué)模型進行求解，并利用算例驗證算法的可行性；范厚明等[5]在引入局部優(yōu)化算法和擂臺法則的基礎(chǔ)上，設(shè)計了混合遺傳算法，對于Solomon的VRPTW標準算例進行求解，得出混合遺傳式算法在求解多目標優(yōu)化問題方面具有良好性能的結(jié)論。實際運用方面：劉枚蓮等[6]在考慮顧客即時需求的情況下，以碳排放和時間窗為約束條件，研究了車輛路徑優(yōu)化問題。

總的來說，有關(guān)車輛路徑規(guī)劃問題的研究碩果累累，但如何將理論研究成果運用到實際的復(fù)雜場景中仍然需要進一步的探索。本文以真實場景為基礎(chǔ)，建立模型約束條件，利用Anylogic軟件對場景進行模擬仿真，以求得最貼近實際情況的最優(yōu)解。

1 問題描述

根據(jù)現(xiàn)行貨運O2O平臺實際運營模式，在同城貨運中，大部分平臺采用“逐級推送”模式的車輛訂單匹配策略[7]，即在貨物匹配時以客戶訂單為中心進行車輛選取。本文以客戶需求為基礎(chǔ)，同時加入車輛容積、半開放等要求，使客戶訂單在最快的時間內(nèi)由最近的車輛完成配送，具體問題如下。

①軟時間窗約束在貨運中具有較強的現(xiàn)實意義，即在現(xiàn)實情況下，貨運O2O平臺中客戶對訂單完成的要求高于對時間的要求，因此訂單超時完成時，大部分顧客仍允許車輛完成訂單，只是會在一定程度上降低顧客滿意度；

②每個車輛有容積限制；

③車輛可訪問多條路徑；

④每個訂單只允許被訪問一次；

⑤車輛完成訂單后無需回到起點。

2 Anylogic模擬仿真設(shè)計

Anylogic是一款廣泛應(yīng)用于物流、供應(yīng)鏈等領(lǐng)域的仿真軟件，其基于多智能體的建模方法具有高效、低成本的優(yōu)勢。本文利用Anylogic軟件模擬問題描述中提到的現(xiàn)行貨運O2O平臺車輛調(diào)度和配貨方法，以計算出算例的最優(yōu)車貨匹配方案。

圖1為貨運O2O配貨在此平臺上的仿真模擬過程，具體方法如下：

圖1 仿真模擬過程

①實地調(diào)研和收集貨運訂單信息(如時間、交貨點、提貨點等信息)、車輛信息(如裝載量、單位運輸成本等信息)并生成EXCEL表格。

②新建一個智能體模型，在主函數(shù)中插入一個GIS地圖，功能為模擬車輛的行駛路徑。將收集的EXCEL表導(dǎo)入到主函數(shù)中。

③在智能體模型中新建訂單、車輛、配貨三個智能體類(如圖2)，用于描述平臺的配貨邏輯和過程。

圖2 新建訂單、車輛、配貨智能體類

實際流程邏輯圖如圖3所示，具體過程如下：

圖3 配貨邏輯

步驟1 訂單時間緊急程度排序。對訂單池中所有訂單進行統(tǒng)計后按照時間緊急順序進行排序，在后面進行訂單車輛分配時，以時間緊急程度為第一要求進行方案優(yōu)化；

步驟2 訂單分配車輛。選取現(xiàn)行訂單中時間最緊急的訂單1，優(yōu)先挑選離訂單1最近的車輛1，檢查車輛容積是否符合現(xiàn)行訂單量容積要求。如果訂單貨物容積<車輛剩余容積，則車輛與訂單匹配完成；如果訂單貨物容積>車輛剩余容積，則尋找車輛2，繼續(xù)檢查是否符合容積要求，按照此邏輯一直找尋到符合要求的車輛X完成訂單1；

步驟3 車輛集貨。車輛X完成訂單1配貨后，根據(jù)剩余容積=車輛原剩余容積-訂單1貨物容積繼續(xù)查看訂單池中剩余訂單中是否存在訂單m容積<剩余容積，若存在則將距離訂單1最近的訂單m1分配給車輛1；直至車輛無剩余集貨訂單，車輛集貨完成。

步驟4 繼續(xù)篩選剩余訂單。在步驟3完成后，進行新一輪的車輛分配和集貨，從當(dāng)前剩余訂單中，選出最緊急的訂單，按照步驟1-步驟3的邏輯進行訂單的車輛分配與車輛集貨步驟，完成車輛2集貨。

步驟5 所有訂單分配完成。在經(jīng)歷多輪配貨集貨之后，所有現(xiàn)行訂單都被完成，本次模擬仿真結(jié)束，得出一個最優(yōu)結(jié)果。

3 Anylogic求解算例

3.1 數(shù)據(jù)獲取與模型參數(shù)設(shè)置

本文對以貨拉拉為主的貨運O2O平臺進行了實際調(diào)研，了解各個平臺實際運作規(guī)則，針對規(guī)則進行算例數(shù)據(jù)獲取與模擬，得到送貨車輛信息(見表1)與貨主訂單信息(見表2)。

表1 送貨車輛信息

表2 貨主訂單信息

模型參數(shù)設(shè)置如下：單位裝卸貨時間成本為60元/小時；貨物裝卸時間系數(shù)為0.1小時/立方米；車輛平均行駛速度30千米/小時。

3.2 算例結(jié)果展示及分析

根據(jù)基本信息與模型參數(shù)設(shè)置進行Anylogic模擬仿真設(shè)計，能夠看到結(jié)果如圖4所示，在系統(tǒng)運行14∶49時，所有訂單都被匹配完成。

圖4 Anylogic模擬仿真結(jié)果

根據(jù)Anylogic仿真結(jié)果，車輛1、2、3、4、6完成10個訂單配送，訂單配送路線依次為：車輛1-5-3-13-15，車輛2-10-8-9-19-20-18，車輛3-1-4-14-11，車輛4-2-12，車輛5-6-16，車輛6-7-17(其中11-20分別代表1-10提貨點對應(yīng)的交貨點)。車輛1的行駛總路程為19.89千米，車輛2的行駛總路徑為46.87千米，車輛3的行駛總路徑為39.43千米，車輛4的行駛總路徑為22.83千米，車輛5的行駛總路徑為18.52千米，車輛6的行駛總路徑為39.29千米。根據(jù)設(shè)定的參數(shù)模型，求得運輸成本為1109.32元，裝卸貨成本為236.4元，總成本為1345.72元。

4 結(jié)語

本文利用Anylogic軟件，對貨運O2O平臺的車輛訂單匹配與路徑規(guī)劃問題進行了研究，通過加入車輛容積限制，以最大程度滿足客戶要求和實現(xiàn)車輛運輸配送成本最小化為目標，進行模擬仿真，以求得最優(yōu)車貨匹配方案。與啟發(fā)式算法不同的是，Anylogic計算結(jié)果為精確的解析解，訂單匹配耗時較長。在實際情況中，處理貨運O2O平臺的海量訂單不僅需要結(jié)果的精確度，更對求解的時間與速度提出了一個更高的要求，因此在后續(xù)研究中，如何利用多種啟發(fā)式方法以提高計算的速度與方案的優(yōu)越性是進一步研究的方向。