混合三维分布估计算法求解分布式加工装配和车辆配送集成调度问题  

Hybrid Three-Dimensional Estimation of Distribution Algorithm for Integrated Scheduling Problem of Distributed Production Assembly and Vehicle Delivery

作　　者：杨绍文 钱斌[1,2] 胡蓉 张梓琪[1,2] YANG Shao-wen;QIAN Bin;HU Rong;ZHANG Zi-qi(Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming,Yunnan 650500,China;Yunnan Key Laboratory of Artificial Intelligence,Kunming,Yunnan 650500,China)

机构地区：[1]昆明理工大学信息工程与自动化学院,云南昆明650500 [2]云南省人工智能重点实验室,云南昆明650500

出　　处：《电子学报》2024年第3期909-923,共15页Acta Electronica Sinica

基　　金：国家自然科学基金(No.62173169,No.61963022);云南省基础研究重点项目(No.202201AS070030)。

摘　　要：本文针对一类广泛存在的分布式加工装配和车辆配送集成调度问题(Integrated Scheduling Problem of Distributed Production Assembly and Vehicle Delivery,ISP_DPAVD),以最小化运输和延迟惩罚总成本为优化目标,提出一种混合三维分布估计算法(Hybrid three-Dimensional Estimation of Distribution Algorithm,H3DEDA)进行求解.ISP_DPAVD包含两个耦合的子问题,即加工装配阶段子问题(子问题1)和车辆配送阶段子问题(子问题2).由于每个子问题1的解(部分解1)均会确定1个具体的子问题2,故ISP_DPAVD的解空间非常庞大.根据这一特点,在H3DEDA中,先设计结合邻域变换的启发式规则来快速获取子问题2的优良解,以实现子问题间的部分解耦并明显缩减搜索空间,再设计三维EDA引导的全局搜索和变邻域驱动的局部搜索来获取ISP_DPAVD的高质量解.通过在不同规模测试问题上的仿真实验和算法比较,验证了H3DEDA求解ISP_DPAVD的有效性.This paper proposes a hybrid three-dimensional distribution estimation algorithm(H3DEDA)to minimize the total cost of transportation and delay penalties for a kind of widely existed integrated scheduling problem(ISP_DPAVD),which includes two coupled subproblems,i.e.,the subproblem in the production and assembly stage(subproblem 1)and the subproblem in the vehicle distribution stage(subproblem 2).Since each solution of subproblem 1 determines a specific sub⁃problem 2,the solution space of the ISP_DPAVD is very large.According to this characteristic,in H3DEDA(Hybrid three-Di⁃mensional Estimation of Distribution Algorithm),the heuristic rules combined with neighborhood transformation are designed to quickly obtain the excellent solution of subproblem 2,so as to achieve partial decoupling between subproblems and signifi⁃cantly reduce the search space.Then,the global search guided by three-dimensional EDA and the local search driven by vari⁃able neighborhood operations are devised to acquire high-quality solution for the ISP_DPAVD.Simulation experiments and comparisons on the test problems with different scales verify the effectiveness of H3DEDA in solving ISP_DPAVD.

关 键 词：分布式加工装配流水车间 车辆配送 集成调度 三维分布估计算法 变邻域搜索 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]