资源描述：
《带时间窗车辆路径问题的改进节约算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、带时间窗车辆路径问题的改进节约算法崔宏志龚加安（陕西省商洛职业技术学院陕西商洛726000）摘要:本文对节约算法进行了改进,并利用改进的节约算法解决了带时间窗约束的多类型车辆路径问题.首先讨论了带时间窗约束的单类型车辆路径问题,给出其模型,并归纳了几种通过改进传统的节约算法得到的用于求解带有具体约束车辆路径问题的改进节约算法。关键词:运筹学;车辆路径问题;时间窗;改进;节约算法TheimprovedsavingmethodsofvehicleroutingproblemwithtimewindowQIANLong-jiangGONGJia-an(ShaanxiShangluoVoca
2、tionalAndTechnicalInstituionShangluo726000)Abstract:Inthispaper,thesavingmethodisimproved,andtheimprovedsavingmethodisusedtosolvethemulti-typevehicleroutingproblemwithtimewindow.Thesingle-typevehicleroutingproblemwithtimewindowconstraintsanditsmodelaregiven,andsomeimprovedsavingmethodsarealsogi
3、ventosolvethedeficiencyofC-Wheuristicalgorithm.Keywords:operationalresearch;vehicleroutingproblem;timewindow;savingmethod;improvement节约算法由Clarke和Wright于1964年提出[1],该算法为解决车辆路径问题提供了一个简单易行的途径,但由于当时车辆路径问题还未衍生各种具体约束,故传统的节约算法无法直接应用于现今的车辆路径问题.本文先归纳了各种针对单类型车辆路径问题的改进节约算法,然后对传统节约算法进行了改进,使之可以解决带时间窗约束的多类型车辆
4、路径问题—–——————————作者简介：崔宏志（1965-),男,陕西商州人,商洛职业技术学院副教授，人文管理系系主任8，结业于西北大学研究生课程班，研究方向：数学建模。车辆路径问题(VehicleRoutingProblem)是由Dantzig和Ramser于1959年提出的,最初是为了解决在满足一组预选确定的客户需求的条件下,同时决定不同种类的车辆的组成和线路,以达到运输费用最少.该类问题在现实中有着很强的应用背景,像生产制造业、航空服务业、物流运输业、炼钢工业中的许多问题都可以转化为此类形式.比如在制造业,某机械加工车间拥有不同种类的车床,其功能不完全相同,相应可加工的工件任
5、务既有相同的也有不同的.如果有一批加工任务等待处理,且每件工件具有到达和完工时间的约束,如何安排这些工件的加工设备和加工顺序使总的消耗费用最低就可以转化为此类模型.此类问题虽经多人潜心研究,但由于其复杂性巨大,目前仍未找到多项式算法,专家们多把精力集中于研究高质量的启发式算法方面.车辆路径问题已由最初的简单车辆运输衍生出各种具体问题,有了更细的划分,比如根据可用车场数分为单车场问题与多车场问题,根据可用车辆的车型数分为单车型问题与多车型问题,根据决策者的要求分为单目标问题与多目标问题等[2].再具体就比如带冷藏系统的车辆运输问题[3].随着VRP问题的持续发展,考虑需求点对于车辆到达
6、的时间有所要求之下,在车辆途程问题之中加入时间窗的限制,便形成了一个新的种类——有时间窗车辆路径问题(VRPwithTimeWindow,VRPTW),此类问题中,车辆除满足VRP问题的限制外,还必须满足需求点的时间窗限制,即由于早到某个客户而引起的等待时间和客户需要的服务时间.自从Savelsbergh[4]证明了VRPTW是N-P难题后,对其算法的研究就集中在了各种启发式算法上.从文献中可以看到,对于车辆路径问题,国内外已经有了深入的研究,近些年比较流行的遗传算法[5]~[6],蚁群算法[7]都已在VRP问题中得到应用,但这些研究主要集中于单一类型车辆,国内关于多类型车辆路径问题
7、的研究较少,与这方面研究相关的文献有Goldenetal.[8](1984),J.A.FerlandandP.Michelon[9](1988),F.H.LiuandS.Y.Shen[10](1999),于波,丁源[11](2006).前面提到的各种文献中有很多采用了灵感来自生物界的遗传算法和蚁群算法.遗传算法运行方式和实现步骤规范,便于具体实用,适用于复杂优化问题,比较而言,节约启发式算法可提高车辆的利用率,能解决大规模问题[12],而且节约算法的思想更
