物流配送车辆路径问题建模及多目标优化算法研究

发布时间：2018-11-05 13:38

【摘要】：物流作为企业的“第三利润源泉”,已经受到人们的广泛关注,配送是物流系统中的重要环节,占物流成本的50%以上,作为物流配送环节的核心问题,车辆路径问题自提出以来,就成为物流配送、运筹学、组合优化等领域的热点问题。合理规划配送路线不仅能够有效的降低物流配送成本,增加企业效益,而且还能提高服务质量,增加顾客满意度。因此,对车辆路径问题的研究具有重要的实用价值和科学意义。车辆路径问题往往具有多个互相制约的目标,是个典型的多目标优化问题,但是应用传统的解决多目标优化问题的方法很难收敛到Pareto最优解集,因此本文将从多目标角度对车辆路径问题的模型和算法进行研究。本文主要研究两类车辆路径问题：带时间窗的车辆路径问题以及带模糊时间窗的开放式车辆路径问题,建立多目标数学模型,并设计不同的多目标进化算法对两模型进行求解。本文主要研究内容如下：(1)带时间窗车辆路径问题。本文建立以最小化行驶路程和最小化使用车辆数量为目标的多目标数学模型,并提出一种多目标混合差分进化算法进行求解。算法采用了自然数编码机制,并重新定义新的个体生成方法；通过引入Pareto支配的概念来评价个体的优劣性,并采用擂台法则构造非支配集。在进化过程中,以差分进化算法为求解主体,通过引入双种群机制和变邻域下降搜索策略,有效平衡的种群在解空间的全局探索能力和局部开发能力,以提高算法搜索效率。实验结果表明多目标混合差分进化算法是求解带时间窗车辆路径问题的有效算法。(2)带模糊时间窗的开放式车辆路径问题。本文考虑了车辆容量约束和车辆最大行驶里程约束,建立以最小化总成本和最大化顾客满意度为目标的多目标数学模型,并提出一种多目标混合遗传算法进行求解。算法采用自然数编码机制,使用混合方法构造初始种群以及适合本文问题的遗传算子,在进化过程中嵌入一种执行模拟退火机制的基于meta-Lamarckian学习策略的局部搜索算法,同时去除重复个体,提高算法的局部开发能力,运用擂台法则构造非支配解集,降低算法时间复杂度,使用调和平均距离方法评价个体的拥挤程度,提高非支配集的分布性。实验结果表明该算法能够有效求解带模糊时间窗的开放式车辆路径问题,并且与NSGA-Ⅱ算法的对比结果也验证了该算法在Pareto解的数量、解的分布性以及收敛性等方面都具有明显的优势。本文将两类车辆路径问题都作为多目标优化问题进行研究,在求解过程中不需要引入偏好,同等的考虑模型中的求解目标,通过设计多目标进化算法进行求解,获得一组非支配解,有利于物流决策者根据不同的实际需求选择不同的决策方案。
[Abstract]:As the "third profit source" of enterprises, logistics has been widely concerned by people. Distribution is an important link in logistics system, accounting for more than 50% of the logistics cost, as the core issue of logistics distribution. Since the vehicle routing problem was proposed, it has become a hot issue in the fields of logistics distribution, operational research, combination optimization and so on. Reasonable planning of distribution routes can not only effectively reduce the cost of logistics distribution, increase the efficiency of enterprises, but also improve the quality of service and customer satisfaction. Therefore, the study of vehicle routing problem has important practical value and scientific significance. The vehicle routing problem is a typical multi-objective optimization problem because it has many mutually restricted objectives. However, it is difficult to converge to the Pareto optimal solution set by applying the traditional method to solve the multi-objective optimization problem. So this paper will study the model and algorithm of vehicle routing problem from multi-objective point of view. In this paper, two kinds of vehicle routing problems are studied: the vehicle routing problem with time window and the open vehicle routing problem with fuzzy time window. The multi-objective mathematical model is established, and different multi-objective evolutionary algorithms are designed to solve the two models. The main contents of this paper are as follows: (1) vehicle routing problem with time window. In this paper, a multi-objective mathematical model with the objective of minimizing the travel distance and minimizing the number of vehicles used is established, and a multi-objective hybrid differential evolutionary algorithm is proposed to solve the problem. The algorithm adopts the encoding mechanism of natural numbers and redefines the new method of individual generation. The concept of Pareto domination is introduced to evaluate the superiority and inferiority of individuals and the non-dominated set is constructed by using the ring rule. In the course of evolution, the differential evolution algorithm is used as the main solution. By introducing the dual population mechanism and variable neighborhood descent search strategy, the global exploration ability and local development ability of the population in the solution space can be effectively balanced, so as to improve the search efficiency of the algorithm. Experimental results show that the multi-objective hybrid differential evolution algorithm is an effective algorithm for solving vehicle routing problems with time windows. (2) Open vehicle routing problems with fuzzy time windows. Considering vehicle capacity constraints and vehicle maximum mileage constraints, a multi-objective mathematical model with the goal of minimizing total cost and maximizing customer satisfaction is established, and a multi-objective hybrid genetic algorithm is proposed to solve the problem. The algorithm adopts the natural number coding mechanism, uses the hybrid method to construct the initial population and genetic operators suitable for the problem in this paper, and embed a local search algorithm based on meta-Lamarckian learning strategy in the evolution process. At the same time, the repetitive individuals are removed, the local development ability of the algorithm is improved, the non-dominated solution set is constructed by using the ring law, the time complexity of the algorithm is reduced, the method of harmonic average distance is used to evaluate the crowding degree of the individual, and the distribution of the non-dominated set is improved. Experimental results show that the algorithm can effectively solve the open vehicle routing problem with fuzzy time window, and the comparison with NSGA- 鈪，

本文编号：2312254