智能運輸調(diào)度系統(tǒng)求解機制研究與實現(xiàn)*

任中明 蔡延光

（廣東工業(yè)大學(xué) 自動化學(xué)院）

1 引言

減少運輸費用是降低物流成本的重要手段[1]，而運輸費效比又與調(diào)度方案的優(yōu)劣密切相關(guān)。運輸調(diào)度是物流企業(yè)中的核心作業(yè)，對于降低物流成本及提高服務(wù)水平具有關(guān)鍵作用。合理正確的調(diào)度可以有效減少車輛的空駛率，實現(xiàn)合理路徑運輸并有效減少運輸成本。同時，在現(xiàn)代物流管理中，運輸調(diào)度的工作量大、技術(shù)性強，要實現(xiàn)調(diào)度過程優(yōu)化具有相當(dāng)難度。因此，對運輸調(diào)度的深入研究具有重要的社會效益和經(jīng)濟效益。

概括來說，運輸調(diào)度問題(Vehicle Routing and Scheduling Problems, VRP&VSP或VRSP) 是指能夠在滿足一定的約束條件（如車輛、時間窗、運輸數(shù)量要求及運輸能力限制等）下，給出適當(dāng)?shù)男熊嚶肪€和任務(wù)分配方案，達(dá)到一定的目標(biāo)（如綜合費用極少、路程最短、時間最少、使用車輛數(shù)盡量少等）。

VRSP模型具有類型多、約束條件多、變量多、結(jié)構(gòu)復(fù)雜及求解工作量大等特點。VRSP已被證明屬于NP-完全問題，具有擴展特征的VRSP也屬于NP-完全問題[2]。針對VRSP的求解問題，國內(nèi)外學(xué)者已提出的算法大體上分為三類：精確算法、近似算法和啟發(fā)式（智能）算法。經(jīng)典的精確算法有分支定界法、K樹算法、動態(tài)規(guī)劃法等。這類算法能夠求得問題的最優(yōu)解，并且具有求解速度快的優(yōu)點，但是缺點在于：往往只針對小規(guī)模的VRP問題有效，而且只能求解一些確定性、弱約束的理想化問題，難以用來求解NP-完全問題。近似算法則主要包括先路線后聚集、先聚集后路線、松弛法以及改進與交換法等算法。

采用近似算法能夠顯著縮小可行解的解空間并降低求解復(fù)雜度，但是采用近似算法來求解VRSP也只是在某種程度上的改善求解質(zhì)量，并不能處理實際復(fù)雜的多目標(biāo)優(yōu)化問題。啟發(fā)式（智能）算法不以找到精確解為目標(biāo)，而是在復(fù)雜問題中以可接受的代價給出問題的次優(yōu)解，代表算法有構(gòu)造算法、不完全優(yōu)化算法、節(jié)約算法、遺傳算法、模擬退火算法、蟻群算法、禁忌搜索算法、粒子群算法等。啟發(fā)式（智能）算法的應(yīng)用，可以在很大程度上緩解由于模型組合的復(fù)雜性及模型的不完備性而帶來的求解難度，有效地提升了對VRSP的求解效率，并使求解結(jié)果更趨于實用。然而，針對某一類VRSP問題采用某種（或改良的）智能算法來求解也許是可行及高效的，但是現(xiàn)實中的VRSP模型卻是受動態(tài)時變、多條件約束及環(huán)境不確定等因素緊密制約的。單一算法既不能適應(yīng)實際的復(fù)雜環(huán)境，也不能在應(yīng)對大多數(shù)的多目標(biāo)優(yōu)化運輸調(diào)度問題時給出滿意的可行方案。

基于以上分析可見，試圖用一種智能算法或是改良的智能算法去求解所有的VRSP是不可能的，也無法滿足對復(fù)雜多變環(huán)境的實際需求，采用此種方法開發(fā)出的系統(tǒng)通用性也較差，求解問題對象也受到很大的局限性。因此，開發(fā)一套簡潔、高效、知識化、實用性強并且具有一定智能處理能力的求解VRSP模型的軟件具有重要實際意義。應(yīng)用智能運輸調(diào)度系統(tǒng)可提高運輸調(diào)度工作效率和調(diào)度水平，降低物流運輸成本。針對VRSP問題，本文通過對典型運輸調(diào)度模型的分析，并結(jié)合模型類參數(shù)結(jié)構(gòu)[3]，提出一種基于智能框架的求解平臺的構(gòu)建方法和運行機制，并重點研究了VRSP模型類自動識別問題。

