|
|
基于并行进化框架的多场景带容量的车辆路径优化算法研究
|
Abstract:
多场景优化问题涉及需要同时优化的多个场景，每个场景都具有特定条件和多个待优化目标。其目标在于寻找一组公共折衷最优解(PCOS)：这些解在所有场景中均可行，且能达成折中的优化效果。带容量约束的多场景车辆路径问题(MSCVRP)考虑了现实配送中的不确定扰动，目前针对该问题研究较少。本文提出一种基于并行进化框架的多场景带容量车辆路径优化算法(PEF-MSOA)。通过利用各场景的knee点和约束极值线构建不同场景间解的转移策略，实现不同场景间的有效信息传递。此外，设计自适应算子选择策略以提升PCOS解集的质量。对比实验中验证了所提算法的有效性与优越性。
Multi-scenario optimization problems involve multiple scenarios that need to be optimized simultaneously, each with specific conditions and multiple objectives to optimize. The goal is to find a set of public compromised optimal solutions (PCOS): feasible in all scenarios and achieving a balanced optimization effect. The multi-scenario capacitated vehicle routing problem (MSCVRP) considers uncertainty disturbances in real-world delivery, with few effective measures for this problem in existing research. In this paper, a multi-scenario capacitated vehicle routing optimization algorithm based on the parallel evolution framework is proposed. The knee solutions and extremal line of each scenario are used to construct a solution transfer strategy, thus achieving information transfer between different scenarios. Besides, an adaptive operator selection strategy is designed to improve the quality of PCOS. The effectiveness and superiority of the proposed algorithm are verified through comparative experiments.
| [1] | Herrero, J.G., Berlanga, A. and Lopez, J.M.M. (2009) Effective Evolutionary Algorithms for Many-Specifications Attainment: Application to Air Traffic Control Tracking Filters. IEEE Transactions on Evolutionary Computation, 13, 151-168. https://doi.org/10.1109/tevc.2008.920677 |
| [2] | Ishibuchi, H. and Murata, T. (1998) A Multi-Objective Genetic Local Search Algorithm and Its Application to Flowshop Scheduling. IEEE Transactions on Systems, Man and Cybernetics, Part C (Applications and Reviews), 28, 392-403. https://doi.org/10.1109/5326.704576 |
| [3] | Yeung, S.H., Man, K.F., Luk, K.M. and Chan, C.H. (2008) A Trapeizform U-Slot Folded Patch Feed Antenna Design Optimized with Jumping Genes Evolutionary Algorithm. IEEE Transactions on Antennas and Propagation, 56, 571-577. https://doi.org/10.1109/tap.2007.915473 |
| [4] | Handl, J., Kell, D.B. and Knowles, J. (2007) Multiobjective Optimization in Bioinformatics and Computational Biology. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 4, 279-292. https://doi.org/10.1109/tcbb.2007.070203 |
| [5] | Dantzig, G.B. and Ramser, J.H. (1959) The Truck Dispatching Problem. Management Science, 6, 80-91. https://doi.org/10.1287/mnsc.6.1.80 |
| [6] | Fadel, G., et al. (2005) Multi-Criteria Multi-Scenario Approaches in the Design of Vehicles. 6th World Congresses of Structural and Multidisciplinary Optimization, Rio de Janeiro, 30 May-3 June 2005. |
| [7] | Deb, K., Zhu, L. and Kulkarni, S. (2018) Handling Multiple Scenarios in Evolutionary Multiobjective Numerical Optimization. IEEE Transactions on Evolutionary Computation, 22, 920-933. https://doi.org/10.1109/tevc.2017.2776921 |
| [8] | Zhu, L., Deb, K. and Kulkarni, S. (2014) Multi-Scenario Optimization Using Multi-Criterion Methods: A Case Study on Byzantine Agreement Problem. 2014 IEEE Congress on Evolutionary Computation (CEC), Beijing, 6-11 July 2014, 2601-2608. https://doi.org/10.1109/cec.2014.6900637 |
| [9] | Deb, K., Zhu, L. and Kulkarni, S. (2015) Multi-Scenario, Multi-Objective Optimization Using Evolutionary Algorithms: Initial Results. 2015 IEEE Congress on Evolutionary Computation (CEC), Sendai, 25-28 May 2015, 1877-1884. https://doi.org/10.1109/cec.2015.7257115 |
| [10] | Wiecek, M.M., Singh, V. and Blouin, V. (2007) Multi-Scenario Multi-Criteria Optimization in Engineering Design. Defense Technical Information Center. |
| [11] | Wiecek, M.M., Blouin, V.Y., Fadel, G.M., Engau, A., Hunt, B.J. and Singh, V. (2009) Multi-Scenario Multi-Objective Optimization with Applications in Engineering Design. In: Barichard, V., et al., Eds., Multiobjective Programming and Goal Programming: Theoretical Results and Practical Applications, Springer, 283-298. https://doi.org/10.1007/978-3-540-85646-7_26 |
| [12] | Zhang, X., Tian, Y. and Jin, Y. (2015) A Knee Point-Driven Evolutionary Algorithm for Many-Objective Optimization. IEEE Transactions on Evolutionary Computation, 19, 761-776. https://doi.org/10.1109/tevc.2014.2378512 |
| [13] | Amri Sakhri, M.S. (2021) Comparative Analysis of Different Crossover Structures for Solving a Periodic Inventory Routing Problem. International Journal of Data Science and Analytics, 14, 141-153. https://doi.org/10.1007/s41060-021-00280-2 |
| [14] | Zitzler, E. and Thiele, L. (1999) Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach. IEEE Transactions on Evolutionary Computation, 3, 257-271. https://doi.org/10.1109/4235.797969 |
| [15] | Schott, J.R. (1995) Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization. Master’s Thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology. |
| [16] | Tian, Y., Cheng, R., Zhang, X. and Jin, Y. (2017) Platemo: A MATLAB Platform for Evolutionary Multi-Objective Optimization [Educational Forum]. IEEE Computational Intelligence Magazine, 12, 73-87. https://doi.org/10.1109/mci.2017.2742868 |
