基于动态DCVS网络模型的流量分析及规划方法*

吴 博，王 彬，薛 洁，刘 辉，熊 新

(1．昆明理工大学信息工程与自动化学院，云南昆明650504;2．云南警官学院信息网络安全学院，云南昆明650223)

1 引言

面对机场日益增加的行李运输量，建立实时高效的机场行李处理系统BHS(Bagage Handing System)变得尤为重要。在整个机场行李处理系统中，负责国内航线运输的国内航站楼(Domestic Terminal)和负责国外航线运输的国际航站楼(International Terminal)之间通常距离较长，这种不同航站楼之间的行李运输称为远端行李运输。远端行李运输系统是整个BHS的关键组成部分，传统的远端行李运输系统一般采用人工车辆运输的方法，目前，随着机场需求的提高和技术的发展，越来越多的国际大型枢纽机场采用目的地编码车系统DCVS(Destination Coded Vehicle System)解决远端行李的输送问题［1-8］。DCVS由若干辆DCV小车、封闭的轨道系统、控制系统和小车调度管理系统等组成，系统使用目的地编码认址技术对DCV小车进行控制，并且可以与BHS中的行李分拣系统直接无缝集成在一起。与原有的BHS控制构架相比较，DCVS真正实现了机场行李处理系统的自动化控制和运行，并且极大地提高了机场行李处理系统的整体运行效率［9-12］。

保障DCVS高速运行的关键是合理的流量规划及有效的实时状态监控，但是远端行李运输的路程较远，轨道设计较为复杂，尤其是在轨道上同时运行的DCV小车数量众多，通常都是平均每分钟数百台，这些特点给DCVS的流量分析、路径规划和运行状态监控带来了困难。目前已采用DCVS的机场的路径规划方法都是提前固定好起点到终点的路径，即DCV按照既定的静态规划方式运行，此外不管实际流量的需求怎样，DCVS的资源都是一直全部在使用中的。这种规划方法由于不考虑系统的实时状态信息而缺乏灵活性，很容易造成资源的浪费，并可能因为行李无法在规定的时间窗口内运达终点而影响整个BHS的正常运行，给旅客带来不便，同时给机场运营造成经济损失。

由于DCVS出现的时间较短，所以相关研究文献较少，但是随着DCVS投入使用数量的增加以及现有流量规划和控制方法所显现出的弊端，已经有研究者开始关注该领域并对DCVS的控制和路径规划问题展开了研究。荷兰Delft理工大学的Tarau等人［13］于2008年针对DCVS建立了基于事件的驱动模型，用多种传统控制方法对DCV运行时间展开了研究，实验表明随着行李数量增加，计算时间呈指数倍增长。2009年，Tarau等人［14］分别使用集中式路径选择控制方法和分散式路径选择控制方法对DCVS的路径规划进行了对比研究。结果表明，集中控制在路径规划的分配上占优，分散式控制在整体计算时间上占优。2009年，Tarau等人［15］针对在集中控制下计算时间长的缺陷，分别使用分布式模型预测控制和分布式启发控制对计算时间进行了优化，结果表明两种方法的结合可以在文献［13］的基础上减少百分之二十的运算时间，但随着行李数量增多，其运算时间的大量增加仍然不可避免。2009年，Tarau等人［16］为了达到计算时间与控制最优的目的，提出了集中启发式控制的策略并用于DCV路径规划的研究上。实验表明，该策略无论在计算时间上还是最优规划上都优于文献［13- 15］的方法。此外 Mao等人［17］针对DCV路径规划，加入不同路段的最大速度与加速度的约束考虑，建立了DCV最优路径规划的时间模型，实验结果显示该模型符合实际需求，可以为实际DCV路径规划提供参考。

上述工作从控制领域中经典的优化规划控制方法出发，大都以单个DCV小车为对象展开研究，试图对每一个小车运行路径进行规划，将问题映射为DCVS内每一个个体的运行时间和运算时间的组合优化问题来求解，从理论上给出了解决方案。但是，由于DCVS中同时运行的DCV小车数量至少高达上百辆，这些路径规划方法所需的运算时间无法满足实际DCVS运行中的实时性要求及流量需求。同时上述方法仅从系统的个体特性出发而没有考虑整个系统的全局流量控制信息，并且忽略了DCV控制系统中的实时状态信息。在实际系统运行中，机场行李流、DCVS轨道系统和控制系统等信息在每个不同的采样时刻都是实时变化的，因此有效地获取DCV系统的实时运行状态和系统流量需求，并据此对DCV小车的运行情况进行整体动态的规划是提高DCVS乃至BHS效率的有效解决方案。

