课题编号：2006024                          

课题名称：大规模VRPTW模型智能算法设计研究  

负责单位：长安大学汽车学院                  

负责人：  胡大伟

研究背景与目的：

当前，物流的现代化水平不仅成为反映一个国家现代化程度和综合国力的重要标志，也成为城市经济发展水平的体现。

城市物流配送是一种先进的现代物流形式，它不但给供应者和需求者带来降低物流成本、享受优质服务的直接效益，而且还能为社会节省运输车次、缓解交通压力、减少运输污染、保护生态环境等作出贡献。

而今，由于小批量、多批次的及时配送方式的发展，运输费用正在逐年提升，许多企业的运费已经超越了库存费用，城市交通与改善物流的矛盾也愈演愈烈，城市交通混杂、阻塞、车辆噪音、尾气污染、车祸事故和能源浪费等现象更加严重，若物流路线选择的不合理，还会使物流配送的行车路线变长，导致载运车辆增加，从而使本己拥挤的城市交通加重负担。以

上问题均需要选择合理有效的运输路线来减少重复运输、倒流运输、迂回运输、单程运输和空驶等，这样不仅提高配送效率，控制了物流成本，而且可限制车辆在城市中的运行时间，有效缓解城市交通负担。

    针对以上情况，本研究课题拟采用经典的车辆路线问题研究课题组织框架(VRP)模型，结合配送时间窗要求来优化配送线路，即运用VRPTW使得配送体系合理化。车辆路径问题(Vehicle Routing Problem,VRP)是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。

    本研究课题重点研究大规模‘VRPTW(’Vehicle RoutingProblem With’lime Windows)模型的智能方法。其目标是针对我国城市物流配送特点，建立满足城市物流配送的VR：PTW模型并找出有效智能算法。由于VRPTW问题属于NP-hard问题，运用常规优化方法难以进行求解，故拟采用智能算法对以上理论模型进行算法设计，如对智能算法中的参数进行数值模拟计算，找出较好的参数搭配，分析各种算法对解的质量影响，并运用Solomon标准测试数据进行计算结果测试。同时通过【INGO软件验证建立的数学模型和进行小规模测算对比分析，通过计算机编程，在可接受的计算时间内得到满足一定精度的相对最优解，最终找出解该类问题有效的智能算法，为解决城市物流大规模配送问题奠定理论基础。

    虽然目前国内已有一些有关VRPTW的研究文献，但缺乏有关大规模此类问题的测试和验算，特别是缺少类似Solomon数据这样的标准测试，使得实际应用价值受到限制。

研究内容：

本项目研究主要内容包括两个方面：一是城市物流配送系统中I VRPTW数学模型的建立；二是针对该类模型的智能算法设计研究。首先,通过对我国城市物流市场调查，对物流配送系统进行分析，在此基础上进I行系统分类，分别建立相应的数学理论模型(如定义、目标函数、约束条件)及其变形模型，采用小规模标准测试数据运用LINGO软件对理论数学模型进行检验。其次，模型确认无误后，对系统模型分别进行智能算法设计，并运用相应的算法语言(如C++)，采用大规模标准测试数据(如Solomon数据)进行测算。本项目拟采用TA(Tabu Algorithms)、SA(Simulated Annealing)、GA(Genetic Algorithms)、ACA(ant colonv algorithm)等进行求解。由于这几种方法在国内外应用十分广泛，通过对这几种算法的求解方法(如邻域的构造、初始解的确定、算法参数的控制等)的改进，便于形成纵向和横向的比较从而找出大规模城市物流配送优化方法和规律，便于在实际工程广泛应用。