甘 宝，薛玉玺，魏文萍

（兰州交通大学 交通运输学院，甘肃 兰州 730070）

基于改进遗传算法的车辆路径问题

甘 宝，薛玉玺，魏文萍

（兰州交通大学 交通运输学院，甘肃 兰州 730070）

为了研究物流中心的服务效率和车辆的合理调度方案，以汽车载重量作为影响车辆路线安排的主要因素，以经典的车载容量约束条件下的车辆路径问题为原型建立数学模型，通过求解该数学模型的最优解来获得车辆最优路径。由初始状态随机生成的可行解作为初始的车辆路径方案，通过改进的遗传算法不断地调整染色体的交叉和变异概率进行优化，最终得到物流中心车辆安排的合理方案。通过多次求解算例，都能够得到满意的车辆路径方案，不仅验证了该数学模型的有效性和实践性，而且也验证了改进后遗传算法的收敛性和鲁棒性，同时得到了改进遗传算法交叉和变异概率的调整范围。该模型和算法不仅可以提高物流中心的服务效率，而且可以为物流中心的车辆调度方案提供支持和帮助。

物流配送；车辆路径问题；遗传算法；交叉算子；收敛性

0 引言

当代物流业在电子商务的推动下蓬勃发展，客户对货物配送的要求也越来越高。就配送中心而言，要考虑如何降低配送费用、缩短配送时间以及提高配送效率和服务水平等。要实现这些目标，车辆路径安排（又称车辆路径问题，Vehicle Routing Problem，简称VRP）是关键所在。该问题由Dantzig和Ramse[1]于1959年首先提出，其一般定义为：对一系列装、卸点，合理组织行车路线，使车辆有序地通过它们，在满足一定的约束条件（如：货物需求量、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如：费用最少、时间最短、用车数最少等）。……