The Impact of perturbation mechanisms on the operation of the swap heuristic

• Autorzy: Misztal Wojciech

Identyfikatory

DOI

10.14669/AM.VOL86.ART2

• Języki publikacji: EN

Abstrakty

EN

In this study, an attempt was made to assess the impact of the most popular perturbation movements (i.e. Multiple-Swap(2-2), Multiple-Shift(2-2) and Multiple-K-Shift(1)), as well as the number of their calls on the quality of solutions and the time in which Swap(2-1) heuristics returns them. For this purpose, the iterative local search algorithm (ILS) was triggered, in which Swap(2-1) heuristics has cooperated with a single perturbation mechanism. The number of perturbations was changed in the range from 1 to 30. Each time the time and the difference between the percentage improvement of the objective function value of the solution obtained utilizing the Swap(2-1) algorithm cooperating with the perturbation mechanism and this algorithm working alone was checked. Based on the results obtained, it was found that the overall level of improvement in the quality of the returned solution is similar when using all of the considered perturbation mechanisms (is in the range of 2.49% to 4.02%). It has been observed that increasing the number of initiated perturbations does not guarantee an improvement in the quality of the returned solution. Perturbation movements similar to the motion initiated by the local search algorithm do not significantly improve the solution (they only entail extending the duration of action). The structure of the study has the following form. The Introduction chapter provides information on the Vehicle Routing Problem. The chapter Research methods contain a description of ILS and Swap(2-1) approaches and perturbation mechanisms considered. The last two chapters include the results of tests and conclusions.

Słowa kluczowe

EN

optimization; vehicle routing problem; local search; Swap (2-1); perturbation mechanisms

• Wydawca: Wydawnictwo Naukowe Sieci Badawczej Łukasiewicz - Przemysłowego Instytutu Motoryzacji
• Czasopismo: Archiwum Motoryzacji
• Rocznik: 2019
• Tom: Vol. 86, nr 4
• Strony: 27--39
• Opis fizyczny: Bibliogr. 30 poz., rys., tab., wykr.

Twórcy

autor

Misztal Wojciech

• Department of Agricultural, Forestry and Transport Machines, University of Life Sciences in Lublin, 28 Głęboka Str., 20-612 Lublin, Polska

Bibliografia

