文 / 黃 婧 李 樂 曹云祥 陳 浩 邵世洲 肖光偉 肖龍恩 周彬偉 王黎明 袁佩玲

隨著全球信息化的不斷發(fā)展，物流行業(yè)得到了飛速發(fā)展。由于運輸業(yè)務(wù)多、車輛裝載率低，物流運輸費用超過了庫存費用，同時由于貨物及時配送服務(wù)與城市交通狀況直接的矛盾，物流配送車輛路徑優(yōu)化成為物流系統(tǒng)最為關(guān)鍵的一環(huán)，對整個物流運輸成本、效益和速度至關(guān)重要，因此如何選擇最優(yōu)物流配送車輛路徑，及時將貨物送到客戶手中，成為物流研究領(lǐng)域中的熱點問題。

物流配送車輛路徑優(yōu)化問題是以最少車輛數(shù)、最小車輛總行程完成貨物的配送任務(wù)，從而達(dá)到成本最小或時間最短等目標(biāo)。對于物流配送車輛路徑問題，傳統(tǒng)優(yōu)化方法搜索時間長，難以找到最優(yōu)路徑，造成物流配送成本高。為了降低物流配送成本，提高車輛路徑優(yōu)化效率，提出一種調(diào)度引擎服務(wù)的物流配送車輛路徑優(yōu)化算法。首先，對物流配送車輛路徑基礎(chǔ)數(shù)據(jù)進行錄入，然后建立相應(yīng)的應(yīng)用數(shù)據(jù)模型，最后采用調(diào)度引擎對車輛路徑問題的運輸場景模型進行求解。通過具體實例對算法進行試驗，結(jié)果表明，調(diào)度引擎服務(wù)提高尋優(yōu)效果，找到物流配送車輛路徑的最優(yōu)算法，降低物流配送成本，并為物流配送車輛路徑選擇提供了一種有效算法。

一、基于車輛配載線路優(yōu)化問題的建模

1.調(diào)度引擎模型建設(shè)

物流配送車輛調(diào)度實質(zhì)就是走什么樣的路線進行運輸?shù)膯栴}，其描述為：在車輛載重量和各客戶需求量已知的前提下，至少派多少輛車才能滿足需求且車輛的總行程最短，從而找到最小成本的配送方案，同時要去滿足以下條件：

(1)每一個客戶只被一輛車訪問一次，每輛車只服務(wù)一條線路。

(2)所有配送車輛以配送中心為起點并最終回到物流配送中心。

(3)每條配送路徑上客戶需求量之和不能超過車輛的載重量。

(4)每輛車所走的路線盡量不能重復(fù)。

綜上所述可知，本項目重點是解決湖北中煙的城市干線運輸配送問題，湖北中煙省內(nèi)共有 6 家工廠（A、B、C、D、E、F），這些工廠生產(chǎn) 90～100個品規(guī)的香煙，工廠間的距離在 100～600公里之間，同一個品規(guī)的香煙有可能在多個工廠同時生產(chǎn)。各個配送中心需要從幾家不同工廠訂購數(shù)量、品規(guī)各異的香煙，截單時間為每天上午9:00和下午16:00；當(dāng)天9:00之前收到的所有訂單均當(dāng)日內(nèi)完成派送處理，所以車輛在8:30左右來工廠倉庫取貨運走；當(dāng)天16:00之后收到的所有訂單將在次日處理，車輛一般在次日早上8:30來工廠倉庫取貨。由于車輛運輸距離較長，一般路上要行駛幾天才能運抵目的地。通常，從不同工廠訂購不同品規(guī)的香煙，配載問題比較突出?？紤]車輛的行程距離和裝載量，目前車輛完成一次配載可以最多到3 個工廠倉庫配載，然后將它們運送到最多 4 個配送中心。在每個卷煙廠倉庫裝貨時，要考慮裝貨的先后順序，以便到達(dá)不同客戶站點卸貨時能夠避免倒箱操作。這樣可方便用1輛車從 3 個以上卷煙廠倉庫配載不同品規(guī)的香煙配送給1個配送中心，避免使用多輛車?？紤]運輸貨值較高，因此每輛車駕駛室都安裝有定位裝置和攝像頭，車輛行駛的實時地理位置會更新到TMS系統(tǒng)；TMS系統(tǒng)會定期維護限定司機行駛的路線，并監(jiān)控司機行駛是否偏離規(guī)定路線，如出現(xiàn)異常偏離，給出預(yù)警信息。