2 VRSP模型分析

自1959年VRP問題被Dantzig和Ramser首次提出以來，它的數(shù)學(xué)模型就隨著研究的深入而不斷得到擴充完善，出現(xiàn)了各種針對不同問題，包含不同約束內(nèi)容及變量條件的數(shù)學(xué)模型[4～5]，歸結(jié)起來有兩種風(fēng)格：基于車流的VRSP模型；基于物流的VRSP模型。本文采用基于物流的VRP模型，可表示為：

其中，式(1.1)為目標(biāo)函數(shù)，規(guī)定優(yōu)化目標(biāo)為所有車輛行駛的路徑最短；式(1.2)～(1.4)是車輛裝載能力限制，用來確保車輛的載貨量始終不超過其裝載容量；式(1.5)表示道路約束，保證車輛行駛的路徑長度不超過其最大里程；式(1.6)～(1.8)表示任務(wù)約束，式(1.6)用來確保每個客戶都被訪問到，且每條路徑上的客戶數(shù)不超過總客戶數(shù)；式(1.7)表示每條路徑的客戶的組成；式(1.8)限制每個客戶只能由一臺車輛服務(wù)；式(1.9)表示車輛k是否參加了配送，參加為1，否則為0。

從上述VRP數(shù)學(xué)模型可以看出VRP模型結(jié)構(gòu)復(fù)雜、規(guī)模龐大，同時具有參數(shù)眾多及數(shù)據(jù)關(guān)系復(fù)雜的特點?；赩RP的涵義，并分析公式模型可以看出VRSP模型事實上是由目標(biāo)參數(shù)、約束條件（多種約束的組合，包括供需點、車輛、時間、路徑等）以及變量三個部分組成。在結(jié)構(gòu)化處理VRSP模型的需求下，可以將VRSP模型的參數(shù)[3]分為標(biāo)準(zhǔn)模型參數(shù)和擴展模型參數(shù)兩大類。其中，標(biāo)準(zhǔn)模型包括：1-車隊結(jié)構(gòu)參數(shù)，2-供應(yīng)結(jié)構(gòu)參數(shù)，3-需求結(jié)構(gòu)參數(shù)，4-網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)，5-作業(yè)類型參數(shù)；擴展模型包括：6-約束條件參數(shù)，7-函數(shù)及數(shù)字特征參數(shù)，8-目標(biāo)函數(shù)參數(shù)。同時，鑒于計算機對自然語言理解的局限性，并為了方便計算機對模型求解目標(biāo)及約束條件的理解處理，對模型類的參數(shù)進行數(shù)字編碼。

以車隊結(jié)構(gòu)參數(shù)編碼含義為例說明（數(shù)字為編碼，-表示分割符，后面內(nèi)容為編碼含義）：則 1-車隊結(jié)構(gòu)參數(shù)下的各參數(shù)編碼方式如下：

11-車隊數(shù)量：111-一個；112-一個以上；113-待定。

12-車隊位置：121-固定；122-待定。

13-每個車隊擁有的車輛數(shù)：131-一輛；132-一輛以上；133-待定。

14-車輛重量：141-所有車輛的載重量相等；142-所有車輛的載重量不完全相等。

15-車輛類型：151-普通車輛；152-專用車輛；153-普通和專用車輛混合車隊。

采用同樣的編碼方式可以獲得所有已確定參數(shù)類型的模型參數(shù)編碼，限于文章篇幅，讀者可參閱參考文獻(xiàn)[3]中第2節(jié)模型分類與表示的相關(guān)內(nèi)容。

3 系統(tǒng)運行機制設(shè)計

