论文部分内容阅读
【摘 要】 在城市道路中车辆的行驶路径的收集与分析，对于城市道路交通的管理具有重要的意义。比如特殊车辆的路径跟踪、安全部门对于违法车辆的追踪，另外车辆行驶路径数据的收集与分析对于日后城市道路交通的建设具有重要的参考价值。
【关键词】 智能交通；车辆；路径识别；方法
引言：
车辆路径问题是运输组织优化中的核心问题，也是运筹学中的一类经典的组合优化问题，旨在借助构造适当的车辆行驶路线以实现运输成本的最优化。随着市场经济的发展和物流专业化水平的提高，车辆路径问题从提出之初就受到广泛关注。到目前为止，该问题的应用不仅仅局限在汽车交通运输领域，在航空、通讯、电力、工业管理和计算机应用等领域也有一定的应用。
一、智能交通系统的综合性概述
城市交通系统作为一个动态系统，在其中包括了众多复杂因素，如，人、环境、道路、交通规则等，这些因素相互关联又相互制约，是一个典型的复杂系统。社交网络中人的关系、不同地区之间的人口流动、道路上的交通流等等都可表达为复杂网络模型。智能交通的应用中更多会用到带有时空属性的复杂网络模型，每个节点都有空间坐标信息，并且边和点的属性（甚至结构）会随时间而变化。因此，基于复杂网络的数据管理和模式发现技术尤为重要。除此之外，可视化以直观的方式帮助我们理解获取的知识和模式。例如，将到达各个区域的人数画成热度图（颜色越深，人越多）。将不同时间段的此类热度图连续播放，便可以动态反映整个城市的人口流动规律。与单一数据可视化不同，智能交通中的可视化技术需要同时考虑多个维度，其中空间和时间是两个至关重要的维度。
交通数据由交通基础设施数据和动态交通数据构成。动态交通数据可以通过磁频、波频、视频和移动通信等技术采集。比如，通过在交叉路口埋设感应线圈或安装在固定地点的视频监控设备，可以获得路口的交通流量；用安装在车内GPS等移动定位设备，可记录车辆位置、瞬时速度、行程时间、行程速度、行驶轨迹等交通信息；基于RFID技术可采集关键断面的分车型流量、速度等信息，并获取车辆行驶轨迹；基于手机信令可获取用户运动线路和运动速度等。动态交通数据记录着随时间变化的空间和属性信息，具有动态、多源、连续、无限、时变等特征，是进行实时监控和动态分析的数据基础。但是这些原始数据中信息多且复杂，噪声数据、缺失数据、冗余数据和不一致数据大量存在，严重影响了数据的质量。因而需要对基础数据进行清洗工作，主要步骤：
1、数据分析。利用团队已有的创新性大数据分析方法，对基础数据有针对性地详尽分析，获得关于数据属性的元数据，从而发现数据集中存在的质量问题。
2、定义清洗转换规则。根据上一步数据分析得到的结果定义清洗转换规则与工作流。
3、检测属性错误并标准化。基于统计的方法、聚类方法、关联规则的方法检测数据集中的属性错误，并纠正错误，使数据标准化。
4、数据回流。利用干净的数据替换数据源中原来的“脏数据”。有效的交通数据组织管理和交通数据提取与分析是进行动态交通流和路网拥堵状态分析的两个关键环节。根据交通管理部门和出行者对交通信息访问的实时性和智能化需求，以动态交通流和路网拥堵状态分析为导向，结合交通数据的时空特征和交通领域约束，深入分析数据之间潜在的相似性、相关性和关联性，并对交通数据进行聚类分析、预测分析、关联分析、异常检测等深度挖掘，从而发现不同特征维度、不同数据粒度隐含的知识，利用降维技术分析和处理数据。
二、智能交通系统下的车辆路径识别问题
1、分类
按车辆类型分，可分为单车型问题和多车型问题；按配送中心（车场）数目分，可分为单配送中心（车场）问题和多配送中心（车场）问题；按任务特征分，可分为纯送（取）货问题和装卸混合问题；按有无时间约束分，可分为无时间窗问题和有时间窗问题，另外可以按车辆装载情况、按优化目标数、按车辆对车场的所属关系、按已知信息的确定性分等不同分类标准进行分类。
2、模型及算法
车辆调度问题是一个较为复杂的组合优化问题，可以从不同的角度进行建模。一般来说，车辆调度问题可以构造成整数规划模型，也可以构造成图论及其他模型，这些模型之间存在着某种联系，但从建立模型时的出发点考虑，大多数模型均可看作是几种模型的变形与组合。自车辆路径问题提出以来，国内外学者对于不同类型的车辆调度问题提出了许多不同的数学模型，并提出了许多获得问题最优解或次优解的算法。车辆路径问题的求解方法，基本上可分为精确算法、启发式算法和亚启发式算法三大类，具体分类情况如表1所示：
目前在车辆路径问题模型研究方面，都是从不同角度、不同方向开展，例如结合实际考虑时间窗、车场数、车型等要素，各有侧重。在算法研究中，国内外都进行了大量的算法研究，从20世纪60年代的集中在各种形式的节约算法，到70～80年代提出了各式各样的基于数学规划的算法，80年代后期时至今日，各种智能算法和并行算法的广泛应用[4]。由于基本VRP问题属于NP-hard问题，使得各类VRP问题求解难度更加复杂，仍值得进一步研究。从现有研究文献看，围绕车辆路径问题的研究非常广泛，在此我们从多车场、多车型、有时间窗VRP问题三方向对现有研究文献进行综述，并结合社会经济发展所带来的新变化，对VRP问题未来研究趋势提出看法。
三、智能交通系统下的多车型车辆路径问题综述
多车型车辆路径问题是车辆路径问题的一种扩展。根据车辆的型号是否相同，可将车辆路径问题分为单车型问题和多车型问题。单车型问题假定车辆的型号相同，即具有相同的最大载重量与最大行驶距离以及相同的固定成本与变动成本，而多车型问题则不同，通常各车型的最大载重不同或使用成本不同。自1984年Golden等首先研究了多车型车辆路径问题以来，国内外学者针对多车型车辆路径问题的求解算法进行广泛探索。 1、多车场车辆路径问题综述
多车场车辆路径问题是基本车辆路径问题的扩展，指的是有数个车场同时对多个用户进行服务，要求对各车场的车辆和行驶路线进行适当的安排，在保证满足各用户需求的前提下，使总的运输成本最低。多车场车辆路径问题，实际上不仅是路径问题，它还涉及到了场站的选择和分配问题，一般可以分解为两个子问题：将顾客分派给场站；为每个场站优化线路。目前国内外关于多车场车辆调度问题的研究主要集中在算法的改进上，从传统的启发式算法的应用到现在集中于现代启发式算法的应用，同时注重结合实际运行情况，对多车场问题进行扩充。
2、带时间窗的车辆路径问题综述
带时间窗的车辆路径问题是基本车辆路径问题的扩展问题，即在VRP问题的基础上给每个客户加上服务所允许的时间窗约束。时间窗则是一个时间段，由客户要求的最早服务时间和最晚服务时间确定的一个服务时间区间。这里的时间窗是从客户角度出发，即可称为客户（需求）时间窗。因此考虑VRPTW问题，不仅需要在空间上进行车辆路径规划，而且还需要在时间上进行合理的安排。
四、智能交通系统下车辆路径问题研究趋势
随着社会经济的快速发展，消费者对服务质量要求越来越高，物流作为生产性服务产业，作用日益凸显。车辆路径问题作为物流系统优化中的关键一环，也对之提出更高要求。然而市场竞争的日趋激烈，使得企业间的竞争更加白热化，企业与企业间的竞争，开始转变为联盟与联盟间的竞争，企业面临更大的压力与挑战。随着信息技术与互联网技术的突飞猛进，特别是电子商务的快速发展，联盟车辆调度问题则会成为车辆路径问题的一个新的应用研究领域。例如：菜鸟网络科技有限公司、重庆市农业电子商务产业发展联盟的成立，都是通过组建联盟方式，利用互联网技术，有效整合资源，合理调度各个配送企业的车辆资源。如何降低成本，提高服务质量一直是企业面临的重要问题。为了提高服务质量，将客户（需求）时间窗引入VRP问题中，在添加客户时间窗的基础上考虑成本最低，是目前VRP中最常见的问题。然而服务质量的提高与服务成本的提高成正比，服务质量与服务成本的平衡成为企业关注焦点之一。为此，从企业成本控制角度出发考虑时间窗，即在调用车辆时考虑正在运行的车辆，等待其执行任务时间，赋予其一个时间窗，我们可称为车辆（供给）时间窗，这时是否可以得出更优的调度方案呢？将车辆（供应）时间窗概念引入车辆路径问题中，可能也是VRP问题未来的一个新的研究趋势。
参考文献：
[1]李军耀.物流配送车辆优化调度理论与方法[M].北京：中国物资出版社，2012（26）：139.
[2]唐生明.突发事件下的车辆路径问题研究综述[J].铁道运输与经济，2013（12）：56-59.
[3]邹彤宝.多车场车辆路径问题的遗传算法[J].计算机工程与应用，2012（21）：82-83.
【关键词】 智能交通；车辆；路径识别；方法
引言：
车辆路径问题是运输组织优化中的核心问题，也是运筹学中的一类经典的组合优化问题，旨在借助构造适当的车辆行驶路线以实现运输成本的最优化。随着市场经济的发展和物流专业化水平的提高，车辆路径问题从提出之初就受到广泛关注。到目前为止，该问题的应用不仅仅局限在汽车交通运输领域，在航空、通讯、电力、工业管理和计算机应用等领域也有一定的应用。
一、智能交通系统的综合性概述
城市交通系统作为一个动态系统，在其中包括了众多复杂因素，如，人、环境、道路、交通规则等，这些因素相互关联又相互制约，是一个典型的复杂系统。社交网络中人的关系、不同地区之间的人口流动、道路上的交通流等等都可表达为复杂网络模型。智能交通的应用中更多会用到带有时空属性的复杂网络模型，每个节点都有空间坐标信息，并且边和点的属性（甚至结构）会随时间而变化。因此，基于复杂网络的数据管理和模式发现技术尤为重要。除此之外，可视化以直观的方式帮助我们理解获取的知识和模式。例如，将到达各个区域的人数画成热度图（颜色越深，人越多）。将不同时间段的此类热度图连续播放，便可以动态反映整个城市的人口流动规律。与单一数据可视化不同，智能交通中的可视化技术需要同时考虑多个维度，其中空间和时间是两个至关重要的维度。
交通数据由交通基础设施数据和动态交通数据构成。动态交通数据可以通过磁频、波频、视频和移动通信等技术采集。比如，通过在交叉路口埋设感应线圈或安装在固定地点的视频监控设备，可以获得路口的交通流量；用安装在车内GPS等移动定位设备，可记录车辆位置、瞬时速度、行程时间、行程速度、行驶轨迹等交通信息；基于RFID技术可采集关键断面的分车型流量、速度等信息，并获取车辆行驶轨迹；基于手机信令可获取用户运动线路和运动速度等。动态交通数据记录着随时间变化的空间和属性信息，具有动态、多源、连续、无限、时变等特征，是进行实时监控和动态分析的数据基础。但是这些原始数据中信息多且复杂，噪声数据、缺失数据、冗余数据和不一致数据大量存在，严重影响了数据的质量。因而需要对基础数据进行清洗工作，主要步骤：
1、数据分析。利用团队已有的创新性大数据分析方法，对基础数据有针对性地详尽分析，获得关于数据属性的元数据，从而发现数据集中存在的质量问题。
2、定义清洗转换规则。根据上一步数据分析得到的结果定义清洗转换规则与工作流。
3、检测属性错误并标准化。基于统计的方法、聚类方法、关联规则的方法检测数据集中的属性错误，并纠正错误，使数据标准化。
4、数据回流。利用干净的数据替换数据源中原来的“脏数据”。有效的交通数据组织管理和交通数据提取与分析是进行动态交通流和路网拥堵状态分析的两个关键环节。根据交通管理部门和出行者对交通信息访问的实时性和智能化需求，以动态交通流和路网拥堵状态分析为导向，结合交通数据的时空特征和交通领域约束，深入分析数据之间潜在的相似性、相关性和关联性，并对交通数据进行聚类分析、预测分析、关联分析、异常检测等深度挖掘，从而发现不同特征维度、不同数据粒度隐含的知识，利用降维技术分析和处理数据。
二、智能交通系统下的车辆路径识别问题
1、分类
按车辆类型分，可分为单车型问题和多车型问题；按配送中心（车场）数目分，可分为单配送中心（车场）问题和多配送中心（车场）问题；按任务特征分，可分为纯送（取）货问题和装卸混合问题；按有无时间约束分，可分为无时间窗问题和有时间窗问题，另外可以按车辆装载情况、按优化目标数、按车辆对车场的所属关系、按已知信息的确定性分等不同分类标准进行分类。
2、模型及算法
车辆调度问题是一个较为复杂的组合优化问题，可以从不同的角度进行建模。一般来说，车辆调度问题可以构造成整数规划模型，也可以构造成图论及其他模型，这些模型之间存在着某种联系，但从建立模型时的出发点考虑，大多数模型均可看作是几种模型的变形与组合。自车辆路径问题提出以来，国内外学者对于不同类型的车辆调度问题提出了许多不同的数学模型，并提出了许多获得问题最优解或次优解的算法。车辆路径问题的求解方法，基本上可分为精确算法、启发式算法和亚启发式算法三大类，具体分类情况如表1所示：
目前在车辆路径问题模型研究方面，都是从不同角度、不同方向开展，例如结合实际考虑时间窗、车场数、车型等要素，各有侧重。在算法研究中，国内外都进行了大量的算法研究，从20世纪60年代的集中在各种形式的节约算法，到70～80年代提出了各式各样的基于数学规划的算法，80年代后期时至今日，各种智能算法和并行算法的广泛应用[4]。由于基本VRP问题属于NP-hard问题，使得各类VRP问题求解难度更加复杂，仍值得进一步研究。从现有研究文献看，围绕车辆路径问题的研究非常广泛，在此我们从多车场、多车型、有时间窗VRP问题三方向对现有研究文献进行综述，并结合社会经济发展所带来的新变化，对VRP问题未来研究趋势提出看法。
三、智能交通系统下的多车型车辆路径问题综述
多车型车辆路径问题是车辆路径问题的一种扩展。根据车辆的型号是否相同，可将车辆路径问题分为单车型问题和多车型问题。单车型问题假定车辆的型号相同，即具有相同的最大载重量与最大行驶距离以及相同的固定成本与变动成本，而多车型问题则不同，通常各车型的最大载重不同或使用成本不同。自1984年Golden等首先研究了多车型车辆路径问题以来，国内外学者针对多车型车辆路径问题的求解算法进行广泛探索。 1、多车场车辆路径问题综述
多车场车辆路径问题是基本车辆路径问题的扩展，指的是有数个车场同时对多个用户进行服务，要求对各车场的车辆和行驶路线进行适当的安排，在保证满足各用户需求的前提下，使总的运输成本最低。多车场车辆路径问题，实际上不仅是路径问题，它还涉及到了场站的选择和分配问题，一般可以分解为两个子问题：将顾客分派给场站；为每个场站优化线路。目前国内外关于多车场车辆调度问题的研究主要集中在算法的改进上，从传统的启发式算法的应用到现在集中于现代启发式算法的应用，同时注重结合实际运行情况，对多车场问题进行扩充。
2、带时间窗的车辆路径问题综述
带时间窗的车辆路径问题是基本车辆路径问题的扩展问题，即在VRP问题的基础上给每个客户加上服务所允许的时间窗约束。时间窗则是一个时间段，由客户要求的最早服务时间和最晚服务时间确定的一个服务时间区间。这里的时间窗是从客户角度出发，即可称为客户（需求）时间窗。因此考虑VRPTW问题，不仅需要在空间上进行车辆路径规划，而且还需要在时间上进行合理的安排。
四、智能交通系统下车辆路径问题研究趋势
随着社会经济的快速发展，消费者对服务质量要求越来越高，物流作为生产性服务产业，作用日益凸显。车辆路径问题作为物流系统优化中的关键一环，也对之提出更高要求。然而市场竞争的日趋激烈，使得企业间的竞争更加白热化，企业与企业间的竞争，开始转变为联盟与联盟间的竞争，企业面临更大的压力与挑战。随着信息技术与互联网技术的突飞猛进，特别是电子商务的快速发展，联盟车辆调度问题则会成为车辆路径问题的一个新的应用研究领域。例如：菜鸟网络科技有限公司、重庆市农业电子商务产业发展联盟的成立，都是通过组建联盟方式，利用互联网技术，有效整合资源，合理调度各个配送企业的车辆资源。如何降低成本，提高服务质量一直是企业面临的重要问题。为了提高服务质量，将客户（需求）时间窗引入VRP问题中，在添加客户时间窗的基础上考虑成本最低，是目前VRP中最常见的问题。然而服务质量的提高与服务成本的提高成正比，服务质量与服务成本的平衡成为企业关注焦点之一。为此，从企业成本控制角度出发考虑时间窗，即在调用车辆时考虑正在运行的车辆，等待其执行任务时间，赋予其一个时间窗，我们可称为车辆（供给）时间窗，这时是否可以得出更优的调度方案呢？将车辆（供应）时间窗概念引入车辆路径问题中，可能也是VRP问题未来的一个新的研究趋势。
参考文献：
[1]李军耀.物流配送车辆优化调度理论与方法[M].北京：中国物资出版社，2012（26）：139.
[2]唐生明.突发事件下的车辆路径问题研究综述[J].铁道运输与经济，2013（12）：56-59.
[3]邹彤宝.多车场车辆路径问题的遗传算法[J].计算机工程与应用，2012（21）：82-83.