基于大数据平台的动态车辆路径调度算法

,,

(1.湖南师范大学 数学与计算机科学学院,长沙 410081; 2.湖南警察学院 信息技术系,长沙 410138)

0 概述

近年来,研究者对智能交通系统(Intelligent Transportation Systems,ITS)的研究越来越多,而智能交通系统中的车辆路径问题(Vehicle Routing Problem,VRP)是目前电子商务物流配送决策中的热点问题[1],也是带多个约束条件的NP-难问题,如带时间窗约束的车辆路径问题[2](Vehicle Routing Problem with Time Windows,VRPTW)难以用常规方法求解,因而人们多致力于启发式算法的研究。车辆路径问题目前要处理来自多个数据源向其提供的数据收集服务[3],文献[4]描述已经改变了传统智能交通系统(TTS)的数据驱动。通过从各种来源收集大量的数据加工成有用的数据信息,数据驱动可以为车辆路径优化提供新的服务[5],为动态车辆路径问题提供新的依据。收集和组织来自多个实时不同来源数据,为智能交通供应链的决策提供依据是目前的主要挑战[6],这主要是因为数据库的规模非常大,同时没有可用的实时分析工具。

当前智能交通系统路径算法主要面临的困难[7]有:从广泛携带传感器的车辆搜集所需位置数据集;收集从大量实时车辆数据提高及时警报;大量数据需要组织和实时处理;用于数据收集系统结构应该较易部署、低成本,以确保广泛使用。本文利用大数据平台对多源大量数据计算的优势,构建动态车辆路径调度模块的体系框架,同时提出基于大数据平台的动态车辆路径调度算法(BDVRA)。该算法采用动态时间序列构建目标函数模型[8],实时设置警报标志动态修改车辆路径调度策略。

1 基本问题模型

为说明动态车辆路径问题[9],通过实例来说明实时更新路线的车辆路径调度策略,如图1所示。此问题涉及到食品供应链的供应节点和目标节点,供应节点可以是新鲜食品生产收集中心或暂时存储食品仓库的任意分布点,目的地可以是出售新鲜食品零售商店或被运送到其他地点之前冷藏保存食品仓库的任意分布点。图1中涉及到的所有车辆可以在任意位置开始或结束路线,路线的数量等于车辆的数量,即每辆车安排一条路线。每辆车在有限能力提供有限车载量的食品给目标节点,初始方案是每辆车在每个供应节点仅访问一次。大数据分析计算平台用于实时监控从所有的车辆和车辆路线上获取的数据,如果在运输途中供应食物的可能在某种条件导致变质,那么车辆路径要实时更新变化。图1显示了从车辆实时数据分析后生成一个动态调度的实例,如:车辆P1在路径1-2上产生一个警报而延误了目标节点3的如期交货时间,这个警报触发了创建新路径模块,车辆1从节点2重新路由到目标节点4,而车辆2重新路由到目标节点3,车辆3重新路由到目标节点6。

图1 基于警报实时更新路线示意图

定义1(VRPTW问题) 设物流中心仓库有k辆车,N={s},s=1,2,…,k,其中k为待定车辆数,每辆车载重能力为Ns=D;要为q个节点用户供应,用户节点集为U={m},m=0,1,…,q,当m=0时为中心仓库;用户m的需求量为dm,因此d0=0;用户m的时间窗口为[xm,ym];从用户m到用户n的路程为Umn,行驶时间为Tmn;设车辆s到达用户m的时间为Wms,则Wms∈[xm,ym]。如何进行车辆路径调度,使调用的车辆数k最少,且总行车成本P最小。

根据VRPTW问题定义,其数学模型可以概述为:如果车辆s访问客户m后访问客户n,则Ymns=1;否则Ymns=0,其目标函数的一般形式[10]为:

(1)

n=1,2,…,k,s=1,2,…,q,n≠s

(2)

(3)

为了得出图1中基于警报实时更新车辆路径问题的数学模型,用一个时间序列的路线图来描述,如图2所示。

