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

doi:10.12263/DZXB.20210320

电子学报 ›› 2022, Vol. 50 ›› Issue (7): 1621-1630.DOI: 10.12263/DZXB.20210320

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

唐捷凯¹^,², 胡蓉¹^,², 钱斌¹^,², 金怀平¹, 向凤红¹

^1.昆明理工大学信息工程与自动化学院，云南昆明 650500
^2.昆明理工大学云南省人工智能重点实验室，云南昆明 650500

收稿日期:2021-03-07 修回日期:2021-07-20 出版日期:2022-07-25
- 作者简介:
- 唐捷凯男，1997年出生，云南昆明人.硕士研究生.研究方向为优化调度与智能算法.E-mail: tjk1379@foxmail.com
  胡蓉(通讯作者) 女，1974年出生，贵州安顺人.副教授，硕士生导师.研究方向为优化方法与决策支持系统.E-mail: ronghu@vip.163.com
  钱斌男，1976年出生，云南曲靖人.教授，博士生导师.研究方向为智能调度理论与方法.E-mail: bin.qian@vip.163.com
  金怀平男，1987年出生，云南曲靖人.副教授，硕士生导师，目前研究方向为数据挖掘与机器学习.E-mail: jinhuaiping@gmail.com
  向凤红男，1964年出生，四川省盐亭人.教授，硕士生导师.研究方向为智能优化方法.E-mail: xiangfh5447@sina.com
- 基金资助:
- 国家自然科学基金 (62173169); 云南省基础研究重点项目 (202101AS070097)

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

TANG Jie-kai¹^,², HU Rong¹^,², QIAN Bin¹^,², JIN Huai-ping¹, XIANG Feng-hong¹

^1.Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming, Yunnan 650500, China
^2.Key Laboratory of Artificial Intelligence in Yunnan Province, Kunming University of Science and Technology, Kunming, Yunnan 650500, China

Received:2021-03-07 Revised:2021-07-20 Online:2022-07-25 Published:2022-07-30
- Supported by:
- National Natural Science Foundation of China (62173169); A Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions (202101AS070097)

摘要/Abstract

摘要：

针对供应链中一类广泛存在的带多行程批量配送的多工厂集成调度问题（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.

关键词: 多工厂供应链, 多行程配送, 集成调度, 贝叶斯统计推断, 帝国竞争算法

Abstract:

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.

Key words: multi-factory supply chain, multi-trip delivery, integrated scheduling, Bayesian statistical inference, imperialist competitive algorithm

中图分类号:

TP273

唐捷凯, 胡蓉, 钱斌, 等. 混合帝国竞争算法求解带多行程批量配送的多工厂集成调度问题[J]. 电子学报, 2022, 50(7): 1621-1630.

Jie-kai TANG, Rong HU, Bin QIAN, et al. Hybrid Imperialist Competitive Algorithm for Solving Multi-Factory Integrated Scheduling Problem with Multi-Trip Batch Delivery[J]. Acta Electronica Sinica, 2022, 50(7): 1621-1630.

图/表 8

表1 符号表

符号	说明
$i, j$	工件或客户下标, $i, j = 1,2, ⋯, N$
$f$	工厂编号 $f = 1,2, ⋯, F$
$k$	车辆编号 $k = 1,2, ⋯, K f$
$w$	车辆行程编号 $w = 1,2, ⋯, W k f$
$E s u m$	各工厂加工产生的总功耗 $k W ⋅ h$
$C e$	单位电价
$q i$	工件 $i$ 的重量 $t$ , $q i ∈ 0, Q$
$W k$	车辆的自重 $t$
$N e l i t e$	车辆在客户 $i$ 到客户 $N e l i t e E = N E m p E × P e l i t e$ 的货运负载 $t$ , $L i, j ∈ 0, Q$
$D i j$	客户 $i$ 到客户 $j$ 的距离 $k m$
$C B k f w$	$f$ 厂 $k$ 车的第 $w$ 批次配送开始时间
$A i$	工件 $i$ 送达客户 $i$ 的时间
$λ L$	车辆与加速度、滚动阻力、重力等相关的油耗系数
$λ k$	车辆与空气密度和车辆前表面积等相关的油耗系数
$G i j$	车辆在客户 $i$ 到客户 $j$ 的耗油量
$G s u m$	配送阶段产生的总油耗
$C g$	单位油价
$T i$	工件 $i$ 违规超时时常
$λ p$	违约超时的惩罚系数
$V j f$	如果工件 $j$ 分配在 $f$ 厂加工则为1,否则为0, $V j f ∈ 0,1$
$X i j f$	如果工件 $j$ 在紧接着工件 $i$ 之后在 $f$ 厂加工则为1,否则为0, $X i j f ∈ {0,1}$
$Y i j k f w$	若客户 $j$ 由 $f$ 厂 $k$ 车的第 $w$ 批次行程配送则为1,否则为0, $Y j k f w ∈ 0,1$
$Z i j k f w$	若客户 $i$ 紧接着客户 $j$ 由 $f$ 厂 $k$ 车的第 $w$ 批次行程配送则为1,否则为0, $Z i j k f w ∈ 0,1$

