An iterated local search method for determining routes in the transport of raw materials and agri-food processing products

• Autorzy: Misztal Wojciech

Identyfikatory

DOI

10.2478/agriceng-2025-0011

Warianty tytułu

PL

Metoda iteracyjnego lokalnego przeszukiwania do wyznaczania tras w transporcie surowców oraz produktów przetwórstwa rolno-spożywczego

• Języki publikacji: EN

Abstrakty

EN

To acquire raw materials and distribute products, agri-food processing companies need to operate at long distances, which is associated with high energy costs and an increased negative impact on the natural environment. Many methods have been developed to reduce energy consumption in transport. One approach that stands out is optimization of transport routes, which provides benefits while incurring hardly any extra costs. In this paper, an attempt was made to modify the ILS-RVND metaheuristic by adjusting its components to the specific character of the problem being solved so that they could yield the expected results with regard to the quality of returned solutions and the time in which they were generated. A group of local search algorithms, Swap (2-1), Cross-exchange (2-1), 3-opt, Or-opt (2) and Displacement, were analyzed. The results of this analysis were used to formulate the final version of the metaheuristic. The efficiency of the algorithm was evaluated using test cases. The solutions generated by the metaheuristic produced considerable improvement in the objective function (70.99% on average) and were obtained within an acceptable time (on average 24.66 CPU seconds).

PL

Pozyskiwanie surowców i dystrybucja produktów wymaga od przedsiębiorstw przetwórstwa rolno-spożywczego pokonywania znacznych odległości, co wiąże się z wysokimi wydatkami energetycznymi oraz zwiększonym negatywnym oddziaływaniem na środowisko. Opracowano wiele metod mających na celu ograniczenie zużycia energii w transporcie. Jednym z wyróżniających się podejść jest optymalizacja tras przejazdów, która zapewnia znaczne korzyści przy ograniczonych nakładach. W pracy podjęto próbę modyfikacji metaheurystyki ILS-RVND poprzez dostosowanie jej elementów do specyfiki rozpatrywanego problemu w celu osiągnięcia poprawy jakości zwracanych rozwiązań oraz skrócenia czasu ich generowania. Przeanalizowano grupę algorytmów przeszukiwania lokalnego: Swap (2-1), Cross-exchange (2-1), 3-opt, Or-opt (2) oraz Displacement. Wyniki wykorzystano do określenia ostatecznej postaci metaheurystyki. Efektywność algorytmu oceniano przy użyciu przypadków testowych. Rozwiązania generowane przez metaheurystykę przynosiły znaczną poprawę funkcji celu (średnio 70,99%) i były otrzymywane w akceptowalnym czasie (średnio 24,66 sekundy CPU).

Słowa kluczowe

EN

transport; optimization; iterated local search; heterogeneous vehicle routing problem

PL

transport; optymalizacja; iteracyjne lokalne przeszukiwanie; problem wyznaczania tras; heterogeniczna flota pojazdów

• Wydawca: Polskie Towarzystwo Inżynierii Rolniczej
• Czasopismo: Agricultural Engineering
• Rocznik: 2025
• Tom: Vol. 29, No. 1
• Strony: 187--200
• Opis fizyczny: Bibliogr. 25 poz., tab., wykr.

Twórcy

autor

Misztal Wojciech

• Department of Agricultural, Forestry and Transport Machines,University of Life Sciences in Lublin, 28 Gleboka Street, 20-612 Lublin, Poland

• https://orcid.org/0000-0001-6214-506X

Bibliografia

