基于決策樹機場電動及燃油特種車輛任務分配

費春國，尚德軒

（中國民航大學電子信息與自動化學院，天津 300300）

基于決策樹機場電動及燃油特種車輛任務分配

費春國，尚德軒

（中國民航大學電子信息與自動化學院，天津 300300）

航班延誤的主要原因之一是機場地面特種車輛調度失誤。隨著機場地面特種車輛“油改電”的進行，機場將引入電動特種車輛和充電樁，在對電動特種車輛進行任務分配和調度過程中將面臨一些新的問題。在電動特種車輛引入的初期，勢必需要研究一種新的方案以解決燃油特種車輛和電動特種車輛共存條件下面臨的任務分配問題。本研究通過ID3決策樹算法對兩種特種車輛狀態(tài)數(shù)據(jù)進行分析歸納，構建決策樹和生成決策規(guī)則集合，得出決策模型，對兩種特征車輛進行合理的任務分配。結果表明：該方法能夠有效準確地解決特種車輛任務分配問題，與傳統(tǒng)方法相比，能夠有效降低人為因素引起的失誤，以提高地面特種車輛的運行效率。

調度；決策樹算法；ID3算法；特種車輛任務分配；分支

隨著“油改電”政策的推出，電動特種車輛在機場的應用將是一種趨勢。未來機場將會出現(xiàn)燃油特種車輛和電動特種車輛混合的局面[1-2]。隨著GPRS技術、信息采集技術和信息網(wǎng)絡技術等在車輛調度領域的應用，也使得車輛調度趨于信息化和自動化[3]。然而現(xiàn)在機場特種車輛調度仍然基于傳統(tǒng)的人工登記和運籌學等方法[4-5]。隨著電動特種車輛的引入，必將引入充電樁等與之配套的裝置，這就使得對電動特種車輛進行任務分配和調度面臨一些新的問題。因此，勢必需要研究一種與之對應的解決方案，以使特種車輛任務分配的效率得到提高。針對上述問題，本文介紹了一種基于決策樹的機場電動及燃油車輛任務分配方案。該方案在所需數(shù)據(jù)已通過先進的信息技術、GPS等技術采集完全的情況下[6]，用決策樹學習算法，對各種數(shù)據(jù)進行歸納分類，從而決策出最能滿足任務需求的特種車輛去執(zhí)行任務。

1 決策樹算法概述

決策樹是一種基于歸納的學習方法中高效實用的一種學習方法。最早起源于20世紀60年代中期，在以前很長一段時間是一種很常用的人工智能技術，Quinlan提出的ID3算法是其典型代表[7-8]。決策樹算法的結構簡單，計算量小，適合大規(guī)模數(shù)據(jù)學習的問題，如今已在機器人導航、數(shù)據(jù)挖掘、風險評估等領域得到廣泛應用[9]。

1.1 決策樹歸納法

決策樹由于其形狀像樹且用于決策而得名。一棵決策樹是由一系列葉子和節(jié)點組成，根節(jié)點和葉節(jié)點對應條件屬性，葉子對應決策類別，不同的屬性構成不同的分支。采用決策樹解決問題時，可利用此事件的屬性值由樹根節(jié)點向下搜索至葉子節(jié)點，葉子節(jié)點包含決策結果[10]。

1.2 決策樹的構造

決策樹是一種典型的分類方法，決策樹算法中數(shù)據(jù)集有訓練集和檢驗集。首先對訓練集進行處理，利用歸納算法生成可讀的規(guī)則和決策樹，然后對新的數(shù)據(jù)即檢驗集進行分析。本質上決策樹是通過一系列規(guī)則對數(shù)據(jù)進行分類的過程。

構建決策樹的算法有很多種，其中常用的算法有ID3、C4.5、CLS、CHAID 和 CART，每種方法都有各自的特點，但其在基于信息論構造決策樹方面是一致的[11]。

建樹所用算法是由對象事件屬性類別決定的。在每一個節(jié)點都有一個需要被測試的屬性，根據(jù)測試結果劃分樣例集，反復上述過程直到某一子樹中的集合相對于某一標準來說是同一類，這一集合即為葉節(jié)點。選擇被測試屬性的標準就是通過計算各個條件屬性尋找最大信息增益和最小信息熵，也就是選擇條件屬性平均熵最小的作為根節(jié)點，同樣的方法選擇其他節(jié)點，從而構成一棵完整的決策樹。

1.3 決策樹的化簡

在處理規(guī)模較大的數(shù)據(jù)時，有時會由于決策樹過于冗余，節(jié)點過多，導致從決策樹中提取的規(guī)則變多，使得問題復雜化，這時需要對所構造的決策樹進行化簡。

