基于实时交通信息的城市动态网络车辆路径优化问题

孟庆珍

河南省开封市妇幼保健院 河南省开封市 475003

1 引言

根据交通运输部数据显示：截至2017年，中国各类机动车的拥有量已达到5亿辆。但是我国城市的人均道路面积仅为7平方米左右。同时，在城镇化建设中，随着我国居民拥有的汽车数量的不断增长，我国道路基础设施的发展速度落后，从超大型城市到三线城市，交通拥堵问题日益严重，而交通拥堵给机动车和道路承受力等资源带来了损耗，也增加了出行者在道路的时空资源消耗，进而导致居民的出行成本、社会的生产成本增加。另外，交通拥堵时，汽车排放的各种污染物如尾气排放也对城市环境造成污染，因此增加了外部成本。面对道路交通拥堵以及汽车数量的增多带来的安全、环境等一系列的社会问题，在目前道路投资有限的前提下，本文建议需采用信息化手段尽可能地对道路交通状况进行实时更新，优化车辆出行的路径规划，以改善城市的道路交通拥堵情况，节省人们的出行时间和提高城市环境质量。

2 实时交通信息概况

信息化代表一个国家或地区利用信息技术和整合各种资源的能力与水平。它是以数据库技术、现代通信、网络为底层基础，构建一个具有庞大规模的、自上而下的、有组织的信息网络体系。它是一种以培养、发展以计算机为主的智能化工具，其也正在成为新的生产力。能够很大程度上的提升人们办事的效率和设备的生产力，为推动人类生活水平和质量进步提供强有力的技术支持。其包括信息获取、信息传递、信息处理、信息再生、信息利用五个基本过程。本文中的实时交通信息的含义是运用现代化的高新科技，例如：北斗导航系统、地理信息系统等技术，将城市的各种动态和静态交通信息实时的从采集交通信息管理系统中，将数据系统化，并应用于车辆路径优化的问题中，以达到共享资源，向车辆的用户提供服务，优化交通营运管理。实时交通流信息的获取与分享示意图见图1。

实时交通信息管理系统实现了交通数据的深度挖掘和细化加工，用以生成多种交通数据信息，并将其传送给道路中的汽车。该系统的工作原理是：首先，通过k聚类算法或者启发式算法识别数据的类型（离散或者连续），处理冗余性和噪音，提高数据的合理性和有效性。并对缺失的数据进行智能补充；第二，构建关联度高的多源数据融合模型，构建数据源和类型丰富的数据库或者数据源以及符合城市实际环境的交通状况指标体系；第三，运用计量经济学或者统计分析的方法对从各种渠道收集的交通流数据进行归一化处理，构建车辆路径特征库，结合车辆出行实时数据和GPS、北斗导航卫星形成的定位数据，构建交通预测模型，实现了动态交通预测。

图1 实时交通流信息获取与分享示意图

3 车辆路径优化

车辆路径问题（VRP），作为运筹学和组合优化领域最经典的问题，其对于解决城市道路交通拥堵的问题，有着十分重要的作用。在目前研究中，许多学者假设任意两个交通网络节点间的车辆行驶时间和路程为已知条件且为静态的常量。在车辆路径规划和根据交通信息车辆行驶的过程中不会发生变化，但在实践中，车辆会受交通流量、上下班高峰期、天气变化、交通事故等因素的影响，车辆行驶速度总在不断变化，从而导致了交通网络中各个路段行程时间也相应地发生变化。以往采用传统静态VRP理论和方法规划车辆路径，有可能使得车辆陷入城市拥堵的交通环境中。因此，在20世纪80年代的动态车辆路径（DVRP）提出和研究引起企业和学者的关注。进入21世纪以来，我国引入的GPS和国产的北斗导航卫星、计算机通信、地理信息系统等技术不断地完善，相关政府和企业投入研发地智能交通信息系统的日益完善，政府、企业和个人实时获取和处理信息地能力得到极大地提高。

众在VRP中，许多学者们创造和改进了各种智能优化算法，例如遗传算法、粒子群算法、启发式算法、神经网络算法、蚁群算法、果蝇算法等。其中最为经典和有效解决问题的是遗传算法、神经网络算法和蚁群算法。遗传算法作为一种最为广泛的求解车辆路径问题的算法，其可以以对问题的所处周围环境和条件未知为前提，其求解问题的步骤最为固定，包括交叉-适应度确定-选择-变异。遗传算法从问题解的串集开始搜索，而不是从单个解开始。这是遗传算法最大的优点。遗传算法从串集开始搜索，受搜索空间的限制性的约束，覆盖面大，必要求求解的变量具有连续性、单峰性、可导性，利于全局择优。对于随机环境下的城市交通信息和突发的车辆问题来说，神经网络VRP算法有着较好的适应性，其可以及时跟踪和反馈城市交通流的各类型参数、道路车辆流的变化，算法的计算精确度高，同时VRP神经网络算法包含了其自有的自组织、自适应、自学习能力。由于原有的蚁群算法有众多缺陷，许多学者们进行了改进，其中使用最为普遍的是Ant-Qsystem算法。

