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

《最小_最大车辆路径问题的禁忌搜索算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第25卷第1期(总第157期)系统工程Vol.25,No.12007年1月SystemsEngineeringJan.,2007文章编号:1001-4098(2007)01-0049-04最小-最大车辆路径问题的禁忌搜索算法1,21刘霞,齐欢(1.华中科技大学系统工程研究所,湖北武汉430074;2.江汉大学物理与信息工程学院,湖北武汉430056)摘要:在对最小-最大车辆路径问题进行描述的基础上,建立了该问题的基本数学模型。针对最小-最大车辆路径问题的目标是最小化整个线路的最长子线路,本文提出了改进的禁忌搜索算法,并用一些典型算例进行了验证。计算结果表明,用该算法求解最小-最大车辆路

2、径问题,不仅可以取得较好的计算结果,而且算法的计算效率较高,收敛速度较快。关键词:最小-最大车辆路径问题;禁忌搜索;启发式中图分类号:O211文献标识码:A法应用于最小-最大车辆路径问题,并用实例进行测试,取1引言得了很好的效果。车辆路径问题(VehicleRoutingProblem,VRP)是指2最小-最大车辆路径问题对一系列发货点(或收货点)组成适当的行车路线,使车辆有序地通过它们,并能在满足一定的约束条件下,达到诸最小-最大车辆路径问题可以描述为:有一个中心仓如路程最短、费用最小或耗费时间尽量少等目的。该类问库,用0表示,拥有m辆相同型号的车,容量都为Q,现有题具有很强的实际应

3、用背景,而且属于NP-hard,因此自n个客户点的运输任务需要完成,以1,2,…,n表示,第i它在1959年由Dantzig和Ramser首次提出以来就得到个客户点的货运量为qi(i=1,2,…,n),且maxqi

4、表示如下:优解,因此这类算法往往只能用于求解小规模问题;经典目标函数:启发式算法有节约法、构造法、两阶段法和不完全优化算nnkz=min{max(∑∑dijxij)+M},k=1,2,…,m(1)法等;现代启发式算法是近20年发展起来的智能算法,如i=0j=0模拟退火算法、遗传算法、禁忌搜索算法和蚁群优化等。约束:nm在实际情况中,存在这样的一类车辆路径问题,它们k∑∑xij=1,j=0,1,2,…,n(2)的基本定义和约束条件与经典VRP一致,但目标不是要i=0k=1nm求整个行车路线的路程最短或费用最少,而是要求整个线xk=1,i=0,1,2,…,n(3)∑∑ijj=0k=1路中行

5、程最长的子线路距离最短或时间最短,如出于社会nn[4]kk因素考虑的校车行车线路制定,邮递员投送报纸,巡逻∑xip-∑xpj=0,k=0,1,2,…,m;p=1,2,…,ni=0j=0车队的巡逻线路制定,紧急情况下空投物资的运送等。这(4)类问题称为最小-最大车辆路径问题(Min-MaxVehicleRoutingProblem,MMVRP)。本文将改进的禁忌搜索算收稿日期:2006-10-29基金项目:国家自然科学基金资助项目(60574088)作者简介:刘霞(1977-),女,华中科技大学博士研究生,江汉大学讲师,研究方向:系统集成与优化;齐欢,男,华中科技大学教授,博士生导师,研

6、究方向:复杂系统建模与仿真,系统分析与集成。50系统工程2007年nn和节约法相结合,生成初始解。步骤如下:k∑∑qixij≤Q,k=1,2,…,m(5)i=0j=0(1)从客户列表中随机选择一个节点,作为一条子线其中,m表示车辆数;n表示客户数;dij表示客户i到客户路经过的第一个客户节点,同时将该节点从客户列表中删j的距离,若已知客户节点的坐标,往往采用Euclidean方除,并设该客户节点为当前节点current,此时该子线路装法计算距离;qi表示客户i的货运量;Q表示每辆车的装载的货物量demand=q(current),长度distance=d(de-k载容量;如果车辆k从客

7、户i离开到达客户j,xij为1,否则pot,current)+d(current,depot)。为0;M表示罚值,可设为一个较大的正数。(2)若客户列表为空,表明所有客户节点都已被分约束(2)和(3)保证每个客户点有且仅有一辆车经过配,初始解产生,结束;否则转步骤(3)。一次;约束(4)保证了子线路的连续性,即车辆到达了一(3)以当前节点current为基础,采用节约法计算子个货物点,也必须从该点离开;约束(5)为容量约束,规线路的下一节点。即