原文传递
基于遗传算法的多车场车辆路径问题研究
| 论文题名： | 基于遗传算法的多车场车辆路径问题研究 |
| 关键词： | 多车场;车辆路径;遗传算法 |
| 摘要： | 物流配送所获取的利润在现代物流企业利润中所占比例非常大，而车辆路径问题又是物流配送中的核心问题。因此对车辆路径问题(VRP)的研究具有非常重要的意义。在实际生活中，大型的物流企业并不只拥有一个配送中心(车场)，而是拥有多个配送中心，这便引出了多车场车辆路径问题(MDVRP)。MDVRP属于NP难问题，求得最优解相当困难，因此该文便采用遗传算法对其进行求解。遗传算法是利用了生物进化的特点，利用染色体在进化过程中的交叉、变异过程，对问题的解空间进行全局搜索，从而寻求较优解。在对多车场车辆路径问题的研究中，设计了两种遗传算法，来适应不同的需求。对小规模，或者求解效果要求不高的数据集，采用单亲遗传算法；而对规模较大，要求求解效果较好，时间要求不高的数据集，采用基于虚拟车场的遗传算法。 该文对MDVRP进行了研究，其主要贡献有以下几个方面： ①对MDVRP的数学模型以及研究方法进行了探讨，构造出了数学模型，并对不同的研究方法进行了归纳总结，并提出了自己的研究方法。 ②在对于小规模数据时，采用把多车场问题转化成多个单车场问题并行解决的方法，使用单亲遗传算法的思想，构造出相应的遗传算子对多车场车辆路径问题进行求解。 ③在对于大规模数据时，采用增加虚拟车场的方法把多车场车辆路径问题进行转换成单车场车辆路径问题，采用普通遗传算法的思想，并构造出相应的遗传算子对其进行求解。 ④对不同规模的数据集进行测试，证明了该文提出的两种解决方法的各自的不同应用场合。所做的模拟系统能用于物流企业，具有实际适用价值。 从论文结构上来看，该文首先介绍了MDVRP的研究背景和当前的研究现状。然后该文对MDVRP进行了描述，提出了该问题的数学模型。在第三章里面，详细介绍了在对小规模的MDVRP进行求解的时候，所采用的单亲遗传算法。单亲遗传算法对MDVRP的求解是针对于把MDVRP转化为多个VRP的解决方法而设计的，其特点是运算速度快。然后在第四章介绍了基于虚拟车场的遗传算法来解决较大规模的MDVRP问题。这种方法的主要思想是增加一个虚拟车场，把多车场问题转化为一个单车场问题加以解决。适应范围是对求解时间要求不高，数据量大的数据集。最后该文设计了模拟系统来测试不同规模的多个实验数据集，并对各个数据集进行求解。在求解的同时对照其它文献的数据进行对比，从而验证算法的优劣性。MDVRP与物流配送中的实际问题有一定的差距，其只适用于单车型MDVRP，则下一步工作目标便是设计更能符合实际物流配送的算法，通过实验和实际运用验证其有效性和实用性。 |
| 作者： | 邓欣 |
| 专业： | 计算机软件与理论 |
| 导师： | 朱征宇 |
| 授予学位： | 硕士 |
| 授予学位单位： | 重庆大学 |
| 学位年度： | 2007 |
| 正文语种： | 中文 |
检索历史
应用推荐
