【作者】 蔡景稳；

【导师】 赵建民；

【作者基本信息】 浙江师范大学 ， 计算机软件与理论， 2011， 硕士

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

【Abstract】 In recent years, Logistics Distribution has become an important "third-party source of profit ", an important part in national economy. Vehicle Routing Problem the is core content area of Logistics Distribution. Therefore, the research on the vehicle routing problem is very important theoretical and practical significance. Today, many logistics companies usually have more than one distribution center (depot). Multiple-Depot Vehicle Routing Problem has become an important new area of research.MDVRP is NP hard problem. Its optimal solution can not be obtained in polynomial time. Modern heuristic settling for less obtaining suboptimal solution of the problem within an acceptable time, has become an important research direction. This article uses an improved genetic algorithm to solve the problem. Genetic algorithms is bioniced by simulate biological evolution of natural selection and genetic mechanism of biological evolution.Using Chromosome crossover and mutation process in the evolutionary process to global search better solution within the solution space. In this paper, I have improverd genetic algorithm,with natural number coding chromosome, improved crossover operator and increasing the external perturbation techniques within the study multi-depot vehicle routing problem.The main work of this paper. First through the multiple depot vehicle routing problem-based learning,established mathematical model and summarized different research methods. Second let MDVRP transformed into general VRP problom by increasing virtual distribution center. Third using improved genetic algorithm to solve the problom.Finally testing different data sets, analyzing, comparing and summarizing experiment results to prove the validity and scope of the improved algorithm.更多还原