动态网络车辆路径派送问题研究-论文.pdf

《动态网络车辆路径派送问题研究-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第l7卷第8期管理科学学报V01．17No．82014年8月JOURNALOFMANAGEMENTSCIENCESINCHINAAug．2014动态网络车辆路径派送问题研究①李妍峰，高自友，李军(1．西南交通大学经济管理学院，成都610031；2．北京交通大学系统科学研究所，北京100044)摘要：讨论了带有实时交通信息的动态网络车辆路径派送问题．问题包含重复性拥堵和非重复性拥堵两种情形．用重复性拥堵下的交通信息以安排初始路径，通过采用遗传算法求解时变车辆调度问题．车辆在行驶过程中需要根据接收到的实时交通信息调整路线．

2、提出在关键点更新路线的机制，并采用Dynasearch算法求解一类特殊的旅行商问题调整路线．通过对SiouxFalls网络进行数值模拟分析，结果表明新策略能在较短时间内改进其他策略，且随着网络动态性增加其优越性更加明显．关键词：实时交通信息；交通网络；遗传算法；时变网络车辆调度问题；旅行商问题中图分类号：F253．4文献标识码：A文章编号：1007—9807(2014)08—0001—090引言动态要素有两部分：一部分是顾客的需求动态变化，另一部分是车辆的行驶时间动态变化．Tan-车辆调度问题(vehiclerouti

3、ngproblem，VRP)iguchi和Shimamoto_8指出目前文献中大多数是运筹学和组合优化领域中的热点研究问题，在DVRP问题的研究主要是针对动态的顾客需求，实际中主要出现在物流配送环节．该问题是在满对于动态行驶时间研究很少．足顾客需求的前提下，找到一组具有最短路径或考虑动态行驶时间的DVRP问题主要包括预最小行驶时间的车辆路线．对于这类问题的研究，测型VRP和基于实时交通信息的DVRP．对于大多数学者考虑所有信息均为静态或事先可以获预测型VRP，路段行驶时间随时问变化但事先可悉．但实际路段走行时间往往会受

4、到交通事故、天以通过预测确定，可以在车辆出发前安排最优路气变化和高峰期的影响不停变化．新顾客需求也线．该问题适用于受上下班高峰期影响的重复性可能在车辆配送过程中才出现．静态VRP理论和拥堵情形．对该问题的处理通常是把一天分为几方法已不能应用于解决该问题．另一方面，现代通个时段，在不同时段内车辆在同一路段上行驶时信技术和智能交通系统的不断发展使得实时获取间不同．该问题也被称为时变VRP(timedepend—和处理信息更加方便．在这种背景下研究动态entvehicleroutingproblem，TDVRP)，最早由Ma

5、—VRP(dynamicvehicleroutingproblem，DVRP)具有landraki提出．随后Malandraki和Daskin⋯、Hill非常重要的实际意义．和Benton[、Malandraki和Dial[坦j、Ichoua等、在DVRP问题的研究中，Psaraftis¨lJ、Bertsi—mas和Ryzin_2-3]和Powell等做了早期的工作．Kok等¨对该问题进行了深入研究．在实时交通Ghiani等和Pillac等对DVRP问题做了很好信息下的DVRP问题中，路段行驶时间受到非重的综述．Pot

6、vin等指出在DVRP问题中主要的复性拥堵情形下突发交通事故的影响发生变化，①收稿日期：2011—04—27；修订日期：2012—04～22．基金项目：国家自然科学基金资助项目(71090402；71001005；71361006)．作者简介：李妍峰(198O一)，女，四川乐山人，博士，副教授，硕士生导师．Email：yanwaa@126．toni一2一管理科学学报2014年8月并且变化事先无法得知．车辆在行驶过程中需要堵(如交通事故、天气变化)的影响而不断变化．根据实时的交通信息更新路线．因此在这类问题车辆在行驶过程

7、中需要根据实时接收到的信息调中如何更新路线是解决问题的关键．文献中相关整路线．由于本文仅考虑派送情形，不包含取货，的实时更新路线机制主要包括两类：一类是只在在初始阶段当顾客的货物分配给车辆后，所有这顾客处更新路段走行时间J．在这种机制下，些顾客的货物都已经装载在初始分配的车辆上，若车辆在去往下一个顾客的途中遇到交通拥挤或因此在行驶过程中不能改变每辆车服务的顾客集者交通事故，由于没有及时更新信息将导致车辆合，但可以改变顾客访问顺序和车辆行驶路线．陷入较长的等待中．第二类为每隔一段时间更新车辆的初始路线安排和顾客订单分配通

8、过求路段走行时间¨悖j．这种更新机制的效率取决于解预测型VRP或TDVRP问题得到【8,16]．车辆在更新时间间隔的选取．若更新时间间隔越大，对外交通网络中路段行驶时间被设定为时间的阶段函界环境的变化反应就越迟缓．若更新时间间隔越数，在不同的时段内，车辆在同一路段上的行驶时小，反应更敏捷，但也增加了路线重新规划的计算间可能会发生变