ВИЗНАЧЕННЯ ОПТИМАЛЬНОГО КІЛЬЦЕВОГО МАРШРУТУ, ЩО ПРОХОДИТЬ ЧЕРЕЗ ЗАДАНУ МНОЖИНУ ПУНКТІВ НА КАРТІ
DOI:
https://doi.org/10.30837/2522-9818.2019.7.102Ключові слова:
транспортна логістика, маршрут на карті, граф, гамільтонів цикл, складність, NP-повнота, алгоритм Дейкстри, приведення, схема пошуку з поверненнямиАнотація
Предметом досліджень є методи та інформаційні технології транспортної логістики. Мета – зниження витрат і скорочення часу на доставку товарів автомобільним транспортом за рахунок розробки і впровадження ефективних методів і алгоритмів пошуку оптимального маршруту розвезення товарів. У статті розглядається завдання пошуку оптимального кільцевого маршруту розвезення товарів зі складу, що проходить через задану множину пунктів на карті. Для вирішення завдання використовуються методи і алгоритми дискретної математики. Отримані наступні результати. Виконаний аналіз проблеми та існуючих методів дискретної математики для її вирішення, визначено недоліки цих методів. Запропоновано метод вирішення завдання, що усуває ці недоліки. Розроблено евристичний алгоритм розв'язання задачі, що реалізує запропонований метод розв'язання. Рішення задачі, що розглядається, зводиться до задачі пошуку гамільтонова циклу на новому графі меншої розмірності. Новий граф будується з початкового графа, що описує карту, і складається з вершин заданої множини пунктів на карті, через які повинен пройти маршрут. Кожна дуга в новому графі з'єднує пару вершин, якщо в початковому графі існує шлях між цими вершинами. Дуга зважується числом, яке визначає мінімальну відстань між вершинами в початковому графі, які вона з'єднує. Для побудови графа використовується алгоритм Дейкстри. Висновки: запропонований метод вирішення розглянутої задачі виконує її приведення до класичної задачі дискретної математики пошуку гамільтонова циклу в графі. Тестування розробленої програми показало працездатність запропонованого методу і алгоритму вирішення завдання. Розроблений метод дозволяє знизити розмірність розв'язуваної задачі, оскільки рішення шукається на новому графі меншої розмірності на відміну від графа, що описує вихідну карту. Фактор зниження розмірності значно зменшує витрати на пошук рішення і підвищує шанси знайти оптимальний маршрут розвезення товарів.
Посилання
Fёdorov, V. A. (2016), "Analysis of the advantages and disadvantages of the traditional method of handling and delivery of goods in transport logistics" ["Analyz prevoskhodstv y nedostatkov tradytsyonnoho sposoba obrabotky y dostavky hruza v transportnoy lohystyke"], Symbol of Science, No. 11 (1), P. 217–218.
Iastremska, O. (2018), "Logistics at an enterprise: the peculiarities of procurement activities" Innovative Technologies and Scientific Solutions for Industries, No. 3 (5), P. 141–148. DOI: https://doi.org/10.30837/2522-9818.2018.5.141.
Ustenko, M. O. "The main problems of transport logistics" ["Osnovni problemy transportnoyi lohistyky"], available at : http://uran.donntu.org/~masters/2012/iii/dyadyk/library/article3.htm (last accessed 08.02.2019).
Horyaynov, A. N. (2006), "Types of routes of vehicles in the transport of goods in the logistics system" ["Vydy marshrutov avtotransportnykh sredstv pry perevozke hruzov v lohystycheskoy systeme"], Utilities of cities, No. 67, P. 304–309.
"Problems of transport logistics: Practical experience of Ukrainian enterprises" ["Problemy transportnoy lohystyky: Praktycheskyy opyt ukraynskykh predpryyatyy"], available at : http://www.ukrlogist.com/node/452 (last accessed 08.02.2019).
Nykolyn, V. Y. (2004), Freight transport : monograph [Hruzovye avtomobyl'nye perevozky : monohrafyya], Varyant, Omsk, 480 p.
Shamys, V. A. "Some aspects of choosing the optimal shipping route" ["Nekotorye aspekty vybora optymal'noho marshruta perevozok"], available at : https://novainfo.ru/article/5296 (last accessed 08.02.2019).
Serheev, V. Y. (2001), Logistics in business [Lohystyka v byznese], Ynfra-M, Moscow, 608 p.
Anderson, Dzh. (2003), Discrete mathematics and combinatorics [Dyskretnaya matematyka y kombynatoryka], Vyl'yams, Moscow, 214 p.
Vershik, A. M. (2013), "Long history of the Monge-Kantorovich transportation problem", Math. Intelligencer, No. 4 (35), P. 1–9. DOI: https://doi.org/10.1007/s00283-013-9380-x.
Kantorovych, L. V. (2011), Selected work. Mathematical and economic work [Yzbrannye trudy. Matematyko-ekonomycheskye raboty], Nauka, Novosybyrsk, 760 p.
"Transport task. Mathematical model" ["Transportnaya zadacha. Matematycheskaya model'"], available at : http://www.grandars.ru/student/vysshaya-matematika/model-transportnoy-zadachi.html (last accessed 08.02.2019).
Rohatkyn, A. Yu., Zakharkyna, M. V. (2016), "Optimization of motor routes: heuristic algorithms and logistics management practices" ["Optymyzatsyya avtotransportnykh marshrutov: evrystycheskye alhorytmy y praktyka lohystycheskoho menedzhmenta"], Bulletin of the Moscow International Academy, No. 1, P. 124–135.
Davendra, D. (2010), Traveling Salesman Problem. Theory and Applications, IntechOpen, London, 336 p. DOI: https://doi.org/10.5772/547.
Hery, M., Dzhonson, D. (1982), Computational machines and difficult tasks [Vychyslytel'nye mashyny y trudnoreshaemye zadachy], Myr, Moscow, 419 p.
"Littleton's algorithm is a method for solving a salesman's problem" ["Alhorytm Lyttla – metod reshenyya zadachy kommyvoyazhera"], available at : https://intellect.ml/algoritm-littla-metod-resheniya-zadachi-kommivoyazhera-7734 (last accessed 08.02.2019).
Clarke, G., Wright, J. (1964), "Scheduling of Vehicles from a central depot to a number of delivery", Operations Research, No. 4 (12), Р. 568–581. DOI: https://doi.org/10.1287/opre.12.4.568.
Bellman, R. (1958), "On a routing problem", Quarterly of Applied Mathematics, No. 1 (16), P. 87–90. DOI: https://doi.org/10.1090/qam/102435.
Dijkstra, E. W. (1959), "A note on two problems in connexion with graphs", Numerische Mathematik, No. 1 (1), P. 269–271. DOI: https://doi.org/10.1007/bf01386390.
Prokopenkov, V. F. (2014), "Finding a closed path in a graph passing through a given set of vertices, which is an eigenvalue of vertices of a graph" ["Poysk zamknutoho puty v hrafe, prokhodyashcheho cherez zadannoe mnozhestvo vershyn, yavlyayushcheesya sobstvennym podmnozhestvom vershyn hrafa"], International Scientific Conference MicroCAD 2014: Section No. 1 – Information and Management Systems, P. 18.
Wirth, N. (1984), "Data Structures and Algorithms", Scientific American, No. 3 (251), P. 60–69. DOI: https://doi.org/10.1038/scientificamerican0984-60.
Ore, O. (2009), The theory of graphs [Teoryya hrafov], URSS, Moscow, 354 p.
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2019 Vladymyr Prokopenkov, Yuryy Kozhyn, Oleh Malykh
Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Наше видання використовує положення про авторські права Creative Commons для журналів відкритого доступу.
Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:
Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License (CC BY-NC-SA 4.0), котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
Автори мають право укладати самостійні додаткові угоди щодо не комерційного та не ексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису опублікованої роботи, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи.