常用的決策樹化簡方法包括：悲觀錯誤修剪法（pessimistic error pruning）、減小錯誤修剪法（reduced error pruning）、基于代價-復雜度的修剪方法（costcomplexity pruning）和代價敏感（cost-sensitive）的決策樹修剪法。

每一種方法通過不同的手段，除去信息中與決策無關的冗余信息，使決策樹得到簡化，容易被人理解，處理問題更簡便。

2 ID3算法基本原理

ID3算法選擇當前訓練集中具有最大信息增益的屬性為測試對象。假設訓練實例集S{S1，S2，…，Si}，分類目標為n。假設xi為屬于Si類訓練實例個數(shù)，S{S1，S2，…，Si}中訓練實例總個數(shù)為x，如果某個實例屬于Si類的概率為Pi，則有：P=xi/x。其總的信息熵為

設屬性A具有m個不同的值?？捎脤傩訟將X劃分為 m 個子集{A1，A2，…，Am}，其中 Aj包含 X 中這樣一些樣本，他們在A上取ai值。若選擇A為測試屬性，那么這些子集就代表訓練集X的節(jié)點長出的新葉節(jié)點。設xij類別為Si的樣本數(shù)，則根據(jù)A劃分訓練集的信息熵值為

Claude Shannon的信息論表明：系統(tǒng)信息的不確定性程度越小，信息傳遞就會越充分。ID3算法就是根據(jù)信息論，以劃分后訓練集的不確定性作為劃分好壞的標準。ID3算法根據(jù)信息熵理論選擇訓練集信息增益最大屬性作為測試屬性，依據(jù)測試屬性的取值進行訓練集的劃分。選擇I（x1，x2，…，xm）值最大的作為擴展屬性。這樣得到的決策樹就會越精確[12]。

ID3算法基本步驟：①選定訓練集X規(guī)模為m的Si；② 判斷 I（x1，x2，…，xm）最小時，依次對擴展屬性進行選??；③依次對所有的樣本數(shù)據(jù)進行處理，判斷是否有例外，若無“例外”則結束；④若③中找到“例外”，則判斷③中的“例外”是否能與子集樣本數(shù)據(jù)合并為新的子集，進行步驟②。

3 決策樹在機場車輛任務分配決策中的應用

車輛調度信息化是車輛調度領域的趨勢。隨著車聯(lián)網(wǎng)等一些技術在機場的應用使得有關特種車輛的各種數(shù)據(jù)都能通過OBD數(shù)據(jù)采集終端和GPS技術等信息手段來獲得[13]。將所獲得的信息通過信息網(wǎng)絡上傳至上位機數(shù)據(jù)中心，然后通過決策樹方法對數(shù)據(jù)中心的數(shù)據(jù)進行合理分類歸納。未來機場會出現(xiàn)燃油和電動2種驅動方式的特種車輛共存的局面，2種驅動方式的特種車輛在調度過程中也必然存在差異性。雖然不同特種車輛的具體功能和服務任務不同，但不同類特種車輛之間在接受任務調派、車輛狀態(tài)等方面存在一定的共性。

目前，機場有部分特種車輛由于作業(yè)任務限制或路途限制，仍不能完全改裝成電動車輛，而只能用燃油為動力驅動或燃油電動混合動力驅動，如拖車、牽引車等。本文只以全燃油或全電力驅動的特種車輛為對象進行研究。下面以引導車為例進行研究，由于機場特殊環(huán)境的限制和處于安全風險的考慮，機場引導車不可能完全改裝成電力驅動。如此，會出現(xiàn)一個全燃油驅動和全電力驅動的2種動力引導車混合的局面。

在引導車的車輛狀態(tài)中，影響決策的因素有多種，其中作業(yè)狀態(tài)和車輛的能源（油量和電量）能否滿足執(zhí)行任務和行駛路途的需要是兩個至關重要的因素。除此之外，數(shù)據(jù)庫中特種車輛狀態(tài)數(shù)據(jù)類別中，車輛是否故障、可接受下一個指令時間、充電/加油完成時間、違章率、任務權重是影響判斷特種車輛是否滿足執(zhí)行任務需要的幾個重要屬性類別。依據(jù)上述引導車狀態(tài)數(shù)據(jù)幾種重要類別，針對引導車，選取通過信息手段獲取，并以完成任務分配的歷史數(shù)據(jù)作為訓練集S，如表1所示。

表1 引導車輛狀態(tài)數(shù)據(jù)Tab.1 State data of guiding vehicle

表1中：A1～A9分別代表狀態(tài)數(shù)據(jù)屬性類別；T表示將要執(zhí)行任務的時間點；t1～t7分別表示1～7號車可接收下一個任務的時間點；Tn表示n號車的充電完成的時間點；“≤”和“≥”分別表示前一時間點在后一時間點之前和之后；“充足”和“匱乏”分別代表引導車的能源能或不能滿足執(zhí)行任務所行駛路途的需要；“任務權重”指執(zhí)行重要任務可行程度。

