带时间窗的动态车辆路径问题的局部搜索算法  

Local search alogrithm of dynamic vehicle routing problem with time window

作　　者：刘霞[1,2] 齐欢[1] 

机构地区：[1]华中科技大学控制科学与工程系,湖北武汉430074 [2]江汉大学物理与信息工程学院,湖北武汉430056

出　　处：《交通运输工程学报》2008年第5期114-120,共7页Journal of Traffic and Transportation Engineering

基　　金：国家自然科学基金项目(60574025)

摘　　要：为有效求解带时间窗的动态车辆路径问题,建立了该问题的数学模型,通过计划周期分片,将动态问题转换为一系列的静态子问题,采用插入法构造初始解,并将重定位法、节点交换法和2-opt*法3种线路间局部搜索方法,以及2-opt法和Or-opt法2种线路内局部搜索方法的不同组合应用于初始解的改进,分析了客户出现时间、地理位置分布与不同客户时间窗范围对线路选择的影响,比较了标准算例的求解结果。结果表明:在线路间进行局部搜索时,重定位法的效果最好,2-opt*法次之,节点交换法的最差;在线路内进行局部搜索时,2-opt法优于Or-opt法;当客户请求出现时间越早,客户比较集中,客户时间窗较宽的情况下,使用的车辆数量较少,整个线路的行驶距离较短,客户延迟时间也较短。In order to effectively solve dynamic vehicle routing problem with time windows, the mathematical model was established, the planning period was cut into slices, and the dynamic problem was partitioned into a series of static sub-problems, the initial solutions were constructed by intertion method. Three inter-route local search approaches including relocation, exchange and 2-opt＊ , and two intra-route local search approaches including 2-opt and Or-opt were introduced, different approaches were combined to improve initial solutions. The influences of arrival time, distribution of geographical location and time window range on route selection were analyzed, and the solving results of standard example were compared. Result shows that relocation method is the best, 2-opt＊ is the second and exchange is the worst for inter-route local search, 2-opt is better than Or-opt for intra-route local search, and the vehicle number, traveling distance and delay of all routes decrease with early requests, concentrated customers and wide time windows. 2 tabs, 6 figs, 10 refs.

关 键 词：交通规划 动态车辆路径问题 局部搜索 时间窗 

分 类 号：U492.22[交通运输工程—交通运输规划与管理]