针对上述研究现状，本文以满足机场远端行李运输的实时流量需求为目标，从DCV控制系统的动态特性和全局角度出发研究DCVS的动态流量规划问题。研究首先基于图论建立DCVS的静态运输网络模型，在此基础上结合系统的实时流量需求变化给出了一种基于最大流最小时间的动态DCVS流量规划、预测和控制方法。该方法通过规划源点所有DCV的整体路径对来实现对DCVS运输轨道系统资源的最大化利用，并且可以对DCVS在特定时间区间内所能完成运输任务的数量进行预测和评估，从而为DCVS的实时流量控制提供依据。实验结果显示，本文方法能够在保证流量需求的前提下优化DCV小车的运行时间，并且优化算法的运算时间很短，有效提高了DCVS的工作效率和资源利用率，同时为保障和提高整个BHS的可控性和稳定性提供了有效的解决方案。

2 基于图论的DCVS静态网络模型构建

2．1 DCVS物理模型描述

在实际DCVS中，机场行李处理系统是从行李通过值机柜台后开始运行的，根据不同的目的地，行李通过传送带被送往不同的终端，若识别到某行李需要进行远端运输，那么该行李就会被传送至DCVS的行李装载站，空的DCV在行李装载站等待行李，一旦在装载站台出现行李流，DCV就按照“一车一行李”的方式将行李进行装载并在DCVS中进行运输［18-20］。如图1所示，DCVS物理模型主要由三部分组成:装载站L(如图1a所示)、卸载站U(如图1b所示)和DCVS运输轨道R(如图1c所示)。假定有m个装载站和n个卸载站，行李依照分拣系统中识别的优先级别预先载入到DCV小车上，DCV通过运输轨道被送到卸载站。

2．2 基于图论的DCVS静态网络模型构建方法

根据上述DCVS物理模型，DCV在DCVS中的行为主要可分为在装载站处装载行李、在轨道系统中运行和到目的地卸载站处卸下行李三种。在无故障的前提下，DCV可在系统中往返运行，重复使用。由于DCV返回时有专门的返回线路，与行李的运输线路没有任何冲突，因此在本文研究中忽略不考虑。可供使用的装载站和卸载站的端口数量是固定的，但实际运行的端口数量可根据实际流量需求的不同加以调整。基于以上分析，本文采用图论的基本理论和网络模型对图1中的DCVS物理模型进行建模和分析。首先把DCV系统定义为一个图，系统中的站点，包括装载站、卸载站和各个交叉站点定义为图的节点，装载站与站点之间、站点与站点之间、站点与卸载站之间的每一条路段定义为图的边。由此得到DCVS物理模型所对应的静态网络模型，记为 G(V，L，U，E)，其中，V={B1，B2，B3，…，Bk}表示交叉站点集，k为交叉站点的个数;L={l1，l2，l3，…，lM}表示装载点站集，M 为装载站点个数;U={u1，u2，u3，…，uN}表示卸载站点集，N 为卸载站点个数;E={e1，e2，e3，…，ej}表示所有路段的集合，其中j为路段的数量。

根据实际的机场DCVS的框架结构，为了后文实验和研究需要，本文给出一个具体的DCVS的网络模型，如图2所示，该系统共有8个装载站，4个卸载站可供使用。尽管实际运行中的DCV系统会在规模和站点数量上有所不同，但在使用本文算法进行流量的分析和规划的目标是，确定当前系统配置是否可以满足该时段的流量需求，因此本文方法对不同规模和站点数量均可适用。可得到该DCVS 的静态网络模型为 G(V，L，U，E)，L={l1，l2，l3，…，l8}，U={u1，u2，u3，u4}，E={e1，e2，e3，…，e32}。并且站点与站点之间是有权连接的，图2中给出的权值是路段的长度，单位是m。同时站点之间的权值还有流量、容量等属性。

