基于遗传算法的车辆路径问题研究

利用遗传算法对路径问题的研究与分析

基于遗传算法的车辆路径问题研究

中文摘要：近些年,物流作为“第三利润源泉”受到国内各行业的极大重视并得到较大的发展。物流的目标就在于以最少的费用满足消费者的需求。配送作为物流中一种特殊的、综合的活动形式,在当今社会经济发展中发挥着越来越重要的作用。配送的核心为配送车辆的调度、货物配装及送货过程。进行配送系统优化,主要是配送车辆调度的优化。对配送车辆进行优化调度,有利于提高物流经济效益、实现物流科学化。本文主要对单车场非满载无时间窗的车辆路径问题和动态车辆路径问题进行了研究。论文首先对现有车辆优化调度问题归类分析。然后对车辆路径问题的传统求解算法的基本思想、性能、适用性进行了分析,在此基础上提出了采用扫描法和遗传算法相结合的启发式算法来求解物流配送车辆优化调度问题的思想。在对遗传算法中的选择操作、邻域结构操作进行改进的基础上,提出了一种求解车辆路径问题的自适应遗传算法。应用C语言编程进行实例计算,结果表明改进的遗传算法明显增强了群体演化的质量,提高了算法的收敛速度,得到了问题的满意解。与传统遗传算法相比,扫描法和改进遗传算法的结合,其优化能力、运行效率、可靠性均有一定的提高。最后论文在对动态行驶时间车辆路径问题进行建模的基础上,尝试采用扫描法和改进遗传算法相结合的方法对此类问题进行求解,在保证客户服务水平的要求下,取得了比较好的结果。

关键词：物流车辆路径问题; 扫描法; 遗传算法

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 modern 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. The 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 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 effectively. 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 have made good effect in ensuring customer service level.

Keyword: Vehicle Routing Problem; sweep method; genetic algorithm

利用遗传算法对路径问题的研究与分析

1引言

车辆路径问题（Vehicle Routing Problem，VRP）是一类在物流配送调度中

具有广泛应用的优化组合问题，在现代物流中居于中心地位。 本文首先介绍了遗传算法在解决简单约束车辆路径问题上的应用，改进了交叉算子，为研究有时间窗装卸问题的遗传算法作了充分准备。本文详细分析了有时间窗装卸问题的数学模型，深入研究解决此问题的分组编码遗传算法，将禁忌思想用于产生可行解的启发式插入搜索算法之中，并构造出适用于多目标的适应度函数，设计新的数据结构，对分组编码遗传算法进行有效实现。

在分组编码遗传算法中提出路径调整思想，设计出一种多策略分组编码遗传

算法。采用多组通用算例测算，将多策略分组编码遗传算法与其它算法进行比较，其求解结果和计算时间都有明显改进，验证了多策略分组编码遗传算法能够有效稳定地收敛到所求问题的解。VRP 最早由Dantzig 和Ramser 于1959 年提出，引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科研究人员的极大重视，成为运筹学与组合优化领域的热点问题。各国研究人员对该问题进行了大量的理论研究及实验分析，取得了重大进展，

其研究成果在运输系统、公交车辆路线设计、快递收发系统、物资调配系统中都已得到了广泛应用。

研究车辆路径问题的特点及算法具有重要的实际意义。本文重点研究解决有

时间窗装卸问题（PDPTW）的遗传算法，作为前期准备，本文作者对遗传算法解决具有简单约束条件的VRP（包括有容量约束的车辆路径问题CVRP 和有时间窗的车辆路径问题VRPTW）进行了初步研究。有容量约束的车辆路径问题

（Capacitated Vehicle routing problem，CVRP）是由一个服务中心（或车场）的若干车辆向多个客户点进行配送服务，在已知待服务客户点和出发点的位置、客户需求及车辆最大负载的前提下，设计车辆配送路径，规划设计方案，使运输成本最小化，即总代价最小（使用车辆尽量少，行车总距离尽量短）。CVRP 实际是多目标组合优化问题，一般以派出车辆最少（运输路线条数最少）为首要目标，行车总距离最短，即总代价最小为次要目标。CVRP 要求满足以下条件及假设：

利用遗传算法对路径问题的研究与分析

（1）所有的配送车辆以配送中心为起点并最终回到配送中心；

（2）每条配送路径上各客户点的需求量之和不超过车辆的负载量；

（3）每个客户点的需求仅由一辆车一次满足。

利用遗传算法对路径问题的研究与分析

2选题的目的

物流已被认为是继降低原材料消耗和提高劳动生产率之后的“第三利润

源”。通过优化物流系统,可以降低物流成本,从而增强企业的市场竞争能力。因此,研究物流系统中的优化问题,具有十分重要的意义,是国内外研究的一个热

点。 库存成本与配送成本是物流系统的核心成本,在物流总成本中占据了很大的比例。如果能降低库存成本与配送成本,就能有效地降低物流成本。 遗传算法是一种应用很广泛的智能优化算法,本文对遗传算法进行了分析研究,针对遗传算法的一些缺陷提出了相应的改进方法。在上述研究基础上,本文基于遗传算法,研究了物流系统中的库存优化问题及车辆路径问题。本文将库存仿真优化问题与车辆路径问题都看作是组合优化问题,并应用遗传算法进行求解。 本文的主要研究工作及贡献可归纳如下: (1)对随机库存系统建立了基于离散事件系统的计算机仿真模型。用系统仿真方法求解最优库存策略时,其难点之一在于仿真的优化。为此,本文将计算机仿真技术和遗传算法相结合,应用遗传算法来优化模型的控制参数,即获得最优的库存控制策略。针对随机系统的特点,设计了候选解收集器,它能够收集在仿真优化过程中产 …… 此处隐藏：10099字，全部文档内容请下载后查看。喜欢就下载吧 ……