图2 车辆路线时序示意图

在图2中,N是目标总数,K是车辆数,M是一辆车在一条路径最大目标数,Di是从供应节点到目标节点i所需时间,Tmk0是车辆k第m趟开始时间,Tmk1是车辆k第m趟到达目标节点时间,Tmk2是车辆k第m趟到达目标节点时间,Si是在目标节点i的处理时间,Ri是车辆行驶到目标节点i的时间窗口,Wj0是到达目标节点j时间窗口的开始时间,Wj1是到达目标节点j时间窗口的结束时间。Xikm∈{0,1}是决策变量,其中,i∈{1,2,…,N},k∈{1,2,…,K},m∈{1,2,…,M}。如果目标节点i有车辆k的第m趟,则Xikm=1;否则Xikm=0。根据图1的数学模型,可以得出图2中食物供应运输总成本的目标函数F:

(4)

k=1,2,…,K,s=1,2,…,q,n≠s

(5)

(6)

其中,ai是与目标节点i关联的迟到罚款系数,即目标函数F的值由从供应节点到目标节点运输成本和从供应节点到目标节点延迟罚款组成。

2 大数据平台动态车辆路径调度策略

基于大数据平台动态车辆路径的体系框架如图3所示。数据收集器从车辆主节点和传感装置收集动态时序数据,每个传入的数据流映射到一个数据收集器节点。每个数据收集器节点有数据聚合器、数据过滤器和数据存储服务器模块。对大量原始位置和传感器车辆数据流形式的原始数据,使用大数据分析软件Hadoop进行预处理数据分析,Hadoop是一个能够对大量数据进行分布式处理的软件框架,对数据预处理更有效率[11]。另外,Hadoop实现了一个分布式文件系统(Hadoop Distributed File System,HDFS)。在分布式计算中,MapReduce框架负责处理了并行编程中分布式存储、工作调度、负载均衡、容错均衡、容错处理以及网络通信等复杂问题,把处理过程高度抽象为2个函数:map和reduce,map负责把任务分解成多个任务,reduce负责把分解后多任务处理的结果汇总起来。

图3 大数据平台动态车辆路径体系结构

对收集到的数据进行处理以生成警报,在用户指定的过滤器创建警报。警报创建模块收集到一个警报位置(警报数据库),被组织成一个HDFS可管理的数据结构。通过较少时间窗口的实时车辆位置和传感器收集到的数据创建实时警报,也可以从过去的车辆位置和传感器数据创建离线警报。因为使HDFS和MapReduce优化处理大文件、数据转到一个记录结构文件更有效,所以数据挖掘要将聚集本地磁盘的车辆位置和传感器非结构化流数据转换为结构化记录文件,并通过在非结构化序列文件中解析记录和提取传感器相关知识,最后数据挖掘模块将结构化的记录移动到HDFS中。控制器模块通过动态车辆路径调度算法向所有车辆发送生成的新路径线路,同时控制器能将当前附近的车辆新路径线路和附加信息增加到动态车辆路径数据中,用于实时更新路径数据。

基于车辆实时数据的动态车辆路径模块的目的是降低新鲜食品的变质程度达到最小化。由于交通状况变化,原来的路径计划进度一般会发生偏差,此外环境的变化,如:温度的增加会导致冷却系统故障。大数据分析平台可以对所有动态车辆有一个全局视图,在大数据计算平台上动态车辆路径模块能为发生警报的车辆及时创建新线路。例如,一辆汽车在预定时间内不能达到预定目的地,可以在一个的食物变质有限时间窗口开始前,重新选择到一个最接近目标的线路。应用大数据平台,动态车辆路径模块了解车辆的状态变量(如卡车容量、位置、速度、容器温度等)对创建新线路很重要,这个新的路线能降低运输车辆产生成本和食品变质率。目前常见的研究主要是利用车辆静态的时间窗口优化车辆路径减低运输成本,本文利用大数据分析计算平台支持多种车辆动态路径算法的优势,提出了一种新的动态车辆路径算法。

