混合三维EDA求解带二维装载约束的车辆配送与分布式生产集成调度问题

Hybrid three-dimensional estimation of distribution algorithm for vehicle distribution with two-dimensional loading constraints and distributed production integrated scheduling problem

针对一类广泛存在的带二维装载约束的车辆配送与分布式生产集成调度问题(VD2LDPISP),本文建立问题模型,并提出混合三维分布估计算法(H3DEDA)进行求解.首先,结合问题各阶段特性,采用各阶段成本均衡策略设计新颖的解码规则,对编码个体进行分阶段解码,可确定较高质量的解码个体.其次,采用三维分布估计算法(3DEDA)学习和积累种群中优质编码个体的块结构及其位置信息,再通过采样3DEDA中的概率模型生成新的编码个体,从而提高算法全局搜索发现解空间中优质解区域的能力.然后,设计高低分层的超启发式局部搜索(HHLS)来增强算法的局部寻优能力.HHLS的低层问题域包含分别针对编码个体、配送阶段解码子个体和生产阶段解码子个体的共16种有效邻域操作,其高层策略域采用概率模型学习优质邻域操作排列的结构信息,进而通过采样该模型来直接控制新邻域操作排列的生成,有利于对不同优质区域进行深入搜索.最后,在不同规模测试问题上的算法比较,验证了所提H3DEDA的有效性.

Aiming at a kind of widely existing vehicle distribution with two-dimensional loading constraints and distributed production integrated scheduling problem(VD2LDPISP),this paper establishes the problem model and proposes a hybrid three-dimensional estimation of distribution algorithm(H3DEDA)to solve it.Firstly,combining with the characteristics of each stage of the problem,a novel decoding rule is designed by using the cost balance strategy of each stage.The coding individual is decoded in stages,and the decoding individual with high quality can be determined.Secondly,the three-dimensional estimation of distribution algorithm(3DEDA)is used to learn and accumulate the block structure and location information of high-quality coding individuals in the population,and generates new coding individuals by sampling the probability model in 3DEDA,which can improve the ability of the algorithm to find high-quality solution regions in the solution space globally.Then,the hyper-heuristic local search(HHLS)is designed to enhance the local optimization capability of the algorithm.The HHLS low-level problem domain contains 16 effective neighborhood operations for coding individuals,decoding sub-individuals in distribution and production phase.It is high-level policy domain,by using the probability model learning quality neighborhood operation arrangement of information structure,and then by sampling the model to directly control the new neighborhood operation arrangement,it is conducive to in-depth search of different high-quality areas.Finally,the effectiveness of the proposed H3DEDA is verified by comparison of algorithms on different scale test problems.