求解带装载能力限制的开放式车辆路径问题的遗传算法

《求解带装载能力限制的开放式车辆路径问题的遗传算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第26卷第2期(总第170期)系统工程Vol.26,No.22008年2月SystemsEngineeringFeb.,2008文章编号:100124098(2008)0220078206X求解带装载能力限制的开放式车辆路径问题的遗传算法符卓,聂靖(中南大学交通运输工程学院,湖南长沙410075)摘要:对带装载能力限制的开放式车辆路径问题的求解进行了研究,提出了一种用于求解该问题的遗传算法。对算法中几个关键操作的不同实现方式的性能进行了比较。给出了算法对标准测试算例的运算结果,并与文献中目前最好的

2、结果进行了比较和分析。关键词:车辆路径问题;开放式车辆路径问题;遗传算法;物流配送中图分类号:U491文献标识码:A车辆路径问题(vehicleroutingproblem,VRP)存在于合式VRP中,每一条路线都是哈密顿圈(Hamiltoniancy2物流配送运输等运输服务的运输路线编排问题中,是近二cle),而在OVRP中是哈密顿路径(Hamiltonianpath),两十多年来运筹学界的研究热点之一。其一般描述是:对一者都属于NP2难问题。众所周知,用精确算法求解NP2难问系列给定的客户点,

3、要求确定适当的车辆行驶路线,使其题时,其算法的计算量一般将随着问题规模的增大而呈指从车场(如配送中心等)出发,有序地对它们进行服务,并数增长。从实际应用的角度来说,普遍接受的明智做法是在满足一定的约束条件下(如车辆载重量、客户需求量、时设计相应的启发式算法,在可接受的时间内求出问题的近间窗限制等),使总运输成本达到最小(如使用车辆数最优解。少、车辆行驶总距离最短等)。本文将研究提出一种求解带装载能力限制的开放式为了便于对VRP进行系统的研究,运筹学界将其分车辆路径问题的遗传算法,并对所采用的新的遗

4、传算子和[1]为两大类:闭合式VRP和开放式VRP。当车辆完成运输几种改进策略对算法性能的影响进行对比,更进一步地,任务后必须返回原出发点时(即车辆的行驶路线是闭合式将计算结果与文献中已有的其它算法的结果相比较,分析的),称之为闭合式VRP,一般就简称为车辆路径问题用遗传算法求解OVRP的可行性和优劣性。(VRP);当不要求车辆完成任务后返回原出发点,或者是要求其沿原去程路线返回时(即车辆的行驶路线是开放1问题的分析式的),称之为开放式VRP(openvehicleroutingproblem,带

5、装载能力限制的OVRP(capacitatedOVRP,OVRP)。在不需要严格区分的场合,统称为车辆路径问题COVRP),是OVRP中的最基本类型。该问题的主要约束(VRP)。条件有,每条线路开始于车场,终止于某一个客户点(或反VRP被提出来后,国内外学术界首先对以物流配送过来);每个客户点由一辆车访问(服务)一次且仅一次,且为应用背景的闭合式VRP进行了广泛研究,取得了许多其需求量全部得到满足;每一条路线上各客户点的需求量令人注目的成果。而对于OVRP,尽管以往有过一些有关之和不超过其车辆装载

6、能力。优化目标一般包括:(1)最小的案例描述及其研究报道,但直到最近几年,在闭合式化所使用的车辆数(假设每一条线路由一辆车负责,因此VRP的研究基础上,才开始从理论上对其进行系统的研有时也称最小化线路数),(2)最小化车辆总行驶路程或时究。文献[2]对其研究进展进行了简要的归纳和分析。间。对于VRP,其求解算法的研究一直是研究的重点和难Sariklis和Powell是最早对COVRP进行研究的学点。与闭合式VRP相比,在OVRP中没有车辆必须返回原者,他们提出了一个基于最小生成树的两阶段启发式算出

7、发点的限制,但这并没有使问题变得简单和容易。在闭法[3]。在算法的第一阶段,首先根据车辆的装载能力对客X收稿日期:2007209222;修订日期:2007211223基金项目:国家自然科学基金资助项目(70671108)作者简介:符卓(19602),男,中南大学交通运输工程学院教授,博士生导师,研究方向:交通运输规划与管理,物流配送管理。第2期符卓,聂靖:求解带装载能力限制的开放式车辆路径问题的遗传算法79户点进行分组,并使得所形成的组数为最少,然后通过按用的车辆数目为K.给定的规则不断调整客户点

8、的分配,以降低各组中的运输阶段2:根据初始化条件随机生成初始解。为了提高费用。在第二阶段,通过对各组求解一个带有罚值的最小初始解的多样性及其质量,分别按如下两种方式各生成种生成树问题来产生开放式路径,且通过迭代使不可行解逐群的一半组成。步转变为可行解。①按K随机生成初始解,不在乎其是否可行。以项数在此基础上,我们也对COVRP进行了研究,提出了为(N+K)生成序列Y,其中N为客户点数目,K为当前最一个用禁忌搜索这一现代启发式算法来构造的求解算好解中所使用的车辆数目;该序列首项为0,