带时间窗车辆路径问题的改进约算法.doc

带时间窗车辆路径问题的改进节约算法 崔宏志 龚加安 （陕西省商洛职业技术学院 陕西 商洛 726000） 摘 要: 本文带时间窗约束的多类型车辆路径问题首先讨论了带时间窗约束的单类型车辆路径问题,给出其模型,并改进传统的节约算法得到用于求解带有具体约束车辆路径问题的改进节约算法关键词: ; 时间窗; 改进; 节约算法 The improved saving methods of vehicle routing problem with time window QIAN Long-jiang GONG Jia-an (Shaanxi Shangluo Vocational And Technical Instituion Shangluo 726000) Abstract: In this paper, the saving method is improved, and the improved saving method is used to solve the multi-type vehicle routing problem with time window. The single-type vehicle routing problem with time window constraints and its model are given, and some improved saving methods are also given to solve the deficiency of C-W heuristic algorithm. Key words: operational research; vehicle routing problem; time window; saving method; improvement 节约算法由Clarke和Wright于1964年提出[1],该算法为解决车辆路径问题提供了一个简单易行的途径,但由于当时车辆路径问题还未衍生各种具体约束,故传统的节约算法无法直接应用于现今的车辆路径问题.本文先归纳了各种针对单类 型车辆路径问题的改进节约算法,然后对传统节约算法进行了改进,使之可以解决 带时间窗约束的多类型车辆路径问题 —–—————————— 作者简介：崔宏志（1965-),男,陕西商州人,商洛职业技术学院副教授，人文管理系系主任，结业于西北大学研究生课程班，研究方向：数学建模。 车辆路径问题(Vehicle Routing Problem)是由Dantzig和Ramser于1959年提出,最初是为了解决在满足一组预选确定的客户需求的条件下, 同时决定不同种类的车辆的组成和线路,以达到运输费用最少该类问题在现实中有着很强的应用背景,像生产制造业、航空服务业、物流运输业、炼钢工业中的许多问题都可以转化为此类形式比如在制造业, 某机械加工车间拥有不同种类的车床,其功能不完全相同,相应可加工的工件任务既有相同的也有不同的如果有一批加工任务等待处理,且每件工件具有到达和完工时间的约束,如何安排这些工件的加工设备和加工顺序使总的消耗费用最低就可以转化为此类模型此类问题虽经多人潜心研究,但由于其复杂性巨大,目前仍未找到多项式算法, 专家们多把精力集中于研究高质量的启发式算法方面车辆路径问题已由最初的简单车辆运输衍生出各种具体问题,有了更细的划分,比如根据可用车场数分为单车场问题与多车场问题,根据可用车辆的车型数分为单车型问题与多车型问题, 根据决策者的要求分为单目标问题与多目标问题等[].再具体就比如带冷藏系统的车辆运输问题随着VRP问题的持续发展,考虑需求点对于车辆到达的时间有所要求之下,在车辆途程问题之中加入时间窗的限制,便形成了一个新的种类——有时间窗车辆路径问题VRP with Time Window,VRPTW),此类问题中,车辆除满足VRP问题的限制外,还必须满足需求点的时间窗限制,即由于早到某个客户而引起的等待时间和客户需要的服务时间VRPTW 是N-P难题后,对其算法的研究就集中在了各种启发式算法上. 从文献中可以看到,对于车辆路径问题,国内外已经有了深入的研究,比较流行的遗传算法,蚁群算法都已在VRP问题中得到应用,但这些研究主要集中于单一类型车辆,国内关于多类型车辆路径问题的研究较少,与这方面研究相关的文献有Golden et al.(1984), J.A.Ferland and P.Michelon[9](1988),F.H.Liu and S.Y.Shen[10](1999),于波,丁源[11](2006). 前面提到的各种文献中有很多采用算法.这里我们着重讨论了简单易行的C-W节约算法得来的改进型节约算法,在对单类型带时间窗车