• [1] Aghezzaf B., Fahim H.E.: Iterated local search algorithm for solving the orienteering problem with soft time windows. Springerplus. 2016, 5(1), 1781. DOI:10.1186/s40064-016-3440-6.
• [2] Alvarez A., Munari P.: An exact hybrid method for the vehicle routing problem with time windows and multiple deliverymen. Computers & Operations Research. 2017, 83, 1-12. DOI:10.1016/j.cor.2017.02.001.
• [3] Arnold F., Sörensen K.: Knowledge-guided local search for the vehicle routing problem. Computers & Operations Research. 2019, 105, 32-46. DOI:10.1016/j.cor.2019.01.002.
• [4] Bräysy O., Gendreau M.: Vehicle Routing Problem with Time Windows, Part II: Metaheuristics. Transportation Science. 2005, 39(1), 119-139. DOI:10.1287/trsc.1030.0057.
• [5] Cordeau J.F., Gendreau M., Hertz A., Laporte G., Sormany J.S.: New heuristics for the vehicle routing problem. In: Langevin A., Riopel D., eds.: Logistics Systems: Design and Optimization. New York: Springer-Verlag. 2005, 279-297. DOI:10.1007/0-387-24977-X_9.
• [6] Den B.M., Stützle T., Dorigo M.: Design of iterated local search algorithms. In: Boers EJW, ed. Applications of Evolutionary Computing. Vol 2037. Lecture notes in computer science. Berlin, Heidelberg: Springer Berlin Heidelberg. 2001, 441-451. DOI:10.1007/3-540-45365-2_46.
• [7] Eberle D.U., von Helmolt D.R.: Sustainable transportation based on electric vehicle concepts: a brief overview. Energy & Environmental Science. 2010, 3(6), 689. DOI:10.1039/c001674h.
• [8] El-Sherbeny N.A.: Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods. Journal of King Saud University - Science. 2010, 22(3), 123-131. DOI:10.1016/j.jksus.2010.03.002.
• [9] Feng Y.J., Zhu H.P., He F.: VRP Problem Research with Workshop Road Constraints Based on Tabu Search. Advanced Materials Research. 2014, 945-949, 3438-3443. DOI:10.4028/www.scientific.net/AMR.945-949.3438.
• [10] Galos J., Sutcliffe M., Cebon D., Piecyk M., Greening P.: Reducing the energy consumption of heavy goods vehicles through the application of lightweight trailers: Fleet case studies. Transportation Research Part D: Transport and Environment. 2015, 41, 40-49. DOI:10.1016/j.trd.2015.09.010.
• [11] Geroliminis N., Haddad J.: Quantitative methods in transportation systems. EURO Journal on Transportation and Logistics. 2014, 3(3-4), 177-178. DOI:10.1007/s13676-014-0044-6.
• [12] Golden B., Raghavan S., Wasil E., eds.: The Vehicle Routing Problem: Latest Advances and New Challenges. Boston, MA: Springer US. 2008. DOI:10.1007/978-0-387-77778-8.
• [13] Imran A., Salhi S., Wassan N.A.: A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem. European Journal of Operational Research. 2009, 197(2), 509-518, DOI:10.1016/j.ejor.2008.07.022.
• [14] Irnich S., Toth P., Vigo D.: Chapter 1: the family of vehicle routing problems. In: Toth P., Vigo D., eds.: Vehicle Routing: Problems, Methods, and Applications, Second Edition. Philadelphia, PA: Society for Industrial and Applied Mathematics. 2014, 1-33. DOI:10.1137/1.9781611973594.ch1.
• [15] Liong C.Y., Wan R.I., Omar K., Mourad Z.: Vehicle routing problem: Models and solutions. Journal of Quality Measurement and Analysis. 2008, 4(1), 205-218.
• [16] Lourenço H.R., Martin O.C., Stützle T.: Iterated Local Search. In: Glover F., Kochenberger G.A., eds.: Handbook of Metaheuristics. Boston: Kluwer Academic Publishers. 2003, 320-353. DOI:10.1007/0-306-48056-5_11.
• [17] McNabb M.E., Weir J.D., Hill R.R., Hall S.N.: Testing local search move operators on the vehicle routing problem with split deliveries and time windows. Computers & Operations Research. 2015, 56, 93-109, DOI:10.1016/j.cor.2014.11.007.
• [18] Palhazi C.D., Goos P., Sörensen K., Arráiz E.: An iterated local search algorithm for the vehicle routing problem with backhauls. European Journal of Operational Research. 2014, 237(2), 454-464. DOI:10.1016/j.ejor.2014.02.011.
• [19] Penna P.H.V., Subramanian A., Ochi L.S.: An Iterated Local Search heuristic for the Heterogeneous Fleet Vehicle Routing Problem. Journal of Heuristics. 2013, 19(2), 201-232. DOI:10.1007/s10732-011-9186-y.
• [20] Pop P.C., Fuksz L., Marc A.H.: A variable neighborhood search approach for solving the generalized vehicle routing problem. In: Polycarpou M., de Carvalho A.C.P.L.F., Pan J.S., Woźniak M., Quintian H., Corchado E., eds.: Hybrid Artificial Intelligence Systems. Vol 8480. Lecture notes in computer science. Cham: Springer International Publishing. 2014, 13-24. DOI:10.1007/978-3-319-07617-1_2.
• [21] Robinson J., Brase G., Griswold W., Jackson C., Erickson L.: Business models for solar-powered charging stations to develop infrastructure for electric vehicles. Sustainability. 2014, 6(10), 7358-7387. DOI:10.3390/su6107358.
• [22] Serrenho A.C., Norman J.B., Allwood J.M.: The impact of reducing car weight on global emissions: the future fleet in Great Britain. Mathematical, Physical and Engineering Sciences. 2017, 375(2095). DOI:10.1098/rsta.2016.0364.
• [23] Stopka O., Stopkova M., Kampf R.: Application of the operational research method to determine the optimum transport collection cycle of municipal waste in a predesignated urban area. Sustainability. 2019, 11(8), 2275. DOI:10.3390/su11082275.
• [24] Stopka O., Zitricky V., Abramovic B., Marinov M., Ricci S.: Innovative technologies for sustainable passenger transport. Journal of Advanced Transportation. 2019, 1-2. DOI:10.1155/2019/4197246.
• [25] Subramanian A., Penna P.H.V., Uchoa E., Ochi L.S.: A hybrid algorithm for the Heterogeneous Fleet Vehicle Routing Problem. European Journal of Operational Research. 2012, 221(2), 285-295. DOI:10.1016/j.ejor.2012.03.016.
• [26] Subramanian A., Uchoa E., Ochi L.S.: A hybrid algorithm for a class of vehicle routing problems. Computers & Operations Research. 2013, 40(10), 2519-2531. DOI:10.1016/j.cor.2013.01.013.
• [27] Tan K.C., Lee L.H., Zhu Q.L., Ou K.: Heuristic methods for vehicle routing problem with time windows. Artificial Intelligence in Engineering. 2001, 15(3), 281-295. DOI:10.1016/S0954-1810(01)00005-X.
• [28] Toth P., Vigo D., eds.: The Vehicle Routing Problem. Society for Industrial and Applied Mathematics. 2002. DOI:10.1137/1.9780898718515.
• [29] Wang S., Tao F., Shi Y., Wen H.: Optimization of Vehicle Routing Problem with Time Windows for Cold Chain Logistics Based on Carbon Tax. Sustainability. 2017, 9(5), 694. DOI:10.3390/su9050694.
• [30] Zhang L., Niu H.: An Algorithm for Vehicle Routing Problem with Soft Time Windows Using Tabu Search. In: Wang Y., Yi P., An S., Wang H., eds. ICCTP 2009. Reston, VA: American Society of Civil Engineers. 2009, 1-6. DOI:10.1061/41064(358)458.