田帅辉 欧丽英

摘  要：城市居民小批量、个性化、便利化、高效化等配送需求以及日益拥堵的城市交通对城市配送效率提出更高的挑战。针对城市配送路径优化问题，以平均配送时间与总配送费用帕累托最优为目标，构建考虑时间窗的城市配送车辆路径优化模型，对遗传算法进行改进，在标准遗传算法的基础上加入筛选算子和择优算子并适当改进初始种群设计和选择、交叉算子，最后通过算例验证模型的可行性和改进算法的有效性。结果表明改进后的遗传算法在求解考虑时间窗的车辆路径优化模型时，相较于标准的遗传算法的寻优能力有显著优势。

关键词：改进遗传算法;时间窗;多目标优化;城市配送

中图分类号：F272.14    文献标识码：A

Abstract： The distribution needs of urban residents， such as small batch， individualization， convenience， high efficiency and increasingly congested urban traffic， pose a higher challenge to the efficiency of urban distribution. Aiming at the problem of urban distribution routing optimization， taking the Pareto optimization of average distribution time and total distribution cost as the objective， a vehicle routing optimization model with time windows for urban distribution considering time window is construct， and the genetic algorithm is also improved， which is added screening operator and optimizing operator on the basis of standard genetic algorithm， and the initial population design and selection， crossover operator is improved appropriately. Finally， the feasibility of the model and the effectiveness of the improved algorithm are verified by an example. The results show that the improved genetic algorithm has significant advantages over the standard genetic algorithm in solving the vehicle routing optimization model with time windows.

Key words： improved genetic algorithm; time window; multi-objective; urban distribution

0  引  言

近年來，随着电子商务、O2O、新零售等新型商业模式的迅猛发展，全国城市配送市场规模已突破万亿，预计2021年将超过2万亿。同时，我国城市居民的消费需求呈现小批量、个性化、多样化、便利化、高效化等特征，这对城市配送效率提出了更高的要求和挑战。

围绕城市配送路径优化，国内外学者进行了深入的研究。关于城市配送路径优化，部分学者从优化算法的角度进行研究。其中，吴聪[1]令遗传算法交叉系数和变异系数随适应度的大小、迭代次数和进化过程中个体未改变的数目自适应调整;罗勇[2]提出对遗传算法算子进行改进;申艳光[4]、胡钟骏[5]等则将遗传算法与其他算法进行结合，结合其他算法的优势来弥补遗传算法的不足。……