基于决策树机场电动及燃油特种车辆任务分配

费春国，尚德轩

（中国民航大学电子信息与自动化学院，天津 300300）

基于决策树机场电动及燃油特种车辆任务分配

费春国，尚德轩

（中国民航大学电子信息与自动化学院，天津 300300）

航班延误的主要原因之一是机场地面特种车辆调度失误。随着机场地面特种车辆“油改电”的进行，机场将引入电动特种车辆和充电桩，在对电动特种车辆进行任务分配和调度过程中将面临一些新的问题。在电动特种车辆引入的初期，势必需要研究一种新的方案以解决燃油特种车辆和电动特种车辆共存条件下面临的任务分配问题。本研究通过ID3决策树算法对两种特种车辆状态数据进行分析归纳，构建决策树和生成决策规则集合，得出决策模型，对两种特征车辆进行合理的任务分配。结果表明：该方法能够有效准确地解决特种车辆任务分配问题，与传统方法相比，能够有效降低人为因素引起的失误，以提高地面特种车辆的运行效率。

调度；决策树算法；ID3算法；特种车辆任务分配；分支

随着“油改电”政策的推出，电动特种车辆在机场的应用将是一种趋势。未来机场将会出现燃油特种车辆和电动特种车辆混合的局面[1-2]。随着GPRS技术、信息采集技术和信息网络技术等在车辆调度领域的应用，也使得车辆调度趋于信息化和自动化[3]。然而现在机场特种车辆调度仍然基于传统的人工登记和运筹学等方法[4-5]。随着电动特种车辆的引入，必将引入充电桩等与之配套的装置，这就使得对电动特种车辆进行任务分配和调度面临一些新的问题。因此，势必需要研究一种与之对应的解决方案，以使特种车辆任务分配的效率得到提高。针对上述问题，本文介绍了一种基于决策树的机场电动及燃油车辆任务分配方案。该方案在所需数据已通过先进的信息技术、GPS等技术采集完全的情况下[6]，用决策树学习算法，对各种数据进行归纳分类，从而决策出最能满足任务需求的特种车辆去执行任务。

1 决策树算法概述

决策树是一种基于归纳的学习方法中高效实用的一种学习方法。最早起源于20世纪60年代中期，在以前很长一段时间是一种很常用的人工智能技术，Quinlan提出的ID3算法是其典型代表[7-8]。决策树算法的结构简单，计算量小，适合大规模数据学习的问题，如今已在机器人导航、数据挖掘、风险评估等领域得到广泛应用[9]。

1.1 决策树归纳法

决策树由于其形状像树且用于决策而得名。一棵决策树是由一系列叶子和节点组成，根节点和叶节点对应条件属性，叶子对应决策类别，不同的属性构成不同的分支。采用决策树解决问题时，可利用此事件的属性值由树根节点向下搜索至叶子节点，叶子节点包含决策结果[10]。

1.2 决策树的构造

决策树是一种典型的分类方法，决策树算法中数据集有训练集和检验集。首先对训练集进行处理，利用归纳算法生成可读的规则和决策树，然后对新的数据即检验集进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。

构建决策树的算法有很多种，其中常用的算法有ID3、C4.5、CLS、CHAID 和 CART，每种方法都有各自的特点，但其在基于信息论构造决策树方面是一致的[11]。

建树所用算法是由对象事件属性类别决定的。在每一个节点都有一个需要被测试的属性，根据测试结果划分样例集，反复上述过程直到某一子树中的集合相对于某一标准来说是同一类，这一集合即为叶节点。选择被测试属性的标准就是通过计算各个条件属性寻找最大信息增益和最小信息熵，也就是选择条件属性平均熵最小的作为根节点，同样的方法选择其他节点，从而构成一棵完整的决策树。

1.3 决策树的化简

在处理规模较大的数据时，有时会由于决策树过于冗余，节点过多，导致从决策树中提取的规则变多，使得问题复杂化，这时需要对所构造的决策树进行化简。

常用的决策树化简方法包括：悲观错误修剪法（pessimistic error pruning）、减小错误修剪法（reduced error pruning）、基于代价-复杂度的修剪方法（costcomplexity pruning）和代价敏感（cost-sensitive）的决策树修剪法。

每一种方法通过不同的手段，除去信息中与决策无关的冗余信息，使决策树得到简化，容易被人理解，处理问题更简便。

2 ID3算法基本原理