VRSP模型類的表示方式為系統(tǒng)提供了運行支持，它負(fù)責(zé)為VRSP問題信息的人機交互、模型辨識、模型處理、知識化模型的生成、模型求解的整個處理過程提供模型表示支持。系統(tǒng)的詳細(xì)設(shè)計從數(shù)據(jù)組織、模型庫構(gòu)造、算法庫管理、規(guī)則庫構(gòu)造、經(jīng)驗庫構(gòu)造、學(xué)習(xí)機制及解題機制幾個方面依次入手。而系統(tǒng)在模塊上大體則可劃分為：輸入輸出模塊、知識庫管理模塊、學(xué)習(xí)子系統(tǒng)以及主處理程序模塊。同時，鑒于智能算法的在VRSP問題上的求解優(yōu)勢，依托該類算法特征進行系統(tǒng)運行機制的設(shè)計。采用此方法構(gòu)建的求解系統(tǒng)，能夠綜合利用智能算法求解大規(guī)模VRSP模型的優(yōu)勢和智能決策系統(tǒng)的計算經(jīng)驗來簡化VRSP的求解過程以及降低計算復(fù)雜程度。系統(tǒng)運行機制如圖1所示.

基于圖1所示的求解處理機制，系統(tǒng)的各個模塊的組成及功能如下：輸入輸出模塊包括輸入?yún)?shù)信息和輸出規(guī)劃方案。知識庫管理模塊包括模型庫、算法庫、經(jīng)驗庫及規(guī)則庫管理及使用，模型庫用于存放已有過求解記錄的典型模型類，算法庫用來存放求解模型所用到的算法文件路徑或者算法代碼，同時提供算法的輸入輸出函數(shù)接口，規(guī)則庫是用于存儲從問題基本信息到問題模型表示的轉(zhuǎn)換規(guī)則，經(jīng)驗庫則存儲經(jīng)驗?zāi)Ｐ偷那蠼馑惴ń?jīng)驗。主處理程序模塊則包括模型預(yù)處理、模型識別及建立、模型求解、求解評估調(diào)優(yōu)幾個階段，對于其處理步驟以下做重點闡述。

3.1 模型預(yù)處理

由調(diào)度人員完成輸入VRSP模型的各種變量及參數(shù)信息。首先，由系統(tǒng)對輸入信息進行初次分類、整理、分析，篩選出無法為系統(tǒng)識別處理的條件，以備對規(guī)劃結(jié)果需進行調(diào)優(yōu)時作為參考條件用。然后，通過對輸入?yún)?shù)信息的分析、提取及再次整理，生成對應(yīng)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。在此過程中，針對規(guī)模較大的網(wǎng)絡(luò)拓?fù)鋾r，可以考慮采用近似算法來縮小可行解的搜索空間以降低求解復(fù)雜程度，如采用先聚集后路線的算法將部分集中的點作為一個點來處理，在完成總體的求解后，再將此點分解為一個子拓?fù)渚W(wǎng)絡(luò)進行迭代求解。最后，根據(jù)篩選后的參數(shù)信息，結(jié)合VRSP模型的類參數(shù)編碼規(guī)則，生成對應(yīng)參數(shù)的編碼。

3.2 模型識別及建立

根據(jù)之前生成的對應(yīng)參數(shù)編碼，組合模型的編碼表示方式。依據(jù)VRSP模型的定義[3]，模型之間存在多種關(guān)系，如父子關(guān)系、相似關(guān)系、運算關(guān)系、等價關(guān)系、派生子類等。這些關(guān)系的存在不僅極大的擴展了模型類的類型，同時也為模型的求解提供了極大的有利條件。對模型之間的關(guān)系的探究，對降低模型的復(fù)雜程度、縮減可行解的狀態(tài)空間數(shù)量以及減少求解的運算量都能起到積極作用。

（1）父類與子類

模型的父子關(guān)系可以簡單描述為集合中的包含關(guān)系。例如，如果VRSP模型中車隊數(shù)量取值為待定，其實數(shù)量就包含了一個及一個以上，此時假定其他的條件都相同，并且已存在對單車隊的求解，如果再去求解待定車隊的問題，則對單車隊的求解經(jīng)驗完全可作為經(jīng)驗解調(diào)用。此關(guān)系對其它參數(shù)（如每個車隊擁有的車輛數(shù)、車輛類型及供應(yīng)點數(shù)量等）同樣適用。

