The distributed flexible job shop scheduling problem(DFJSP)has attracted great attention with the growth of the global manufacturing industry.General DFJSP research only considers machine constraints and ignores worke...The distributed flexible job shop scheduling problem(DFJSP)has attracted great attention with the growth of the global manufacturing industry.General DFJSP research only considers machine constraints and ignores worker constraints.As one critical factor of production,effective utilization of worker resources can increase productivity.Meanwhile,energy consumption is a growing concern due to the increasingly serious environmental issues.Therefore,the distributed flexible job shop scheduling problem with dual resource constraints(DFJSP-DRC)for minimizing makespan and total energy consumption is studied in this paper.To solve the problem,we present a multi-objective mathematical model for DFJSP-DRC and propose a Q-learning-based multi-objective grey wolf optimizer(Q-MOGWO).In Q-MOGWO,high-quality initial solutions are generated by a hybrid initialization strategy,and an improved active decoding strategy is designed to obtain the scheduling schemes.To further enhance the local search capability and expand the solution space,two wolf predation strategies and three critical factory neighborhood structures based on Q-learning are proposed.These strategies and structures enable Q-MOGWO to explore the solution space more efficiently and thus find better Pareto solutions.The effectiveness of Q-MOGWO in addressing DFJSP-DRC is verified through comparison with four algorithms using 45 instances.The results reveal that Q-MOGWO outperforms comparison algorithms in terms of solution quality.展开更多
Cooperative multi-agent reinforcement learning（ MARL） is an important topic in the field of artificial intelligence,in which distributed constraint optimization（ DCOP） algorithms have been widely used to coordinat...Cooperative multi-agent reinforcement learning（ MARL） is an important topic in the field of artificial intelligence,in which distributed constraint optimization（ DCOP） algorithms have been widely used to coordinate the actions of multiple agents. However,dense communication among agents affects the practicability of DCOP algorithms. In this paper,we propose a novel DCOP algorithm dealing with the previous DCOP algorithms＇ communication problem by reducing constraints.The contributions of this paper are primarily threefold：（1） It is proved that removing constraints can effectively reduce the communication burden of DCOP algorithms.（2） An criterion is provided to identify insignificant constraints whose elimination doesn＇t have a great impact on the performance of the whole system.（3） A constraint-reduced DCOP algorithm is proposed by adopting a variant of spectral clustering algorithm to detect and eliminate the insignificant constraints. Our algorithm reduces the communication burdern of the benchmark DCOP algorithm while keeping its overall performance unaffected. The performance of constraint-reduced DCOP algorithm is evaluated on four configurations of cooperative sensor networks. The effectiveness of communication reduction is also verified by comparisons between the constraint-reduced DCOP and the benchmark DCOP.展开更多
针对带时间窗的多车型电动车辆路径问题(heterogeneous electric vehicle routing problem with time windows,HEVRPTW),综合考虑客户需求差异、车辆异构特性和充电约束等因素,构建以总行驶成本最小化为目标的混合整数规划模型,并提出...针对带时间窗的多车型电动车辆路径问题(heterogeneous electric vehicle routing problem with time windows,HEVRPTW),综合考虑客户需求差异、车辆异构特性和充电约束等因素,构建以总行驶成本最小化为目标的混合整数规划模型,并提出结合层次聚类机制的混合变邻域搜索算法(hybrid variable neighborhood search,HVNS)进行求解。该算法采用层次聚类机制对客户节点进行空间划分,并结合贪婪算法生成初始解;在局部搜索阶段,整合单点插入、两点交换、两段交换及2–opt等多种邻域操作算子,并引入充电站优化策略优化路径选择。基于标准测试案例通过与Gurobi求解器和遗传算法(genetic algorithm,GA)进行仿真对比实验,并对电池容量、充电时间、时间窗宽度、车辆数量等关键参数进行敏感性分析。结果表明:HVNS能在更短时间内获得与Gurobi相近的优质解,验证了模型的正确性及其在不同规模问题求解中的优越性能;与GA相比,HVNS在求解质量上实现了10%~20%的提升,同时在稳定性和收敛性方面更优;通过参数优化确定了最佳配置方案(电池容量为150 kWh、充电时间为45 min、时间窗宽度为90 min、车辆数量为8辆),实现了总行驶成本最小化与客户满意度最大化的平衡。研究结果验证了HVNS是求解HEVRPTW的有效方法,本研究为物流企业电动车辆路径优化提供了科学的决策支持工具。展开更多
针对现有的基于蚁群优化思想求解分布式约束优化问题的算法收敛较慢、容易陷入局部最优等问题,提出了一种基于多种群的随机扰动蚁群算法(random disturbance based multi-population ant colony algorithm to solve distributed constra...针对现有的基于蚁群优化思想求解分布式约束优化问题的算法收敛较慢、容易陷入局部最优等问题,提出了一种基于多种群的随机扰动蚁群算法(random disturbance based multi-population ant colony algorithm to solve distributed constraint optimization problems,RDMAD)来求解分布式约束优化问题。首先,RDMAD提出了一种分工合作机制,将种群按比例划分为采用贪婪搜索的子种群和采用启发式搜索的子种群,同时构建分级更新策略,提高算法收敛速度和求解质量;然后对采用贪婪搜索的子种群设计自适应变异算子和奖惩机制,防止算法陷入局部最优;最后在算法陷入停滞时触发随机扰动策略,增加种群多样性。将RDMAD与七种最先进的非完备算法在三类基准问题上的寻优结果进行了实验对比,结果表明RDMAD在求解质量和收敛速度上优势明显,且稳定性较高。展开更多
基金supported by the Natural Science Foundation of Anhui Province(Grant Number 2208085MG181)the Science Research Project of Higher Education Institutions in Anhui Province,Philosophy and Social Sciences(Grant Number 2023AH051063)the Open Fund of Key Laboratory of Anhui Higher Education Institutes(Grant Number CS2021-ZD01).
文摘The distributed flexible job shop scheduling problem(DFJSP)has attracted great attention with the growth of the global manufacturing industry.General DFJSP research only considers machine constraints and ignores worker constraints.As one critical factor of production,effective utilization of worker resources can increase productivity.Meanwhile,energy consumption is a growing concern due to the increasingly serious environmental issues.Therefore,the distributed flexible job shop scheduling problem with dual resource constraints(DFJSP-DRC)for minimizing makespan and total energy consumption is studied in this paper.To solve the problem,we present a multi-objective mathematical model for DFJSP-DRC and propose a Q-learning-based multi-objective grey wolf optimizer(Q-MOGWO).In Q-MOGWO,high-quality initial solutions are generated by a hybrid initialization strategy,and an improved active decoding strategy is designed to obtain the scheduling schemes.To further enhance the local search capability and expand the solution space,two wolf predation strategies and three critical factory neighborhood structures based on Q-learning are proposed.These strategies and structures enable Q-MOGWO to explore the solution space more efficiently and thus find better Pareto solutions.The effectiveness of Q-MOGWO in addressing DFJSP-DRC is verified through comparison with four algorithms using 45 instances.The results reveal that Q-MOGWO outperforms comparison algorithms in terms of solution quality.
基金Supported by the National Social Science Foundation of China(15ZDA034,14BZZ028)Beijing Social Science Foundation(16JDGLA036)JKF Program of People’s Public Security University of China(2016JKF01318)
文摘Cooperative multi-agent reinforcement learning（ MARL） is an important topic in the field of artificial intelligence,in which distributed constraint optimization（ DCOP） algorithms have been widely used to coordinate the actions of multiple agents. However,dense communication among agents affects the practicability of DCOP algorithms. In this paper,we propose a novel DCOP algorithm dealing with the previous DCOP algorithms＇ communication problem by reducing constraints.The contributions of this paper are primarily threefold：（1） It is proved that removing constraints can effectively reduce the communication burden of DCOP algorithms.（2） An criterion is provided to identify insignificant constraints whose elimination doesn＇t have a great impact on the performance of the whole system.（3） A constraint-reduced DCOP algorithm is proposed by adopting a variant of spectral clustering algorithm to detect and eliminate the insignificant constraints. Our algorithm reduces the communication burdern of the benchmark DCOP algorithm while keeping its overall performance unaffected. The performance of constraint-reduced DCOP algorithm is evaluated on four configurations of cooperative sensor networks. The effectiveness of communication reduction is also verified by comparisons between the constraint-reduced DCOP and the benchmark DCOP.
文摘针对带时间窗的多车型电动车辆路径问题(heterogeneous electric vehicle routing problem with time windows,HEVRPTW),综合考虑客户需求差异、车辆异构特性和充电约束等因素,构建以总行驶成本最小化为目标的混合整数规划模型,并提出结合层次聚类机制的混合变邻域搜索算法(hybrid variable neighborhood search,HVNS)进行求解。该算法采用层次聚类机制对客户节点进行空间划分,并结合贪婪算法生成初始解;在局部搜索阶段,整合单点插入、两点交换、两段交换及2–opt等多种邻域操作算子,并引入充电站优化策略优化路径选择。基于标准测试案例通过与Gurobi求解器和遗传算法(genetic algorithm,GA)进行仿真对比实验,并对电池容量、充电时间、时间窗宽度、车辆数量等关键参数进行敏感性分析。结果表明:HVNS能在更短时间内获得与Gurobi相近的优质解,验证了模型的正确性及其在不同规模问题求解中的优越性能;与GA相比,HVNS在求解质量上实现了10%~20%的提升,同时在稳定性和收敛性方面更优;通过参数优化确定了最佳配置方案(电池容量为150 kWh、充电时间为45 min、时间窗宽度为90 min、车辆数量为8辆),实现了总行驶成本最小化与客户满意度最大化的平衡。研究结果验证了HVNS是求解HEVRPTW的有效方法,本研究为物流企业电动车辆路径优化提供了科学的决策支持工具。
文摘针对现有的基于蚁群优化思想求解分布式约束优化问题的算法收敛较慢、容易陷入局部最优等问题,提出了一种基于多种群的随机扰动蚁群算法(random disturbance based multi-population ant colony algorithm to solve distributed constraint optimization problems,RDMAD)来求解分布式约束优化问题。首先,RDMAD提出了一种分工合作机制,将种群按比例划分为采用贪婪搜索的子种群和采用启发式搜索的子种群,同时构建分级更新策略,提高算法收敛速度和求解质量;然后对采用贪婪搜索的子种群设计自适应变异算子和奖惩机制,防止算法陷入局部最优;最后在算法陷入停滞时触发随机扰动策略,增加种群多样性。将RDMAD与七种最先进的非完备算法在三类基准问题上的寻优结果进行了实验对比,结果表明RDMAD在求解质量和收敛速度上优势明显,且稳定性较高。
