Модели и алгоритмы оптимизации транспортных маршрутов при организации перевозок бизнес-товаров
ВВЕДЕНИЕ 11
1. АНАЛИЗ СОСТОЯНИЯ ПРОБЛЕМЫ 16
1.1. Бизнес процесс организации.
…………………………………………….18
1.2. Информационная технология управления.
………………………………28
1.2.1. Построение сценария информационного процесса… 28
1.2.2. Построение схемы документооборота… 30
1.3. Формулирование целей и задач ИС………………………………………
32
1.4. Функциональная структура ИС 34
1.4.1. Внешние объекты и диаграммы окружения….………………………
34
1.4.2. Данные, результаты, хранилища и логическая модель………………
35
1.4.3. Внешние объекты и диаграммы окружения….………………………
36
2. МАТЕМАТИЧЕСКЕ МОДЕЛИ И МЕТОДЫ СФОРМУЛИРОВАННЫХ ЗАДАЧ. 44
2.1. Расчёт данных для формирования маршрута движения..………………
44
2.1.1. Построение математической модели. 44
2.1.2. Разработка методов решения 45
2.2. Формирование маршрута движения 46
2.2.1. Построение математической модели. 46
2.2.2. Обзор существующих методов решения..……………………………
48
2.2.2.1. Метод полного перебора. 48
2.2.2.2. Алгоритм ближайшего соседа… 51
2.2.2.3. Метод ветвей и границ………….…………………………………
53
2.2.2.4. Метод эластичной сети………….…………………………………
60
2.2.2.5. Муравьиный алгоритм.……………………………………………
61
2.2.2.5.1. Биологическое обоснование. 62
2.2.2.5.2. Вариации алгоритма. 63
2.2.2.5.3. Этапы решения задачи при помощи муравьиных
алгоритмов 64
2.2.2.5.4. Применение для задачи коммивояжёра………………………
65
2.2.2.6. Генетический алгоритм 68
2.2.2.7. Выводы. 75
2.2.3. Разработка модифицированного метода решения..…………………
77
3. РАЗРАБОТКА ИНФОРМАЦИОННОЙ СИСТЕМЫ ДОСТАВКИ ТОВАРОВ 83
3.1. Информационное обеспечение. 83
3.1.1. Концептуальное проектирование базы данных………………………
83
3.1.2. Логическое проектирование базы данных……………………………
89
3.1.3. Ведение БД 90
3.1.3.1. Определение списка событий. 90
3.1.3.2. Классификация событий. 91
3.1.3.3. Постановка задач ведения БД………………………………………
93
3.2. Разработка алгоритмов решения прикладных задач ……………………
95
3.2.1. Технология обработки данных. 95
3.2.2. Системное программное обеспечение. 98
3.2.3. Пакеты инвариантных прикладных программ………………………
98
3.2.4. Прикладное программное обеспечение. 99
3.2.4.1. Алгоритмы организации диалога с пользователем………………
99
3.2.4.2. Алгоритмы решения прикладных задач…………………………
100
ЗАКЛЮЧЕНИЕ 107
CONCLUSION 108
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ……………………………
109
ПРИЛОЖЕНИЯ 114
Приложение 1. Формы документов……………………………………………
114
Приложение 2. Обзор задачи коммивояжёра.…………………………………
120
Приложение 3. Решение задач на контрольном примере.……………………
128
Приложение 4. Продолжение решения примера задачи коммивояжёра методом ветвей и границ… 137
Приложение 5. Объём БД………………………………………………………
142
Приложение 6. Контрольный пример базы данных..…………………………
143
Приложение 7. Интерфейс информационной системы………………………
147
Приложение 8. Листинг программного кода.…………………………………
153
Приложение 9. Тестирование работы спроектированной ИС..………………
179
Приложение 10. Акт о внедрении. 192
Приложение 11. Словарь терминов……………………………………………
193
Результатом диссертационной работы является вклад в развитие научного направления логистики и область знаний по автоматизации решения задачи нахождения оптимального кольцевого маршрута.
Объектом исследования является построение оптимального кольцевого транспортного маршрута при организации перевозок бизнес- товаров.
УДК: 004.023 – Эвристические методы.
Актуальность объекта исследования. Нередко в конечных фирмах- дистрибьюторах эффективность организации перевозок бизнес-товаров полностью обусловлена знаниями и навыками логистов. Так на решение задач, как правило, уходит довольно много времени и, соответственно, средств, а решения далеко не всегда оказываются оптимальными из-за сложности их нахождения, больших объёмов работы, ограниченного времени и человеческого фактора. Таким образом задача оптимизации транспортных маршрутов при организации перевозок бизнес-товаров по-прежнему является актуальной задачей, решение которой и программная реализация полученного решения до доступного универсального в рамках своей ниши продукта позволит широкому кругу дистрибьюторов более эффективно использовать свои ресурсы и повысить прибыль.
Предметом данного диссертационного исследования является сравнительный анализ существующих алгоритмов построения оптимальных
кольцевых маршрутов, а так же разработка нового алгоритма построения на базе известных алгоритмов в области решения транспортных задач.
Актуальность предмета данного диссертационного исследования заключается в отсутствии гарантированно точных алгоритмов построения оптимальных кольцевых маршрутов, работающих за полиномиальное время.
Актуальность данного диссертационного исследования заключается в отсутствии у существующих алгоритмов построения оптимальных кольцевых маршрутов необходимого для широкого практического применения рядовыми дистрибьюторами соотношения точность результата/скорость работы/ресурсозатратность.
Проблемой данного диссертационного исследования является разработка нового алгоритма построения оптимальных транспортных кольцевых маршрутов при организации перевозок бизнес-товаров.
Основным противоречием в данном диссертационном исследовании является выбор между степенью оптимальности построенного маршрута, скоростью работы разрабатываемого алгоритма, требуемой для корректной работы алгоритма вычислительной мощностью и тем, насколько алгоритм удачен при потоковом решении большого количества задач.
Связь актуальности темы с характером научных результатов диссертации состоит в том, что результатом данного диссертационного исследования является вклад в развитие научного направления логистики в виде нового алгоритма построения оптимальных транспортных кольцевых маршрутов, который обладает более выгодным соотношением точность результата/скорость работы/ресурсозатратность по сравнению с существующими, что является актуальным запросом.
Целью данного диссертационного исследования является повышение эффективности и точности алгоритмов построения транспортных кольцевых маршрутов и повышение универсальности программных продуктов, использующих данный метод.
Для достижения поставленной цели в рамках диссертации решены следующие задачи:
• аналитический обзор существующих методов и алгоритмов;
• глубокий анализ предметной области, выбор инструментария;
• разработка усовершенствованного алгоритма построения оптимальных транспортных кольцевых маршрутов доставки товаров, подходящего для быстрого решения задач;
• разработка информационной системы доставки товаров на базе разработанного алгоритма;
• экспериментальное обоснование теоретических положений диссертации.
Теоретическими основами исследования являются теория логистики, теория информации, теория управления перевозками, теория баз данных, теория проектирования автоматизированных информационных систем и др.
Методологическими основами исследования являются метод системного анализа, метод сравнений и аналогий, метод построения функциональной структуры системы, метод представления информационной технологии в виде поведенческой модели, метод построения диаграмм потоков данных, методы решения задачи коммивояжёра, алгоритм Флойда- Уоршелла и др.
В числе информационных источников диссертации использованы:
• научные источники в виде данных и сведений из книг, журнальных статей, научных докладов и отчётов, материалов научных конференций, семинаров и др.;
• результаты собственных расчетов и проведенных экспериментов. Научная новизна исследования. Разработан усовершенствованный алгоритм построения оптимальных транспортных кольцевых маршрутов доставки товаров, позволяющий за счёт включения алгоритма Флойда-
Уоршелла и особенностей программной реализации решать задачи (в т.ч. больших размерностей) с более выгодным соотношением точность результата/скорость работы/ресурсозатратность.
Целью проведения экспериментов являются:
• демонстрация того, что разработанный в данной диссертационной работе алгоритм отрабатывает корректно, быстро решает
типовые задачи рядовой фирмы-дстрибьютора на реальных данных, успешно интегрируется в информационную систему доставки товаров и готов к практическому применению в работе дистрибьюторов;
• обоснование теоретического положения о том, что параллельный
алгоритм Флойда даёт значительный выигрыш во времени против последовательного.
Полезность результатов диссертационной исследования состоит в том, что они:
• вносят вклад в развитие научного направления логистики;
• создают условия для прорыва в автоматизации транспортной логистики.
Достоверность результатов данной диссертационной работы определяется за счёт использования проверенных практикой корректных математических методов и алгоритмов, за счёт результатов проведённых экспериментов и тестового прогона разработанной информационной системы с использованием реальных данных.
Научные выводы по результатам диссертационной работы:
• разработан усовершенствованный алгоритм построения
оптимальных транспортных кольцевых маршрутов доставки товаров, позволяющий решать задачи с более выгодным соотношением точность результата/скорость работы/ресурсозатратность;
• разработана информационная система доставки товаров.
1. Мокшин В.В., Кирпичников А.П., Буйнова Е.Л., Гараева Э.Р., Ямалтдинова А..А., Золотухин А.В. Особенности оптимизации работы систем массового обслуживания в Anylogic на примере фитнес-центра // Вестник технологического университета. 2019. Т. 22, №5, с. 132-140. ISSN: 1998-7072
2. А.М.Гаджинский . Логистика [Текст]: Учебник для высших и средних специальных учебных заведений. – ИВЦ “Маркетинг”, 2001. – 395 с.
3. Суздальцев В.А., Осипова А.Л. Проектирование информационных систем: Учебное пособие. Казань: Изд.-во Казан. Гос. Техн. Ун-та, 2007.
4. Осипова А.Л. Структурный анализ при проектировании информационных систем. Материалы всероссийской научно-технической конференции. «Проблемы и перспективы развития информационных технологий». Казань, КНИТУ-КАИ, 2012, с.139 – 147.
5. Ризаев И.С., Осипова А.Л. Технология структурного анализа и проектирования информационных систем. Сборник трудов XII международной н-п конференции «Фундаментальные и прикладные исследования, разработка и применение высоких технологий в промышленности» С-Петербург, 2011, Том 3, Часть 1. С.154-156.
6. Эминов Ф.И. Информационные технологии управления предприятиями. – Казань: Мастер Лайн, 2015. – 144 с.
7. Корбут А. А., Финкельштейн Ю. Ю. Дискретное программирование. – М., Наука, 1969. – C. 258-264
8. G. Gutin, A. Yeo, A. Zverovich. Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP Архивная копия от 29 июля 2007 на Wayback Machine // Discrete Applied Mathematics 117 (2002)
9. Решение задачи коммивояжера методом ближайшего соседа. Copyright (c) Moscow Power Engineering Institute, 2007-2013. [Электронный ресурс]. URL: http://twt.mpei.ac.ru/MCS/Worksheets/nvatot.xmcd
10. Костюк Ю. Л. Эффективная реализация алгоритма решения задачи коммивояжера методом ветвей и границ // Прикладная дискретная математика. Вычислительные методы в дискретной математике, 2010. №2 (20). С. 78-90.
11. A. H. Land and A. G. Doig. An automatic method of solving discrete programming problems, С. 497-520.
12. Little J. D. C., Murty K. G., Sweeney D. W., Karel C. An algorithm for the traveling salesman problem // Operations Research. 1963 Vol. 11, No 6. P. 972-989.
13. Richard Durbin, David Willshaw. An analogue approach to the travelling salesman problem using an elastic net method (англ.) // Nature. — 1987- 04-22. — Vol. 326, iss. 6114. — P. 689–691. — doi:10.1038/326689a0.
14. M. Resta, Portfolio optimization through elastic maps: Some evidence from the Italian stock exchange, Knowledge-Based Intelligent Information and Engineering Systems, B. Apolloni, R.J. Howlett and L. Jain (eds.), Lecture Notes in Computer Science, Vol. 4693, Springer: Berlin — Heidelberg, 2010.
15. Кирпичников А.П., Буйнова Е.Л., Гараева Э.Р., Ризаев И.С. Формирование маршрута движения транспорта при доставке товаров потребителям // Вестник технологического университета. 2019. Т. 22, №8, с. 175-180. ISSN: 1998-7072
16. Кажаров А. А., Курейчик В. М. Муравьиные алгоритмы для решения транспортных задач. Известия Российской академии наук. Теория и системы управления. 2010. № 1. С. 32-45.
17. Bonabeau, E. «Editor’s Introduction: Stigmergy.» special Issue of Artificial Life on Stigmergy. Volume 5, Issue 2 / Spring 1999, p.95-96.
18. M. Dorigo, 1992. Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italy.
19. J.-L. Deneubourg, S. Aron, S. Goss et J.-M. Pasteels, The self- organizing exploratory pattern of the Argentine ant, Journal of Insect Behavior, volume 3, page 159, 1990
20. Stützle et H.H. Hoos, MAX MIN Ant System, Future Generation Computer Systems, volume 16, pages 889—914, 2000.
21. Штовба С.Д. Муравьиные алгоритмы // Exponenta Pro. Математика в приложениях, 2003, №4, с.70-75.
22. C. Blum, 2005 «Ant colony optimization: Introduction and recent trends». Physics of Life Reviews, 2: 353—373.
23. Алсагарова Е.В. Метаэвристические методы оптимизации в экономике. // Экономика. Право. Менеджмент: сборник трудов молодых исследователей БГУ.– 2014. – Выпуск 1(1) [Электронный ресурс]. URL: http://izdatelstvo.isea.ru/epm/archive.aspx?id=1
24. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. – М: Физматлит, 2014.
25. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы: Учебное пособие. – 2-е изд. – М: Физматлит, 2006.
26. Holland J.H. Adaptation in Natural and Artificial Systems: An Introductory Analysys with Application to Biology, Control and Artificial Intelligence. University of Michigan, 1975.
27. Моров В. А. Применение генетического алгоритма к задачам оптимизации. Реализация генетического алгоритма для задачи коммивояжера. // Вестник Амурского государственного университета. 2012.
№57. [Электронный ресурс]. URL: https://vestnik.amursu.ru/wp-content/uploads/2017/12/N57_4.pdf.
28. В.М.Гавриляко. Задача коммивояжера и генетические алгоритмы // Радіоелектроніка, інформатика, управління. 2003. №1 (9).
[Электронный ресурс]. URL: https://cyberleninka.ru/article/n/zadacha- kommivoyazhera-i-geneticheskie-algoritmy.
29. Steven S. Skiena. The Algorithm Design Manual. Second Edition. Springer, 2008.
30. Рогаткин А.Ю., Захаркина М.В. Оптимизация автотранспортных маршрутов: эвристические алгоритмы и практика логистического менеджмента // Вестник Московской международной академии. 2016. №1. [Электронный ресурс]. URL: https://cyberleninka.ru/article/n/optimizatsiya- avtotransportnyh-marshrutov-evristicheskie-algoritmy-i-praktika-logisticheskogo- menedzhmenta.
31. Дал У., Дейкстра Э., Хоор К. Структурное программирование – М.:Мир, 1975. – 248 с.
32. Конников П.В., Кудинов В.А. Оптимизация методом муравьиной колонии как метаэвристика. [Электронный ресурс]. URL: http://scientific- notes.ru/pdf/008-05.pdf.
33. Пожидаев М.С. Алгоритмы решения задачи маршрутизации транспорта. Дисс. … канд. техн. наук. – Томск, 2010. – 135 с.
34. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07- 013151-1.
35. Ризаев И.С., Яхина З.Т. Базы данных/Лабораторный практикум. – К., «Мастер Лайн», 2003.
36. Everett N. McKay. UI is Communication: How to Design Intuitive, User Centered Interfaces by Focusing on Effective Communication. – 2013.
37. Jenifer Tidwell. Designing Interfaces. – 2011.
38. Тюхтина А.А. Методы дискретной оптимизации: Часть 1: Учебно-методическое пособие. – Нижний Новгород: Нижегородский госуниверситет, 2014. – 62 с.
39. М. Свами, К. Тхуласираман. Графы, сети и алгоритмы. — Москва: Мир, 1984.
40. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978. – 432 с.
41. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
42. William I. Gasarch. The P=?NP poll. // SIGACT News. — 2002. — Т. 33, № 2. — С. 34—47. — doi:10.1145/1052796.1052804.
43. Klir, George J. Facets of systems science. — Springer, 1991. — С. 121—128. — ISBN 9780306439599.
44. Bremermann, H.J. (1962) Optimization through evolution and recombination In: Self-Organizing systems 1962, edited M.C. Yovitts et al., Spartan Books, Washington, D.C. pp. 93-106.
45. Эминов Ф.И. Офисные и промышленные информационные сети.
– Казань: Мастер Лайн, 2016. – 346 с.
Хочешь уникальную работу?
Больше 3 000 экспертов уже готовы начать работу над твоим проектом!
4.8 (105 отзывов)
4.8 (40 отзывов)
5 (22 отзыва)
4.9 (826 отзывов)
4.9 (20 отзывов)
4.8 (373 отзыва)
4.9 (298 отзывов)
4.9 (66 отзывов)
4.9 (343 отзыва)
