The Impact of Perturbation Mechanisms on the Operation of the Swap Heuristic
More details
Hide details
Department of Agricultural, Forestry and Transport Machines, University of Life Sciences in Lublin, Polska
Wojciech Misztal   

Department of Agricultural, Forestry and Transport Machines, University of Life Sciences in Lublin, Głęboka 28, 20-612, Lublin, Polska
Submission date: 2019-11-28
Final revision date: 2019-12-09
Acceptance date: 2019-12-10
Publication date: 2019-12-23
The Archives of Automotive Engineering – Archiwum Motoryzacji 2019;86(4):27–39
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.
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.
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.
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.
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.
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.
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.
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.
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.
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/
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Toth P., Vigo D., eds.: The Vehicle Routing Problem. Society for Industrial and Applied Mathematics. 2002. DOI:10.1137/1.9780898718515.
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.
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.
Online joint replacement-order optimization driven by a nonlinear ensemble remaining useful life prediction method
Tao Yan, Yaguo Lei, Naipeng Li, Xiaosheng Si, Liliane Pintelon, Reginald Dewil
Mechanical Systems and Signal Processing
Research on low-emission vehicle powered by LPG using innovative hardware and software
Arkadiusz Małek, Jacek Caban, Branislav Sarkan
The Archives of Automotive Engineering – Archiwum Motoryzacji
Technical review of supervised machine learning studies and potential implementation to identify herbal plant dataset
Jeremy Carnagie, Aditya Prabowo, Iwan Istanto, Eko Budiana, Ivan Singgih, Indri Yaningsih, František Mikšík
Open Engineering
Organization of Urban Transport Organization – Presentation of Bicycle System and Bicycle Infrastructure in Lublin
Agnieszka Dudziak, Jacek Caban
LOGI – Scientific Journal on Transport and Logistics
The planning process of transport tasks for autonomous vans
Aleksander Nieoczym, Jacek Caban, Ondrej Stopka, Tomasz Krajka, Mária Stopková
Open Engineering
Declaration of availability