An adaptive differential evolution algorithm to solve the multi-compartment vehicle routing problem: A case of cold chain transportation problem
Submitted: 2023-06-22
|Accepted: 2024-01-26
|Published: 2024-01-31
Copyright (c) 2024 naratip supattananon, Supaporn Sankul, Raknoi Akararungruangkul
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Downloads
Keywords:
Adaptive differential evolution algorithm, cold chain transportation network, metaheuristics, multi-compartment vehicle routing problem
Supporting agencies:
Abstract:
This research paper introduces an adaptive differential evolution algorithm (ADE algorithm) designed to address the multi-compartment vehicle routing problem (MCVRP) for cold chain transportation of a case study of twentyeight customers in northeastern Thailand. The ADE algorithm aims to minimize the total cost, which includes both the expenses for traveling and using the vehicles. In general, this algorithm consists of four steps: (1) The first step is to generate the initial solution. (2) The second step is the mutation process. (3) The third step is the recombination process, and the final step is the selection process. To improve the original DE algorithm, the proposed algorithm increases the number of mutation equations from one to four. Comparing the outcomes of the proposed ADE algorithm with those of LINGO software and the original DE based on the numerical examples In the case of small-sized problems, both the proposed ADE algorithm and other methods produce identical results that align with the global optimal solution. Conversely, for larger-sized problems, it is demonstrated that the proposed ADE algorithm effectively solves the MCVRP in this case. The proposed ADE algorithm is more efficient than Lingo software and the original DE, respectively, in terms of total cost. The proposed ADE algorithm, adapted from the original, proves advantageous for solving MCVRPs with large datasets due to its simplicity and effectiveness. This research contributes to advancing cold chain logistics with a practical solution for optimizing routing in multi-compartment vehicles.
References:
Brest, J., Greiner, S., Boskovic, B., Mernik, M., & Zumer, V. (2006). Self-adapting control parameters in differential evolution: A comparative study on numerical benchmark problems. IEEE Transactions on evolutionary computation, 10(6), 646-657. https://doi.org/10.1109/TEVC.2006.872133
Chen, L., Liu, Y., & Langevin, A. (2019). A multi-compartment vehicle routing problem in cold-chain distribution. Computers & Operations Research, 111, 58-66. https://doi.org/10.1016/j.cor.2019.06.001
Chowmali, W., & Sukto, S. (2020). A novel two-phase approach for solving the multi-compartment vehicle routing problem with a heterogeneous fleet of vehicles: a case study on fuel delivery. Decision Science Letters, 9(1), 77-90. https://doi.org/10.5267/j.dsl.2019.7.003
Chowmali, W., & Sukto, S. (2021). A hybrid FJA-ALNS algorithm for solving the multi-compartment vehicle routing problem with a heterogeneous fleet of vehicles for the fuel delivery problem. Decision Science Letters, 10, 497-510. https://doi.org/10.5267/j.dsl.2021.6.001
Cui, L., Li, G., Lin, Q., Chen, J., & Lu, N. (2016). Adaptive differential evolution algorithm with novel mutation strategies in multiple sub-populations. Computers & Operations Research, 67, 155-173. https://doi.org/10.1016/j.cor.2015.09.006
Das, S., Abraham, A., Chakraborty, U. K., & Konar, A. (2009). Differential evolution using a neighborhood-based mutation operator. IEEE Transactions on evolutionary computation, 13(3), 526-553. https://doi.org/10.1109/TEVC.2008.2009457
Das, S., & Suganthan, P. N. (2011). Differential Evolution: A Survey of the State-of-the-Art. IEEE Transactions on evolutionary computation, 15(1), 4-31. https://doi.org/10.1109/TEVC.2010.2059031
Efthymiadis, S., Liapis, N., & Nenes, G. (2023). Solving a heterogeneous fleet multi-compartment vehicle routing problem:a case study. International Journal of Systems Science: Operations & Logistics, 10(1), 2190474. https://doi.org/10.1080/23302674.2023.2190474
Erbao, C., Mingyong, L., & Kai, N. (2008). A Differential Evolution & Genetic Algorithm for Vehicle Routing Problem with Simultaneous Delivery and Pick-up and Time Windows. IFAC Proceedings Volumes, 41(2), 10576-10581. https://doi.org/10.3182/20080706-5-KR-1001.01791
Eshtehadi, R., Demir, E., & Huang, Y. (2020). Solving the vehicle routing problem with multi-compartment vehicles for city logistics. Computers & Operations Research, 115, 104859. https://doi.org/10.1016/j.cor.2019.104859
Guo, N., Qian, B., Hu, R., Jin, H. P., & Xiang, F. H. (2020). A Hybrid Ant Colony Optimization Algorithm for Multi-Compartment Vehicle Routing Problem. Complexity, 2020, 8839526. https://doi.org/10.1155/2020/8839526
Guo, N., Qian, B., Na, J., Hu, R., & Mao, J.-L. (2022). A three-dimensional ant colony optimization algorithm for multi-compartment vehicle routing problem considering carbon emissions. Applied Soft Computing, 127, 109326. https://doi.org/10.1016/j.asoc.2022.109326
Henke, T., Speranza, M. G., & Wäscher, G. (2019). A branch-and-cut algorithm for the multi-compartment vehicle routing problem with flexible compartment sizes. Annals of Operations Research, 275(2), 321-338. https://doi.org/10.1007/s10479-018-2938-4
Heßler, K. (2021). Exact algorithms for the multi-compartment vehicle routing problem with flexible compartment sizes. European Journal of Operational Research, 294(1), 188-205. https://doi.org/10.1016/j.ejor.2021.01.037
Hübner, A., & Ostermeier, M. (2019). A Multi-Compartment Vehicle Routing Problem with Loading and Unloading Costs. Transportation Science, 53(1), 282-300. https://doi.org/10.1287/trsc.2017.0775
Kaabachi, I., Yahyaoui, H., Krichen, S., & Dekdouk, A. (2019). Measuring and evaluating hybrid metaheuristics for solving the multi-compartment vehicle routing problem. Measurement, 141, 407-419. https://doi.org/10.1016/j.measurement.2019.04.019
Kalatzantonakis, P., Sifaleras, A., & Samaras, N. (2023). A reinforcement learning-Variable neighborhood search method for the capacitated Vehicle Routing Problem. Expert Systems with Applications, 213, 118812. https://doi.org/10.1016/j.eswa.2022.118812
Kyriakakis, N. A., Sevastopoulos, I., Marinaki, M., & Marinakis, Y. (2022). A hybrid Tabu search - Variable neighborhood descent algorithm for the cumulative capacitated vehicle routing problem with time windows in humanitarian applications. Computers & Industrial Engineering, 164, 107868. https://doi.org/10.1016/j.cie.2021.107868
Li, K., Li, D., & Wu, D. (2022). Carbon Transaction-Based Location-Routing- Inventory Optimization for Cold Chain Logistics. Alexandria Engineering Journal, 61(10), 7979-7986. https://doi.org/10.1016/j.aej.2022.01.062
Mallipeddi, R., & Suganthan, P. N. (2010). Ensemble of constraint handling techniques. IEEE Transactions on evolutionary computation, 14(4), 561-579. https://doi.org/10.1109/TEVC.2009.2033582
Marinaki, M., Taxidou, A., & Marinakis, Y. (2023). A hybrid Dragonfly algorithm for the vehicle routing problem with stochastic demands. Intelligent Systems with Applications, 18, 200225. https://doi.org/10.1016/j.iswa.2023.200225
Mirzaei, S., & Wøhlk, S. (2019). A Branch-and-Price algorithm for two multi-compartment vehicle routing problems. EURO Journal on Transportation and Logistics, 8(1), 1-33. https://doi.org/10.1007/s13676-016-0096-x
Moonsri, K., Sethanan, K., & Worasan, K. (2022). A Novel Enhanced Differential Evolution Algorithm for Outbound Logistics of the Poultry Industry in Thailand. Journal of Open Innovation: Technology, Market, and Complexity, 8(1), 15. https://doi.org/10.3390/joitmc8010015
Neri, F., & Tirronen, V. (2010). Recent advances in differential evolution: a survey and experimental analysis. Artificial intelligence review, 33, 61-106. https://doi.org/10.1007/s10462-009-9137-2
Ostermeier, M., Henke, T., Hübner, A., & Wäscher, G. (2021). Multi-compartment vehicle routing problems: State-of-the-art, modeling framework and future directions. European Journal of Operational Research, 292(3), 799-817. https://doi.org/10.1016/j.ejor.2020.11.009
Pitakaso, R., Sethanan, K., & Jamrus, T. (2020). Hybrid PSO and ALNS algorithm for software and mobile application for transportation in ice manufacturing industry 3.5. Computers & Industrial Engineering, 144, 106461. https://doi.org/10.1016/j.cie.2020.106461
Punyakum, V., Sethanan, K., Nitisiri, K., Pitakaso, R., & Gen, M. (2022). Hybrid differential evolution and particle swarm optimization for Multi-visit and Multi-period workforce scheduling and routing problems. Computers and Electronics in Agriculture, 197, 106929. https://doi.org/10.1016/j.compag.2022.106929
Qin, A. K., & Suganthan, P. N. (2005). Self-adaptive differential evolution algorithm for numerical optimization. 2005 IEEE congress on evolutionary computation,
Qiu, F., Zhang, G., Chen, P.-K., Wang, C., Pan, Y., Sheng, X., & Kong, D. (2020). A Novel Multi-Objective Model for the Cold Chain Logistics Considering Multiple Effects. Sustainability, 12(19), 8068. https://doi.org/10.3390/su12198068
Rabbani, M., Tahaei, Z., Farrokhi-Asl, H., & Saravi, N. A. (2017, 10-13 Dec. 2017). Using meta-heuristic algorithms and hybrid of them to solve multi compartment Vehicle Routing Problem. 2017 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), https://doi.org/10.1109/IEEM.2017.8290047
Sethanan, K., & Jamrus, T. (2020). Hybrid differential evolution algorithm and genetic operator for multi-trip vehicle routing problem with backhauls and heterogeneous fleet in the beverage logistics industry. Computers & Industrial Engineering, 146, 106571. https://doi.org/10.1016/j.cie.2020.106571
Silvestrin, P. V., & Ritt, M. (2017). An iterated tabu search for the multi-compartment vehicle routing problem. Computers & Operations Research, 81, 192-202. https://doi.org/10.1016/j.cor.2016.12.023
Souza, I. P., Boeres, M. C. S., & Moraes, R. E. N. (2023). A robust algorithm based on Differential Evolution with local search for the Capacitated Vehicle Routing Problem. Swarm and Evolutionary Computation, 77, 101245. https://doi.org/10.1016/j.swevo.2023.101245
Storn, R., & Price, K. (1997). Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. Journal of global optimization, 11, 341-359. https://doi.org/10.1023/A:1008202821328
Tiwari, K. V., & Sharma, S. K. (2023). An optimization model for vehicle routing problem in last-mile delivery. Expert Systems with Applications, 222, 119789. https://doi.org/10.1016/j.eswa.2023.119789
Wichapa, N., & Khokhajaikiat, P. (2018). Solving a multi-objective location routing problem for infectious waste disposal using hybrid goal programming and hybrid genetic algorithm. International Journal of Industrial Engineering Computations, 9, 75-98. https://doi.org/10.5267/j.ijiec.2017.4.003
Xia, C., Sheng, Y., Jiang, Z.-Z., Tan, C., Huang, M., & He, Y. (2015). A Novel Discrete Differential Evolution Algorithm for the Vehicle Routing Problem in B2C E-Commerce. International Journal of Bifurcation and Chaos, 25(14), 1540033. https://doi.org/10.1142/S0218127415400337
Yahyaoui, H., Kaabachi, I., Krichen, S., & Dekdouk, A. (2020). Two metaheuristic approaches for solving the multi-compartment vehicle routing problem. Operational Research, 20(4), 2085-2108. https://doi.org/10.1007/s12351-018-0403-4
Zhang, J., & Sanderson, A. C. (2009). JADE: adaptive differential evolution with optional external archive. IEEE Transactions on evolutionary computation, 13(5), 945-958. https://doi.org/10.1109/TEVC.2009.2014613
Zhang, Y., Hua, G., Cheng, T. C. E., & Zhang, J. (2020). Cold chain distribution: How to deal with node and arc time windows? Annals of Operations Research, 291(1), 1127-1151. https://doi.org/10.1007/s10479-018-3071-0
Zhu, S., Fu, H., & Li, Y. (2021). Optimization Research on Vehicle Routing for Fresh Agricultural Products Based on the Investment of Freshness-Keeping Cost in the Distribution Process. Sustainability, 13(14), 8110. https://doi.org/10.3390/su13148110
