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

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

Routing and Scheduling Optimization of Freeway Service Patrols Based on the Improved Algorithm Combined Genetic with Simulated Annealing

In order to allocate the limited Freeway Service Patrols (FSP) resources reasonably, the optimization model of the deterministic FSP routing and scheduling was established. the problem of deploying the limited FSP resource was investigated, the objective of the optimization modeling based on the full coverage model was minimizing the overall average incident response time; the connected routing was treated as a chromosome, the improved algorithm combined genetic with Simulated Annealing was coded based on MATLAB, dynamic crossover and mutation probability and the Metropolis criterion for simulated annealing was added to the progeny update, moreover, the dynamic genetic algorithm was used to vehicle scheduling in the improved algorithm; the improved algorithm was validated based on Sioux Falls" network and data, and the calculated results were compared with the corresponding scenario and simulated annealing algorithm. The results show that the results were reduced by 23.35% and 28.28% compared the improved algorithm with the corresponding scenario, moreover, a comparison with the simulated annealing algorithm shows that the improved algorithm performs better in searching for the optimal solution and computational efficiency, and it is more suitable for medium and large road network in Routing and Scheduling Optimization.