《基于遗传算法的车辆路径问题研究》由会员分享，可在线阅读，更多相关《基于遗传算法的车辆路径问题研究（27页珍藏版）》请在金锄头文库上搜索。
1、武汉理工大学毕业设计论文说明书基于遗传算法的车辆路径问题研究中文摘要：近些年,物流作为“第三利润源泉”受到国内各行业的极大重视并得到较大的发展。物流的目标就在于以最少的费用满足消费者的需求。配送作为物流中一种特殊的、综合的活动形式,在当今社会经济发展中发挥着越来越重要的作用。配送的核心为配送车辆的调度、货物配装及送货过程。进行配送系统优化,主要是配送车辆调度的优化。对配送车辆进行优化调度,有利于提高物流经济效益、实现物流科学化。本文主要对单车场非满载无时间窗的车辆路径问题和动态车辆路径问题进行了研究。论文首先对现有车辆优化调度问题归类分析。然后对车辆路径问题的传统求解算法的基本思想、性能、适用
2、性进行了分析,在此基础上提出了采用扫描法和遗传算法相结合的启发式算法来求解物流配送车辆优化调度问题的思想。在对遗传算法中的选择操作、邻域结构操作进行改进的基础上,提出了一种求解车辆路径问题的自适应遗传算法。应用C语言编程进行实例计算,结果表明改进的遗传算法明显增强了群体演化的质量,提高了算法的收敛速度,得到了问题的满意解。与传统遗传算法相比,扫描法和改进遗传算法的结合,其优化能力、运行效率、可靠性均有一定的提高。最后论文在对动态行驶时间车辆路径问题进行建模的基础上,尝试采用扫描法和改进遗传算法相结合的方法对此类问题进行求解,在保证客户服务水平的要求下,取得了比较好的结果。关键词：物流车辆路径问
3、题; 扫描法; 遗传算法Abstract:Recent years, logistics, taken as the third profit resource, has been developing rapidly. The object of logistics is to satisfy the requirements of consumers with least cost. As an especial and integrated activity of logistics, physical distribution plays an important role in mo
4、dern society. Vehicle Routing Problem (VRP) is the main part of the distribution system optimizing. It is benefits to make economic benefits.This paper mainly studied a type of vehicle routing problem with single depot, non-full load and without time windows and a dynamic vehicle routing problem. Th
5、e restrictions and math models of vehicle routing problem is analyzed. This paper also compared and analyzed the basic ideas, capabilities and applicability of tradition method heuristics of VRP. Based on this, this paper put forward an improved genetic algorithm for vehicle routing problem, through
6、 changing its select operation and neighborhood structure operation, an adaptive genetic algorithm was presented for solving this problem. Computational results based on C language programming demonstrated that the adaptative algorithm improved the quality of the results and can solve the problem ef
7、fectively. Exemplifications proved that this algorithm can enhance capability of optimization, solving efficiency and reliability of running. Finally, a dynamic vehicle routing problem with random time window is modeled. This problem is also solved by sweep and genetic algorithms method. The method
8、have made good effect in ensuring customer service level.Keyword: Vehicle Routing Problem; sweep method; genetic algorithm1引言车辆路径问题（Vehicle Routing Problem，VRP）是一类在物流配送调度中具有广泛应用的优化组合问题，在现代物流中居于中心地位。 本文首先介绍了遗传算法在解决简单约束车辆路径问题上的应用，改进了交叉算子，为研究有时间窗装卸问题的遗传算法作了充分准备。本文详细分析了有时间窗装卸问题的数学模型，深入研究解决此问题的分组编码遗传算法，将
9、禁忌思想用于产生可行解的启发式插入搜索算法之中，并构造出适用于多目标的适应度函数，设计新的数据结构，对分组编码遗传算法进行有效实现。在分组编码遗传算法中提出路径调整思想，设计出一种多策略分组编码遗传算法。采用多组通用算例测算，将多策略分组编码遗传算法与其它算法进行比较，其求解结果和计算时间都有明显改进，验证了多策略分组编码遗传算法能够有效稳定地收敛到所求问题的解。VRP 最早由Dantzig 和Ramser 于1959 年提出，引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科研究人员的极大重视，成为运筹学与组合优化领域的热点问题。各国研究人员对该问题进行了大量的理论研
10、究及实验分析，取得了重大进展，其研究成果在运输系统、公交车辆路线设计、快递收发系统、物资调配系统中都已得到了广泛应用。研究车辆路径问题的特点及算法具有重要的实际意义。本文重点研究解决有时间窗装卸问题（PDPTW）的遗传算法，作为前期准备，本文作者对遗传算法解决具有简单约束条件的VRP（包括有容量约束的车辆路径问题CVRP 和有时间窗的车辆路径问题VRPTW）进行了初步研究。有容量约束的车辆路径问题（Capacitated Vehicle routing problem，CVRP）是由一个服务中心（或车场）的若干车辆向多个客户点进行配送服务，在已知待服务客户点和出发点的位置、客户需求及车辆最大负
11、载的前提下，设计车辆配送路径，规划设计方案，使运输成本最小化，即总代价最小（使用车辆尽量少，行车总距离尽量短）。CVRP 实际是多目标组合优化问题，一般以派出车辆最少（运输路线条数最少）为首要目标，行车总距离最短，即总代价最小为次要目标。CVRP 要求满足以下条件及假设：（1）所有的配送车辆以配送中心为起点并最终回到配送中心；（2）每条配送路径上各客户点的需求量之和不超过车辆的负载量；（3）每个客户点的需求仅由一辆车一次满足。2选题的目的物流已被认为是继降低原材料消耗和提高劳动生产率之后的“第三利润源”。通过优化物流系统,可以降低物流成本,从而增强企业的市场竞争能力。因此,研究物流系统中的优化
12、问题,具有十分重要的意义,是国内外研究的一个热点。 库存成本与配送成本是物流系统的核心成本,在物流总成本中占据了很大的比例。如果能降低库存成本与配送成本,就能有效地降低物流成本。 遗传算法是一种应用很广泛的智能优化算法,本文对遗传算法进行了分析研究,针对遗传算法的一些缺陷提出了相应的改进方法。在上述研究基础上,本文基于遗传算法,研究了物流系统中的库存优化问题及车辆路径问题。本文将库存仿真优化问题与车辆路径问题都看作是组合优化问题,并应用遗传算法进行求解。 本文的主要研究工作及贡献可归纳如下: (1)对随机库存系统建立了基于离散事件系统的计算机仿真模型。用系统仿真方法求解最优库存策略时,其难点之
13、一在于仿真的优化。为此,本文将计算机仿真技术和遗传算法相结合,应用遗传算法来优化模型的控制参数,即获得最优的库存控制策略。针对随机系统的特点,设计了候选解收集器,它能够收集在仿真优化过程中产生的Pareto解;提出了M精英选择算子,用于保护潜在的最优个体,使它们在交叉、变异算子中不被破坏。针对两种常用的库存控制策略进行了仿真优化的实验,结果表明本文提出的仿真优化方法是有效的。 (2)旅行商问题(TSP)是车辆路径问题的子问题。为了求解TSP问题,研究了常用于TSP问题的三种交叉算子的优化效果,提出了一种求解TSP问题的高效混合遗传算法HGA-TSP。在该算法中以变形的OX算子作为交叉算子,以2
14、-opt算法作为遗传算法的变异算子;提出了K近邻点集的概念以缩减搜索空间并提高算法的时间效率。 (3)将单配送中心,多辆运输车且无约束的车辆路径问题建模成具有总路径长度最短、子路径长度均衡性好这两个目标的双目标多旅行商问题(MTSP),并基于HGA-TSP算法,研究了三种求解上述问题的解决方案。 (4)对于带能力约束的车辆路径问题(CVRP),提出了一种新的双层染色体编码方案和一种子路径交换算法。双层染色体编码方案不需要预先知道最优解所需要的车辆数,并能确保染色体不违反能力约束,这更适合求解实际物流配送系统中的车辆路径问题。此外,相对于常用的单层染色体编码方案,该编码方案还能降低搜索空间的大小
15、,从而提高搜索效率并降低计算时间。子路径交换算法可以有效提高遗传算法的求解精度。基于上述双层染色体编码方案和子路径交换算法,设计了两种求解CVRP问题的混合遗传算法,分别是HGA-CVRP算法和HGA-SE-CVRP算法。 (5)对于带时间窗约束的车辆路径问题(VRPTW,首先改进了双层染色体编码方案,以便在编程实现时更方便地进行子路径的处理。然后研究了遗传算法与邻域搜索算法的结合方式,在遗传算法中引入了带克隆操作的邻域搜索算子。最后提出了一种求解VRPTW问题的新型混合遗传算法HGA-VRPTW。 (6)综合应用了面向对象分析与设计、多线程、UML等先进的软件开发方法与技术,设计并开发了VR
16、P仿真实验室,这是一个用于研究车辆路径问题的软件包,具有使用简便、界面美观的特点。VRP仿真实验室在本文的研究中发挥了重要的作用,是研究车辆路径问题的有力工具。本文对大量的基准测试实例(Benchmark)进行了仿真计算,计算结果表明,本文所提出的一系列算法能有效求解物流系统中的库存优化问题与车辆路径问题。3 问题描述3.1车辆路径问题定义车辆路线问题（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。 由此定义不难看出，旅行商问题（Traveling Saleman Pro
