混合遗传算法的多因素快递配送车辆路径分析

Study on vehicle path for package delivery with multiple factors based on hybrid genetic algorithm

针对快递配送过程中存在多种影响配送效率和成本的因素,建立时间成本数学模型.该模型考虑到客户接收的时间约束、拥堵路段不同时段的时间成本,以及配送时间约束等因素.并在此基础上提出一种混合遗传算法,该算法采用特有的编码方式,实现对车辆路径、配送时间节点、误点时间成本等信息的编解码,此外考虑到标准遗传算法在搜索大规模数据时易出现早熟收敛,搜索效率下降等问题,该混合遗传算法增加了局部搜索模块,通过三角分布概率更新劣等基因,从而提高算法的局部搜索能力.通过仿真实验得到快递车辆配送路径及配送时间节点等优化信息,并验证了算法和数学模型的有效性.

Considering there are multiple factors affecting delivery efficiency and cost of package in the process of express,this paper develops a mathematical model with clients’time constraint of receiving,time cost in jammed traffic at different time and time constraint of delivery.Besides,a modified hybrid genetic algorithm is proposed which having a specialized coding and decoding strategy considering multi-factors including path,de⁃livery node time,cost of delay time and other information.Furthermore,with the consideration that the standard genetic algorithm easily falls into premature convergence and has low search efficiency,a local search module which can update inferior genes according to a strategy of triangular probability distribution is proposed to im⁃prove the genetic algorithm.Finally,the effectiveness of the algorithm and mathematical model are verified through numerical experiments,and the delivery path,delivery time and other information are determined.