【作者】 邓欣；

【导师】 朱征宇；

【作者基本信息】 重庆大学 ， 计算机软件与理论， 2007， 硕士

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

【Abstract】 It’s the high time that the delivering of goods in the logistics shares the large part of the benefit. So the research of the VRP(vehicle routing problems) has the very important significance for the core role of the logistic economic. In nowadays, the big logistic companies not only have one depot but for the distributed depots in large area, and it causes the MDVRP(multi-depot vehicle routing problems). Involved by the NP hard problems, the MDVRP can’t be resolved to achieve the perfect outcome. So the genetic algorithm (short for GA) is considered by this paper. The GA has the character of the biologic evolution with the crossover, mutation procedure and has the globe research of the result space to find out the excellent result. This paper designs two different kind of the GAs to resolve the MDVRP for the different scale. For the small scale of the MDVRP, the Partheno-Genetic Algorithm (short for PGA ) is used. But for the larger size of the MDVRP, the GA with the virtual depot is used. The PGA has the characteristic of the quick research of the result but for the lack of the capability of finding excellent outcome in larger size MDVRP. Though the GA with the virtual depot has the slow speed in researching the outcome contrasted to PGA, it has the good ability to achieve the perfect result especially larger scale MDVRP.This paper contributes to the research of MDVRP in four aspects:①Discuss the mathematics model of the MDVRP and the research methods. After that this paper establishes the mathematics model and then puts its own research method.②Using the Partheno-Genetic Algorithm to resolve the small size of the MDVRP, this paper constructs the algorithm of crossover, mutation and local search of PGA.③To resolve the larger size of the MDVRP the GA with virtual depot is used. Firstly, the MDVRP can be transferred to the single depot VRP by added the virtual depot. Then the GA with crossover and mutation operation can resolve the VRP with the virtual depot.④This paper uses many different kind of test dada to test the performance of the PGA and the GA with virtual depot. By the test, it can illustrate the different using range of the two algorithms.In this paper, it introduces the research background and the research actuality firstly. Then it describes the MDVRP and then brings forward the mathematics model of the MDVRP. In the third chapter, this paper illustrates the PGA including the data structural, the decode method, the crossover, the mutation and the loach search operation. It also claims that the PGA can transfer the MDVRP to several single depot VRPs and resolves them synchronously and has the good result in the small size of the MDVRP. At the fourth chapter, this paper describes the GA with virtual depot to how to resolve the larger scale of the MDVRP. The main idea is adding the virtual depot to the MDVRP and transfer the MDVRP to one single VRP. Though it will cost more time than the PGA, it has the good performance in resolve the larger ones. At last, this paper designs the simulation system which can be used for real life. It uses many different kind of test dada to test the performance of the PGA and the GA with virtual depot. By the contrast test of the two algorithms, it can illustrate the different using range of the two algorithms.There is still some difference between the academic research and the real life using. The two algorithms in this paper are suit for the single kind of vehicle. Our next step is to invent new algorithms to resolve the real problems in logistics, and justify them by testing in experiment or by the application of real life.更多还原