Artificial immune system in planning deliveries in a short time

• Autorzy: Mrówczyńska B. , Król A. , Czech P.

Identyfikatory

DOI

10.24425/bpas.2019.126630

• Języki publikacji: EN

Abstrakty

EN

In the calculations presented in the article, an artificial immune system (AIS) was used to plan the routes of the fleet of delivery vehicles supplying food products to customers waiting for the delivery within a specified, short time, in such a manner so as to avoid delays and minimize the number of delivery vehicles. This type of task is classified as an open vehicle routing problem with time windows (OVRPWT). It comes down to the task of a traveling salesman, which belongs to NP-hard problems. The use of the AIS to solve this problem proved effective. The paper compares the results of AIS with two other varieties of artificial intelligence: genetic algorithms (GA) and simulated annealing (SA). The presented methods are controlled by sets of parameters, which were adjusted using the Taguchi method. Finally, the results were compared, which allowed for the evaluation of all these methods. The results obtained using AIS proved to be the best.

Słowa kluczowe

EN

artificial immune system; genetic algorithm; simulated annealing; open vehicle routing problem; on-time delivery; Taguchi method

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2019
• Tom: Vol. 67, nr 5
• Strony: 969--980
• Opis fizyczny: Bibliogr. 31 poz., rys., tab.

Twórcy

autor

Mrówczyńska B.

• Silesian University of Technology, Faculty of Transport, 8 Krasińskiego St., Katowice, Poland

autor

Król A.

• Silesian University of Technology, Faculty of Transport, 8 Krasińskiego St., Katowice, Poland

autor

Czech P.

• Silesian University of Technology, Faculty of Transport, 8 Krasińskiego St., Katowice, Poland

Bibliografia

• [1] P.P. Repoussis and C.D. Tarantilis, “Solving the fleet size and mix vehicle routing problem with time windows via adaptive memory programming”, Transportation Research Part C: Emerging Technologies 18(5) 695–71 (2010).
• [2] A.D. López-Sánchez, A.G. Hernández-Díaz, D. Vigo, R. Caballero, and J. Molina, “A multi-start algorithm for a balanced real-world open vehicle routing problem”, European Journal of Operational Research 238(1) 104–113 (2014).
• [3] R. Tadeusiewicz, L. Ogiela, and M.R. Ogiela, “The automatic understanding approach to systems analysis and design”, International Journal of Information Management 28(1) 38–48 (2008).
• [4] J. Ferdyn-Grygierek and K. Grygierek, “Multi-variable optimization of building thermal design using genetic algorithms”, Energies 10(10) 1570 (2017).
• [5] K. Pancerz, A. Lewicki, and R. Tadeusiewicz, “Ant-based ex-traction of rules in simple decision systems over ontological graphs”, International Journal of Applied Mathematics and Computer Science 25(2) 377–387 (2015).
• [6] S. Dinu and G. Bordea, “A new genetic approach for transport network design and optimization”, Bull. Pol. Ac.: Tech. 59(3) 263–272 (2011).
• [7] C.-I. Hsu and W.-T. Chen, “Optimizing fleet size and delivery scheduling for multi – temperature food distribution”, Applied Mathematical Modelling 38(3) 1077–1091 (2014).
• [8] R.T. Berger, C.R. Coullard, and M.S. Daskin, “Location-routing problems with distance constraints”, Transportation Science41(1) 29–43 (2007)
• [9] A. Osvald and L.Z. Stirn, “A vehicle routing algorithm for the distribution of fresh vegetables and similar perishable food”, Journal of FoodEngineering 85(2) 285–295 (2008).
• [10] N.H. Moin, S. Salhi, and N.A.B. Aziz, “An efficient hybrid genetic algorithm for the multi-product multi-period inventory routing problem”, International Journal of Production Economics 133(1) 334–343 (2011).
• [11] R. Baños, J. Ortega, C. Gil, A.L. Márquez, and F. de Toro, “A hybrid meta-heuristic for multi-objective vehicle routing problems with time windows”, Computers & Industrial Engineering 65(2) 286–296 (2013).
• [12] C. Pypno and G. Sierpiński, G. Automated large capacity multi-story garage concept and modeling of client service processes, Automation in Construction 81: 422‒433 (2017).
• [13] K. Pancerz, A. Lewicki, R. Tadeusiewicz, and J. Warchoł, “Ant-based clustering in delta episode information systems based on temporal rough set flow graphs”, Fundamenta Informaticae 1–2, 143–158 (2013).
• [14] L.N. De Castro and J. Timmis, Artificial immune systems: a new computational intelligence approach. London; New York: Springer (2002).
• [15] L.N. De Castro and F.J. Von Zuben, The Clonal Selection Algorithm with Engineering Applications, In GECCO 2002 – Work-shop Proceedings, Morgan Kaufmann, 36‒37.
• [16] J.H. Holland, “Adaptation in natural and artificial systems”, The University of Michigan Press, Ann Arbor, MI, 1975.
• [17] N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller, and E. Teller, “Equation of state calculations by fast computing machines”, The Journal of Chemical Physics 21(6) 1087–1092 (1953).
• [18] M. Shukla and S.J. Harkharia, Artificial Immune System-based algorithm for vehicle routing problem with time window con-straint for the delivery of agrifresh produce, Journal of Decision Systems 22(3) 224‒247 (2013).
• [19] A. Azadeh, S. Elahi, M.H. Farahani, and B.Nasirian, “A genetic algorithm Taguchi based approach to inventory routing problem of a single perishable product with transshipment”, Computers & Industrial Engineering 104, 124–133 (2017).
• [20] B. Mrówczyńska and M. Cieśla, “Planning routes of vans in a catering company”, ICLEEE 2017 International Conference of Logistic, Economics and Environmental Engineering. Maribor,Slovenia, 66–70 (2017).
• [21] A.S. Perelson, Applications of optimal control theory to immunology. Recent Developments in Variable Structure Systems, Economics and Biology. Springer Verlag, New-York: 272‒287D (1978).
• [22] C. Janeway, Immunobiology: the immune system in health and disease, 6th ed. New York: Garland Science (2005).
• [23] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs. Springer – Verlag Berlin Heidelberg (1996).
• [24] E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, 1st ed. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc. (1989).
• [25] L. Davis, “Applying adaptive algorithms to epistatic domains”, in Proceedings of the 9th International Joint Conference on Artificial Intelligence – Volume 1, San Francisco, CA, USA, 162–164 (1985).
• [26] V. Černý, “Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm”, Journal of Optimization Theory and Applications 45(1) 41–51 (1985).
• [27] R.K. Roy, A primer on the Taguchi method. Dearborn, Mich: Society of Manufacturing Engineers (1990).
• [28] M. Hajiaghaei-Keshteli, “The allocation of customers to potential distribution centers in supply chain networks: GA and AIA approaches”, Applied Soft Computing, 11(2) 2069–2078 (2011).
• [29] M. Schiffer and G. Walther, “Strategic planning of electric logistics fleet networks: A robust location-routing approach”, Omega80, 31–42 (2018).
• [30] A. Montoya, C. Guéret, J.E. Mendoza, and J. G. Villegas, “The electric vehicle routing problem with nonlinear charging function”, Transportation Research Part B: Methodological 103, 87–110 (2017).
• [31] V. Leggieri and M. Haouari, “A practical solution approach for the green vehicle routing problem”, Transportation Research Part E: Logistics and Transportation Review 104, 97–112 (2017

Uwagi

PL

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).