【作者】 王科峰；

【导师】 叶春明；

【作者基本信息】 上海理工大学 ， 管理科学与工程， 2012， 博士

【摘要】 标准车辆路径问题只考虑商品的配送不考虑废弃物的回收，即只存在货物的正向流动。而受人们环境保护意识的加强、废物再利用所带来的附加经济效益等因素的影响，近些年逆向物流越来越受到人们的关注。在存在逆向物流的环境中，有一种情形是客户点一方面需要车辆对之进行商品的配送，另一方面还需要车辆从它那里收集废弃的商品或可再循环使用的材料，这就导致了当车辆对其进行服务时既需要按照客户点的需要进行送货同时还要将客户点处的货物收集起来带走。当考虑服务的对象是这样一些客户点的时候，对车辆路径进行规划的问题，本文将之统称为“节点具有双重需求的车辆路径问题（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问题的竞争决策算法。通过对标准算例的测试的结果与已有的构造型启发式算法的结果对比发现，竞争决策算法适合用于求解客户节点呈群聚式分布的情况。更多还原

【Abstract】 In the classic vehicle routing problem (VRP), only the commodity’s delivery isconcerned about without the waste material’s recycling. But as the awareness ofenvironmental protection is enhanced and the waste goods’ usage can bring aboutadditional economic benefit, the reverse logistics is paid attention to more and more inthe recent years. In the environment where the reverse logistics exists, there is one casethat the customer ont only need the vehicle to distribute commdities to it but also needthe vehicle to collect the waste or the reusable materials from it, which leads to thevehicle should deliver goods according to the customers’ demand and bring away theuseless goods at the customer while serving it. When the served objects are somecustomers with double demands as above, the corresponding vehicle routing problemis called “the vehicle routing problem with nodes having double demands” abbreviatedas VRPNDD.Because VRP is NP-hard and VRP is the special case of VRPNDD when either ofthe demands is equal to zero, VRPNDD is NP-hard also in general conditions. In VRP,when the problem’s size is large, that is to say, the number of customers is greater than100, it is has already been very difficult to solve the problem for most of exactalgorithms. Most ot the actual problems in the real world are large-size problems, sothe heuristics is always focused by the people. To solve VRPNDD in the real worldneed to depend on the heuristics generally speaking, but under some special cases,does VRPNDD have polynomial algorithm? If it does, it is not necessary to design theheuristics. So the research about VRPNDD should contain the problem’s complexityunder the special case. The important attribute of the delivery and pickup doubledemands make VRPNDD has some new constructive properties and it is more complexto solve compared to VRP in which the customer has only delivery demand. So someresearches about the basic properties of VRPNDD should be done and the heuristicsbased on these properties should be designed. The main work and results in this paperare:(1) Researches about the computational complexity under the case that the vehicle’scapacity is equal to1and greater than or equal to2are done. The results show thatwhen the vehicle’s capacity is equal to1, and the distances are symmetric and satisfy the triangle inequality, VRPNDD has polynomial algorithm, but when thecapacity is greater than or equal to2, VRPNDD is NP-hard even if the distance issymmetric and satisfies the sharpened inequality.(2) Researches about the reducibility under the case that the vehicle’s capacity is equalto1and greater than or equal to2are done. The results show that when thevehicle’s capacity is equal to1and the distances are symmetric and satisfy thetriangle inequality, VRPNDD is reducible, but when the capacity is greater than orequal to2and the distances are symmetric and satisfy the triangle inequality,VRPNDD is unreducible.(3) Based on the characteristics of the solutions for the vehicle routing problem withsplit deliveries and pickups (SVRPPD), two constructive heuristics: the farthestnode split load algorithm (FNSL) without the limitation of used vehicles’ numberand the competitive decision algorithm (CDA) permitting the used vehicles’number unlimited are designed. The computing experiments show that FNSL hasbetter performance on the optimization of total travel distance compared with theexisted algorithms, i.e. the farthest node full split algorithm (FNFL) and the nearestnode full split algorithm (NNFL), but the used vehicles number is more than theother two algorithms’, which shows that FNSL is applicable to the environmentwhere the time is restricted strictly. CDA’s solutions can guarantee the traveldistances is the shortest under the condition that the used vehicles number is theleast. Then CDA is used to test the benchmark of SVRPPD, and some comparisonsare done with the existed heuristics and the solutions show that CDA has excellentperformance.(4) Researches about the vehicle routing problem with split deliveries and pickups andtime windows (SVRPPDTW) are done. Greedy algorithm (GA), two stagealgorithm (TS) and CDA are designed to solve SVRPPDTW. Based on thebenchmark of the vehicle routing problem with time windows (VRPTW), somenew instances adapted to VRPNDD with time windows are generated. Theproposed algorithms are tested on the new instances and the CPLEX optimizationsoftware are used to solve the lower bound model. The results show that GA andTS performance well under the condition that the problem’s size is small, butCDA’s superiority increases as the problem size’s increasing, but the gap with thelower bound increases too. (5) An overview about the vehicle routing problem with simultaneous deliveries andpickups (VRPSDP) are given. The research results of the overview show that theparallel algorithms’ research and designment about the metaheuristics withparallelism in it are not enough and the improvement for the serial algorithmsshould be done in two aspects, i.e. searching for better initial solutions andsearching for valid hybrid algorithms.(6) CDA algorithms of VRPSDP are designed. The comparisons among the testedresults of the existed constructive heuristics and CDA on the VRPSDP benchmarkshow that CDA performs well under the condition that the customers locations areclustered.更多还原