基于遗传算法的快递配送车辆路径问题研究

Study on VRP in Express Distribution Based on Genetic Algorithm

在快递配送过程中,快递配送中心作为货物集散点,首先要分派车辆到各个配送点(客户)送货和取货,为降低配送成本,提高配送效率,车辆的调度是一个重要的问题。根据快递配送的特点,主要研究的车辆路径问题为配送中心在为各分点进行快递配送时,采用快件送达和收集同时服务的配送策略,假设车辆在各点之间的行驶时间服从正态分布,配送分点有软时间窗约束并且快件收集数量服从泊松分布的条件下,建立了问题的求解模型,并进行了基于遗传算法求解的应用设计。该遗传算法通过基于适应度排名和最佳个体保留的选择策略和自适应交叉概率的参数控制来保证所求结果的优良性,并设计算例用matlab编程进行实验,证明了算法的可行性。

In this paper, in accordance with the characteristic of express distribution, we mainly studied the vehicle routing problem in the express distribution to the various branching points of the distribution center which practiced express delivery and simultaneous collecting and dispatching. Assuming the traveling time of the vehicles between the points followed normal distribution, the distriobution points were constrained by a soft time window and the number of the express parcels collected followed the Poisson distribution, we established the model of the problem and designed the genetic algoriihm for its solution, which, through the strategy of selection based on fitness ranking and optimal unit reservation and adaptive crossover probability, ensured the superiority of the result obtained. At the end, we used the matlab programming in a numerical example to validate the feasibility of the algorithm.