摘 要：在随机性信息存在的条件下，带时间窗的实时时变车辆路径问题的研究能有效的降低企业物流成本、提高运作效率和客户满意度，同时带来良好的经济效益和社会效益。本文就这类问题，设计了变邻域搜索算法，来引导插入算法、交换法、2-opt法和重定位法产生较优的路径，并绘出了基于此算法下的求解流程图。最后通过实例验证了变邻域搜索算法在处理实时时变车辆路径问题时的有效性高。文中使用了时变旅行速度模型，满足“先进先出”原则，比旅行时间模型更能反映出实际的交通状况。另外，本文还将变邻域搜索算法扩展到大规模的实时时变车辆路径问题上，弥补了研究领域在此方面的不足。

关键词：带时间窗  实时时变  变邻域搜索算法  旅行速度模型  大规模车辆路径问题

    (Vehicle RoutingProblem, VRP)在物流领域的理论和应用研究非常具有代表性，Canen和Scort将VRP称为“最近十年运筹学领域最成功的研究之一”。电子、信息等科学技术在物流领域的广泛应用，使得能快速处理多种信息的车辆路径系统的开发成为可能，而且企业对这一系统的需求也非常迫切。以往的研究中，人们多数是在路径构造之前，已经获取到确定的客户、车辆、路况等信息，这里将这类问题简称为静态车辆路径问题。但是由于现实生活存在着大量的不确定信息，在路径执行的过程中，可能出现随机的需求，或者发生车辆故障、交通拥堵等情况，这时就需要根据当前获取的信息，对路径进行调整，这类问题简称为动态车辆路径问题。由于不确定信息的存在，静态车辆路径问题的理论和求解方法不一定能够解决动态问题，这就需要为动态的车辆路径问题研究出一套新的理论和方法。