论文部分内容阅读
带时间窗车辆路径问题(Vehicle Routing Problem with Time Windows, VRPTW)作为VRP(Vehicle Routing Problem, VRP)的一个主要分支,一直是运筹学领域的热点研究问题,同时也是关乎到国计民生的物流领域的热点和难点问题。它要求车辆在规定的时间将确定的货物送到指定的地点,是研究最小运输成本的货物配送问题。在如今倡导低碳经济的大背景下,绿色物流受到了政府和商业组织越来越多的关注,因为从长远来看当前的物流战略是不可持续的。因此在设计物流策略时除了传统的经济成本,环境、生态、社会效益也应该考虑在内。交通运输在物流中占主要部分,这点不可否认,因此环境敏感的物流政策需要改变其自身的运输方案,使其转变成对生态环境有更少负面影响的可持续的配送网络。研究VRPTW问题的碳排放具有十分重要的现实意义。本文一开始对车辆路径问题的定义及模型进行了简单回顾,并对其扩展问题进行了分类介绍,重点介绍了VRPTW的特点及其模型,并总结了当前求解VRPTW的常规方法。然后引入一种群集智能算法-人工蜂群算法(ABC),作为本文提及模型的求解方法。算法设计可以分为两部分：第一部分根据VRPTW的时间窗以及车辆容量约束,结合当前应用比较成功的初始解生成方法以及局部搜索方法,设计适合于此问题的ABC算法(ABC1),并用标准测试集验证可行性。最后从跟随蜂以及侦查蜂选择,邻域搜索三方面对ABC算法进行改进(ABC2),用相同的测试集比较,证明改进后算法的优越性。第二部分针对考虑碳排放的带时间窗车辆路径问题(Emission Vehicle Routing Problem with Time Windows, EVRPTW)建立相应模型,在相同参数下,用ABC2对两个模型进行求解,对结果进行比较。实验结果分为两方面：第一通过Solomon标准测试集证明了ABC2在求解VRPTW的有效性；第二通过对两个模型计算结果的对比说明尽管在考虑碳排放的情况下行驶距离略有增加,但碳排放量有较明显的减少,证明通过改变优化目标来降低碳排放有一定的理论可操作性。