基于調(diào)度引擎服務(wù)的智能線路優(yōu)化研究

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

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

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

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

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

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

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

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

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

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

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

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

2.線路的選擇

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

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

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

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

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

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

解題步驟如下：

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

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

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

方案舉例：

假設(shè)三角形AiA6A7的外圍路線A6A7是斷開線路，則先斷開A6A7，然后按照上面所說的兩個(gè)條件查找其他的斷開線路，此時(shí)得方案為（圖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ù)分配算法，每個(gè)任務(wù)都有一定的價(jià)值，各個(gè)小車執(zhí)行不同的任務(wù)，行走的路徑不同會(huì)導(dǎo)致執(zhí)行任務(wù)代價(jià)不一。小車綜合評(píng)價(jià)各個(gè)任務(wù)后，對(duì)收益最高的任務(wù)進(jìn)行投標(biāo)，通過拍賣的方式競(jìng)爭(zhēng)任務(wù)的執(zhí)行權(quán)，經(jīng)過多輪的任務(wù)和路徑優(yōu)化后，最終達(dá)到分配結(jié)果的最優(yōu)圖，如圖3。

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

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

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

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

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

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

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

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

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

圖3 前后路徑對(duì)比

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

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

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

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

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

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

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

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

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

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

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

4.結(jié)果分析

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

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

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

三、結(jié)語

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