3.1 基于決策樹任務分配模型的構建

數(shù)據(jù)集分為訓練集和測試集，利用ID3算法對上述訓練集S進行處理，使用信息熵增益方法作為屬性選擇標準，確定每個節(jié)點所對應的測試屬性，選擇具有最高信息增益的屬性作為當前節(jié)點的測試屬性，以便使用該屬性所劃分獲得的訓練樣本子集進行分類所需信息最小。

表1共有7個樣例，選取“燃油”為正例，“電動”為負例，其中有3個正例和4個負例，“燃油”x11=3，“電動”x21=4，總個數(shù)x=7，當前的信息熵即為

利用“車類”劃分如圖1所示。

圖1 車類劃分訓練集Fig.1 Training set of vehicle division

被劃分為2部分后各分支的信息熵分別為

劃分后在A1樣本下的條件信息熵為

那么屬性A1帶來的信息增益為

同理可得其他5個屬性信息增益為：Gain（A2）=0.412 8；Gain（A3）=0.386 6；Gain（A4） =0.361 4；Gain（A5）=0.401 7；Gain（A6）=0.358 6。

以“車類”為根節(jié)點，重復上述步驟，繼續(xù)擴展下面的分支。相對于S1和S2，A2的信息增益最大，先以電動特種車輛為例展開以下分支。此時，利用A2劃分S2，如圖2所示。

圖2 A2劃分S2Fig.2 S2divided by A2

重復進行上述步驟，確定各個根節(jié)點對應的屬性類別，可得“電動”特種車輛的決策樹，如圖3所示。

圖3 電動特種車輛決策樹Fig.3 Decision tree of special electric vehicle

同“電動”特種車數(shù)據(jù)處理，重復上述步驟可得“燃油類”特種車輛的決策樹，如圖4所示。

圖4 燃油特種車輛決策樹Fig.4 Decision tree of special fuel vehicle

通過對根節(jié)點、各內部節(jié)點和葉節(jié)點的選擇和確定，可完成對數(shù)據(jù)集S的ID3算法決策樹模型的構建，如圖5所示。

圖5 訓練集S決策樹模型Fig.5 Decision tree model of training set S

為了更貼近自然語言，以上構建的決策樹也可用下述規(guī)則集合來描述，以其中一個分支為例：

1）若“車輛 Cn”為“電動車”，“工作狀態(tài)”為作業(yè)，“車輛狀態(tài)”正常，“電量”充足，“可接受下一個任務”時間tn在下一個任務開始時間Tn之前，那么派出該車執(zhí)行任務；

2）若“車輛 Cn”為“電動車”，“工作狀態(tài)”為作業(yè)，“車輛狀態(tài)”故障，那么不派出該車執(zhí)行任務；

3）若“車輛 Cn”為“電動車”，“工作狀態(tài)”為作業(yè)，“車輛狀態(tài)”正常，“電量”匱乏，那么不派出該車執(zhí)行任務；

4）若“車輛 Cn”為“電動車”，“工作狀態(tài)”為作業(yè)，“車輛狀態(tài)”正常，“電量”充足，“可接受下一個任務”時間tn在下一個任務開始時間Tn之后，那么不派出該車執(zhí)行任務。

剩余分支情況的規(guī)則描述同上。利用ID3算法對訓練集S進行處理，確定各個內部節(jié)點，得出可讀的規(guī)則和訓練集S決策樹模型即任務分配模型。

3.2 特種車輛任務分配實例

現(xiàn)有引導飛機?？咳蝿誂，需派出滿足任務需求的引導車去執(zhí)行。有可供選擇的引導車C1～C5，車輛實時狀態(tài)數(shù)據(jù)集SA如表2所示。

表2 引導車狀態(tài)數(shù)據(jù)Tab.2 State data of guiding vehicle

利用3.1中任務分配模型和上述可讀規(guī)則對數(shù)據(jù)集 SA進行分類決策，最終輸出結果為：C1∶No，C2∶No，C3∶No，C4∶Yes，C5∶No，即派出電動引導車 C4去執(zhí)行任務。

4 結語

通過決策樹算法對數(shù)據(jù)集SA進行決策歸納，最終輸出決策結果為C4，即派出電動引導車C4執(zhí)行任務。由以上結果可知，與傳統(tǒng)運籌學和人工調度方法相比，決策樹算法能夠對數(shù)據(jù)合理歸納分類，快速精確決策出執(zhí)行任務所需要的特種車輛，減少了人為因素的影響。ID3決策樹算法有明顯的優(yōu)點：①ID3算法理論清晰，方法簡單，且具有較強的學習能力；②ID3算法涉及的概念較為成熟，易于構造；③在訓練數(shù)據(jù)集較完全情況下，ID3算法模型正確預測實際數(shù)據(jù)的誤差較小；④在數(shù)據(jù)集結構比較固定的情況下，ID3算法分類速度比較理想。

