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