• Absi, N., Cattaruzza, D., Feillet, D., Ogier, M., & Semet, F. (2020). A heuristic branch-cut-and-price algorithm for the ROADEF/EURO challenge on Inventory Routing. Transportation Science, 54(2), 313-329. https://doi.org/10.1287/trsc.2019.0961.
• Alonso-Pecina, F., Hérnandez-Báez, I. Y., López-Díaz, R. E., & Cruz-Rosales, M. H. (2024). Iterated Local Search Approach to a Single-Product, Multiple-Source, Inventory-Routing Problem. Mathematics, 12(7), 991. https://doi.org/10.3390/math12070991.
• Alvarez, A., & Munari, P. (2017). An exact hybrid method for the vehicle routing problem with time windows and multiple deliverymen. Computers & Operations Research, 83, 1-12. https://doi.org/10.1016/j.cor.2017.02.001.
• Amador-Fontalvo, J. E., Paternina-Arboleda, C. D., & Montoya-Torres, J. R. (2014). Solving the heterogeneous vehicle routing problem with time windows and multiple products via a bacterial metaheuristic. International Journal of Advanced Operations Management, 6(1), 81-100. https://doi.org/10.1504/IJAOM.2014.059622.
• Baran, J. (2018). Supply chain management in agri-food processing enterprises. Journal of Modern Science, 4, 39 (4), 217-230. https://doi.org/10.13166/jms/103641.
• Cerchione, R., Singh, R., Centobelli, P., & Shabani, A. (2018). Food cold chain management: From a structured literature review to a conceptual framework and research agenda. The International Journal of Logistics Management, 29(3), 792-821. https://doi.org/10.1108/IJLM-01-2017-0007.
• Chaudhuri, A., Dukovska-Popovska, I., Subramanian, N., Chan, H. K., & Bai, R. (2018). Decisionmaking in cold chain logistics using data analytics: a literature review. The International Journal of Logistics Management, 29(3), 839-861. https://doi.org/10.1108/IJLM-03-2017-0059.
• Dzieniszewski, G., Kuboń, M., Pristavka, M., & Findura, P. (2021). Operating parameters and environmental indicators of diesel engines fed with crop-based fuels. Agricultural Engineering, 25(1), 13- 28. https://doi.org/10.2478/agriceng-2021-0002.
• Kampf, R. (2018). Optimization of delivery routes using the Little´ s algorithm. NAŠE MORE: znanstveni časopis za more i pomorstvo, 65(4 Special issue), 237-239. https://doi.org/10.17818/ NM/2018/4SI.13.
• Kara, B. Y., Sabuncuoglu, I., & Bidanda, B. (Eds.). (2014). Global logistics management. CRC Press. https://doi.org/10.1201/b17845.
• Labadie, N., Prins, C., & Prodhon, C. (2016). Metaheuristics for vehicle routing problems. John Wiley & Sons. https://doi.org/10.1002/9781119136767.
• Lai, D. S., Demirag, O. C., & Leung, J. M. (2016). A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph. Transportation Research Part E: Logistics and Transportation Review, 86, 32-52. https://doi.org/10.1016/j.tre.2015.12.001.
• Lairenlakpam, R., Thakre, G. D., Gupta, P., Singh, Y., & Kumar, P. (2017). Effect of different drive modes on energy consumption of an electric auto rickshaw. In 2017 IEEE Transportation Electrification Conference (ITEC-India) (pp. 1-5). IEEE. https://doi.org/10.1109/ITEC-India.2017.8333832.
• Lapinskaitė, I., & Kuckailytė, J. (2014). The impact of supply chain cost on the price of the final product. Business, Management and Education, 12(1), 109-126. https://doi.org/10.3846/bme.2014.08.
• Liao, W., Liu, L., & Fu, J. (2019). A comparative study on the routing problem of electric and fuel vehicles considering carbon trading. International Journal of Environmental Research and Public Health, 16(17), 3120. https://doi.org/10.3390/ijerph16173120.
• Panggabean, E. M., Mawengkang, H., Azis, Z., & Sari, R. F. (2018). Periodic heterogeneous vehicle routing problem with driver scheduling. In IOP Conference Series: Materials Science and Engineering (Vol. 300, No. 1, p. 012017). IOP Publishing. https://doi.org/10.1088/1757-899X/300 /1/012017.
• Penna, P. H. V., Subramanian, A., & Ochi, L. S. (2013). An iterated local search heuristic for the heterogeneous fleet vehicle routing problem. Journal of Heuristics, 19(2), 201-232. https://doi.org/10.1007/s10732-011-9186-y.
• Plizga, K. (2021). Analysis of Energy Consumption by Electric Agricultural Tractor Model Under Operating Conditions. Agricultural Engineering, 25, 1-12. https://doi.org/10.2478/agriceng-2021-000.
• Pop, P. C., Fuksz, L., & Marc, A. H. (2014, June). A variable neighborhood search approach for solving the generalized vehicle routing problem. In International Conference on Hybrid Artificial Intelligence Systems (pp. 13-24). Cham: Springer International Publishing. https://doi.org/10.1007/978- 3-319-07617-1_2.
• Przywara, A., Koszel, M., Krawczuk, A., & Sotirios Anifantis, A. (2022). The Analysis of the New Farm Tractors Market in Poland in 2010-2020 in the Context of Income Generated by Farmers’ Households. Agricultural Engineering, 26, 65-79. https://doi.org/10.2478/agriceng-2022-0006.
• Rojas-Cuevas, I. D., Caballero-Morales, S. O., Martinez-Flores, J. L., & Mendoza-Vazquez, J. R. (2018). Capacitated vehicle routing problem model for carriers. Journal of Transport and Supply Chain Management, 12(1), 1-9. https://doi.org/10.4102/jtscm.v12i0.345.
• Silva, M. M., Subramanian, A., & Ochi, L. S. (2015). An iterated local search heuristic for the split delivery vehicle routing problem. Computers & Operations Research, 53, 234-249. https://doi.org/10.1016/j.cor.2014.08.005.
• Stopka, O., Stopkova, M., & Kampf, R. (2019). Application of the operational research method to determine the optimum transport collection cycle of municipal waste in a predesignated urban area. Sustainability, 11(8), 2275. https://doi.org/10.3390/su11082275.
• Toth, P. (2002). The vehicle routing problem. SIAM Monographs on Discrete Mathematics and Applications. https://doi.org/10.1137/1.9780898718515.
• Zhou, A. H., Zhu, L. P., Hu, B., Deng, S., Song, Y., Qiu, H., & Pan, S. (2018). Traveling-salesmanproblem algorithm based on simulated annealing and gene-expression programming. Information, 10(1), 7. https://doi.org/10.3390/info10010007.