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

为有效求解带时间窗的动态车辆路径问题,建立了该问题的数学模型,通过计划周期分片,将动态问题转换为一系列的静态子问题,采用插入法构造初始解,并将重定位法、节点交换法和2-opt*法3种线路间局部搜索方法,以及2-opt法和Or-opt法2种线路内局部搜索方法的不同组合应用于初始解的改进,分析了客户出现时间、地理位置分布与不同客户时间窗范围对线路选择的影响,比较了标准算例的求解结果。结果表明:在线路间进行局部搜索时,重定位法的效果最好,2-opt*法次之,节点交换法的最差;在线路内进行局部搜索时,2-opt法优于Or-opt法;当客户请求出现时间越早,客户比较集中,客户时间窗较宽的情况下,使用的车辆数量较少,整个线路的行驶距离较短,客户延迟时间也较短。