2．3 DCVS建模的约束条件分析

根据DCVS运行中的实际情况，为后文研究需要，本文首先对基于图论的DCVS建模过程中的一些物理约束作出如下假设:

(1)在DCVS中，如果某装载站点需处理的行李数量为Nbagage，该站点可供使用的DCV数量为NDCV。那么规定Nbagage≤ NDCV，即不会因起点处没有DCV小车而耽误继续运输行李。

(2)在起点处，假设共有X个行李需要被送往对应的远端目的地，共开放M个装载站对这X个行李进行处理，其中bmax为每个装载站的最大装载量。那么规定这X个行李按照F=X/M(L表示每个装载站可处理行李的数量)分配给每个装载站，并且满足X≤Fbmax。

(3)在卸载站点处，可对早到行李进行存储，若早到行李过多就会由于存储力不够而导致容量溢出。如果用Y表示终点的行李个数，各个卸载站点的最大存储能力为dmax。假定有N个可用的卸载站点，那么规定这Y个行李按照Q=Y/N(Q表示每个卸载站可存储行李的数量)分配给每个卸载站，且满足Y≤Qdmax。

(4)实际运行轨道可能由直线轨道、弯曲轨道、合流轨道、分流轨道以及倾斜15度坡轨道等组成［21］。DCV小车在实际中会因路段和逻辑区域不同而运行在几种速度级别上，在目前的研究中，由于采取整体流量规划的策略，因此考虑的是DCV在整个轨道网络上的平均运输速度，并且假定每一个DCV的运行速度相同。

(5)车辆在某一段轨道上运行时，如果遇到本路段的拥堵或故障等问题，DCV在原位置等待系统恢复正常再继续运行，即除了单独的返回路段以外，DCV在每一路段上单向运行，不可后退到上一级站点重新选择路径。

(6)目前研究中暂未考虑多个DCV流过同一分流站点时的路由选择，以下文算法中规划的各个路段流量为依据，按照先进先通过的原则通过每一个交叉站点。

(7)在机场的行李运输系统中，因为实际的航班运行情况和时间窗口要求会产生行李的运输优先级别不同，该问题一般由BHS中的行李分拣部分来分析解决，对于本文所研究的DCV远端运输系统，行李的优先级别问题已经通过进入装载站时的排队先后而解决，因此在运输过程中无需再考虑行李优先级别问题。

3 基于流量分析的DCVS动态网络模型构建方法

3．1 基于流量分析的DCVS动态网络模型思想

尽管在图1所示的DCVS静态网络模型中，已经得到 DCVS的基本结构，但是该模型只能对DCVS进行静态属性的描述，比如站点之间的连接关系，路段的容量、流量、距离等。但是，在DCVS的实际运行过程中，由于每一时段实际DCVS的系统流量需求可能不同，可用的行李装载站点和行李卸载站点的开放数量可能不同，实际DCV所选择的路径可能不同，因此该模型结构及属性并非静止不变的，而是随时可能发生变化，因此只根据第2．1节中的模型还不足以描述DCVS的动态特征。

文献［13-16］中的研究和实验结果显示:以单个DCV小车作为规划对象的最优化时间算法费时太长，尤其在行李数目增加时，其运算时间几乎呈指数级增长，无法满足DCV控制系统的实际运行时间要求。而整个DCVS运行的最主要目标是行李流必须在指定的时间内运抵远端目的地，因此本文以满足DCVS的流量需求为目标，采用整体流量和路径规划的思想，构建DCV系统的动态网络模型，并在该动态模型的基础上对DCVS的流量控制和路径控制问题展开研究。该方法的基本思想是:以每个统计时间区间上的实际流量需求信息为依据，采用最短时间最大流算法与超级源点和超级汇点相结合的算法预测整个系统可达到的最大流量，用于评估在规定时间窗内，当前的可用资源能否满足系统的需求，从而有效地利用和分配资源;同时，可以有效地掌握当前时刻每条路段上所运行的DCV小车的最佳流量分配方案，这样不但可以保证计划的行李流能够在规定时间内到达远端目的地，同时也可准确地掌握DCVS控制系统的实时信息。