表1 符号表

符号	说明
$i, j$	工件或客户下标, $i, j = 1,2, ⋯, N$
$f$	工厂编号 $f = 1,2, ⋯, F$
$k$	车辆编号 $k = 1,2, ⋯, K f$
$w$	车辆行程编号 $w = 1,2, ⋯, W k f$
$E s u m$	各工厂加工产生的总功耗 $k W ⋅ h$
$C e$	单位电价
$q i$	工件 $i$ 的重量 $t$ , $q i ∈ 0, Q$
$W k$	车辆的自重 $t$
$N e l i t e$	车辆在客户 $i$ 到客户 $N e l i t e E = N E m p E × P e l i t e$ 的货运负载 $t$ , $L i, j ∈ 0, Q$
$D i j$	客户 $i$ 到客户 $j$ 的距离 $k m$
$C B k f w$	$f$ 厂 $k$ 车的第 $w$ 批次配送开始时间
$A i$	工件 $i$ 送达客户 $i$ 的时间
$λ L$	车辆与加速度、滚动阻力、重力等相关的油耗系数
$λ k$	车辆与空气密度和车辆前表面积等相关的油耗系数
$G i j$	车辆在客户 $i$ 到客户 $j$ 的耗油量
$G s u m$	配送阶段产生的总油耗
$C g$	单位油价
$T i$	工件 $i$ 违规超时时常
$λ p$	违约超时的惩罚系数
$V j f$	如果工件 $j$ 分配在 $f$ 厂加工则为1,否则为0, $V j f ∈ 0,1$
$X i j f$	如果工件 $j$ 在紧接着工件 $i$ 之后在 $f$ 厂加工则为1,否则为0, $X i j f ∈ {0,1}$
$Y i j k f w$	若客户 $j$ 由 $f$ 厂 $k$ 车的第 $w$ 批次行程配送则为1,否则为0, $Y j k f w ∈ 0,1$
$Z i j k f w$	若客户 $i$ 紧接着客户 $j$ 由 $f$ 厂 $k$ 车的第 $w$ 批次行程配送则为1,否则为0, $Z i j k f w ∈ 0,1$

图1 MFISP_MTBD示意图

图2 编码示意图

图3 资源个体示意图

图4 精英国家贝叶斯网络图

图5 HBICA流程图

表2 ICA、ED_ICA、B_ICA与HBICA的有效性对比结果

问题规模	ICA	ED_ICA	B_ICA	HBICA
问题规模	AVG	AVG	AVG	AVG
20×4	14 450.9	14 988.0	14 340.5	14 199.9
25×4	14 494.4	15 357.3	13 815.2	13 873.7
30×4	26 201.7	26 782.9	25 864.8	25 596.4
35×5	31 427.5	32 927.3	30 487.5	30 053.6
40×5	30 568.0	31 770.0	29 822.2	28 684.1
45×5	38 818.3	40 691.0	38 403.7	36 964.1
50×5	35 008.1	36 311.2	34 476.0	33 051.3
55×5	43 688.4	48 533.1	42 848.4	40 734.6
60×5	39 830.7	41 186.8	38 931.9	36 048.2
70×6	55 374.2	57 541.4	53 308.9	49 980.1
75×6	58 836.0	60 235.3	56 007.4	51 461.8
80×6	66 920.6	68 368.6	65 620.3	61 159.9
85×6	72 998.5	75 846.1	70 183.5	65 691.7
90×6	81 412.9	84 581.4	79 584.2	74 158.8
95×6	92 680.9	95 428.5	89 531.7	82 419.5
100×7	103 939.1	106 037.4	100 467.0	95 075.9
110×7	105 511.1	107 240.7	101 652.1	94 401.1
120×7	107 714.9	110 023.9	102 244.8	92 399.4
130×8	114 532.1	115 963.7	111 945.5	104 564.7
140×8	130 273.5	130 546.4	126 380.4	117 835.0
150×8	145 919.3	147 666.2	139 694.2	129 909.8
160×9	141 979.5	142 290.3	133 988.9	123 245.0
170×9	158 330.2	159 327.2	146 520.4	135 854.0
180×9	162 768.5	163 943.6	151 614.8	141 274.3
160×10	143 235.6	144 221.7	135 621.1	125 496.7
170×10	152 592.7	153 493.5	148 342.6	139 855.0
180×10	145 698.1	145 956.9	135 022.7	126 678.4
Average	85 748.4	87 305.9	82 100.8	76 691.4
NB	0	0	1	27

