基于改进遗传退火算法的高速公路巡逻车路径优化调度

摘要

cqvip:为了合理分配有限的高速公路巡逻车资源,构建了确定型高速公路巡逻车路径及调度优化模型。探讨了有限巡逻车资源路径、调度优化建模问题;构建了以全覆盖模型为基础,以事故响应时间最小为目标的优化模型。将连通的路径作为染色体,基于MATLAB对改进的遗传退火算法进行编码,采用动态交叉及变异概率,在交叉变异后子代更新中引入模拟退火算法Metropolis准则;并在改进的遗传退火算法中加入动态规划算法对巡逻车进行分配。以Sioux Falls路网及数据,对MATLAB编码的遗传退火算法进行验证,计算结果与两种情景假设及模拟退火算法优化结果作比较。结果表明:改进的遗传退火算法求解结果比相应的情景假设求得事故响应时间分别减少了23.35%与28.28%;与模拟退火算法求解结果相比,该方法具有更好的寻优效果及计算效率。MATLAB编码的改进遗传退火算法对中大型路网路径、调度寻优效果较好。