面向多车场冷链物流配送的改进正余弦算法

doi:10.3778/j.issn.1002-8331.2302-0012

摘要/Abstract

摘要： 以冷链物流为对象，研究了一类考虑多中心联合配送和硬时间窗约束的调度问题。基于问题描述建立了以最小化总成本为目标的数学模型。提出了改进正余弦算法（enhanced sine-cosine algorithm，ESCA）以获取当前问题的满意解。结合问题特征创建了融合构造式规则的编解码方法，并辅以个体评估方法实现模型与正余弦算法（sine-cosine algorithm，SCA）的适配。同时，将反向学习机制嵌入ESCA的初始化流程，旨在提升初始解的性能。在种群进化方面，构建了融合双种群机制、非线性参数调节和随机扰动的混合进化机制以平衡寻优过程的全局探索和局部挖掘行为，并通过离散邻域搜索方法避免搜索停滞。开展了案例研究和算法对比实验，结果验证了ESCA算法的良好性能。

关键词: 优化, 调度, 正余弦算法, 混合, 邻域搜索

Abstract: This work deals with a multiple-depot cold chain logistics distribution optimization problem with considerations of hard time windows. Firstly, the problem domain is presented and the programming model is formulated to minimize the total cost. Then, an algorithm named ESCA is developed for solution methodology. By virtue of the problem nature, a novel constructive encoding and decoding method, as well as an evaluation function, are designed to adjust SCA to the considered problem. Meanwhile, the opposition-based learning method is embedded into SCA to improve performance of initial solutions. To balance exploration and exploitation abilities, a hybrid individual update method is designed by combing the multi-population mechanism, the non-linear transition and the random perturbation. In addition, a discrete neighbor search method is used to avoid search stagnation. Finally, experiments on the case study and the algorithm comparison analysis are concocted to validate the efficiency of ESCA.

Key words: optimization, scheduling, sine-cosine algorithm, hybridizations, neighbor search

路世昌, 刘丹阳. 面向多车场冷链物流配送的改进正余弦算法[J]. 计算机工程与应用, 2024, 60(9): 326-337.

LU Shichang, LIU Danyang. Enhanced Sine-Cosine Algorithm for Multiple-Depot Cold Chain Logistics Distribution Optimization[J]. Computer Engineering and Applications, 2024, 60(9): 326-337.

参考文献