表3 HBICA与3种有效算法的对比结果

问题规模	IWOA	HGA	TS	HBICA
问题规模	AVG	AVG	AVG	AVG
20×4	14 268.2	14 414.9	14 354.4	14 199.9
25×4	13 961.2	13 862.3	14 080.1	13 873.7
30×4	26 025.5	25 769.6	25 820.0	25 596.4
35×5	31 076.8	30 842.0	30 187.0	30 053.6
40×5	30 139.5	29 559.6	28 858.1	28 684.1
45×5	39 016.5	37 960.4	36 910.6	36 964.1
50×5	34 448.4	33 998.9	33 250.6	33 051.3
55×5	43 948.9	42 758.1	41 259.7	40 734.6
60×5	38 744.0	38 069.4	36 709.2	36 048.2
70×6	54 328.0	52 822.6	50 091.9	49 980.1
75×6	55 981.9	55 393.9	51 828.6	51 461.8
80×6	65 762.8	64 385.1	60 943.9	61 159.9
85×6	71 195.4	69 467.9	66 918.4	65 691.7
90×6	80 101.6	77 252.1	73 970.9	74 158.8
95×6	89 302.6	87 123.2	83 528.2	82 419.5
100×7	99 500.5	99 212.0	97 535.8	95 075.9
110×7	103 555.3	100 595.5	96 217.9	94 401.1
120×7	103 871.5	101 820.3	96 041.8	92 399.4
130×8	111 969.6	110 147.8	105 902.3	104 564.7
140×8	125 733.7	123 363.5	118 681.5	117 835.0
150×8	142 677.4	137 137.8	132 839.5	129 909.8
160×9	138 169.1	131 364.5	126 731.4	123 245.0
170×9	153 361.2	143 737.1	143 447.1	135 854.0
180×9	158 705.4	150 812.5	145 711.6	141 274.3
160×10	137 840.0	132 938.2	128 748.5	125 496.7
170×10	149 058.4	146 947.9	142 150.4	139 855.0
180×10	141 476.2	134 507.9	131 902.1	126 678.4
Average	83 489.6	80 972.8	78 319.3	76 691.4
NB	0	1	3	24

参考文献 23

1	GHARAEIA, JOLAIF. A multi-agent approach to the integrated production scheduling and distribution problem in multi-factory supply chain[J]. Applied Soft Computing, 2018, 65: 577-589.
2	MOONSS, RAMAEKERSK, CARISA, et al. Integrating production scheduling and vehicle routing decisions at the operational decision level: A review and discussion[J]. Computers & Industrial Engineering, 2017, 104: 224-245.
3	ZHENL, MAC L, WANGK, et al. Multi-depot multi-trip vehicle routing problem with time windows and release dates[J]. Transportation Research Part E: Logistics and Transportation Review, 2020, 135: 101866.
4	WANGY, LEIL F, ZHANGD X, et al. Towards delivery-as-a-service: Effective neighborhood search strategies for integrated delivery optimization of E-commerce and static O2O parcels[J]. Transportation Research Part B: Methodological, 2020, 139: 38-63.
5	WASSANN, WASSANN, NAGYG, et al. The multiple trip vehicle routing problem with backhauls: Formulation and a two-level variable neighbourhood search[J]. Computers & Operations Research, 2017, 78: 454-467.
6	LEEJ, KIMB I, JOHNSONA L, et al. The nuclear medicine production and delivery problem[J]. European Journal of Operational Research, 2014, 236(2): 461-472.
7	WANGJ, YAOS, SHENGJ C, et al. Minimizing total carbon emissions in an integrated machine scheduling and vehicle routing problem[J]. Journal of Cleaner Production, 2019, 229: 1004-1017.
8	GANJIM, KAZEMIPOORH, HADJI MOLANAS M, et al. A green multi-objective integrated scheduling of production and distribution with heterogeneous fleet vehicle routing and time windows[J]. Journal of Cleaner Production, 2020, 259: 120824.
9	ABDOLLAHZADEHV, NAKHAIKAMALABADII, HAJIMOLANAS M, et al. A multifactory integrated production and distribution scheduling problem with parallel machines and immediate shipments solved by improved whale optimization algorithm[J]. Complexity, 2018, 2018: 5120640.
10	詹文法, 邵志伟. 一种集成电路测试流程分级动态调整方法[J]. 电子学报, 2020, 48(8): 1623-1630.
	ZHANW F, SHAOZ W. Hierarchical dynamic adjustment method for integrated circuit testing process[J]. Acta Electronica Sinica, 2020, 48(8): 1623-1630. (in Chinese)