（2）相似類

由于VRSP模型類的不完備性，使得獲取的新模型的模型結(jié)構(gòu)不可預(yù)料以及新模型的經(jīng)驗算法可能不存在。此時，通過引入逆反算子、松弛算子等手段來獲取相似類，進而通過與相似類的類比、自動學(xué)習(xí)獲取求解經(jīng)驗，導(dǎo)出對問題求解的新算法。

（3）類的運算

VRSP模型類的參數(shù)標(biāo)準(zhǔn)化也為模型類的運算提供了支持。模型的運算包括交、并、補等運算方式。其運算關(guān)系等價于集合的交、并、補運算。特殊之處在于，模型類的運算在于為模型庫的擴展找到一條切實有效的途徑，并可以通過運算分解或組合要求解的模型，充分利用已有求解經(jīng)驗來達(dá)到求解實際問題的目的。

（4）等價類

在VRSP模型中引入等價類是為了實現(xiàn)在求解概念意義上相同的模型的算法的互用。等價類在很大程度上與輸入的參數(shù)有關(guān)，也是多樣的。例如，假定VRSP模型中的其他條件相同，則車輛數(shù)為1且車輛載重量相等的任意類與車輛數(shù)為1且車輛載重量不全相等的任意類事實上是等價的，即為等價類。

（5）派生子類

通過一個多項式復(fù)雜度的單值或多值算子使模型類B變換得到的模型類為模型類A的子類，則說明兩個模型類具有派生子類的關(guān)系。

以上的模型關(guān)系可存放于規(guī)則庫中供模型求解過程中的各階段使用。當(dāng)然，模型的識別還要求在數(shù)據(jù)庫中已經(jīng)存在相應(yīng)的典型模型。通過對各種模型類的關(guān)系分析利用，可以實現(xiàn)在多數(shù)情況下對新模型的識別，也能夠充分利用模型結(jié)構(gòu)相似性、數(shù)據(jù)相似性和已有的計算經(jīng)驗來簡化求解過程以及降低計算復(fù)雜程度。

3.3 模型求解

模型關(guān)系的確定有利于模型的簡化及運算，因此要充分利用模型之間的各種關(guān)系來進行模型求解。例如，假設(shè)模型類A為模型類B的父類，適合A的求解算法不存在而適合B的求解算法存在，則優(yōu)先采用B的求解算法進行求解。同樣，相似關(guān)系、等價類及派生關(guān)系的確定，也可以使模型求解時充分利用已有的典型模型類的求解經(jīng)驗，簡化模型類求解方式，降低求解復(fù)雜度。模型求解的主要步驟如下：

(1) 篩選模型庫和經(jīng)驗庫，查找是否存在相同的模型類，如果存在則直接調(diào)用已存儲模型類的處理經(jīng)驗，在參數(shù)相同的情況下可以直接調(diào)用其結(jié)論；如果不存在，轉(zhuǎn)入步驟（2）。

(2) 調(diào)用規(guī)則庫中存儲的模型類關(guān)系規(guī)則，根據(jù)規(guī)則依次核對新模型類與已存儲典型模型類之間是否存在父子關(guān)系、相似關(guān)系、運算關(guān)系、等價關(guān)系或派生子類。如果相應(yīng)的關(guān)系存在，則依據(jù)規(guī)則調(diào)用已存儲典型模型的處理算法（包括對算法的再處理）求解；如果不存在，轉(zhuǎn)入步驟 (3) 。

(3) 結(jié)合模型庫、經(jīng)驗庫及規(guī)則庫，針對新模型問題的特點進行分析，生成新的組合模型類，然后用推理機構(gòu)依據(jù)控制策略集中的控制策略調(diào)整任務(wù)分配方案，選擇比較適合的算法，求解此調(diào)度問題。

在上述步驟中，如果已有的算法不能夠滿足當(dāng)前模型類的求解，則需考慮采用算法的自動生成機制和局部調(diào)優(yōu)機制進行算法的重構(gòu)。但算法自動重構(gòu)的實現(xiàn)也面臨著相當(dāng)多的挑戰(zhàn)，需要在實踐中不斷深入研究和完善，并最終達(dá)到實用化目的。

