多车型开放式车辆路线问题的混合启发式算法

王晓博，任春玉，李海晨

多车型开放式车辆路线问题的混合启发式算法

王晓博，任春玉，李海晨

多车型开放式车辆路线问题，是物流配送优化中不可缺少的环节。针对标准遗传算法存在收敛速度慢，局部搜索能力差，易早熟的缺点，采用混合启发式算法进行优化求解。采用实数序列编码，使问题变得更简洁；有针对性地构建初始解，提高了解的可行性；用基于排序的选择与最佳保留相结合策略，保证群体的多样性；引入部分算术交叉算子，加强染色体的全局搜索能力；利用模拟退火算法的Boltzmann机制，控制遗传算法的交叉、变异操作，提高了算法的收敛速度和搜索效率。仿真结果表明混合启发式算法在求解质量和计算效率上好于标准遗传算法。

多车型开放式车辆路线问题；实数序列编码；部分算术交叉算子；Boltzmann机制；混合启发式算法

1 引言

开放式车辆路线问题（Open Vehicle Routing Problem，OVRP）是经典车辆路线问题（Vehicle Routing Problem，VRP）的拓展问题。OVRP和VRP最显著的区别在于：车辆在服务完最后一个顾客点后，不要求其回到出发车场，若需要回到车场，则必须沿原路返回。

目前研究较多的是车辆路线封闭问题，就是大家所熟知的VRP问题，但对于开放的车辆路线安排问题的研究结果还不多。

OVRP问题研究方法主要有精确算法、启发式算法和智能优化方法。精确性算法在可以求解的情况下，其解通常要优于人工智能算法；但其算法只能有效求解中小规模的OVRP问题[1]。

在解决实际较大规模的问题时，启发式算法能够在较少时间内，求出满足实际需要的满意解，尽管这个解实际上不是最优的。……