ID3算法选择当前训练集中具有最大信息增益的属性为测试对象。假设训练实例集S{S1，S2，…，Si}，分类目标为n。假设xi为属于Si类训练实例个数，S{S1，S2，…，Si}中训练实例总个数为x，如果某个实例属于Si类的概率为Pi，则有：P=xi/x。其总的信息熵为

设属性A具有m个不同的值。可用属性A将X划分为 m 个子集{A1，A2，…，Am}，其中 Aj包含 X 中这样一些样本，他们在A上取ai值。若选择A为测试属性，那么这些子集就代表训练集X的节点长出的新叶节点。设xij类别为Si的样本数，则根据A划分训练集的信息熵值为

Claude Shannon的信息论表明：系统信息的不确定性程度越小，信息传递就会越充分。ID3算法就是根据信息论，以划分后训练集的不确定性作为划分好坏的标准。ID3算法根据信息熵理论选择训练集信息增益最大属性作为测试属性，依据测试属性的取值进行训练集的划分。选择I（x1，x2，…，xm）值最大的作为扩展属性。这样得到的决策树就会越精确[12]。

ID3算法基本步骤：①选定训练集X规模为m的Si；② 判断 I（x1，x2，…，xm）最小时，依次对扩展属性进行选取；③依次对所有的样本数据进行处理，判断是否有例外，若无“例外”则结束；④若③中找到“例外”，则判断③中的“例外”是否能与子集样本数据合并为新的子集，进行步骤②。

3 决策树在机场车辆任务分配决策中的应用

车辆调度信息化是车辆调度领域的趋势。随着车联网等一些技术在机场的应用使得有关特种车辆的各种数据都能通过OBD数据采集终端和GPS技术等信息手段来获得[13]。将所获得的信息通过信息网络上传至上位机数据中心，然后通过决策树方法对数据中心的数据进行合理分类归纳。未来机场会出现燃油和电动2种驱动方式的特种车辆共存的局面，2种驱动方式的特种车辆在调度过程中也必然存在差异性。虽然不同特种车辆的具体功能和服务任务不同，但不同类特种车辆之间在接受任务调派、车辆状态等方面存在一定的共性。

目前，机场有部分特种车辆由于作业任务限制或路途限制，仍不能完全改装成电动车辆，而只能用燃油为动力驱动或燃油电动混合动力驱动，如拖车、牵引车等。本文只以全燃油或全电力驱动的特种车辆为对象进行研究。下面以引导车为例进行研究，由于机场特殊环境的限制和处于安全风险的考虑，机场引导车不可能完全改装成电力驱动。如此，会出现一个全燃油驱动和全电力驱动的2种动力引导车混合的局面。

在引导车的车辆状态中，影响决策的因素有多种，其中作业状态和车辆的能源（油量和电量）能否满足执行任务和行驶路途的需要是两个至关重要的因素。除此之外，数据库中特种车辆状态数据类别中，车辆是否故障、可接受下一个指令时间、充电/加油完成时间、违章率、任务权重是影响判断特种车辆是否满足执行任务需要的几个重要属性类别。依据上述引导车状态数据几种重要类别，针对引导车，选取通过信息手段获取，并以完成任务分配的历史数据作为训练集S，如表1所示。

表1 引导车辆状态数据Tab.1 State data of guiding vehicle

表1中：A1～A9分别代表状态数据属性类别；T表示将要执行任务的时间点；t1～t7分别表示1～7号车可接收下一个任务的时间点；Tn表示n号车的充电完成的时间点；“≤”和“≥”分别表示前一时间点在后一时间点之前和之后；“充足”和“匮乏”分别代表引导车的能源能或不能满足执行任务所行驶路途的需要；“任务权重”指执行重要任务可行程度。

3.1 基于决策树任务分配模型的构建

数据集分为训练集和测试集，利用ID3算法对上述训练集S进行处理，使用信息熵增益方法作为属性选择标准，确定每个节点所对应的测试属性，选择具有最高信息增益的属性作为当前节点的测试属性，以便使用该属性所划分获得的训练样本子集进行分类所需信息最小。

表1共有7个样例，选取“燃油”为正例，“电动”为负例，其中有3个正例和4个负例，“燃油”x11=3，“电动”x21=4，总个数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。

以“车类”为根节点，重复上述步骤，继续扩展下面的分支。相对于S1和S2，A2的信息增益最大，先以电动特种车辆为例展开以下分支。此时，利用A2划分S2，如图2所示。

图2 A2划分S2Fig.2 S2divided by A2

重复进行上述步骤，确定各个根节点对应的属性类别，可得“电动”特种车辆的决策树，如图3所示。

