物流配送车辆路径问题_VRP_算法研究

收稿日期: 2006-10-25 基金项目:福建省教育厅资助项目( JA03006) 作者简介:方金城( 1977-) ,男,福建福清人,讲师,硕士研究生,主要从事物流管理、信息系统分析与设计研究. 张岐山( 1962-) ,男,黑龙江绥化人,教授,博士生导师,主要从事智能信息系统研究 . 第 22 卷第 2期 徐 州 工 程 学 院 学 报 2007 年 2 月 Vol. 22 No . 2 Journal of Xuzhou Institute of Technolog y FEB. 2007 物流配送车辆路径问题( VRP)算法研究 方金城1, 2,张岐山1 ( 1.福州大学,　福建　福州　350002;　2.福建工程学院,　福建　福州　350014) 　　【摘　要】　物流配送车辆路径问题( VRP)属于 NP- hard 问题.文章介绍了当前最具有代表 性的算法,分析并总结了各种算法的优缺点及目前的改进情况,指出目前启发式算法是求解车辆路 径问题的主要方法,至于大规模客户集的配送路径优化问题或者是多约束的复杂 VRP 问题,可以 考虑利用多种算法相结合的办法来解决. 【关键词】　物流配送; 车辆路径问题; 算法 【中图分类号】　O224　【文献标识码】A 【文章编号】1673-0704( 2007) 02-0084-05 1　车辆路径问题( VRP)概述 物流配送车辆路径问题( Vehicle Routing Problem, VRP)最早是由 Dantzig 和 Ramser 于 1959年首次提 出的.该问题的研究目标是对一系列的顾客需求点设计适当的路线, 使车辆有序地通过它们,在满足一定的 约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等)下,达到一定的优 化目标(如里程最短、费用最少、时间尽量少、车队规模尽量小、车辆利用率尽量高等) [ 1] . 一般地,车辆路径问题可以这样描述:某一配送中心有V 辆车,需要对C个节点(客户) 进行运输配送, 每 个节点的货物需求量是g i( i = 1, 2,⋯, C) ,每辆配送车的最大载重量是Q .设 cij 表示节点 i到节点 j 的运输成 本,如时间、路程、花费等.取配送中心编号为 0,各节点编号为 i( i = 1, 2, ⋯, C) , 定义变量如下: 　　　　　　　　x ij k = 1,车辆 k由节点 i驶向节点 j 0,否则 　　, 　　　　　　　　yik = 1, 节点 i的配送任务由车辆 k 完成 0, 否则 . 建立此问题的数学模型: 　　　　　　　　minZ = ∑C i= 0 ∑C j = 0 ∑V k= 1 cij x ij k, ( 1) 　　　　　　　　∑C i= 0 g iy ik ≤ Q　k = 1, 2,⋯, V , ( 2) 　　　　　　　　∑V k= 1 y ik = 1, i = 1, 2,⋯, C V , i = 0 , ( 3) 　　　　　　　　∑C i= 0 x ij k = y j k ,　j = 1, 2,⋯, C　k = 1, 2, ⋯, V , ( 4) 　　　　　　　　∑C j= 1 x ij k = y ik,　i = 0, 1, 2, ⋯, C　k = 1, 2,⋯, V . ( 5) ·84· 上述模型中, 式( 2)为车辆的容量约束; 式( 3)保证了每个节点的运输任务仅由一辆车完成,而所有运输 任务则由V 辆车协同完成; 式( 4)和式( 5)限制了到达和离开某一节点的车辆有且仅有一辆. VRP 中若每一项运输任务都有时间限制, 则问题就变成了带时间窗的车辆路径问题( Vehicle Rout ing Problem w ith Time Window s, VRPTW) . 2　VRP 问题的求解算法 求解车辆路径问题的方法非常丰富,基本上可以分为精确算法和启发式算法两大类[ 2] . 2. 1　求解 VRP 问题的精确算法 求解 VRP 问题的精确算法主要运用线性规划、整数规划、非线性规划等数学规划技术来描述物流系统 的数量关系, 以便求得最优决策.求解 VRP 问题常用的精确算法有分枝定界法、割平面法、动态规划法、网络 流算法等. 这些方法从理论上给出了VRP 问题精确求法, 在可以求解的情况下,其解通常要优于启发式算法.由于 精确算法在求解时引入了严格的数学方法(手段) ,因而无法避开指数爆炸问题,从而使该类算法只能有效求 解小规模的VRP 问题,并且通常这些算法都是针对某一特定问题设计的,适用能力较差,因此在实际中其应 用范围很有限 [ 3] . 2. 2　求解 VRP 问题的启发式算法 由于VRP 问题是强 NP 难题,高效的精确算法存在的可能性不大,所以寻找近似算法是必要和现实的, 为此专家们主要把精力花在构造高质量的启发式算法上.目前己经提出的启发式算法很多,按照 Cesar Reg 的分类法,基本可以分为三类:构造启发式算法、两阶段启发式算法和智能化启发式算法. 2. 2. 1　构造启发式算法 构造启发式算法在求解 VRP 问题时通常是从初始解出发, 以邻域搜索的方式实现解的改进, 并在较 短的时间内获得一个可以接受的解. 它包括: 2. 2. 1. 1　节约算法 节约算法是由 Clarke 和Wright于 1964年提出的,用以解决车辆数不固定的 VRP 问题. 该算法的基本 思路是按节约值从大到小构造路径,在车辆容量限制下,依序将对应的两客户点排入路径中,直至所有客户 都被排入路径为止[ 1] . Solomon 于 1983年将此法应用于求解时间窗约束的 VRP 问题.此时, 在考虑将节省 值较大的两客户排入路径时,还需要考虑时间窗的限制.这种算法具有运算速度快的优点, 特别是在小规模 的配送优化中,节约算法的优化精度与最优解很接近,并且能够很快给出结果.但在客户规模增加后, 容易出 现不理想的优化结果. 2. 2. 1. 2　最邻近法 最邻近法最早由 Rosenkrantz和 Stearns等人于 1977年提出的. 算法从配送中心开始[ 1] ,搜索距离配送 中心最近的、未访问的节点作为第一个节点并设为已访问,然后以该点为中心搜索与之相邻的、未访问的节 点.如果加上该点不会超出容量限制,则将该点加入到线路中并设为已访问, 否则结束该条线路.重复上述步 骤,寻找距离配送中心的最近的未访问的节点作为新线路的第一个节点,生成新的线路,直到将所有的节点 都访问过.最邻近法算法简单,可以在较短时间内求得初始解,但易早熟收敛,容易陷入局部最优. 2. 2. 1. 3　最近插入法 最近插入法的算法 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 与最邻近法基本相似.这种算法的关键是依序选择最合适的未分配的节点在路 线中进行最佳位置的插入, 以构建配送路线,直至不存在可行插入节点时新增一条初始路线[ 4] .插入法最早 是 Mole 和 Jameson 于 1976年所提出, 用于求解 VRP 问题的方法; 1983年 Solomon 将此方法应用于求解 VRPTW 问题. 用最近插入法求得的解比最邻近法求得的解更优,但在计算过程中, 也耗费了更多的计算量. 2. 2. 1. 4　扫描法 扫描法最早由 Gillet t和 Miller提出的 [ 1] .它假设车辆的路线位于一个几何平面上,平面上的所有点是以 极坐标来表示,配送中心为原点.先选定一尚未使用的车辆,在不违反车辆容量限制的前提下,从角度最小且 尚未指派的节点开始, 依顺时针或逆时针的方向扫描.当车辆容量超过时,结束该条线路.重复上述 步骤 新产品开发流程的步骤课题研究的五个步骤成本核算步骤微型课题研究步骤数控铣床操作步骤 , 生 成新的线路, 直到将所有的节点都被排入, 最后再用求解旅行商问题( T SP)的算法对每一条路线分别进行优 ·85· 方金城, 等: 物流配送车辆路径问题( VRP)算法研究 化.用扫描法求解 VRP 问题, 能在较短的时间内求得可行的满意解, 但不一定能导出最优解. 2. 2. 2　两阶段启发式算法 Christof ides、M ingozzi、T oth 于 1979年提出了两阶段启发式算法,来改进构造算法求解的不足.该算法 第一阶段常用构造启发式算法来求得一可行解, 第二阶段常用 Insert method、2- exchange、2- sw ap、2- OPT、3- OPT 等改善技术,通过对点的调整,在始终保持解可行的情况下,力图向最优目标靠近, 每一步都 产生另一个可行解以代替原来的解,使目标函数得以改进,一直继续到不能再改进目标函数为止. 两阶段法 在求解过程中,常常采用交互式优化技术, 把人的主观能动作用加入到 VRP 问题的求解过程中[ 3] . 2. 2. 3　智能化启发式算法 20世纪90年代以来, 由于人工智能方法在解决组合优化问题的强大功能,不少学者开始将人工智能引 入车辆路线问题的求解中, 并构造了大量的基于人工智能的启发式算法(智能化启发式算法) .智能化启发式 算法包括: 2. 2. 3. 1　禁忌搜索算法 禁忌搜索的思想最早由 Glover 在 1986年提出的,是一种全局逐步寻优算法.它引入了一个禁忌表记录 下已经搜索过的局部最优点,在下一次搜索中利用禁忌表中的信息不再或者有选择地搜索这些点,以此来跳 出局部最优点,从而实现全局优化. 1991年, Gendreau等人将禁忌搜索方法应用于 VRP. 该算法求解过程中 的邻域,是通过 GEM 过程得到的. 1994年, Garcia等将禁忌算法应用于 VRPTW 问题. D. Brand A～A～o 和 Jos A ～ A ～ ( 2006)用禁忌搜索算法求解了带回程取货的 VRP 问题 [ 5] . 用禁忌搜索算法求解 VRP 问题虽然能保证对 不同的有效搜索途径的探索,但由于涉及复杂的邻域转换和求解策略,因而在实际中不容易实现. 2. 2. 3. 2　模拟退火法 模拟退火法最早是由 Metropolis( 1953)提出的,是一种基于热力学原理的随机搜索算法. Osman( 1993) 对 VRP 问题的模拟退火算法进行了研究, 提出模拟退火方法适合于解决路线分组问题. 用模拟退火法求解 VRP 问题时, 把物理退火中原子获得能量相当于分配最优节点, 将原子振动模拟为线路寻优空间的随机搜 索.搜索过程由执行分配的成对交换完成, 搜索初始解为配送总成本.对现有分配情况用任意成对交换产生 新的分配, 从而对配送路线不断进行改进, 直至找到最优路线. 模拟退火算法适合大规模的需求固定或者 随机需求的 VRP 问题. Tavakkoli- Moghaddam, R. 等人( 2006)利用一种混合模拟退火算法求解了单个路 径长度的车辆途程问题 [ 6] . 从理论上讲,用模拟退火法求解 VRP 问题,可以求得全局最优解, 但在实际应用 中, 由于受计算时间的限制,往往只能给出一个近似的最优解.为了使模拟退火算法求出的近似解更准确, 一般重复执行模拟退火法多次, 从中选取最好的解作为最终的近似最优解. 2. 2. 3. 3　神经网络算法 神经网络模型最早由 McCulloch和 Pit ts于 1943 年提出. 模型主要利用神经网络中神经元的协同并行 计算能力来构造的优化算法.它将实际问题的优化解与神经网络的稳定状态相对应,把实际问题的优化过程 映射为神经网络系统的演化过程.神经网络算法求解 VRP 问题可能会导致网络最终收敛于局部极小解, 甚 至可能收敛到问题的不可行解. 此外,网络最优的最终结果很大程度依赖于网络的 参数 转速和进给参数表a氧化沟运行参数高温蒸汽处理医疗废物pid参数自整定算法口腔医院集中消毒供应 ,即参数鲁棒性较差. 袁健和刘晋( 2002)采用一种改进了的平均场退火方法和 Hopf ield 神经网络解法相结合,求解了随机需求情 形 VRP 问题 [ 7] ; 王德东和郑丕谔( 2005)利用混沌神经网络算法,对一类随机需求服从泊松分布的车辆选径 问题进行了求解,并与平均场退火算法和模拟退火算法进行了比较[ 8] .结果表明,该算法具有很强的避免陷 入局部极小点的能力和较强的全局搜索能力,较大地提高了优化的时间性能和求解质量. 2. 2. 3. 4　遗传算法 遗传算法最早是由 Holland在 1975年提出的,是进行局部搜索改进的一类算法. 1991年, T hang iah首先 将遗传算法用于求解VRP 问题.遗传算法求解 VRP 问题时, 主要利用生物进化世代性与最优路线搜索迭代 性间的共性, 在全局范围内搜索配送路线的最优解.如遇同一级配送节点分支的相同耗费情况,则均予以考 虑, 分别参与下一步骤迭代, 并由后续步骤逐渐淘汰, 最终确定最优配送路线;如遇同一级配送节点分支的 不同耗费情况, 则“适者幸存”,由耗费少的配送分支获得继续迭代的权利, 但并不能确定其最优资格, 必须 ·86· 徐州工程学院学报　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　2007 年第 2 期 参与后续淘汰步骤, 直至迭代结束, 得到最优配送路线.遗传算法具有良好的鲁棒性、灵活性、通用性,特别 适合于大规模 VRP 问题的求解. 但由于算法本身还存在的一些缺陷,如易出现早熟收敛,局部搜索能力差, 因此不能保证最大概率收敛到全局最优解.张丽萍等人( 2002)通过引入新颖交叉算子,构造了一种改进遗传 算法, 摆脱了传统遗传算法对群体多样性的要求,不存在“早熟收敛”问题,可以有效地求得 VRP 的优化 解[ 9] ; Berger 和 Barkaoui( 2004)利用并行混合遗传算法求解了带时间窗的车辆路径问题[ 10] ;郎茂祥( 2006)通 过构建单亲遗传算法,有效改进了传统遗传算法对复杂 VRP 问题搜索效率低, 易陷入“早熟收敛”的缺 陷[ 11 ] . 2. 2. 3. 5　蚁群算法 蚁群算法是 Dorig o提出的一种基于群体仿生的智能优化算法.该算法的基本原理是模拟蚁群搜索食物 的行为:蚂蚁群找到食物时,它们总能找到一条从食物到巢穴之间的最优路径.这是因为蚂蚁在寻找路径时 会在路径上释放出一种特殊的信息素. 当它们碰到一个还没有走过的路口时,就随机地挑选一条路径前行, 与此同时释放出与路径长度有关的信息素. 路径越长,释放的激素浓度越低. 当后来的蚂蚁再次碰到这个路 口的时候, 选择激素浓度较高路径概率就会相对较大.这样形成了一个正反馈.最优路径上的激素浓度越来 越大,而其它的路径上激素浓度却会随着时间的流逝而消减,最终整个蚁群会找出最优路径.该算法在求解 VRP 问题方面有良好效果,但存在如计算时间较长,容易陷入局部最优等问题.黄岚等人( 2002)给出蚂蚁算 法在旅行商问题中的具体应用, 并通过 3- opt 方法和去交叉策略对问题求解和局部优化[ 12] ; 郝晋等人 ( 2002)针对基本蚁群算法, 设计出一种新颖的随机扰动蚁群算法, 并将其应用于求解复杂T SP 问题[ 13] ;吴建 军等人( 2004)针对物流配送路径选择问题, 提出了一种混合蚁群算法来克服经典蚁群算法时间复杂性过大 的难点[ 14] . 2. 2. 3. 6　微粒群算法 PSO算法是由 Kennedy 和 Eberhart于 1995年提出的一种基于群智能方法的演化计算技术[ 15] .该算法 是通过模拟鸟群的捕食行为来达到优化问题的求解.首先在解空间内随机初始化鸟群,鸟群中的每一只鸟称 为“粒子”,这些“粒子”在解空间内以某种规律移动, 经过若干次迭代后找到最优解.在每一次迭代中, 粒子通 过跟踪两个“极值”来更新自己.第一个是粒子本身的最优解(“Pbest”) .另一个极值是整个微粒群目前找到 的最优解(“Gbest”) . 找到这两个极值后, 每个粒子根据自己的飞行速度, 决定自身的走向及飞行距离. 用 PSO算法求解 VRP 问题具有收敛速度快、依赖的经验参数少、简便易行等特点, 但与其他进化类优化算法 一样存在易于陷入局部最优的缺陷.黄岚等人( 2003)通过引入交换子和交换序的概念, 构造出一种特殊的 粒子群优化算法求解旅行商问题 [ 16] ; 肖健梅等人( 2005)设计了一种新的实数编码 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 , 将车辆路径问题转 化成准连续优化问题, 并采用罚函数法处理约束条件,从而把微粒群算法应用于车辆路径问题的求解 [ 17] . 此外, 近年来也有学者借鉴了免疫系统的自组织学习、自适应调节的特点, 提出了用免疫算法来求解 VRP 问题.算法中模拟了生物免疫系统对外来抗原的排除,把抗原对应于待求解的问题, 抗体对应于问题的 一个解.国内亓霞等人( 2003)利用免疫算法的全局搜索能力和收敛性,将新型的启发式算法用于解决 VRP; 章兢等人( 2004)构造了一种免疫克隆算法来求解 VRP,并在算法中引入了克隆选择、克隆删除、受体编辑、 体细胞高频变异、抗体循环补充等思想. 免疫克隆算法能快速收敛于全局最优解,克服了遗传算法中易陷入 局部最优解和收敛速度慢的缺点,可有效地解决物流配送车辆路径优化问题. 3　结语 VRP 是 NP- hard 问题,如果用精确算法来求解,只能解决规模比较小的问题, 而且求解过程需要的运 行时间较长.因此, 目前启发式算法(特别是智能化启发式算法)是求解车辆路径问题的主要方法. 需要 说明 关于失联党员情况说明岗位说明总经理岗位说明书会计岗位说明书行政主管岗位说明书 的是,启发式算法虽然能够比较快地解决有关问题, 但该算法的优劣往往取决于算法设计者的实际经验以及 处理的样本空间的大小.在实际求解过程中,应根据各类算法的适用范围,并针对配送优化问题的具体情况, 寻找最适合的求解方法, 搜索最优配送路线. 对于大规模客户集的配送路径优化问题或者是多约束的复杂 VRP 问题,可以考虑利用多种算法相结合的办法来解决. ·87· 方金城, 等: 物流配送车辆路径问题( VRP)算法研究 参　考　文　献 [ 1] 蔡临宁.物流系统规划——建模及实例分析[ M ] . 北京:机械工业出版社, 2003: 205- 214. [ 2] 程世东,刘小明, 王兆赓.物流配送车辆调度研究的回顾与展望[ J] . 交通运输工程与信息学报, 2004, ( 3) : 93- 97. [ 3] 尚华艳. 物流配送中车辆路径问题研究[ D] . 武汉理工大学硕士学位论文, 2005: 29- 30. [ 4] 霍佳震,张磊. 求解配送\收集旅行商问题的启发式算法[ J] . 同济大学学报(自然科学版) , 2006, 34( 1) : 134- 138. [ 5] Brand A ～ A ～ o , Jo s A ～ A ～ . A new tabu search algor ithm for the vehicle routing problem with backhauls [ J] . European Journal of Operational Research, 2006, ( 2) : 540- 555. [ 6] Tavakkoli- M oghaddam, R . Safaei, N and Gho lipour , Y . A hybrid simulated annealing fo r capacitated vehicle r out ing pr oblems w ith the independent r oute leng th[ J] . Applied Mathematics and Computation, 2006, ( 2) : 445- 454. [ 7] 袁健,刘晋, 卢厚清. 随机需求情形 VRP 的退火网络解法[ J] . 系统工程理论与实践, 2002, ( 3) : 109- 113. [ 8] 王德东,郑丕谔. 车辆路径问题的混沌神经网络解法[ J] .计算机集成制造系统, 2005, ( 12) : 1747- 1750. [ 9] 张丽萍, 柴跃廷. 车辆路径问题的改进遗传算法[ J] .系统工程理论与实践, 2002, ( 8) : 79- 84. [ 10] Ber ger, Barkaoui. A parallel hybrid genetic alg orithm for t he vehicle r outing pr oblem w ith time w indows[ J] . Computer s and Operations Research, 2004, ( 12) : 2037- 2053. [ 11] 郎茂祥. 用单亲遗传算法求解配送车辆调度问题的研究[ J] .交通与计算机, 2006, ( 1) : 119- 121. [ 12] 黄岚,王康平,周春光, 等.基于蚂蚁算法的混合方法求解旅行商问题[ J] . 吉林大学学报(理学版) , 2002, ( 4) : 369- 373. [ 13] 郝晋,石立宝,周家启. 求解复杂 TSP 问题的随机扰动蚁群算法[ J] .系统工程理论与实践, 2002, ( 9) : 88- 91. [ 14] 吴建军,刘军.物流配送路径安排问题的混合蚁群算法[ J] . 土木工程学报, 2004, ( 8) : 98- 101. [ 15] 吴启迪,汪镭.智能微粒群算法研究及应用[ M ] . 江苏教育出版社, 2005: 1- 38. [ 16] 黄岚, 王康平, 周春光, 等. 粒子群优化算法求解旅行商问题[ J] . 吉林大学学报(理学版) , 2003, ( 4) : 477- 480. [ 17] 肖健梅,李军军,王锡淮. 求解车辆路径问题的改进微粒群优化算法[ J] . 计算机集成制造系统, 2005, ( 4) : 577- 581. [ 18] 亓霞,陈森发,黄昆鸟. 基于免疫算法的物流配送车辆路径优化问题研究[ J] . 土木工程学报, 2003, 36( 7) : 43- 46. [ 19] 章兢,周泉 . 基于免疫克隆算法的物流配送车辆路径优化研究 [ J] . 湖南大学学报(自然科学版) , 2004, 31( 5) : 54- 58. Study of Algorithms for Vehicle Routing Problem( VRP) in Logistics Distribution FANG Jin- cheng 1, 2, ZHANG Qi- shan1 ( 1. Fuzhou University, Fuzh ou 350002, Ch in a; 2. Fujian University of T ech nology, Fuzhou 350014, China) 【Abstract】　Vehicle rout ing problem ( VRP) in logist ics dist ribut ion is an NP- hard problem. T he paper gives an int roduction of algorithms that are the most representative ones current ly ; it analy zes and summarizes both the advantages and disadvantages of various alg orithms and current status of their improvement. It points out that heurist ic algorithm is the major method to solve vehicle rout ing problem . As to the opt im ization of distribution rout ine for client sets of larg e scale or complex VRP problems w ith many rest rictions, the combinat ion of several algorithms is advised to be adopted to solve these problems. 【Key words】　logist ics dist ribution; vehicle routing problem ( VRP) ; algorithms (责任编辑　徐永铭) ·88· 徐州工程学院学报　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　2007 年第 2 期