遗传算法在多车场车辆路径问题中的应用研究

摘要

当前,物流配送已成为企业重要的“第三方利润源”。车辆路径问题(VehicleRouting Problem,VRP)是物流配送领域的核心内容。对车辆路径问题的研究具有非常重要的理论与现实意义。如今物流企业通常不只拥有一个配送中心(车场),而是拥有多个配送中心,多车场车辆路径问题(Multiple-Depot Vehicle Routing Problem,MDVRP)逐渐成为车辆路径问题领域的重要的新研究方向。
　　 MDVRP属于NP难问题,即无法在多项式时间内求得最优解。现代启发式算法退而求其次,在可接受时间范围内求得问题的次优解,逐渐成为求解车辆路径问题的一个重要方向。因此本文采用改进的遗传算法对其进行求解。遗传算法是模拟生物进化论的自然选择和遗传学机理的生物进化过程仿生设计的,利用染色体在进化过程中的交叉、变异等过程,在解空间内进行全局搜索,寻求更优解。本文在对多车场车辆路径问题的研究中,改进了遗传算法,采用自然数编码染色体、改进的交叉算子及增加内外扰动等技术来求解。
　　 本文的主要工作:1)通过对多车场车辆路径问题的学习,建立数学模型,并对不同研究方法进行总结归纳；2)增加了虚拟配送中心的方法,将多车场问题转化为单车场问题；3)采用改进的遗传算法对其求解。通过不同的数据集的测验,并对实验结果进行分析、比较和总结,证明改进算法有效性和适用范围。