4 模型构建

为了研究实时交通信息的动态网络的车辆路径问题，本文简单描述动态网络中VRP问题的模型构建过程。本文将动态交通管理系统与配送货物的车辆路径优化问题相结合，研究虑问题中包含常发性交通拥堵和偶发性交通拥堵两种情形，并采用遗传算法进行模型的求解策略，已解决在实时交通状况和车辆状态下规划最佳的行车路线。

4.1 问题描述

本文假定：（1）在城市范围内只设置1个配送中心，所有车辆的装车容量固定，运输车辆在原始状态下都停在配送中心，并在运输任务完成或者调度周期结束前返回：（2）车辆费用由车辆购置费用、燃油费用和维修费用三部分组成；（3）车辆行驶速度由时间和道路的交通状况决定，各时间区间车辆的行驶速度一定；1个调度周期分为若干离散区间，调度中心只知道当前时间行驶速度。（4）在同一个周期内的客户需求确定，l辆车服务至少服务一位客户，在需求有时间差要求，车辆只能等待，但不许服务延迟。

4.2 构建模型

4.3 求解

本文采用遗传算法（GA）求解得到初始路径，首先需要安排车辆的初始路径，初始路线安排后，车辆在行驶过程中需要根据实时交通信息系统传输的交通信息对行驶的路况判别，然后做出是否更新路线的决定。本文的路线更新机制是车辆在行驶过程中每到达一个配送的目的节点， 路段瞬时行程时间更新一次。并且车辆的路径优化中总是选择当前配送节点到下一个节点的瞬时最短路径。由于现代化的通信移动技术和实时交通信息系统可以及时准确的地变化中的交通环境，且能够高精度地预测交通网络中任意两节点的行程时间， 因此当车辆到达路网中任意一个节点时都可以更新路段行程时间，并通过采用遗传算法很容易计算得到当前配送节点到下一个节点的瞬时最短路径。

遗传算法的求解过程：

4.3.1 染色体编码

遗传算法不能直接处理问题空间的参数，必须把它们转换成遗传空间的由基因按一定染色体编码，目前的几种常用的编码技术有二进制编码、浮点数编码、字符编码和编程编码等。编码应具备三个原则：完备性。问题空间中的所有点（候选解）都能作为GA空间中的点（染色体）表现；健全性。GA空间中的染色体能对应所有问题空间中的候选解；非冗余性。交通信息数据的染色体和车辆优化路径的候选解一一对应。在算法中的基因是城市路网转换的节点，所以本例中采取了有序的二进制编码方式。

4.3.2 染色体交叉

杂交体现了信息交换的思想。由交换概率挑选的每两个父代，通过将相异的部分基因进行交换，从而产生新的个体，新个体组合了其父辈个体的特征。在遗传算法中，在编码串中某段码元如果是有效车辆路径或接近于有效路径，则其继承了父代的优良基因特征；其次，交叉生成的子代应是有效的个体，即符合有序的二进制编码规则。

4.3.3 染色体选择

遗传算法目的选择的目的是为了从交换后的群体中选出优良的个体，使它们有机会作为父代为下一代繁衍子孙。体现了达尔文的适者生存原则。在车辆路径优化中，其体现节点之间最短路径选择。本文的选择机制是轮盘赌方式，即在第N代个体中如果有有效路径，则有效路径中的最佳路径直接进入下一代。

4.3.4 染色体变异

变异首先在所有的路径中随机选择一定数量的个体，对于选中的个体以一定的概率随机地改变串结构数据中某个路径的值。

最后，可以通过仿真软件，对该模型进行仿真求解，并验证其可行性和有效性。

5 结语

本文在实时交通信息环境下解决车辆路径问题，介绍了实时交通信息的概况，分析了车辆路径优化的静态VRP与动态VRP的区别，以及在实践中使用DVRP的优势，简要介绍了构建这类问题的数学模型的过程。今后，还要针对基于实时交通信息的动态网络车辆路径问题开展进一步的研究以便可以有效地找到实时最短路径、降低配送成本。