3.4 求解評估調(diào)優(yōu)

首先，在對模型類進行求解之前，要依據(jù)VRSP模型的輸入信息和模型的約束參數(shù)，確定要優(yōu)化的目標(biāo)，并根據(jù)要優(yōu)化的目標(biāo)和采用的智能算法采取對應(yīng)的評價手段及參考指標(biāo)。其次，采用人機協(xié)同尋優(yōu)的方式（人機協(xié)同尋優(yōu)可以盡量避免系統(tǒng)在運行中因陷入循環(huán)而無法獲取最終結(jié)果，或者因陷入局部最優(yōu)而得出不可接受的解）評價所獲得規(guī)劃方案是否合理，并在各種方案之間進行分析比較以獲取最可行的規(guī)劃方案；然后，如果獲得優(yōu)化方案不能滿足優(yōu)化目標(biāo)，則采用新的方式組合模型類，制定評價手段及參考指標(biāo)并求解，直到取得滿意的可行方案。最后，如果獲得的優(yōu)化方案滿足優(yōu)化目標(biāo)，則輸出經(jīng)優(yōu)化后的調(diào)度方案，并且對相應(yīng)的經(jīng)驗庫、模型庫進行更新，同時存儲此典型模型類的求解案例。

4 系統(tǒng)的實現(xiàn)

作者采用Delphi7.0編程工具，并在SQL Server 2000數(shù)據(jù)庫環(huán)境下，在Windows XP 操作系統(tǒng)上編程實現(xiàn)的智能運輸調(diào)度求解系統(tǒng)的原型系統(tǒng)，初步實現(xiàn)了部分功能及界面。該系統(tǒng)由Delphi7.0實現(xiàn)流程控制與人機交互界面的顯示，由SQL Server 2000數(shù)據(jù)庫系統(tǒng)存儲系統(tǒng)的模型類參數(shù)庫、模型庫、求解經(jīng)驗庫及規(guī)則庫。如圖2所示為系統(tǒng)在輸入?yún)?shù)后的新模型生成界面。

圖2 模型生成界面

5 結(jié)束語

本文根據(jù)復(fù)雜運輸調(diào)度問題的研究狀況和發(fā)展趨勢，簡要分析了各種VRSP模型求解算法優(yōu)缺點，提出了一種基于VRSP模型參數(shù)結(jié)構(gòu)化分類的智能求解平臺的構(gòu)建思路和運行機制。在此基礎(chǔ)上，嘗試用人機結(jié)合和集成多種技術(shù)的方式來構(gòu)建開放的、智能化的、可重構(gòu)的決策支持系統(tǒng)來求解復(fù)雜運輸調(diào)度問題。仿真分析和初步應(yīng)用的效果令人滿意。證明其在處理復(fù)雜運輸調(diào)度問題上具有相當(dāng)大的潛力。

[1]張燕華,俞健,朱大均.交通經(jīng)濟學(xué)[M].上海社會科學(xué)院出版社,1998:115-119.

[2]Lenstra J K, Rinnooy Kan A H G.Complexity of vehicle routing and scheduling problems[J].Networks, 1981,11:221-227.

[3]蔡延光,錢積新,孫優(yōu)賢.智能運輸調(diào)度系統(tǒng)模型庫構(gòu)造與管理[J].系統(tǒng)工程理論與實踐,2000(9):83-90.

[4]魏明,蔡延光.一種基于混沌領(lǐng)域搜索的自適應(yīng)混沌遺傳算法[J].計算機應(yīng)用研究, 2009,26(2):464-465.

[5]蔡延光,宋康,張敏捷,武鑫.自適應(yīng)多目標(biāo)混合差分進化算法在聯(lián)盟運輸調(diào)度中的應(yīng)用[J].計算機應(yīng)用, 2010,30(11)：2887-2890.

[6]郎茂祥.裝卸混合車輛路徑問題的模擬退火算法研究 [J].系統(tǒng)工程學(xué)報,2005,20(5): 485-491.