针对一类广泛存在的分布式生产-运输-装配集成调度问题(Integrated scheduling problem of distributed production,transportation and assembly,ISPDPTA),建立问题模型并提出一种增强三维分布估计算法(Enhanced three-dimensional estimation of distribution algorithm,E3DEDA)进行求解.在E3DEDA的全局搜索部分,先根据ISPDPTA的问题特性,对包含工厂信息的工件与产品进行多段编码,并依据最短路径规则获得各车辆路径;再采用双三维概率模型分别学习和积累种群中较优个体的工件块与产品块结构及其位置信息,并采样生成新个体,从而增强算法发现优质解空间区域的能力.在E3DEDA的局部搜索部分,设计自适应变邻域局部搜索来增强算法的局部搜索能力.具体而言,针对问题各阶段特性,设计10种有效的邻域操作组成备选集合,并采用二维概率模型学习由不同邻域操作所构成的优质邻域结构信息,进而采样生成合理的邻域操作排列并依次执行,以实现对全局搜索所发现优质区域的深入搜索.此外,设计块结构概率评价更新机制,可提升算法执行效率.最后,通过仿真试验与算法对比验证E3DEDA可有效求解ISPDPTA.
Enhanced Three-dimensional Estimation of Distribution Algorithm for Solving Integrated Scheduling Problem of Distributed Production,Transportation and Assembly
Aiming at a kind of integrated scheduling problem of distributed production,transportation and assembly(ISPDPTA),which widely exists in real-life applications,the model of the problem is established first.And then,an enhanced three-dimensional estimation of distribution algorithm(E3DEDA)is proposed to solve the model.In global search stage,E3DEDA uses a multi-segment encoding mechanism to represent jobs and productions that contain factory information based on the characteristics of ISPDPTA,in which each vehicle path is determined by applying the shortest path rule.Besides,two three-dimensional probability matrices are adopted to enhance the ability of E3DEDA for finding promising search regions.That is,the matrices separately learn and accumulate the information about the structure and location of job blocks and product blocks stemming from elite individuals found during the search process.Thereby,new individuals are generated by sampling the two matrices.In local search stage,E3DEDA adopts adaptive variable neighborhood local search to improve the local search ability of the algorithm.Especially,ten neighborhood operations are used to form the alternative set based on the characteristics of each stage of ISPDPTA,and a two-dimensional probability matrix is used to learn the information about high-quality neighborhood structures regarding different neighborhood operations.By sampling the matrix,permutations are generated and a series of neighborhood operations are in turn performed on the solutions of E3DEDA,so as to intensively examine promising search regions discovered by the global search stage.Moreover,a probability evaluation updating mechanism of block structure is proposed to improve the efficiency of the algorithm.Finally,simulations and comparisons demonstrate that E3DEDA can effectively solve ISPDPTA.
distributed productionvehicle transportationintegrated schedulingthree-dimensional estimation of distribution algorithmblock structure
NETL
NSTL
万方数据
维普
