混合帝国竞争算法求解带多行程批量配送的多工厂集成调度问题

Hybrid Imperialist Competitive Algorithm for Solving Multi-Factory Integrated Scheduling Problem with Multi-Trip Batch Delivery

针对供应链中一类广泛存在的带多行程批量配送的多工厂集成调度问题(Multi-Factory Integrated Scheduling Problem with Multi-Trip Batch Delivery,MFISP_MTBD),建立其数学模型并提出基于贝叶斯统计推断的混合帝国竞争算法(Hybrid Bayesian statistical inference-based Imperialist Competitive Algorithm,HBICA)进行求解.根据MFISP_MTBD问题特性,结合多行程标签机制设计新型编解码策略,并基于该策略构造新型启发式规则以提高初始解的质量.为有效保留优质解的模式信息,采用贝叶斯概率模型学习机制替换标准帝国竞争算法中的同化机制.为更加明确地引导搜索方向,算法每代均利用各帝国中的精英国家(即精英解或个体)重构贝叶斯概率模型,进而对其采样生成新种群.利用9种有效邻域操作动态构造各帝国中每个国家的局部搜索,并对由各帝国内部相邻国家间竞争所确定的强势国家(即获胜国)执行其局部搜索,进而对各帝国中的殖民国家(即该帝国内的最强国家)依次执行所有弱势国家的局部搜索.仿真实验和算法比较验证了所提算法可有效求解MFISP_MTBD.

Aiming at a kind of widely existing multi-factory integrated scheduling problem with multi-trip batch delivery(MFISP_MTBD)in the supply chain,this paper establishes the mathematical model,and a hybrid Bayesian statistical inference-based imperialist competitive algorithm(HBICA)is proposed to solve it.According to the characteristics of the MFISP_MTBD,a new encoding and decoding strategy based on multi-trip labeling mechanism is proposed,on this basis,a new heuristic rule is constructed to improve the quality of the initial solution.To effectively preserve the pattern information of the high-quality solution,the Bayesian probability model learning mechanism is used to replace the assimilation mechanism in the imperial competition algorithm.Afterwards,each generation of the algorithm reconstructs the Bayesian probability model by using the elite countries(i.e.elite solution or individual)in each empire to guide the search direction explicitly,and new population is generated by sampling it.The local search for each country in each empire is dynamically constructed by 9 effective neighborhood operations.Local search is carried out on the strong country(i.e.the winning country)determined by the competition among neighboring countries within the empire,and local search of weak countries is carried out in turn for the colonial countries in each empire(i.e.the strongest countries in the empire).Simulation experiments and comparisons on different instances demonstrate that the proposed algorithm can effectively solve MFISP_MTBD.