煙草公司都有自己專用的地圖數(shù)據(jù)庫，用來規(guī)劃運輸調(diào)度；TMS系統(tǒng)可以訪問煙草公司的內(nèi)部地圖數(shù)據(jù)庫，目前該TMS系統(tǒng)應(yīng)用華為調(diào)度引擎系統(tǒng)將配載站點序列信息發(fā)送至TMS系統(tǒng)，TMS系統(tǒng)根據(jù)調(diào)度引擎給出路線優(yōu)化（選擇可通行街道路線）的結(jié)果安排車輛調(diào)度，同時監(jiān)控司機是否在指定路線上行駛。

2.線路的選擇

現(xiàn)以多節(jié)點路線選擇問題為例，將運輸費用最低和運輸時間最短作為目標(biāo)函數(shù)，建立多目標(biāo)函數(shù)的數(shù)學(xué)模型。

假設(shè)從i城市到j(luò)城市要經(jīng)過M個地點節(jié)點，各地點節(jié)點有N種運輸方式可供選擇。在綜合時效性、經(jīng)濟性等因素的影響下，決策出運輸費用最低、運輸時間最短的最優(yōu)路線。數(shù)學(xué)模型以運費最低、運輸時間最短作為優(yōu)化目標(biāo)，假設(shè)物品的運輸費用為Q1，運輸時間為Q2，運輸時間成本為Q3，現(xiàn)建立如下數(shù)學(xué)模型：

①最優(yōu)目錄函數(shù)：Q最優(yōu)=min{Q1+Q2}運輸費用：

運輸時間成本：Q3=δ1Q2（δ1（時間變量）≧0，運輸時間不考慮在成本內(nèi)時，Q3=0）

3.線路的優(yōu)化

武漢物流中心A1向10個客戶Ai（i=1、2、...10）配送貨物，其配送網(wǎng)絡(luò)如圖1，線路上的數(shù)字表示兩者之間的距離，配送中心有裝載量0.3t和0.7t的車若干輛，試制定最優(yōu)送貨方案。

解題步驟如下：

(1)整個外圍路線連線總里程：每個客戶之間距離綜合S=56KM

(2)該系統(tǒng)中所有的三角邊差，如表1【例：三角邊差為三角形AiA6A7中兩條星型線路AiA6、AiA7之間與外圍線路A6A7的差稱為三角形邊差（）】。

(3)由表1可以看出三角邊差最小的星型三角形有三角形AiA6A7、三角形AiA7A8、三角形AiA8A9三個，因此有三種方案：

方案舉例：

假設(shè)三角形AiA6A7的外圍路線A6A7是斷開線路，則先斷開A6A7，然后按照上面所說的兩個條件查找其他的斷開線路，此時得方案為（圖2）；

送貨車輛：2（0.7t）+1（0.3t）（共3輛）；

圖1 配送路線

圖2 最優(yōu)路徑

送貨線路：Ai-A3-A2-A1-A10-Ai(0.7t)、Ai-A6-A5-A4-Ai(0.7t)和Ai-A7-A8-A9-Ai（0.3t）；

線路優(yōu)化的核心算法是采用基于拍賣的任務(wù)分配算法，每個任務(wù)都有一定的價值，各個小車執(zhí)行不同的任務(wù)，行走的路徑不同會導(dǎo)致執(zhí)行任務(wù)代價不一。小車綜合評價各個任務(wù)后，對收益最高的任務(wù)進行投標(biāo)，通過拍賣的方式競爭任務(wù)的執(zhí)行權(quán)，經(jīng)過多輪的任務(wù)和路徑優(yōu)化后，最終達(dá)到分配結(jié)果的最優(yōu)圖，如圖3。

二、基于調(diào)度引擎下的線路優(yōu)化案例分析

1.數(shù)據(jù)參數(shù)輸入

商品信息：卷煙成品、原料、輔料、半成品、宣傳品等運輸物資，其運輸物資基本屬性包括訂單號（唯一）、裝貨地信息、卸貨地信息、最早要求到貨時間、最晚要求到貨時間、運單量。

運輸車輛信息：與中煙公司簽訂運輸協(xié)議的承運商公司以及中煙公司自有的車輛。

地點信息：倉庫信息、商業(yè)公司地點信息、虛擬倉庫信息、分區(qū)信息（按訂單運輸區(qū)域劃分）、倉庫提貨時間、商業(yè)公司營業(yè)時間等。

車輛信息：車輛類型、載重容積、最大站點數(shù)/件數(shù)、區(qū)域限制、運輸商品信息等。

訂單信息：商品重量體積、提卸貨地點、分區(qū)信息、裝卸效率、提卸貨停留時間等。

計費信息：中煙公司給到的各區(qū)域計費表、承運商信息、不同商品的計費公式、噸位折算公式或標(biāo)準(zhǔn)。

表1 系統(tǒng)中所有的三角邊差

圖3 前后路徑對比

