任中明 蔡延光

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

1 引言

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

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

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

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

基于以上分析可見，試圖用一種智能算法或是改良的智能算法去求解所有的VRSP是不可能的，也無法滿足對復雜多變環(huán)境的實際需求，采用此種方法開發(fā)出的系統(tǒng)通用性也較差，求解問題對象也受到很大的局限性。因此，開發(fā)一套簡潔、高效、知識化、實用性強并且具有一定智能處理能力的求解VRSP模型的軟件具有重要實際意義。應用智能運輸調(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ù)學模型就隨著研究的深入而不斷得到擴充完善，出現(xiàn)了各種針對不同問題，包含不同約束內(nèi)容及變量條件的數(shù)學模型[4～5]，歸結(jié)起來有兩種風格：基于車流的VRSP模型；基于物流的VRSP模型。本文采用基于物流的VRP模型，可表示為：

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

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

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

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

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

3.1 模型預處理

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

3.2 模型識別及建立

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

（1）父類與子類

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

（2）相似類

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

（3）類的運算

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

（4）等價類

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

（5）派生子類

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

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

3.3 模型求解

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

(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)系或派生子類。如果相應的關(guān)系存在，則依據(jù)規(guī)則調(diào)用已存儲典型模型的處理算法（包括對算法的再處理）求解；如果不存在，轉(zhuǎn)入步驟 (3) 。

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

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

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

首先，在對模型類進行求解之前，要依據(jù)VRSP模型的輸入信息和模型的約束參數(shù)，確定要優(yōu)化的目標，并根據(jù)要優(yōu)化的目標和采用的智能算法采取對應的評價手段及參考指標。其次，采用人機協(xié)同尋優(yōu)的方式（人機協(xié)同尋優(yōu)可以盡量避免系統(tǒng)在運行中因陷入循環(huán)而無法獲取最終結(jié)果，或者因陷入局部最優(yōu)而得出不可接受的解）評價所獲得規(guī)劃方案是否合理，并在各種方案之間進行分析比較以獲取最可行的規(guī)劃方案；然后，如果獲得優(yōu)化方案不能滿足優(yōu)化目標，則采用新的方式組合模型類，制定評價手段及參考指標并求解，直到取得滿意的可行方案。最后，如果獲得的優(yōu)化方案滿足優(yōu)化目標，則輸出經(jīng)優(yōu)化后的調(diào)度方案，并且對相應的經(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ù)復雜運輸調(diào)度問題的研究狀況和發(fā)展趨勢，簡要分析了各種VRSP模型求解算法優(yōu)缺點，提出了一種基于VRSP模型參數(shù)結(jié)構(gòu)化分類的智能求解平臺的構(gòu)建思路和運行機制。在此基礎(chǔ)上，嘗試用人機結(jié)合和集成多種技術(shù)的方式來構(gòu)建開放的、智能化的、可重構(gòu)的決策支持系統(tǒng)來求解復雜運輸調(diào)度問題。仿真分析和初步應用的效果令人滿意。證明其在處理復雜運輸調(diào)度問題上具有相當大的潛力。

[1]張燕華,俞健,朱大均.交通經(jīng)濟學[M].上海社會科學院出版社,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)域搜索的自適應混沌遺傳算法[J].計算機應用研究, 2009,26(2):464-465.

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

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