基于分布估计算法的车辆调度问题研究

发布时间：2018-04-09 15:49

本文选题：VRP　切入点：分布估计算法　出处：《昆明理工大学》2017年硕士论文

【摘要】：随着市场竞争越来越激烈,科学技术的快速发展和物流的专业水平不断提高,大量企业已经把先进的物流理论技术引入到了企业管理中来,并且把物流作为提高市场竞争力与核心竞争水平的一个重要的手段。怎样对配送系统的车辆路径进行优化来降低企业物流成本是此问题主要研究内容。物流配送中的车辆路径优化问题(Vehicle Routing Problem,VRP)属于典型的NP-hard问题,其计算时间也会随着问题规模的变大而越来越长,应用传统精确算法求解该问题复杂性较大。因此,目前大部分研究学者主要用智能优化算法对车辆调度问题进行求解。分布估计算法(Estimation of Distribution Algorithm,EDA)是一种基于概率分布模型的进化算法,在近年来也得到了普遍的关注和发展,并且成功的应用于多个工业发展领域,取得了良好效果。故而本文主要针对不同约束条件的车辆路径优化问题,对其进行了三种改进,并分别采用改进算法进行仿真来验证算法的有效性。首先,针对总行驶距离指标下的车辆载重约束的经典车辆路径优化问题,设计了合适的编码机制和概率模型,将传统的二进制编码改为十进制编码方式,减少了编码之间转换的繁琐过程,根据车辆调度问题特点,将普通的二维概率矩阵改为三维矩阵,即每辆车对应一个单独的二维矩阵,最后加入了局部搜索机制,对优质个体进行更加细致的搜索,进而提出了一种解决此问题的改进分布估计算法(Improved Estimation of Distribution Algorithm,IEDA)。通过Matlab应用IEDA算法对容量约束车辆调度问题进行仿真,表明提高了算法全局搜索能力,降低了总的配送费用(路程),从而验证了该算法的有效性。其次,对随机需求的多车型车辆调度问题将随机需求问题利用时间轴转换成一系列的的静态车辆调度问题,另外对于多车型问题考虑以装载率为选择车辆的依据,建立了考虑装载率和油耗等综合成本的优化目标的车辆调度问题。针对随机需求多车型VRP问题特点,在上一章算法的基础上,将分布估计算法与并行节约算法相混合,提出了混合分布估计算法(HEDA)。然后,对考虑综合成本低碳车辆调度问题,提出一种自适应分布估计算法(Adaptive Estimation of DistributionAlgorithm,AEDA)。对初始概率模型机制进行改进,使得概率模型能够积累更多的优质信息,以便算法初期的搜索范围更加广泛,又设计了基于信息熵的自适应更新机制来更新学习速率和变异率,增强算法的搜索能力。
[Abstract]:With the increasingly fierce market competition, the rapid development of science and technology and the continuous improvement of the professional level of logistics, a large number of enterprises have introduced advanced logistics theory and technology into enterprise management.And logistics as an important means to improve market competitiveness and core competition level.How to optimize the vehicle routing of distribution system to reduce the logistics cost is the main research content.Vehicle Routing problem in logistics distribution is a typical NP-hard problem, and its computational time will become longer and longer with the increase of the size of the problem. The application of traditional accurate algorithm to solve the problem is more complex.Therefore, at present, most scholars mainly use intelligent optimization algorithm to solve vehicle scheduling problem.Estimation of Distribution algorithm (EDAA) is an evolutionary algorithm based on probabilistic distribution model. It has been widely concerned and developed in recent years, and has been successfully applied in many industrial development fields, and has achieved good results.Therefore, this paper mainly aims at the vehicle routing optimization problem with different constraints, and makes three improvements to it, and uses the improved algorithm to simulate to verify the effectiveness of the algorithm.First of all, aiming at the classical vehicle path optimization problem with vehicle load constraints under the total driving distance index, an appropriate coding mechanism and probability model are designed to change the traditional binary code to the decimal coding method.According to the characteristics of vehicle scheduling problem, the ordinary two-dimensional probability matrix is changed to three-dimensional matrix, that is, each vehicle corresponds to a separate two-dimensional matrix. Finally, a local search mechanism is added.An improved Estimation of Distribution algorithm is proposed to solve this problem.The simulation of the capacity constrained vehicle scheduling problem using Matlab IEDA algorithm shows that the algorithm improves the global search ability and reduces the total distribution cost, thus validates the effectiveness of the algorithm.Secondly, for the multi-model vehicle scheduling problem with random demand, the stochastic demand problem is transformed into a series of static vehicle scheduling problems by using the time-axis. In addition, the loading rate is considered as the basis for vehicle selection for the multi-vehicle model problem.The vehicle scheduling problem considering the comprehensive cost such as loading rate and fuel consumption is established.In view of the characteristics of stochastic demand multi-vehicle VRP problem, a hybrid distribution estimation algorithm is proposed based on the algorithm in the previous chapter, which combines the distributed estimation algorithm with the parallel saving algorithm.Then, an adaptive Estimation of distribution algorithm is proposed to solve the problem of low carbon vehicle scheduling with integrated cost.The mechanism of initial probabilistic model is improved so that the probabilistic model can accumulate more high quality information so that the search range of the initial algorithm can be more extensive. An adaptive updating mechanism based on information entropy is designed to update the learning rate and mutation rate.Enhance the search ability of the algorithm.
【学位授予单位】：昆明理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：U492.22

【参考文献】