3．2 流量需求分析

DCVS流量规划需满足以下条件:(1)在每个时间区间上满足行李流的总需求;(2)总的行李流必须在规定的时间窗内到达卸载站;(3)每条路段上的DCV流量在容量允许范围内。根据机场的实际行李流信息、机场远端行李处理过程中的行李处理要求与规定以及行李到达时间安排等数据综合考虑，可以得到每个时间区间上的行李流信息，其中包括实际中转行李需求、当前提供的装载站数量、当前提供的卸载站数量等。表1给出了其中四个不同时间区间上的远端行李处理需求信息数据。

Table 1 Data of different sampling intervals表1 不同采样时刻区间的数据

以时间区间1为例，此时段系统中一共有待远端运输的行李1 450件，即对DCV的需求是1 450车次。时间区间1内的所有行李都需要在规定的时间窗口内完成从装载站到卸载站的运输，目前可供使用的装载站数量为8，实际在用的装载站数量为5，可供使用的的卸载站数量为4，实际在用的卸载站数量为2。

3．3 基于最大流最短时间原理的DCVS动态流量规划算法的实现

由于一般的最大流算法只适用于单源单汇情况下的流量分析，而在DCVS中，一般都是要同时开放多个装载站点和卸载站点，因此单源单汇算法不足以解决DCVS的实际流量分析问题。因此，本文首先为DCVS静态模型加入超级源点与超级汇点，如图3所示。在图3中，构建超级源点S与各个装载站相连接，超级汇点T与各个卸载站相连接。图3中路段上括号内的第一个权值为该路段的距离，第二个权值为该路段最大可容纳的DCV流量(下文简称容量)，第三个权值为经过该路段所需要花费的时间(下文简称时间)。因为与超级源点、超级汇点连接的路段在实际中是不存在的，所以与超级站点相连路段中的第一个权值与第三个权值是不存在的，即为0，但是该路段上的容量权值是存在的。对于装载站而言，从超级源点到各个装载站的流方向为流入，根据流的平衡条件，即流入超级节点的流量等于流出超级节点的流量法则可知，该段上的容量应该等于从该装载站点流出的流量之和。同理，对于卸载站而言，从各个卸载站到超级汇点的流方向为流出，该段上的容量应该等于流入该装载站的流量之和。

接下来利用最短时间最大流算法对图3所示的模型进行动态流量规划，具体规划方法(如图4所示)如下:

(1)输入图3所示的加入超级源点和超级汇点后的网络G，任意找到一条初始可行流，并确定该初始可行流f(k)=0，此时k=0。

(2)记f(k)为经过k次调整得到的最小时间费用流，构建对应的有向图网络W(f(k))。

(3)利用Dijkstra算法求出W(f(k))中从S到T的最短路R(k)，若R(k)不存在，则f(k)是最小时间最大流，转向(5);否则，转向(4)。

(4)在W(f(k))中找到对应的增广链μ，在增广链μ上对f(k)按式(1)进行流量调整，得到新的可行流f(k+1)，此时令k=k+1，转入(2)。

其中，cij表示从起点i到终点j路段上的容量表示第k次构建的可行流fij，θk表示第k次的调整量，u+表示正向弧集合，u－表示反向弧集合。

(5)停止运算，并输出当前最小时间可行流f(k)，作为G的最小时间最大流。

本文采用Linear Interactive and General Optimizer(以下简称Lingo)平台实现上述算法的仿真。Lingo是一套专门用于求解最优化问题的软件包，它由美国芝加哥大学的Linus Schrage开发［22］。该软件既可用于求解线性规划问题，还可以用于解决非线性规划问题。如图5所示，以表1中的时间区间4为例，在当前开启8个装载站、4个卸载站时，经过Lingo计算得出:可提供的DCV运输次数，即图5a中的Objective value是2 485次，计算该数据并规划出相对应的流量分配的计算时间仅需0．07 s，该算法可在极短时间内运算得到当前系统资源配置下特定时间区间4上的实际最大行李流，从而可为DCV系统的实时规划和控制提供有力支持。

