遗传算法的VRP模型建模及求解

遗传算法的VRP模型建模及求解

卫伟

中国铁路郑州局集团有限公司洛阳车务段三门峡车站河南三门峡472000

1引言

由于经济全球化、物流在国民生产总值中的份额、生产模式的改变、企业竞争（成本、效率）、环境、现代信息技术对于传统物流的冲击，研究物流具有重要意义。物流配送作为物流系统中一个不可分割的部分，对于物流路径优化将会使物流系统变得更加完善。于是车辆调度就成为一个急需解决的关键问题，VRP模型也应运而生。目前有不少研究者都运用遗传算法解决了一些物流领域的问题。

2VRP问题的产生

现代物流研究是由多种多样的方面构成的，而车辆调度问题VRP（VehicleRoutingProblem）是其中的一个关键，VRP问题很大程度上影响着现代物流的发展。物流配送就是卖家根据用户的订货需求,将货物集中在配送中心，再由配送中心进行货物的分装、搭配,并将配好的货物按照卖家的要求及时安全送交给买家。因为在物流配送业务中，存在着很大的不确定性，所以就有许多优化决策问题亟待解决。国内外许多学者为运输车辆路线安排问题（VRP）构建了优化模型，并形成了许多解决问题的算法。

车辆调度问题（VRP）是为使用车辆（车辆数量确定或者不确定）访问客户而产生的路径，路径的和（即总成本）最小的一个问题。VRP问题的条件是：每一客户只被车辆访问一次，且每条路径上的客户需求量之和不超过车辆的能力。

3遗传算法（GA）的优点

由美国Michigan大学的JohnHolland教授创建的遗传算法(GeneticAlgorithms简称GA)是解决这一问题的一个方法。遗传算法是从达尔文的物种进化论、魏茨曼的物种选择学说和孟德尔的群体遗传学说三种生物学上的理论演变而来的。遗传算法就是将自然界中的遗传机制和生物进化论进行模拟，从而形成的一种搜索过程最优解的算法。

对于求解物流配送路径优化问题，遗传算法的出现为解决这个问题提供了一种全新的方法。按照遗传算法的规则，设置一个初始种群，并从其开始，采用基于适应值比例的选择策略在当前的种群中选择个体，使用算法中杂交策略和变异规则产生第二代种群，通过不断的杂交和变异，产生一代代种群，直至产生满足最终期望值的终止条件。对于无法使用枚举法获得最优解的大规模问题，人们早已把精力放在寻找最优解上。遗传算法就是能够寻求最优解的工具之一。

1）遗传算法不依赖于问题本身的特征即不依赖于初始条件；

2）不与求解空间有紧密关系，对解域，无可微或连续的要求。求解稳健，但收敛速度慢。能获得全局最优。适合于求解空间不知的情况，特别适合于求解许多我们看来非常棘手的问题，所以在求解VRP时大多是利用遗传算法。

4数学模型

4.1模型假设

VRP问题所涉及的实际的一个物流系统可以由这样的一个经典的VRP即问题抽象型，需要设定一些前提:

某物流配送中心，对一定区域范围内的客户点进行配送服务，配送中心有足够物品供给给客户，但每个客户点的需求量不一定，且每个客户需求点距配送中心和需求点间的距离已知。要求每辆车的装载量不能超过其额定载重量。每辆车完成任务之后都要回到源点。为了提高车辆的利用率，如何安排车辆路线和进行车辆调度既能满足配送任务，又能使车辆运行成本最低。

特对模型的参数符号说明如下：

设配送中心为，共有个客户点,其中,客户点的需求量为；配送中心有辆车可供负责配送任务，经过扫描算法分组之后确定需要辆车，每辆车的最大载重量为，车辆的实际装载量是,其一次配送的最大距离为。每条回路上的客户数为，由集合表示第辆车对应的路径，表示第辆车对应的子回路中顺序为的客户点。配送中心与客户点的距离为，客户点与客户点之间距离为，如何安排车辆对客户点的访问次序，可使其运输路线的总长度最短？本文主要解决VRP问题中的最短线路问题。

4.2模型建立

可以建立模型如下：

（1）为目标函数，求使车辆行驶距离最短；（2）保证有足够的车辆来完成运送任务；（3）一个回路中客户点的需求量不能超过车辆所能承载的重量；（4）每条路径的运行路线长度不能超过车辆一次配送的最大距离；（5）当第K辆车有运送任务时为1，没有配送任务时为0；（6）每辆车对应的客户点数不能超过总的客户数；（7）每组回路由哪几个客户构成；（8）客户与车辆是多对一的关系；（9）每辆车的配送任务都完成，保证每个客户都服务到。

5案例计算分析

本文以一个VRP案例进行计算分析。实例:某物流中心，需要向20个客户送货。物流中心的坐标为(14.5km,13.0km)，20个客户的坐标及其货物需求量如表所示。

按照上述的遗传算法用MATLAB编制了计算机程序，并进行了大量的实验。应用遗传算法求解VRP得出的最终配送方案为：0-10-1-14-2-18-9-15-5-11-13-8-12-4-19-7-3。并且得出相应的最短运输路径为161.9KM。

6总结

本文建立了一个物流配送路径优化问题的数学模型，并采用标准遗传算法求解了这个物流配送路径优化问题，最后得到了一个满足条件的最优解。通过本文距离可以得到，对于解决VRP问题，通过遗传算法计算可以更快、更合理地实现物流车辆线路的安排，取得了较好的应用效果。但由于本文研究的是标准遗传算法，所以并不是每次的计算结果都相同。

参考文献

[1]孙辉.遗传算法在物流企业配送业务中的应用[D].吉林大学.2005

[2]黄中鼎,潘洪伟,张书源,等.现代物流管理[M].上海:复旦大学出版社，2007.

[3]黄晓滨,邹书蓉,张洪伟.免疫遗传算法及其在VRP中的应用[N].成都信息工程学院学报.2008.12

[4]邵宏,刘兴.大规模车辆路径问题的启发式算法[J].中国农机化.2008

[5]贾楠,吕永波,付蓬勃,任远.物流配送问题中VRP的数学模型及其求解算法[J].物流技术2007

[6]刘云忠,宣慧玉.车辆路径问题的模型及算法研究概述[N].管理工程学报.2005

[7]张强,师军.基于遗传算法的分层路径寻优算法[J].陕西师范大学.2008

[8]周屹,李海龙,王锐.遗传算法求解物流配送中带时间窗的VRP问题[N].哈尔滨:吉林大学学报.2008年3月

[9]高运良.基于免疫遗传算法的物流配送VRP求解[D].武汉科技大学.2007.

[10]黄少荣.遗传算法及其应用[D].电脑知识与技术2008.11.pp.1874-1876,1882