资源描述：
《车辆路线问题研究现状及发展方向》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、总第202期交 通 科 技SerialNo.2022004年第1期TransportationScience&TechnologyNo.1Feb.2004车辆路线问题研究现状及发展方向张 强 荆 刚 陈建岭(山东大学机械工程学院 济南 250061)摘 要 随着现代物流在我国的迅猛发展,车辆运输路线规划对于降低物流成本显得越来越重要。总结车辆路线问题(VRP)的研究状况,并分析今后的发展方向。关键词 物流 配送 车辆路径问题 启发式算法 人工智能 当前的物流业正向全球化、信息化、一体化发展,配送在供应链中
2、的作用显得更加重要。由于现代配送具有多频次、小批量、多品种、高效率的特点,配送要准确做到7R(rightproduct,rightquality,righttime,rightplace,rightcondition,rightcustomer,rightcost),因此,设计合理、有效的车辆路线方案,尽量减少车辆数量和配送里程图1VRP示意图数就成为非常实际的问题。本文对车辆路线问题的研究现状进行综合分析,进而提出车辆路线问2 车辆路线问题研究现状题的研究发展方向。经过几十年的研究发展,车辆路线问题研究1
3、 车辆路线问题概述取得了大量成果。下面从车辆路线问题的现有研究型态和求解方法两个方面介绍车辆路线问题的车辆路线问题(vehicleroutingproblem,研究现状。[1]VRP)自1959年由Danting和Ramser提出以2.1 车辆路线问题型态来,一直是网络优化问题中最基本的问题之一,由在基本车辆路线问题(VRP)的基础上,车辆于其应用的广泛性和经济上的重大价值,一直受路线问题在学术研究和实际应用上产生了许多不到国内外学者的广泛关注。车辆路线问题可以描同的延伸和变化型态,包括时窗限制车辆路线问述
4、如下(如图1):设有一场站(depot),共有M辆题(vehicleroutingproblemswithtimewindows,货车,车辆容量为Q,有N位顾客(customer),每VRPTW)、追求最佳服务时间的车辆路线问题位顾客有其需求量D。车辆从场站出发对客户进(VRPDT)、多车种车辆路线问题(fleetsizeand行配送服务最后返回场站,要求所有顾客都被配mixvehicleroutingproblems,FSVRP)、车辆多送,每位顾客一次配送完成,且不能违反车辆容量次使用的车辆路线问题(v
5、ehicleroutingprob2的限制,目的是所有车辆路线的总距离最小。车辆lemswithmultipleuseofvehicle,VRPM)、考虑路线的实际问题包括配送中心配送、公共汽车路收集的车辆路线问题(vehicleroutingproblems线制定、信件和报纸投递、航空和铁路时间表安withbackhauls,VRPB)、随机需求车辆路线问题排、工业废品收集等。(vehicleroutingproblemwithstochasticde2mand,VRPSD)等。收稿日期:20032062
6、232004年第1期 张 强等:车辆路线问题研究现状及发展方向612.2 求解方法用,很多学者也将人工智能引入车辆路线问题的2.2.1 求解方法演进求解中,并构造了大量的基于人工智能的启发式综合过去有关车辆路线问题的求解方法,可算法。禁忌搜索法(TS)基本上是属于一种人工以分为精确算法(exactalgorithm)与启发式解法智能型(AI)的局部搜寻方法,Willard首先将此(heuristics),其中精密算法有分支界限法、分支算法用来求解VRP,随后亦有许多位学者也发表切割法、集合
7、涵盖法等;启发式解法有节约法、模了求解VRP的TS算法。西南交通大学的袁庆[4]拟退火法、确定性退火法、禁忌搜寻法、基因算法、达等设计了考虑时间窗口和不同车辆类型的禁[2]神经网络、蚂蚁殖民算法等。1995年,Fisher曾忌算法,这种算法主要采用GENIUS方法产生初将求解车辆路线问题的算法分成三个阶段。第一始解,然后禁忌算法对初始解优化。模拟退火方法[5]阶段是从1960年到1970年,属于简单启发式方具有收敛速度快,全局搜索的特点,Osman对式,包括有各种局部改善启发式算法和贪婪法VRP的模拟退火算
8、法进行了研究,他提出的模拟(Greedy)等;第二阶段是从1970年到1980年,属退火方法主要适合于解决路线分组。遗传算法具于一种以数学规划为主的启发式解法,包括指派有求解组合优化问题的良好特性,Holland首先法、集合分割法和集合涵盖法;第三阶段是从采用遗传算法(GA)编码解决VRPTW问题。现1990开始至今,属于较新的方法,包括利用严谨在多数学者采用混合策略,分别采用两种人工智[6]启发式方法、人工智能