图3 电动特种车辆决策树Fig.3 Decision tree of special electric vehicle

同“电动”特种车数据处理，重复上述步骤可得“燃油类”特种车辆的决策树，如图4所示。

图4 燃油特种车辆决策树Fig.4 Decision tree of special fuel vehicle

通过对根节点、各内部节点和叶节点的选择和确定，可完成对数据集S的ID3算法决策树模型的构建，如图5所示。

图5 训练集S决策树模型Fig.5 Decision tree model of training set S

为了更贴近自然语言，以上构建的决策树也可用下述规则集合来描述，以其中一个分支为例：

1）若“车辆 Cn”为“电动车”，“工作状态”为作业，“车辆状态”正常，“电量”充足，“可接受下一个任务”时间tn在下一个任务开始时间Tn之前，那么派出该车执行任务；

2）若“车辆 Cn”为“电动车”，“工作状态”为作业，“车辆状态”故障，那么不派出该车执行任务；

3）若“车辆 Cn”为“电动车”，“工作状态”为作业，“车辆状态”正常，“电量”匮乏，那么不派出该车执行任务；

4）若“车辆 Cn”为“电动车”，“工作状态”为作业，“车辆状态”正常，“电量”充足，“可接受下一个任务”时间tn在下一个任务开始时间Tn之后，那么不派出该车执行任务。

剩余分支情况的规则描述同上。利用ID3算法对训练集S进行处理，确定各个内部节点，得出可读的规则和训练集S决策树模型即任务分配模型。

3.2 特种车辆任务分配实例

现有引导飞机停靠任务A，需派出满足任务需求的引导车去执行。有可供选择的引导车C1～C5，车辆实时状态数据集SA如表2所示。

表2 引导车状态数据Tab.2 State data of guiding vehicle

利用3.1中任务分配模型和上述可读规则对数据集 SA进行分类决策，最终输出结果为：C1∶No，C2∶No，C3∶No，C4∶Yes，C5∶No，即派出电动引导车 C4去执行任务。

4 结语

通过决策树算法对数据集SA进行决策归纳，最终输出决策结果为C4，即派出电动引导车C4执行任务。由以上结果可知，与传统运筹学和人工调度方法相比，决策树算法能够对数据合理归纳分类，快速精确决策出执行任务所需要的特种车辆，减少了人为因素的影响。ID3决策树算法有明显的优点：①ID3算法理论清晰，方法简单，且具有较强的学习能力；②ID3算法涉及的概念较为成熟，易于构造；③在训练数据集较完全情况下，ID3算法模型正确预测实际数据的误差较小；④在数据集结构比较固定的情况下，ID3算法分类速度比较理想。

在机场地面特种车辆作业过程中，合理的任务分配是提高作业效率、减少航班延误的重要环节。在车辆状态数据信息化条件下，本文通过决策树ID3算法对机场特种车辆相关状态及数据进行分类归纳决策，然后根据实际任务需要决策出适合执行任务的特种车辆。相比传统的调度策略，能够高效决策出最能满足执行任务需要的特种车辆，并在一定程度上减少人为因素的影响，能够较理想地解决机场特种车辆调度信息化后特种车辆的任务分配问题。

[1]杨 扬,关 伟,马继辉.基于列生成算法的电动公交车辆调度计划优化研究[J].交通运输系统工程与信息,2016,16(5):198-204.

[2]杨培颖,马湘山.中国民航机场特种车辆“油改电”前瞻[J].中国民用航空,2015(5):30-32.

[3]刘晓琳,刘胜飞,魏江龙,等.机场特种车辆指挥调度系统设计[J].自动化与仪表,2010,25(3):1-3.

[4]郭辉煌,李 军.车辆优化调度问题的研究现状评述[J].西南交通大学学报,1995,30(4):376-382.

[5]樊 玮,吴建波,衡红军.基于多Agent的机场地面服务车辆调度方法研究[J].计算机应用与软件,2015(10):256-259.

[6]姚伟锋,赵俊华,文福拴,等.基于双层优化的电动汽车充放电调度策略[J].电力系统自动化,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算法的分析与优化[J].计算机工程与设计,2012,33(8):3089-3093.

[12]曲开社,成文丽,王俊红.ID3算法的一种改进算法[J].计算机工程与应用,2003,39(25):104-107.

[13]陆 檩,王珏明,章民融.车辆监控调度系统的设计和实现[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—），男，浙江慈溪人，副教授，博士，研究方向为神经网络优化算法、机场车辆调度优化算法、电力系统负载优化和工业控制等.