基于大数据计算平台动态车辆路径调度算法,依托大数据计算平台对数据处理的效率,如果某辆车在当前路径有一个警报发生时,算法将基于当前位置和现有车载能力为车辆生成一个新的顺序路径表。如果找到一个可行的解决方案,新的顺序路径表通过车辆由控制器模块发送到当前所有连接平台的在线车辆。如果没有找到可行解,当前车辆获得本地生成的警报进行修复车辆路径,例如:当前某车辆可以路由到最近的交货地点,转向原来没有计划的车辆路径。本文算法应用大数据计算平台为工具,采用目标函数及约束条件实现车辆运输总成本最小化的优化解。

算法基于大数据计算平台动态车辆路径算法

输入设车辆集K={1,2,…,k},目标节点集N={0,1,…,n},N=0时为中心仓库

输出每辆车的最优路径及路径序列S={s1,s2,…,sk}

步骤1从大数据计算平台获取处理车辆路径数据集;

步骤2初始化,从源端N0开始,初始化一个空路由表S,并置N=0;

步骤3如果所有目标节点N都被路由,则转步骤5;

步骤4否则,计算其他没有被路由目标点的成本函数F;

步骤4.1如果有目标节点发生警报,则获得当前的位置和未路由的其他目标节点Ni;

步骤4.2目标节点Ni作为一个新的输入,N=N+1;

步骤4.3找到了可行解,发送新的解给所有的车辆Ki;

步骤4.4否则,在当前位置标记警报,获得局部解并为车辆提高警惕,转步骤3;

步骤5整理调度序列S={s1,s2,…,sk},并输出,结束。

3 实验分析

为了验证基于大数据计算平台动态车辆路径算法的正确性和效率,采用Sioux Fall网络[12]进行数值模拟,网络中包括24个节点和76条路段,节点之间的线路双向运行的时间做了简单修正,数值模拟的网络如图4所示。

图4 Sioux Fall网络

初始路线通过数据收集器从车辆主节点和传感装置收集动态时序数据得到,使用大数据分析软件Hadoop进行预处理数据分析,MapReduce框架负责处理并行编程中分布式存储、工作调度、负载均衡、容错均衡、容错处理以及网络通信等复杂问题。本文求解BDVRA问题得到的初始路线如表1所示。

表1 初始线路

在模拟过程中,分别采用4条初始线路对本文算法以及传统推动插入启发式(Push-forward Insertion Heuristic,PFIH)算法[13]和基于禁忌(Tabu)搜索车辆路径算法[14]进行数值模拟实验。从表2可以看出,采用本文算法获取的线路优化结果明显优于传统算法,表明本文算法是有效的;采用本文算法获取的最优解,明显优于PFIH和Tabu搜索算法,具体的结果如表2所示。

表2 3种算法优化结果比较

将模拟数值增加,进一步测试本文算法的时间性能,分别用10/4、50/10、100/20、500/50、1 000/100(分别表示路径节点数/车辆数)数值对3种算法进行测试。本文为了评估大数据计算平台框架处理的性能,进行了上述不同数量的车辆,同时使用Amazon Elastic Compute Cloud(EC2)基础设施[15]进行实验。图5和图6显示了本文BDVRA算法与传统基于推动插入启发式(PFIH)算法和基于禁忌(Tabu)搜索车辆路径算法在时间性能上进行比较。

图5 3种算法运行的时间性能比较

图6 3种算法目标函数F值比较

可以看出,随着数据量增加时3种算法的运行时间和目标函数F值都随之上升。但数据量在500/50时,PFIH和禁忌(Tabu)搜索算法明显急剧上升,BDVRA由于利用大数据计算平台对初始数据处理,在时间性能上有明显优势,如图5所示。在整个车辆运输总成本上,由于利用标记警报动态修改路径算法,目标函数F的值也比其他2种算法优越,如图6所示。