表2 業(yè)務(wù)場景各種約束和調(diào)整

距離矩陣數(shù)據(jù)：需要提前準(zhǔn)備好運輸?shù)攸c經(jīng)緯度以及兩兩之間的距離數(shù)據(jù)。

2.線路規(guī)劃參數(shù)設(shè)置

線路規(guī)劃及優(yōu)化：在考慮業(yè)務(wù)場景各種約束條件之下，以運輸成本最低為目標(biāo)，給到最終規(guī)劃的路徑，包括車次信息、各車次站點順序、裝載率、車次總體積、車次總距離、工作時長、所屬區(qū)域、對應(yīng)的訂單信息、預(yù)計到達(dá)發(fā)貨倉庫時間、預(yù)計離開發(fā)貨倉庫時間、預(yù)計到達(dá)卸貨倉庫時間、預(yù)計離開卸貨倉庫時間。

線路調(diào)整：基于系統(tǒng)輸出的車次，可以進行人工干預(yù)，調(diào)整車次上站點順序、調(diào)整不同車次上運單的分配。

參數(shù)調(diào)整：根據(jù)實際業(yè)務(wù)場景，可以針對裝卸貨效率、沿線配載角度、提卸貨停留時長、可拼載最大站點數(shù)、要求的裝載率目標(biāo)這些參數(shù)進行調(diào)整。

3.業(yè)務(wù)場景覆蓋

單點提多點送：同時考慮到訂單要求的到貨時間，按沿線進行配載；考慮提卸貨的停留時間和裝卸效率；考慮道路的擁堵情況（設(shè)置擁堵系數(shù)），可把訂單按區(qū)域進行配送；考慮超載情況。

多點提單點卸：同時考慮提卸貨時間要求，按業(yè)務(wù)區(qū)域劃分；考慮停留時間和裝卸效率；考慮超載情況。

多點提多點送：無需考慮邊提邊送的業(yè)務(wù)場景；需考慮訂單的提卸貨時間和裝卸效率；可考慮超載情況。

在上述三種場景中都支持商品和車輛的對應(yīng)關(guān)系、車輛和運輸?shù)攸c（不一定是單個省市或者倉庫）的對應(yīng)、運輸?shù)攸c和商品的關(guān)系對應(yīng)。

4.結(jié)果分析

調(diào)度引擎優(yōu)化后的結(jié)果顯示行程數(shù)量會減少，提升了整體資源和車載量空間的利用率，減少行駛里程和配送時間，從而降低總運輸成本。一方面，我們可以查驗一下針對現(xiàn)有行程的設(shè)定條件和驗算結(jié)果是否有效；另一方面，我們還會通過下面的方法進一步降低運輸成本。

調(diào)度引擎服務(wù)的優(yōu)化算法可以應(yīng)對訂單的動態(tài)變化，比如有新訂單加入、訂單內(nèi)容（數(shù)量/品規(guī)）變化等。如果在當(dāng)天截單后又來了新訂單請求，則系統(tǒng)會盡快確認(rèn)是否可以將其添加到現(xiàn)有行程規(guī)劃中，即使車輛已在第一個工廠取貨完畢，新訂單仍有機會在第二工廠取貨前添加進來完成及時配載。因此，通過深層次的訂單合并會進一步提高資源利用率；如果訂單內(nèi)容（比如裝箱數(shù)量）有變化，這些信息也會及時在系統(tǒng)里自動更新。優(yōu)化算法會自動從可用車隊選擇不同運輸服務(wù)公司提供的最便宜車輛（依據(jù)每個站點的可用車輛信息），來降低總運輸成本。

調(diào)度引擎服務(wù)提供 API 接口，用來直接集成訂單和車輛數(shù)據(jù)，如，技術(shù)數(shù)據(jù)、倉庫信息、區(qū)域信息、距離信息、運價規(guī)則信息、引擎接口緩存，第一次初始化后，如果沒有變動，時間配載時就不需要帶基礎(chǔ)數(shù)據(jù)參數(shù)。

三、結(jié)語

合理地規(guī)劃物流運輸系統(tǒng)中車輛的線路，是提高物流企業(yè)經(jīng)濟效益的關(guān)鍵。本文針對物流配送車輛線路優(yōu)化問題進行分析，針對當(dāng)前存在的問題，利用調(diào)度引擎服務(wù)分析，搜索具有并行性和速度快的特點，提出一種基于引擎算法的物流配送車輛線路優(yōu)化問題求解方法。通過對比試驗對其進行驗證，結(jié)果表明，本方法提高了尋優(yōu)效率，能夠快速找到最優(yōu)線路，在物流配送車輛線路優(yōu)化中有著廣闊的應(yīng)用前景。