Генетичний алгоритм для розподілу маршрутів доставки
Анотація
Інформаційні технології стали невід’ємною частиною життя сучасного суспільства. Саме тому їх активно застосовують для вирішення складаних завдань, що пов’язані з оптимізацією діяльності в економіці, менеджменті, фінансах, соціальній та інших сферах. Логістика не стала винятком, а інформаційні технології використовують для автоматизації процесу доставки, що сприяє ефективній та рентабельній роботі підприємств. Це можливо за умови раціонального використання ресурсів постачальника та забезпечення його ефективним способом розподілу маршрутів доставки. Саме цим пояснюється актуальність даної роботи. Метою статті є розробка генетичного алгоритму для визначення оптимального плану доставки, а також порівняння його роботи з деякими відомими методами оптимізації доставки. Об’єктом дослідження є маршрути доставок. Предмет дослідження – алгоритм розподілу маршрутів доставки. В статті запропоновано генетичний алгоритм для розв’язку задачі комівояжера з декількома маршрутами. Представлено постановку задачі визначення оптимального плану доставки, розглянуто можливість застосування генетичного алгоритму для поставленої задачі, описано вид генетичного алгоритму та представлено блок-схему його реалізації. Підготовлено програмну реалізацію генетичного алгоритму та інших методів розподілу маршрутів доставки, що здійснено за допомогою мови програмування C++ та фреймворку Qt. Для роботи алгоритмів потрібно згенерувати замовлення, транспортні засоби та депо, а також увести необхідні параметри алгоритмів. Отримано результати роботи алгоритму та інших обраних методів за допомогою програми, що дозволило оцінити їх ефективність на основі експериментальних даних при заданих параметрах та порівнювати їх роботу. Експериментально встановлено перевагу запропонованого генетичного алгоритму над відомим мурашиним на випадково згенерованих тестах. Це свідчить про прикладну цінність отриманих результатів та можливості застосування алгоритму у реальних умовах розподілу маршрутів доставок.
Завантаження
Посилання
Dantzig, G. B., Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6 (1), 80-91. doi: https://doi.org/10.1287/mnsc.6.1.80.
Stodola, P., Mazal, J. (2015). Tactical models based on a multi-depot vehicle routing problem using the ant colony optimization algorithm. International journal of mathematical models and methods in applied sciences, 9, 330-337.
Chitty, D., Wanner, E., Parmar, R., & Lewis, P. (2019). Applying Partial-ACO to Large-scale Vehicle Fleet Optimisation. arXiv. Retrieved from https://arxiv.org/abs/1904.07636.
Diestel, R. (2005). Graph Theory. NY: Springer-Verlag.
Cormen, T., Leiserson, C., Rivest, R., & Stein, C. (2009). Introduction to Algorithms (2nd ed.). MIT Press.
Knuth, D. (1974). Postscript about NP-hard problems. ACM SIGACT News, 6(2), 15-16. doi: https://doi.org/10.1145/1008304.1008305.
Nakonechny, S.I., Savina, S.S. (2003). Mathematical programming: textbook. Kyiv: KNEU. (іn Ukrainian)
Eiben, A. E., Raué, P., Ruttkay, Z. (1994). Genetic algorithms with multi-parent recombination. PPSN III: Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature Jerusalem, October 9–14, 2010, Israel, 78-87.
Mitchell, M. (1995). Genetic algorithms: an overview. Complexity, 1(1), 31-39. doi: https://doi.org/10.1002/cplx.6130010108.
Mitchell, M. (1996). An introduction to genetic algorithms. Cambridge, MA: MIT Press.
Koza, J. R. (1994). Introduction to genetic programming. In K. E. Kinnear (Ed.), Advances in Genetic Programming. Cambridge: MIT Press, 21-41.
Steeb, W.-H. (2001). The Nonlinear Workbook: Chaos, Fractals, Cellular Automata, Neural Networks, Genetic Algorithms, Fuzzy Logic: with C++, Java, SymbolicC++ and Reduce Programs. Singapore: World Scientific.