4 结束语

车辆路径最优调度问题是一种组合优化问题,如果节点数量较多、车辆状态无掌控、实时环境变化等,则无法获取准确的最优解。为对车辆的运行路线进行合理的规划,确保车辆总成本最小化,本文提出基于大数据计算模型的车辆路径调度算法。该算法首先应用大数据计算平台对数据进行收集、存储、处理和分析计算,然后利用平台MapReduce实现以几秒钟的时间上限创建实时警报并修改车辆路径。该算法提高了数据分析处理速度,对推动启发式搜索PFIH和禁忌(Tabu)搜索算法进行了优化,增强了算法实时动态处理能力,提高了算法寻优性能。下一步继续将本文BDVRA算法应用到多个目标的动态车辆路径调度问题中,求得多个解以有利于决策者做出正确的决策,为研究动态车辆路径调度问题提供一种新的途径与方法。

[1] 曹剑东,郑四发,李 兵,等.动态车辆调度系统设计与开发[J].计算机工程,2008,34(7):280-282.

[2] 王 君,李 波,卢志刚.带时间窗动态车辆路径问题的优化调度策略[J].计算机工程,2012,38(13):137-141.

[3] 李妍峰,高自友,李 军.基于实时交通信息的城市动态网络车辆路径优化问题[J].系统工程理论与实践,2013,33(7):1813-1819.

[4] ZHANG J,WANG F,WANG K,et al.Data-driven Intelligent Transportation Systems:A Survey[J].IEEE Transactions on Intelligent Transportation Systems,2011,12(4):1624-1639.

[5] CLAES R,HOLVOET T,WEYNS D.A Decentralized Approach for Anticipatory Vehicle Routing Using Delegate Multi-agent Systems[J].IEEE Transactions on Intelligent Transportation Systems,2011,12(2):364-373.

[6] STEIL D A,PATE J R,KRAFT N A,et al.Patrol Routing Expression,Execution,Evaluation,and Engage-ment[J].IEEE Transactions on Intelligent Trans-portation Systems,2011,12(1):58-72.

[7] SCHMITT E,JULA H.Vehicle Route Guidance Systems:Classification and Comparison[C]//Proceedings of IEEE ITSC’06.Toronto,Canada:[s.n.],2006:242-247.

[6] PEARAFTIS H N.Dynamic;Vehicle Routing Problems[M].Berlin,Germany:Springer,1988.

[8] GHIANI G,GUERRIERO F,LAPORTE G,et al.Real-time Vehicle Routing:Solution Concepts,Algorithms and Parallel Computing Strategies[J].European Journal of Operational Research,2003,151(1):1-11.

[9] PILLAC V,GENDREAU M,GUERET C,et al.A Review of Dynamic Vehicle Routing Problems[J].European Journal of Operational Research,2013,225(1):1-11.

[10] POTVIN J Y,XU Y,BENYAHIA I.Vehicle Routing and Scheduling with Dynamic Travel Times[J].Com-puter & Operation Research,2006,33(4):1129-1137.

[11] TANIGUCHI E,SHIMAMOTO H.Intelligent Transportation System Based Dynamic Vehicle Routing and Scheduling with Variable Travel Times[J].Transportations Research Part C:Emerging Technologies,2004,12(3/4):235-250.

[12] LEBLANC L,MORLOK E K J,PIERSKALLA W P.An Efficient Approach to Solving the Road Network Equilibrium Traffic Assignment Problem[J].Trans-portations Research,1975,9(5):309-318.

[13] SOLOMON M M.Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints[J].Operations Research,1987,35(2):254-265.

[14] GLOVER F.Tabu Search Part I[J].ORSA Journal on Computing,1989,1(3):190-206.

[15] THANGIAH S R,OSMAN I H,VINAYAGAMOORTHY R.Algorithms for the Vehicle Routing Problems with Time Deadlines[J].American Journal of Mathematical and Management Sciences,1993,13(3/4):323-355.