Probabilistic Traveling Salesman Problem and Harmony Search Algorithms in Pharmacy Supply Optimization

Sebastian Twaróg; Jacek Szołtysek; Krzysztof Szwarc; Urszula Boryczka

doi:10.18778/0208-6018.345.06

Autor

Sebastian Twaróg University of Economics in Katowice, Faculty of Management, Department of Social Logistics https://orcid.org/0000-0003-0855-7965
Jacek Szołtysek University of Economics in Katowice, Faculty of Management, Department of Social Logistics https://orcid.org/0000-0003-3266-0241
Krzysztof Szwarc University of Silesia in Katowice, Faculty of Computer Science and Materials Science https://orcid.org/0000-0003-3341-1511
Urszula Boryczka University of Silesia in Katowice, Faculty of Computer Science and Materials Science https://orcid.org/0000-0002-2698-6934

DOI:

https://doi.org/10.18778/0208-6018.345.06

Słowa kluczowe:

probabilistyczny problem komiwojażera, poszukiwanie harmonii, niezawodność zaopatrzenia aptek

Abstrakt

W artykule wskazano na utylitarne znaczenie probabilistycznego problemu komiwojażera (PTSP) w planowaniu tras przejazdu przez przedsiębiorstwa świadczące usługi dystrybucyjne dla aptek, ze szczególnym uwzględnieniem zmiennego zapotrzebowania odbiorców. Problem optymalizacyjny został rozwiązany za pomocą algorytmu poszukiwania harmonii (HS), a jego użyteczność została zweryfikowana na podstawie jednej rzeczywistej instancji PTSP (reprezentującej problem niezawodności zaopatrzenia aptek) oraz trzech zadań z ogólnodostępnej biblioteki TSPLIB (dostosowanych do PTSP). W wyniku przeprowadzonych badań stwierdzono znaczną użyteczność hybrydowego podejścia, zakładającego połączenie HS z popularną metodą 2‑opt, które umożliwiło uzyskanie dobrych rezultatów w akceptowalnym (w zastosowaniach praktycznych) czasie.

Pobrania

Statystyki pobrań niedostępne.

Bibliografia

Bianchi L., Gambardella L. M., Dorigo M. (2002), Solving the Homogeneous Probabilistic Traveling Salesman Problem by the ACO Metaheuristic, [in:] M. Dorigo, G. Di Caro, M. Sampels (eds.), Ant Algorithms. ANTS. Lecture Notes in Computer Science, vol. 2463, Springer, Berlin–Heidelberg, pp. 176–187, https://doi.org/10.1007/3-540-45724-0_15

Boryczka U., Szwarc K. (2018), The Adaptation of the Harmony Search Algorithm to the ATSP, [in:] N. Nguyen, D. Hoang, T. P. Hong, H. Pham, B. Trawiński (eds.), Intelligent Information and Database Systems. ACIIDS 2018. Lecture Notes in Computer Science, vol. 10751, Springer, Cham, pp. 341–351, https://doi.org/10.1007/978-3-319-75417-8_32

Boryczka U., Szwarc K. (2019), The Adaptation of the Harmony Search Algorithm to the ATSP with the evaluation of the influence of the pitch adjustment place on the quality of results, “Journal of Information and Telecommunication”, vol. 3(1), pp. 2–18, https://doi.org/10.1080/24751839.2018.1503149

Bowler N. E., Fink T. M.A., Ball R. C. (2003), Characterization of the probabilistic traveling salesman problem, “Physical Review E”, vol. 68(3), https://doi.org/10.1103/PhysRevE.68.036703

Geem Z. W. (2000), Optimal design of water distribution networks using harmony search, PhD thesis, Korea University.

GUS (2017), Apteki i punkty apteczne w Polsce, https://stat.gov.pl/files/gfx/portalinformacyjny/pl/defaultaktualnosci/5513/15/2/1/apteki_i_punkty_apteczne_w_2017.pdf (accessed: 3.08.2018).

Hetmaniok E., Jama D., Słota D., Zielonka A. (2011), Application of the Harmony Search algorithm in solving the inverse heat conduction problem, “Zeszyty Naukowe. Matematyka Stosowana/Politechnika Śląska”, no. 1, pp. 99–108.

IQVIA (2017), Rynek farmaceutyczny w 2017 roku, https://www.nia.org.pl/wp-content/uploads/2018/01/IQVIA_Rynek_farmaceutyczny_2017_RAPORT.pdf (accessed: 3.08.2018).

Jaillet P. (1985), Probabilistic Traveling Salesman Problems, PhD thesis, MIT, Cambridge.

Jaillet P. (1988), A Priori Solution of a Traveling Salesman Problem in Which a Random Subset of the Customers are Visited, “Operations Research”, vol. 36(6), pp. 929–936, https://doi.org/10.1287/opre.36.6.929

Kiełkowicz K., Kokosiński Z. (2012), Algorytm hybrydowy dla probabilistycznego problemu komiwojażera, “Czasopismo Techniczne. Automatyka”, no. 109 (1 AC), pp. 115–126.

Liu Y. H. (2007), A hybrid scatter search for the probabilistic traveling salesman problem, “Computers & Operations Research”, vol. 34(10), pp. 2949–2963, https://doi.org/10.1016/j.cor.2005.11.008

Rynek aptek (2018), Trend spadkowy jest trwały – liczba aptek spada, http://www.rynekaptek.pl/marketing‑i‑zarzadzanie/trend‑spadkowy‑jest‑trwaly‑liczba‑aptek‑spada,27271.html (accessed: 3.08.2018).

Szołtysek J. (2016), Logistyka w sferze dystrybucji, [in:] S. Kuf, E. Płaczek, A. Sadowski, J. Szołtysek, S. Twaróg, Vademecum logistyki, Difin, Warszawa, pp. 116–136.

Weiler C., Biesinger B., Hu B., Raidl G. R. (2015), Heuristic Approaches for the Probabilistic Traveling Salesman Problem, [in:] R. Moreno Díaz, F. Pichler, A. Quesada Arencibia (eds.), Computer Aided Systems Theory – EUROCAST 2015. EUROCAST 2015. Lecture Notes in Computer Science, vol. 9520, Springer, Cham, pp. 342–349, https://doi.org/10.1007/978-3-319-27340-2_43

Yang X. S. (2009), Harmony Search as a Metaheuristic Algorithm, [in:] Z. W. Geem (eds.), Music Inspired Harmony Search Algorithm. Studies in Computational Intelligence, vol. 191, Springer, Berlin–Heidelberg, pp. 1–14, https://doi.org/10.1007/978-3-642-00185-7_1

Zott C., Amit R., Massa L. (2011), The cusiness model: Recent developments and future research, “Journal of Management”, vol. 37(4), pp. 1019–1049, https://doi.org/10.1177/0149206311406265