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

1 带时间窗车辆路径问题的改进节约算法崔宏志龚加安(陕西省商洛职业技术学院陕西商洛 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 节约算法由 Clark e和 Wrigh t于196 4年提出[1], 该算法为解决车辆路径问题提供了一个简单易行的途径, 但由于当时车辆路径问题还未衍生各种具体约束,,然后对传统节约算法进行了改进,使之可以解决带时间窗约束的多类型车辆路径问题—–——————————作者简介:崔宏志( 1965-), 男,陕西商州人,商洛职业技术学院副教授,人文管理系系主任,结业于西北大学研究生课程班,研究方向:数学建模。 2 车辆路径问题(Vehicle Routing Problem) 是由 Dantzig 和 Ramser 于1959 年提出的, 最初是为了解决在满足一组预选确定的客户需求的条件下, 同时决定不同种类的车辆的组成和线路, 以达到运输费用最少. 该类问题在现实中有着很强的应用背景, 像生产制造业、航空服务业、物流运输业、炼钢工业中的许多问题都可以转化为此类形式. 比如在制造业, 某机械加工车间拥有不同种类的车床, 其功能不完全相同, 相应可加工的工件任务既有相同的也有不同的. 如果有一批加工任务等待处理, 且每件工件具有到达和完工时间的约束, 如何安排这些工件的加工设备和加工顺序使总的消耗费用最低就可以转化为此类模型.