An adaptive differential evolution algorithm to solve the multi-compartment vehicle routing problem: A case of cold chain transportation problem

Authors

DOI:

https://doi.org/10.4995/ijpme.2024.19928

Keywords:

Adaptive differential evolution algorithm, cold chain transportation network, metaheuristics, multi-compartment vehicle routing problem

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.

Downloads

Download data is not yet available.

Author Biographies

Supaporn Sankul, Khonkaen University

Department of Industrial Engineering, Faculty of Engineering

Naratip Supattananon, Rajamangala University of Technology Isan

Department of Welding Technical Education, Faculty of Technical Education

Raknoi Akararungruangkul, Khonkaen University

Department of Industrial Engineering, Faculty of Engineering

Narong Wichapa, Kalasin University

Department of Industrial Engineering, Faculty of Engineering and Industrial Technology

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

Downloads

Published

2024-01-31

How to Cite

Sankul, S., Supattananon, N., Akararungruangkul, R., & Wichapa, N. (2024). An adaptive differential evolution algorithm to solve the multi-compartment vehicle routing problem: A case of cold chain transportation problem. International Journal of Production Management and Engineering, 12(1), 91–104. https://doi.org/10.4995/ijpme.2024.19928

Issue

Section

Papers