11	何小娟, 曾建潮. 基于Bayesian统计推理的分布估计算法求解柔性作业车间调度问题[J]. 系统工程理论与实践, 2012, 32(2): 380-388.
	HEX J, ZENGJ C. Solving flexible job-shop scheduling problems with Bayesian statistical inference-based estimation of distribution algorithm[J]. Systems Engineering-Theory & Practice, 2012, 32(2): 380-388. (in Chinese)
12	姚友杰, 钱斌, 董钰明, 等. 基于EDA的绿色零等待作业车间调度问题求解[J]. 电子学报, 2021, 49(2): 225-232.
	YAOY J, QIANB, DONGY M, et al. EDA-based for the green no-wait job shop scheduling problem[J]. Acta Electronica Sinica, 2021, 49(2): 225-232. (in Chinese)
13	CHENS F, QIANB, LIUB, et al. Bayesian Statistical Inference-Based Estimation of Distribution Algorithm for the re-Entrant Job-Shop Scheduling Problem with Sequence-Dependent Setup Times[M]//Intelligent Computing Methodologies. Cham: Springer International Publishing, 2014: 686-696.
14	杨晓林, 胡蓉, 钱斌, 等. 增强分布估计算法求解低碳分布式流水线调度[J]. 控制理论与应用, 2019, 36(5): 803-815.
	YANGX L, HUR, QIANB, et al. Enhanced estimation of distribution algorithm for low carbon scheduling of distributed flow shop problem[J]. Control Theory & Applications, 2019, 36(5): 803-815. (in Chinese)
15	PÉREZ-RODRÍGUEZR, HERNÁNDEZ-AGUIRREA. Simulation optimization for the vehicle routing problem with time windows using a Bayesian network as a probability model[J].The International Journal of Advanced Manufacturing Technology, 2016, 85(9/10/11/12): 2505-2523.
16	李明, 雷德明. 基于新型帝国竞争算法的高维多目标柔性作业车间调度[J]. 控制理论与应用, 2019, 36(6): 893-901.
	LIM, LEID M. Novel imperialist competitive algorithm for many-objective flexible job shop scheduling[J]. Control Theory & Applications, 2019, 36(6): 893-901. (in Chinese)
17	LEID M, LIM, WANGL. A two-phase meta-heuristic for multiobjective flexible job shop scheduling problem with total energy consumption threshold[J]. IEEE Transactions on Cybernetics, 2019, 49(3): 1097-1109.
18	ARDALANZ, KARIMIS, POURSABZIO, et al. A novel imperialist competitive algorithm for generalized traveling salesman problems[J]. Applied Soft Computing, 2015, 26: 546-555.
19	HOSSEINIS, KHALEDA AL. A survey on the imperialist competitive algorithm metaheuristic: Implementation in engineering domain and directions for future research[J]. Applied Soft Computing, 2014, 24: 1078-1094.
20	MARANDIF, FATEMI GHOMIS M T. Integrated multi-factory production and distribution scheduling applying vehicle routing approach[J]. International Journal of Production Research, 2019, 57(3): 722-748.
21	裴小兵, 于秀燕, 王尚磊. 混合帝国竞争算法求解旅行商问题[J]. 浙江大学学报(工学版), 2019, 53(10): 2003-2012.
	PEIX B, YUX Y, WANGS L. Solution of traveling salesman problem by hybrid imperialist competitive algorithm[J]. Journal of Zhejiang University(Engineering Science), 2019, 53(10): 2003-2012. (in Chinese)
22	QIANB, WANGL, HUANGD X, et al. An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers[J]. Computers & Operations Research, 2009, 36(1): 209-233.
23	MONTGOMERYD C. Design and Analysis of Experiments[M]. Hoboken: John Wiley and Sons, 2005.

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

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 23

相关文章 1

编辑推荐

Metrics