在機場地面特種車輛作業(yè)過程中，合理的任務分配是提高作業(yè)效率、減少航班延誤的重要環(huán)節(jié)。在車輛狀態(tài)數(shù)據(jù)信息化條件下，本文通過決策樹ID3算法對機場特種車輛相關狀態(tài)及數(shù)據(jù)進行分類歸納決策，然后根據(jù)實際任務需要決策出適合執(zhí)行任務的特種車輛。相比傳統(tǒng)的調度策略，能夠高效決策出最能滿足執(zhí)行任務需要的特種車輛，并在一定程度上減少人為因素的影響，能夠較理想地解決機場特種車輛調度信息化后特種車輛的任務分配問題。

[1]楊 揚,關 偉,馬繼輝.基于列生成算法的電動公交車輛調度計劃優(yōu)化研究[J].交通運輸系統(tǒng)工程與信息,2016,16(5):198-204.

[2]楊培穎,馬湘山.中國民航機場特種車輛“油改電”前瞻[J].中國民用航空,2015(5):30-32.

[3]劉曉琳,劉勝飛,魏江龍,等.機場特種車輛指揮調度系統(tǒng)設計[J].自動化與儀表,2010,25(3):1-3.

[4]郭輝煌,李 軍.車輛優(yōu)化調度問題的研究現(xiàn)狀評述[J].西南交通大學學報,1995,30(4):376-382.

[5]樊 瑋,吳建波,衡紅軍.基于多Agent的機場地面服務車輛調度方法研究[J].計算機應用與軟件,2015(10):256-259.

[6]姚偉鋒,趙俊華,文福拴,等.基于雙層優(yōu)化的電動汽車充放電調度策略[J].電力系統(tǒng)自動化,2012,36(11):30-37.

[7]DANTZIG G B,RAMSER J H.The truck dispatching problem[J].Management Science,1959,6(1):80-91.

[8]QU W,ZHANG D Z.Security Metrics Models and Application with SVM in Information Security Management[C]//International Conference on Machine Learning and Cybernetics,Hongkong,2007:3234-3238.

[9]蔡競峰,蔡自興,John Durkin.決策樹技術及其當前研究方向[J].控制工程,2005,12(1):15-18.

[10]李賢鵬,何松華,趙孝敏,等.改進的ID3算法在客戶流失預測中的應用[J].計算機工程與應用,2009,45(10):242-244.

[11]黃宇達,范太華.決策樹ID3算法的分析與優(yōu)化[J].計算機工程與設計,2012,33(8):3089-3093.

[12]曲開社,成文麗,王俊紅.ID3算法的一種改進算法[J].計算機工程與應用,2003,39(25):104-107.

[13]陸 檁,王玨明,章民融.車輛監(jiān)控調度系統(tǒng)的設計和實現(xiàn)[J].計算機應用與軟件,2005,22(12):127-129.

（責任編輯：黃 月）

Task assignment of electric and fuel special vehicles based on decision tree

FEI Chunguo,SHANG Dexuan
（College of Electronic Information and Automation,CAUC,Tianjin 300300,China）

One of the main reasons of flight delay is the failure of airport ground vehicle allocation.With the airport ground special vehicle change from oil-driven to electricity-driven,electric vehicles and charging pile will be introduced,and the electric vehicle assignment and scheduling process will face new problems.In early stage of the introduction of electric vehicles,it is necessary to study a new scheme to solve the problem of task allocation under the coexistence of special oil vehicles and special electricity vehicles.The ID3 decision tree algorithm of two kinds of special vehicle state data are analyzed and summarized,and decision tree is constructed to generate decision rules set as well as decision model of task allocation for two kinds of characteristics of the vehicle.Results show that the proposed method can effectively and accurately solve the task assignment problem of special vehicles.Compared with the traditional methods,this method can effectively reduce the errors caused by human factors and improve the operation efficiency of special vehicles.

scheduling;decision tree algorithm;ID3 algorithm;task assignment of special vehicles;branch

V35；TP393.1

：A

：1674－5590（2017）04－0046－05

2017-01-10；

：2017-03-08

：國家自然科學基金項目（61403395）

費春國（1974—），男，浙江慈溪人，副教授，博士，研究方向為神經(jīng)網(wǎng)絡優(yōu)化算法、機場車輛調度優(yōu)化算法、電力系統(tǒng)負載優(yōu)化和工業(yè)控制等.