最小-最大车辆路径问题的禁忌搜索算法.doc

最小-最大车辆路径问题的禁忌搜索算法 第25卷第1期(总第157期) 2007年1月 系统工程 SystemsEngineering V01.25.No.】 Jan..2007 文章编号:1001—4098(2007)Ol一0049—04 最小一最大车辆路径问题的禁忌搜索算法 刘霞,齐欢 (1.华中科技大学系统工程研究所,湖北武汉430074; 2.江汉大学物理与信息工程学院,湖北武汉430056) 摘要:在对最小一最大车辆路径问题进行描述的基础上.建立了该问题的基本数学模型.针对最小一最大车辆 路径问题的目标是最小化整个线路的最长子线路,本文提出了改进的禁忌搜索算法.并用一些典型算例进行 了验证.计算结果表明.用该算法求解最小一最大车辆路径问题,不仅可以取得较好的计算结果.而且算法的计 算效率较高.收敛速度较快. 关键词:最小一最大车辆路径问题;禁忌搜索;启发式 中图分类号:o2l1文献标识码:A 引言 车辆路径问题(VehicleRoutingProblem,VRP)是指 对一系列发货点(或收货点)组成适当的行车路线,使车辆 有序地通过它们,并能在满足一定的约束条件下.达到诸 如路程最短,费用最小或耗费时间尽量少等目的.该类问 题具有很强的实际应用背景.而且属于NP—hard.因此自 它在1959年由Dantzig和Ramser首次提出以来就得到了 专家学者的极大重视并进行了大量的研究[J].车辆路径 问题的求解方法可以分为三类:精确算法,经典启发式算 法和现代启发式算法.精确算法如树搜索法,分枝定界法, 整数线性规划等.由于大部分实际问题都难以找到最优 解,因此这类算法往往只能用于求解小规模问题;经典启 发式算法有节约法,构造法,两阶段法和不完全优化算法 等;现代启发式算法是近2O年发展起来的智能算法,如模 拟退火算法,遗传算法,禁忌搜索算法和蚁群优化等. 在实际情况中,存在这样的一类车辆路径问题.它们 的基本定义和约束条件与经典VRP一致,但目标不是要 求整个行车路线的路程最短或费用最少,而是要求整个线 路中行程最长的子线路距离最短或时间最短.如出于社会 因素考虑的校车行车线路制定[4],邮递员投送报纸,巡逻 车队的巡逻线路制定,紧急情况下空投物资的运送等.这 类问题称为最小一最大车辆路径问题(Min—MaxVehicle RoutingProblem.MMVRP).本文将改进的禁忌搜索算 法应用于最小.最大车辆路径问题.并用实例进行测试.取 得了很好的效果. 2最小一最大车辆路径问题 最小一最大车辆路径问题可以描述为:有一个中心仓 库.用0表示.拥有辆相同型号的车.容量都为Q,现有 个客户点的运输任务需要完成,以1.2,…,表示.第 个客户点的货运量为q(=1.2,….),且maxq~Q.每辆 车从仓库出发.经过一系列客户点并装载货物,最终回到 仓库.规定每个客户点的任务必须且只能由一辆车来完 成.要求整个线路中行程最长的子线路长度尽可能短 具体的数学模型可表示如下: 目标函数: 2=min{max(∑∑d)+),k=l,2,…,re(1)=D;D 约束: ∑ ∑=0 =0.1,2,…, =0.1.2.…, (2) (3) ∑一∑=0,k=o.1.2.…,州;户一1,2,….J=0i0 (4) *收稿日期:2006一10—29 基金项目:国家自然科学基金资助项目 作者简介:刘霞(1977一),女.华中科技大学博士研究生,江汉大学讲师,研究方向:系统集成与优化;齐欢,男.华中科技大学教授, 博士生导师,研究方向:复杂系统建模与仿真,系统分析与集成. ,● l1 =: 50系统工程2007焦 ∑∑q,k≤Q.k一1,2,…,(5)f一0J一0 其中,表示车辆数;表示客户数;d,,表示客户到客户 的距离,若已知客户节点的坐标,往往采用Euclidean方 法计算距离;q.表示客户i的货运量;Q表示每辆车的装 载容量;如果车辆k从客户离开到达客户J.为1,否则 为0;表示罚值,可设为一个较大的正数. 约束(2)和(3)保证每个客户点有且仅有一辆车经过 一 次;约束(4)保证了子线路的连续性,即车辆到达了一 个货物点,也必须从该点离开;约束(5)为容量约束,规 定了每条子线路装载的货物量不能超出车辆的容量.为满 足条件(5),在目标函数中加入了罚值,即如果某条子 线路装载的货物量超出车辆的装载容量,目标函数为 max(∑∑d,,)+M.此时M为一个很大的正数,否则…0=0 目标函数为max(∑∑d,,),即M为0.一0J一0 3禁忌搜索 禁忌搜索(TabuSearch,TS)的思想最早由Glover (1986)提出,它是对局部搜索的一种扩展,是一种全局逐 步寻优算法,是对人类智力过程的一种模拟.TS算法通