基于群体智能算法的通勤车辆路径优化问题

Swarm Intelligence Algorithm for the Multi Destination Vehicle Routing Problem

为解决员工通勤难的问题,面向大型企业为员工提供统一接送通勤服务,研究多目的地和多车型的车辆路径问题,并建立相应的数学模型,提出群体智能算法对其进行求解。基于现实生活中通勤服务车辆实际约束,采用混合整数规划方法,以最小化运营成本为目标构建多目的地和多车型的车辆路径问题的数学模型。提出一种基于S-N链的解表示方法以及对应的解码过程和评价准则,并采用群体智能算法中的蜘蛛猴优化算法对问题进行求解。为验证蜘蛛猴优化算法的有效性,将其与粒子群优化算法进行比较。结果表明,在相同求解时间下,蜘蛛猴优化算法求解此问题的性能更优。对17组随机算例进行测试,验证所提数学模型和蜘蛛猴优化算法能够有效解决多目的地和多车型的车辆路径问题。

To solve the problem of employee commutes laborious,a multi-destination and multi-type vehicle routing problem is studied for large enterprises to provide uniform transfer and commuting services for employees.The corresponding mathematical model is built,and the swarm intelligence algorithm is used to solve the optimal solution.Based on the actual constraints of commuting service vehicles in real life,a mathematical model of multi-destination and multi-vehicle routing problem is constructed by using mixed integer programming method to minimize operating costs.A solution representation method based on S-N chain,the corresponding decoding process and evaluation criteria are developed,and the spider monkey optimization algorithm in swarm intelligence algorithm is used to solve the problem.In order to verify the effectiveness of spider monkey optimization algorithm,it is compared with particle swarm optimization algorithm.The results show that spider monkey optimization algorithm has better performance in solving this problem under the same solving time.17 groups of multi-group random examples are tested to verify that the mathematical model,by using the spider monkey optimization algorithm,the multi-destination and multivehicle routing problems can be effectively solved.