[1] 孙宝凤, 刘娇娇, 姚天姿, 等. 考虑能量消耗的纯电动物流车柔性时间窗路径规划问题[J]. 吉林大学学报 (工学版), 2023, 53(4): 1047-1059.
SUN B F, LIU J J, YAO T Z, et al. Electric delivery vehicle routing problem with flexible time window integrated with energy consumption estimation[J] Journal of Jilin University (Engineering and Technology Edition), 2023, 53(4): 1047-1059.
[2] CHAUDHURI A, DUKOVSKA-POPOVSKA I, SUBRAMANIAN N, et al. Decision-making in cold chain logistics using data analytics: a literature review[J]. The International Journal of Logistics Management, 2018, 39(3): 839-861.
[3] BRAEKERS K, RAMAEKERS K, VAN NIEUWENHUYSE I. The vehicle routing problem: state of the art classification and review[J]. Computers & Industrial Engineering, 2016, 99: 300-313.
[4] KONSTANTAKOPOULOS G D, GAYIALIS S P, KECHAGIAS E P. Vehicle routing problem and related algorithms for logistics distribution: a literature review and classification[J]. Operational Research, 2020, 22: 2033-2062.
[5] DENG F, QIN H, LI J, et al. The pickup and delivery problem with time windows and incompatibility constraints in cold chain transportation[J]. Transportation Science, 2022, 57(2): 444-462.
[6] 宋强. 改进迭代局部搜索算法在 MMTVRP 中的应用[J]. 计算机工程与应用, 2017, 53(7): 248-255.
SONG Q. Application of improved iterated local search algorithm in MMTVRP[J]. Computer Engineering and Applications, 2017, 53(7): 248-255.
[7] ZHANG L Y, TSENG M L, WANG C H, et al. Low-carbon cold chain logistics using ribonucleic acid-ant colony optimization algorithm[J]. Journal of Cleaner Production, 2019, 233: 169-180.
[8] DOU S, LIU G, YANG Y. A new hybrid algorithm for cold chain logistics distribution center location problem[J]. IEEE Access, 2020, 8: 88769-88776.
[9] ZHANG D, CAI S, YE F, et al. A hybrid algorithm for a vehicle routing problem with realistic constraints[J]. Information Sciences, 2017, 394: 167-182.
[10] MIRJALILI S. SCA: a sine cosine algorithm for solving optimization problems[J]. Knowledge-Based Systems, 2016, 96: 120-133.
[11] KHRISSI L, EL AKKAD N, SATORI H, et al. Clustering method and sine cosine algorithm for image segmentation[J]. Evolutionary Intelligence, 2022, 15: 669-682.
[12] VALI M, SALIMIFARD K, GANDOMI A H, et al. Application of job shop scheduling approach in green patient flow optimization using a hybrid swarm intelligence[J]. Computers & Industrial Engineering, 2022, 172: 108603.
[13] 马莹莹, 杜暖男. 基于改进正余弦算法的机器人路径规划[J]. 重庆交通大学学报 (自然科学版), 2021, 40(9): 17-23.
MA Y Y, DU N N. Robot path planning based on the improved sine cosine algorithm[J]. Journal of Chongqing Jiaotong University (Natural Science), 2021, 40(9): 17-23.
[14] ADAM S P, ALEXANDROPOULOS S A N, PARDALOS P M, et al. No free lunch theorem: a review[M]//Approximation and optimization: algorithms, complexity and applications. [S.l.]: Springer, 2019: 57-82.
[15] GHAREHCHOPOGH F S, SHAYANFAR H, GHOLIZADEH H. A comprehensive survey on symbiotic organisms search algorithms[J]. Artificial Intelligence Review, 2020, 53: 2265-2312.
[16] 王永琦, 吴飞, 江潇潇, 等. 求解并行机拖期与能耗成本优化调度的混合教-学算法[J]. 计算机应用研究, 2019, 36(3): 673-676.
WANG Y Q, WU F, JIANG X X, et al. Hybrid teaching-learning-based optimization algorithm for optimizing tardiness and energy cost on parallel machine scheduling[J]. Application Research of Computers, 2019, 36(3): 673-676.
[17] 王永琦, 吴飞, 孙建华. 求解连续空间优化问题的改进蜂群算法[J]. 计算机应用研究, 2018, 35(3): 658-660.
WANG Y Q, WU F, SUN J H. Modified artificial bee colony algorithm for solving continuous space optimization problems[J]. Application Research of Computers, 2018, 35(3): 658-660.
[18] LIN A, WU Q, HEIDARI A A, et al. Predicting intentions of students for master programs using a chaos-induced sine cosine-based fuzzy K-nearest neighbor classifier[J]. IEEE Access, 2019, 7: 67235-67248.
[19] 宋强. 求解异构并行机调度问题的混合多目标教-学优化算法[J]. 控制理论与应用, 2020, 37(10): 2242-2256.
SONG Q. A hybrid multi-objective teaching-learning-based optimization algorithm for unrelated parallel machine schedu-
ling problem[J]. Control Theory & Applications, 2020, 37(10): 2242-2256.
[20] ?LHAN ?. An improved simulated annealing algorithm with crossover operator for capacitated vehicle routing problem[J]. Swarm and Evolutionary Computation, 2021, 64: 100911.
[21] 殷旅江, 高亮, 李登桥, 等. 改进元胞遗传算法的转塔式贴片机贴装优化[J]. 华中科技大学学报 (自然科学版), 2015, 43(3): 113-117.
YIN L J, GAO L, LI D Q, et al. Component placement optimization for turret mounting machine based on improved cellular genetic algorithm[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2015, 43(3): 113-117.
[22] JEON G, LEEP H R, SHIM J Y. A vehicle routing problem solved by using a hybrid genetic algorithm[J]. Computers & Industrial Engineering, 2007, 53(4): 680-692.
[23] YANG W, KE L. An improved fireworks algorithm for the capacitated vehicle routing problem[J]. Frontiers of Computer Science, 2019, 13: 552-564.
[24] MOUTHUY S, MASSEN F, DEVILLE Y, et al. A multistage very large-scale neighborhood search for the vehicle routing problem with soft time windows[J]. Transportation Science, 2015, 49(2): 223-238.
[25] KHODABANDEH E, BAI L, HERAGU S S, et al. Modelling and solution of a large-scale vehicle routing problem at GE appliances & lighting[J]. International Journal of Production Research, 2017, 55(4): 1100-1116.