【作者】 柯鹏；

【导师】 李元香；

【作者基本信息】 武汉大学 ， 计算机软件与理论， 2013， 博士

【摘要】 车辆路径问题(Vehicle Routing Problem,VRP)是运筹学和组合优化等研究领域的一个重要研究内容,其主要目标是求解能以最低成本将货物递送到顾客点的路径集合,因为其重要的应用价值在交通运输,物流配送,邮政快递等行业有着广泛的应用。在过去,成本主要是指与之对应的路径数量和旅行距离,不过,在现实生活中该问题也存在一些值得考虑的其它成本因素。由于没有确定式方法能在多项式时间内有效的求解该问题,许多启发式算法被应用于该问题的求解,其中进化算法已被证明适合于求解该问题。尽管进化算法可以提供较为完整的解决方案在该问题的多个优化目标之间求得相对平衡的解,却很少有专门针对该问题在多目标优化方向上的研究,也更少有研究将解的多样性作为一个专门的研究内容,而这对任何进化计算技术进化性能的良好表现都是至关重要的。论文在进化算法基础上分别提出了三种新的多目标进化算法—种群分布性限制进化算法、改进的种群分布性进化算法、增强的种群分布性进化算法,用于求解VRP问题的两种经典衍生问题：VRPTW和CVRP,尤其是针对至少两个优化目标的优化问题。具体的研究工作内容如下：设计了种群分布性限制进化算法,在算法中提出了一个新的分布比率参数ρ,该参数用于约束种群中相同解的数量,接着给出了六个变异算子,用于增强种群的多样性。在上述算法基础上提出了改进的种群分布性进化算法,给出了一种用于量化VRP问题两个解之间的相似性的方法,设计了一个新的变异过程,该变异过程和进化算法结合在一起用于求解VRP问题可以更好的利用搜索空间。新的变异过程包括三个基本函数,其中两个可以随机的选择路径和顾客点,另外一个则是确定性的,用于将顾客点重新插入到路径中去。此外,还提出了三个新的变异算子,用于调整路径之间的顾客点分配和在路径内部顾客点的服务顺序。该算法的主要优点是：它不依赖于具体解的编码形式,也可以适用于任何一种VRP问题的衍生问题,并且具有线性的时间复杂度提出了一个新的可以有效求解CVRP,VRPTW问题的增强的种群分布性进化算法(Enhanced coverage-restricted evolutionary algorithm,ECREA),该算法可以同时优化至少两个优化目标。该算法整合了上述所提到的相似性量化方法和新的变异过程,以便更好的探索和利用搜索空间,从而保持较高的种群多样性。算法结果表明获得的解提供了更为合适的在多目标之间折中优化的效果。通过将CVRP,VRPTW的测试集测试新算法获得的解与已有的基于单一优化目标考虑的研究结果相比,显示新算法获得的解虽然并非整体上都是最优的,但是至少和后者的很多研究结果相比是可以相提并论的,这主要表现在新算法的解可以在获得更少的路径数量或者更短的旅行距离的同时,相应的其他优化目标和后者的结果的差距控制在2%以内。因为通过一个优化目标所获得的最优解并不必然能表现出多目标的优化效果,因此该算法具有实际意义。接着使用多目标优化的三种性能评价方法分别对利用ECREA算法求解VRPTW问题的双目标优化和三目标优化的结果进行了分析,并与著名的多目标优化算法NSGA-II获得的解进行了比较,结果表明前者在很多测试实例中获的了比后者更好的结果。而在求解CVRP问题时,由于测试集的测试实例的目标并没有冲突,所以没有进行多目标的优化性能分析。由于已有的VRP问题的研究大多倾向于单目标优化或将对多个优化目标优化后的结果以单目标的方式进行分析,论文则提出通过利用正式的多目标评估方法对多目标优化的性能进行适当比较和分析,并给出了最后的结论。更多还原

【Abstract】 Vehicle Routing problem is an important reserch direction for combinatorial optimization and operation reserch. Its main purpose is to get the routes that can delivev goods to the custom with the lowest cost, Because of its important application value in the transportation, logistics, courier industry has a wide range of applicationsSince there is no way to solve this problem in determine polynomial time effectively, many heuristic algorithms have been applied to solve the problem, wherein evolutionary algorithms have been proven suitable for solving the problem. Although evolutionary algorithms can provide a more complete solution to the problem in multiple optimization objectives relative balance between the obtained solution, very few specifically for the multi-objective optimization problem in the direction of research, but also less likely to have studied the solution diversity as a specialized research content, which may put the performance of any evolutionary computation techniques are vital good performance.This paper, based on evolutionary algorithms, proposed a new multi-objective evolutionary algorithm-Enhanced coverage-restricted evolutionary algorithm, ECREA,which is used for two classic variants of VRP:VRPTW and CVRP,and the particular optimization goal is for at least two optimization objectives. Related research works are as follows:Proposed a method can be quantified the VRP similarity between two solutions, and this information, is then used to determine an individual solutions and other solutions in the population similarity, on the basis of which effective assessment population diversity. The main advantage of the method are:it does not depend on the specific encoding of solution,and can also be applied to any kind of VRP variants, and it has a linear time complexity.Designed a new process of mutation, the mutation process and evolutionary algorithms that incorporated for VRP can be used to make better use of the search space. The new process involves three basic functions, two of which are random used to choose the route and customer, the other is a deterministic for customer re-inserted into the routed to go. In addition, proposed three new mutation operator, used to adjust the route inter the customer distribution and the route service order.Proposed a new solution that can effectively solve CVRP,VRPTW by means of Enhanced coverage-restricted evolutionary algorithm, ECREA, the algorithm can be optimized simultaneously at least two optimization objectives. The algorithm integrates the above mentioned similarity quantitative methods and mutation process in order to better explore and exploit the search space, so as to maintain a high diversity of population. The results show that the solution obtained algorithm provides a more suitable compromise between the multi-objective optimization results.By the test on CVRP, VRPTW benchmark set, the new algorithm results compared to solutions with the existing optimization goals based on a single study considered showed the new algorithm to obtain a solution, though not on the whole are optimal, but at least, and the latter compared to the results of many studies can be compared, which is mainly manifested in the new solution algorithm can obtain fewer number of routes or shorter travel distance, while the corresponding other optimization objectives and the results of the latter different less than2%. Because obtained through an optimization goal is not necessarily the optimal solution can exhibit multi-objective optimization results, so the algorithm has practical value.Then the three multi-objective optimization performance metric are used in ECREA VRPTW bi-objective optimization problem and three-objective optimization, results were analyzed and compared with the famous multi-objective optimization algorithm NSGA-II solutions obtained were compared the results showed that the former won in many of the test cases better results than the latter. In solving the CVRP problem, because the test case test set goals and there is no conflict, there is no multi-objective optimization performance analysis.Because most existing studies regarding VRP tend to present and analyse the multiple objective optimization results in single objective manner, the paper has put forward through the use of formal methods for multi-objective evaluation of the performance of multi-objective optimization proper comparison and analyzed, and with the final conclusion更多还原