我们对当前动态规划结果中的所有路段依次进行标号，标号结果为1～61，将该算法规划后的各个路段上流量分配情况与静态时路段的容量通过柱状图进行对比，可以得到图5b。由图5b中可以直观地观测到当前的实际流量分配以及容量与流量的差别。

控制时段4规划后的动态模型如图6所示。由于超级源点S、汇点T的构建作用是为了进行流量的整体规划而加入的，因此在完成动态规划后，删除S、T，从而可以得到最终的DCV轨道系统动态模型，如图7所示，其中括号内第一个权值为长度，第二个权值为流量，第三个权值为时间。由图7可知，规划后的网络由7个装载站点、4个卸载站点、18个中间站点、45条实际路段组成。相对于规划前的静态网络减少了1个站点和16条路段。使用本文方法对其进行流量规划后可知:系统在该时段内可以承载的最大行李总数为2 485件，目前的系统配置是可以满足该时段流量的需求的。

由本文所提出的动态网络流量规划方法原理可知，即使在模型结构规模扩大、节点数增加的情况下，按照图4中的算法步骤，仍然可以实现对DCVS动态模型的分析、规划，从而得出对应的最优动态流量规划方案，确保系统内的DCV小车运输时间最短的情况下得到整个运输网络中的最大流量。

按照上述步骤分别使用本文方法对控制时段1、控制时段2和控制时段3的行李运输场景进行了流量规划仿真，结果如图8所示。根据表1的实验结果可知:控制时段3和控制时段4一样，当前可以达到的最大流量满足控制系统要求，但控制时段1和控制时段2中需要处理的行李量则超出了系统当时配置所能达到的最大量，此时可以通过增开装载站或卸载站的控制策略来满足实际行李流的需求。表2列出了使用本文方法分析后需新增开的站点的数量变化情况及最大流量变化状况。

Table 2 Flow after planning表2 规划后的流量

由上述实验及结果可知:(1)本文方法可以实现基于最大流最短时间原理的动态流量分析，为系统在不同时段的不同条件的流量规划提供了基础;(2)在这个动态规划过程中，该方法可以准确预测出当前配置下DCV系统的整体最大可达流量，从而为系统的全局规划提供了精确的依据;(3)该方法在能够保证流量最大化的同时优化每个路段上的DCV车辆分配，因此可以缩短DCVS的整体运行时间，提高DCVS和BHS的工作效率;(4)本文算法的运算速度快，不会带来额外的时间成本。

该方法综合考虑DCVS流量和时间两个重要因素的要求，可以根据DCVS不同时段内的实际流量需求状态来实现动态分析和规划，从而可以更好地利用资源，并为DCVS的控制提供实时的帮助。同时也为保障和提高整个控制系统的可控性和稳定性提供了有效的解决方案。相对于目前DCV系统运行过程中静态无变化的固定路径规划方法，本文方法提供了一种更灵活更高效的全局系统流量规划方法。

4 结束语

在实际的机场行李处理系统中，用于机场行李远端运输的DCV控制系统在每个不同的采样时间区间内的需求都是实时变化的，但实际的系统仍然采用传统固定的规划和控制方法，无法灵活地作出规划，经常造成控制资源的浪费，影响了系统的行李处理效率。因此，有效地获取系统的实时需求变化，并据此动态地规划DCVS的流量分配方案具有重要意义，也是迫切需要解决的问题。

本文围绕上述问题对DCVS的动态流量分析和规划问题展开了研究，给出了一种基于动态DCVS网络模型的最大流最小时间的流量规划方法。该方法实现了:(1)基于图论的DCVS静态网络模型构建;(2)远端行李处理系统在特定时间区间内的综合流量需求分析;(3)带超级节点和超级汇点的DCVS静态网络模型的最大流最小时间算法实现;(4)DCVS的整体流量分析和路径流量分配;(5)基于Lingo平台的实例仿真及结果分析。实验结果显示，该方法可以根据DCVS不同时段的需求和配置动态地完成对DCVS流量的整体规划，并可以根据流量分析的结果判断当前系统的配置能否满足实际需求，实现了对远端行李运输任务的流量任务预测，从而为DCVS的控制决策提供了重要依据。

附中文参考文献: