论文部分内容阅读
标准车辆路径问题只考虑商品的配送不考虑废弃物的回收,即只存在货物的正向流动。而受人们环境保护意识的加强、废物再利用所带来的附加经济效益等因素的影响,近些年逆向物流越来越受到人们的关注。在存在逆向物流的环境中,有一种情形是客户点一方面需要车辆对之进行商品的配送,另一方面还需要车辆从它那里收集废弃的商品或可再循环使用的材料,这就导致了当车辆对其进行服务时既需要按照客户点的需要进行送货同时还要将客户点处的货物收集起来带走。当考虑服务的对象是这样一些客户点的时候,对车辆路径进行规划的问题,本文将之统称为“节点具有双重需求的车辆路径问题(vehicle routing problem withnodes having double demands,VRPNDD)”。由于车辆路径问题(vehicle routing problem,VRP)是NP难问题,且VRP问题是VRPNDD问题在节点需求其中一个为0时的特殊情况,所以VRPNDD问题在一般情况下也是NP难的。在VRP问题中当问题规模比较大的时候,即客户节点个数大于100的时候,采用大多数的精确算法求得精确解已经比较困难,而实际当中的问题很多是大规模问题,所以对VRP问题的启发式算法的研究一直以来都是人们关注的焦点。对实际当中的VRPNDD问题的求解一般也要依靠启发式算法,但是在某些特殊情况下,VRPNDD问题是否存在多项式时间的算法,如果存在那么此时就不必设计启发式算法了。因此对VRPNDD问题的研究应该包括特殊情况下问题的计算复杂性的研究。由于VRPNDD问题节点处存在集货、送货双重需求,这一重要属性使得该问题存在一些新的结构性质,而且求解较之节点只具有送货需求的VRP问题更复杂,这就促使了本文对VRPNDD问题的一些基本性质的研究和基于这些性质的启发式算法的设计。本文主要的研究工作及成果有:(1)对车辆容量为1和大于等于2时的VRPNDD问题的计算复杂性进行了研究。得到车辆容量为1时,在距离对称且满足三角不等式的条件下VRPNDD问题存在多项式时间算法,当容量大于等于2时,即便距离对称且满足更严格的三角不等式,VRPNDD问题仍然是NP难的。(2)对车辆容量为1和大于等于2时的VRPNDD问题的可简化性进行了研究。得到车辆容量为1时,在距离对称且满足三角不等式的条件下,VRPNDD问题可以简化,当容量大于等于2时,在距离对称且满足三角不等式的条件下,VRPNDD问题不可以简化。(3)基于集送货需求可拆分车辆路径问题(vehicle routing problem with splitdeliveries and pickups,SVRPPD)解的特点,设计了两种构造型启发式算法:车辆数无限制条件下的最远点拼车贪婪算法和允许车辆数无限制的竞争决策算法。通过数值实验说明了最远点拼车贪婪算法相对于已有的最远点完全拼车算法和最近点完全拼车算法在路径长度优化方面具有优势,但是使用车辆数偏多,适合应用于时间性比较强的环境条件下,而竞争决算法的求解结果在保证车辆使用数最小的情况下仍然使得路径长度最短。接着使用竞争决策算法对现有SVRPPD标准算例进行了测试,并和已有的启发式算法进行了对比,也收到了很好的效果。(4)对带时间窗集送货需求可拆分车辆路径问题(vehicle routing problem withsplit deliveries and pickups and time windows,SVRPPDTW)进行了研究,提出了贪婪算法、两阶段算法和竞争决策算法。在带时间窗车辆路径问题(vehicle routing problem with time windows,VRPTW)的标准算例的基础上生成了新的适合于求解节点具有双重需求情况下带时间窗问题的算例。提出的算法在新生成的算例的基础上进行了测试,并采用CPLEX优化软件对模型下界进行了求解。结果表明,在规模较小的情况下贪婪算法、两阶段算法计算效果良好,但是随着规模增大竞争决策算法较前两者优势明显增加,但是与问题的下界偏差也增大。(5)对同时送取货车辆路径问题(vehicle routing problem with simultaneousdelivery and plckup,VRPSDP)的算法进行了综述研究。研究表明目前对于具有内在并行性的现代启发式算法的并行程序设计尚显不足,此外,对于VRPSDP的串行算法的改良应该从寻找更好初始解和寻求有效混合算法的角度着手。(6)设计了求解VRPSDP问题的竞争决策算法。通过对标准算例的测试的结果与已有的构造型启发式算法的结果对比发现,竞争决策算法适合用于求解客户节点呈群聚式分布的情况。