车辆优化调度算法研究初探

－46－ 科 技 论 坛 车辆优化调度算法研究初探 王庆贞 赵 雁 钟 斌 王玉龙 （武警工程学院，陕西 西安 710086） 1 概述 国外将物流配送车辆优化调度问题称之为 Vehicle Routing Problem [1] 和Vehicle Scheduling Problem。物流配送车辆优化调度问题最早是由 Dantzig和Ramser[2]于 1959年首次提出的,自此,很 快引起运筹学、应用数学、组合数学、图论与网络分 析、物流科学和计算机应用等学科的专家与运输计 划制定者和管理者的极大重视,成为运筹学与组合 优化领域的前沿与研究热点问题。各学科专家对该 问题进行了大量的理论研究及实验 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ,取得了很 大进展。但是,对随机车辆调度问题的研究还不是 很多；而且,在实际中,车辆调度问题包含许多随机 的因素,因此,研究随机车辆优化调度问题具有广泛 的应用背景和经济价值。 2 车辆路径规划问题求解算法概述 由于 VRP 包含了旅行商问题 (Traveling Salesman Problem , TSP), 而 TSP本身就是NP难 题,所以VRP也是一个NP组合优化难题。自该问 题被提出之日起,国内外学者力求构造高效的算法 来解决这一难题,这些求解算法大体可分为两类,一 类为精确算法(exact algorithm),另一类为近似算法 (approximation algorithm), 其中的近似算法又可以 大致分为三类:构造启发式(constructive heuristics) 算法,改进启发式(improving heuristics)算法,亚启发 式(meta- heuristics)算法。下文就这四类算法近些年 的研究成果做简要评述。 2.1 精确算法 基于VRP的传统数学模型的精确型求解算 法代 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 性的研究成果主要有:Fisher提出的 K- 树 法、Padberg等提出的分枝剪枝法、Kohl和Madsen 用拉格朗日松弛算法求解带有时间窗的 VRP、 Fumero等的修正拉格朗日松弛及子梯度优化方 法、Lorena Luiz等对列生成方法的改进等。精确算 法主要适用于解决问题结构比较清晰、所含各元素 之间的关系明确、边界清楚的良性结构问题。另外, 还有许多实际的VRP不具有良性结构, 并且有些 问题不存在严格最优解(例如,目标之间相互矛盾的 多目标决策问题),或者有些问题要得到最优解需花 费过大的代价,当采用精确算法求解这种类型的问 题时难以得到理想的效果,它们的解决就需依赖于 近似算法。 2.2 构造启发式算法 构造启发式算法[3]是将尚未指定路线的客户 按照某些 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 插入到现有的已部分形成的路线中 去,以最终形成解。该算法是求解VRP问题最早使 用的近似算法。Clarke和Wright提出的C-W节约 算法, Gillett 和 Miller 提出的扫描算法 , 以及 Solomon提出的最近邻启发式算法都是构造启发 式算法中最为经典的算法。其后虽有很多学者将这 些经典算法加以改进,但这些改进大都以缩短计算 时间和减少内存的占用为目标,对于当代如此发达 的计算机而言,这些改进都是微不足道的。虽然构 造启发式算法简单易懂,但有时找到的解离最优解 差的较远, 因此该算法现已不单独用来求解VRP 问题, 而是与改进算法相结合, 用在构造初始解阶 段。 2.3 改进启发式算法 改进启发式算法[4]可以将构造启发式算法得到 的比较差的解,通过邻域的搜索反复改进,得到较好 的解。改进启发式算法大概可以分为路线内部改进 和路线间改进两种,路线内部改进是将某条路线内 部的某些边和结点互换位置,而路线间改进是在相 邻路线之间交换一些边和结点来改进当前的解。具 有代表性的求解VRP的改进启发式算法有 k- opt 以及λ- interchange算法。Opt算法来自于Lin提 出一种旅行商问题 (Traveling Salesman Problem, TSP)的路径优化思想,其思想是对给定的初始回路, 通过每次交换 k条边来改进当前解。该算法在求解 VRP问题时,k条边可以是路线内部的,也可以是路 线之间的。λ- interchange算法由Osman发起,它 的思想是在几条线路之间相互交换一些客户来改 进路线。该算法在后续的研究中也被应用解决多类 VRP问题,如有时间窗的VRP。该类算法的优点是 得到最优解的概率较高, 缺点是随着 k和λ值的 增大, 运算时间会成倍增长, 不利于实时系统的处 理。 2.4 亚启发式算法 构造启发式算法和改进启发式算法都不允许 劣质中间解的产生,而只允许解的优化结果朝好的 方向单向递增,因此这两种算法都较容易陷入局部 最优,为了克服这一缺点,多种亚启发式算法相继出 现。亚启发式算法在优化问题的过程中允许劣质的 中间解出现, 能够跳出局部最优而在全局内寻优。 用于求解VRP问题的亚启发式算法有遗传算法、 模拟退火算法、蚁群算法等。 遗传算法[5]通过多个个体间的选择、交叉等的 遗传操作,相互协力地进行解的探索,与以前的算法 中对单纯的并列的解的探索相比,容易发现更好的 解。遗传算法运用到VRP上,对于解诸如带有时间 窗的VRP,先分组后安排路径的路径规划问题等等 一些具有多目标的路径规划问题,取得了很好的效 果。然而在运用该方法的过程中,问题的遗传因子 型的表现依赖于 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 者的能力。并且该算法所得结 果的好坏,主要依赖于遗传代数和解组规模,在实际 应用中只能根据具体要求,在合理的时间内对问题 进行求解,若所得解不能令人满意,就要增大解组规 模或遗传代数,从而有希望得到问题的全局最优解, 当然,这是以延长计算时间为代价的。 模拟退火算法(simulated annealing algorithm) [6] 是由 irkpatrick等提出的一种求解组合最优化问 题的算法。该方法适用的领域较多,具有较强的实 用性,并可人为地控制迭代次数,反复求解。然而该 方法所得解的好坏与初始状态、温度函数等都有一 定的联系,降温较快的效果不一定很好,效果好的,其 降温过程又极其缓慢。该法创立之初对于解决单目 标路径规划问题可以得到非常满意的解,虽然后经 过一些学者如Ulungu和 Teghem (1994)的研究改 进,可以解决多目标问题,但是就其运算过程和得到 的解来说不如遗传算法的效果好。 蚁群算法是近十几年来新兴起的一种摹仿蚂 蚁觅食行为的算法。可以查到的最早将该算法应用 到路径规划问题上的文献的年代始于 1995年。此 后,Gambardella 和 Dorigo, Stutzle 和 Hoos, 以及 Mazzeo和 Loiseau都有将该算法应用到路径规划 问题中并获得成功。蚁群算法具有群体合作、正反 馈选择、并行计算等三大特点,并且可以根据需要 为人工蚁加入前瞻、回溯等自然蚁所没有的特点。 因此,该算法具有很强的发现较好解的能力。但是 这种算法也存在一些缺陷,如搜索时间较长,容易出 现停滞现象(stagnation behavior),即搜索进行到一 定程度后,所有个体所发现的解完全一致,不能对解 空间进一步进行搜索,不利于发现更好的解。现在 对该算法的研究大多数都集中在对这些缺陷进行 改进上。 结束语 综合上文分析可以发现,每一种算法单独工作 都会存在一些比较大的缺陷,而且随着社会的发展, 问题规模不断扩大化,结构不断复杂化,单一的算法 很难解决现实中复杂化的问题。如果将几类算法融 合贯通,取长补短,就可以克服很多缺点,构造出比较 好的算法。近十几年对算法的研究开始侧重于融合 多种算法,构造混合算法上。回顾了国内外求解该 问题的现有算法并总结了它们的优缺点,为下一步 的研究提供指导,并期能为在该领域内从事研究工 作的学者提供借鉴。 参考文献 [1] vehicle routing problem[J]. Computers &Oper－ ations Research,1999,26(12):1153～1173. [2] Dantzig G, Ramser J. The truck dispatching problem[J]. Management science,1959,(6):80～91. [3]李军.有时间窗的车辆路线安排问题的启发式算 法[J].系统工程,1996,14(5):45～50. [4]林晓宇,李金铭,纪寿文.车辆路径问题 Clarke- Wright算法的改进与实现[J].交通与计算机,2004,6 (22):72～75. [5]李军,谢秉磊,郭耀煌.非满载车辆调度问题的遗传 算法[J].系统工程理论方法应用,2000,9(3):235～239. [6]郎茂祥.装卸混合车辆路径问题的模拟退火算法 研究[J].系统工程学报,2005,20(5):485～491. 作者简介：王庆贞（1981~），男，汉族，山东潍坊 人，工学学士，现为武警工程学院研究生管理大队 硕士研究生。 赵雁（1970~），女，汉族，现为武警工程学院装 备运输系装备技术教研室主任，副教授。 钟斌（1975~），男，汉族，现为武警工程学院装 备运输系装备技术教研室讲师，博士学历。 王玉龙（1986~），男，汉族，河南安阳人，现为武 警工程学院研究生管理大队硕士研究生。 摘 要：分四大类讨论求解该问题的算法:精确算法(exact algorithm),构造启发式算法(constructive heuristic algorithm),改进启发式算法(im- proving heuristic algorithm),和亚启发式算法(meta-heuristic algorithm),评述各类算法适用的问题求解阶段以及各自的优缺点。 关键词：车辆路径规划问题(Vehicle Routing Problem, VRP)；算法；优化调度