Разработка алгоритмов многоальтернативной маршрутизации грузоперевозок в системах транспортной логистики на основе эволюционных методов тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Плотников, Олег Александрович

• Плотников, Олег Александрович
• кандидат технических наук
• 2012

Оглавление диссертации кандидат технических наук Плотников, Олег Александрович

Введение.

Глава 1. Анализ задач информационных систем транспортной логистики, функционирующих в пределах города, и методов их решения.

1.1 Область применения, задачи и функции информационных систем транспортной логистики.

1.2 Постановка задачи маршрутизации транспорта.

1.3 Методы решения задачи маршрутизации транспорта.

1.4 Алгоритмы нахождения оптимального пути между вершинами дорожного графа.

1.5 Использование геоинформационных компонент в составе информационных систем транспортной логистики.

1.6 Цели и задачи исследования.

Глава 2. Разработка алгоритма решения задачи поиска оптимального пути между вершинами дорожного графа с нерегулярным весом ребер.

2.1. Алгоритма А* для решения задачи поиска путей на графе.

2.2 Модификация алгоритма А* и оценка результатов работы.

Глава 3. Разработка алгоритма нахождения глобального плана доставки задачи маршрутизации транспорта.

3.1 Постановка задачи оптимизации глобального плана доставки.

3.2 Разработка модифицированного меметического алгоритма для решения задачи маршрутизации транспорта.

3.3 Алгоритма муравьиной колонии в качестве алгоритма локального поиска.

Глава 4 Разработка проблемно-ориентированного программного обеспечения многоальтернативной маршрутизации грузоперевозок.

4.1. Модульная структура системы маршрутизации.

4.2 Интерфейс программирования приложений.

4.3 База данных приложения и объектно-реляционное отображение.

4.4. Разработка геоинформационной компоненты в составе системы маршрутизации.

4.5. Модуль решения задач маршрутизации проблемноориентированного программного обеспечения.

4.6 Визуальный интерфейс программного средства.

Введение диссертации (часть автореферата) на тему «Разработка алгоритмов многоальтернативной маршрутизации грузоперевозок в системах транспортной логистики на основе эволюционных методов»

Актуальность темы. Одним из способов экономии ресурсов при транспортировке грузов является применение систем поддержки принятия решений в области транспортной логистики. Актуальность данных задач вызвана тем, что до 50% всех затрат на логистику связано с транспортными издержками. Разработка программных пакетов, решающих задачи данной отрасли, требует проведения серьёзных научных исследований с целыо получения эффективных алгоритмов, пригодных для применения в повседневной практике. Одной из ключевых функций таких систем является возможность расчёта и построения эффективных маршрутов различного назначения на транспортной сети. Работа посвящена исследованию одной из таких задач, состоящей в оптимальной маршрутизации парка транспортных средств для выполнения заданного множества заявок.

Особенно актуально решение задач маршрутизации в условиях крупных городов и мегаполисов, в виду разветвленной транспортной сети и большого количества точек доставки. Основными задачами планирования доставки являются: задача нахождения оптимальных маршрутов (задача коммивояжера) и задача оптимальной загрузки транспортных средств (задача о ранце). Задача о коммивояжере и задача о ранце исследуются в теории комбинаторной оптимизации, и относятся к классу ЫР-сложных задач. На практике данные задачи оказываются еще сложнее, за счет выполнения доставки парком транспортных средств с ограниченной грузоподъемностью, нерегулярной средней скорости движения в течение дня, а также необходимости выполнения доставки «точно в срок». Данная задача является задачей маршрутизации транспорта. Исследованиями в данной области занимались М.И. Смирнов, Р.З. Хайруллин, А. О. Алексеев, И. И. Меламед, С. И. Сергеев, И. X. Сигал, 1 Ь. В1апк)п, в. .1еоп и др.

В связи со сложностью задачи маршрутизации, ее решение требует огромных вычислительных и временных затрат. Для проблемно4 ориентированных систем решения задач маршрутизации, важным фактором является время выполнения оптимизации. Вследствие чего, наиболее перспективными методами для решения данной задачи являются эволюционные алгоритмы.

Решение задачи маршрутизации позволяет решить следующие задачи планирования доставки:

- распределение транспортных средств по маршрутам с учетом их грузоподъемности;

- рациональная маршрутизация с учетом строгого соблюдения сроков доставки и нерегулярной средней скорости движения в течение дня;

- как следствие оптимального планирования доставки осуществляется минимизация количества используемых транспортных средств и связанных с ними расходов на эксплуатацию.

Для эффективного решения поставленной задачи необходима разработка специального математического и программного обеспечения. Помимо прочего, необходимо обеспечить визуальные средства просмотра и редактирования базы данных и электронной карты, настройки и отображения результатов работы алгоритмов. Специальное программное обеспечение решения задачи маршрутизации должно отвечать требованиям гибкости и масштабируемости.

Таким образом, в связи с вышеизложенным, актуальность темы продиктована необходимостью дальнейшего развития алгоритмов решения задач маршрутизации грузоперевозок в условиях сложноструктурированных транспортных систем, с учетом оптимального распределения транспортного ресурса по маршрутам доставки, а также обеспечением многоальтернативно-сти выбора.

Тематика диссертационной работы соответствует одному из основных научных направлений ФГБОУ ВПО «Воронежский государственный технический университет»: «Вычислительные комплексы и проблемноориентированные системы управления». 5

Цслыо работы является разработка алгоритмов для решения задачи маршрутизации внутригородских грузоперевозок, которая заключается в определении оптимального плана маршрутов доставки для парка транспортных средств с учетом ограничений грузоподъемности, нерегулярной средней скорости движения в течение дня и выполнения условия доставки «точно в срок».

На основе алгоритмического обеспечения необходима разработка проблемно-ориентированной системы оптимального планирования доставки.

Исходя из данной цели, в работе были определены следующие задачи исследования:

- анализ задач информационных систем транспортной логистики, функционирующих в пределах города, и методов их решения;

- разработка алгоритма решения задачи поиска оптимального пути между вершинами дорожного графа с нерегулярным весом ребер;

- разработка алгоритма нахождения глобального плана маршрутизации транспорта;

- разработка проблемно-ориентированного программного обеспечения многоальтернативной маршрутизации грузоперевозок.

Методы исследования. В работе использованы методы теории эволюционных алгоритмов, комбинаторной оптимизации, системного анализа. При разработке специального программного обеспечения использована теория построения баз данных, объектно-ориентированного программирования, параллельных вычислений, а также шаблоны проектирования.

Тематика работы соответствует п. 4 «Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации», п. 5 «Разработка специального математического и программного обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации» и п. 9 «Разработка проблемно-ориентированных систем управления, принятия решений и оптимизации технических, экономических, биологических, медицинских и социальб пых объектов» паспорта специальности 05.13.01 - «Системный анализ, управление и обработка информации».

Научная новизна. В работе получены следующие результаты, характеризующиеся научной новизной:

- модифицированный алгоритм А*, отличающийся работой на графе с нерегулярным весом ребер, контролем времени прохождения ребер, а также использованием метода контроля оценки эвристического приближения, за счет чего реализуется более направленный поиск, который повышает скорость работы алгоритма;

- модифицированный меметический алгоритм поиска глобального плана маршрутизации транспорта, отличающийся использованием локального поиска на основе алгоритма муравьиной колонии, метода введения «транспопуляций», динамической селекции и исключения неиспользуемых транспортных средств, что приводит к более быстрому и надежному решению;

- модифицированный муравьиный алгоритм в качестве алгоритма локального поиска, адаптированный под поставленную задачу, отличающийся использованием дорожного графа с нерегулярным весом ребер, и учитывающий необходимость доставки «точно в срок»; специальное математическое и программное проблемно-ориентированное обеспечение, отличающееся комплексным подходом к решению задач планирования доставки: выполнение оптимизации для парка автотранспортных средств ограниченной грузоподъемности, с учетом нерегулярной средней скорости движения в течение дня, и выполнения условия доставки «точно в срок».

Практическая значимость и внедрение результатов работы. В ходе диссертационного исследования разработано специальные математическое обеспечение и проблемно-ориентированная программная система решения задач оптимального планирования доставки, которая проводит оптимизацию формирования маршрутов, учитывая грузоподъемность транспортных средств, условия доставки «точно в срок» и нерегулярную среднюю скорость движения в течение дня.

Работа поддержана целевым грантом фонда содействия развитию малых форм предприятий в научно-технической сфере, в рамках программы «УМНИК» (проект №14306), и грантом администрации городского округа город Воронеж на проведение НИОКР, направленной на решение проблем городского хозяйства (договор №33).

Использование разработанной системы оптимизации позволит повысить экономическую эффективность транспортных компаний за счет сокращения издержек, а также повысить лояльность клиентов за счет реализации доставки «точно в срок».

Полученные в диссертации результаты используются в учебном процессе Воронежского государственного технического университета при чтении спецкурсов. Интерактивная система маршрутизации используются в ООО Научно-производственном предприятии «Орт» и ООО «Альфа-Инжиниринг».

Апробация работы. Основные результаты, полученные в диссертационной работе, докладывались и обсуждались на международных и всероссийских конференциях: Всероссийской конференции «Новые технологии в научных исследованиях, проектировании, управлении, производстве» (Воронеж, 2009.); VIII Всероссийской научно-практической конференции «Актуальные вопросы профессионального образования» (Воронеж, 2010.); Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых, секция «Информационные технологии» (Воронеж, 2011); XII Международной научно-методической конференции «Информатика: проблемы, методология, технологии.» (Воронеж, 2012); V Международной научно-производственной конференции «Новые технологии управления движением технических объектов» (Москва, 2012); а также на научных конференциях Воронежского государственного технического университета.

Публикации. Основные результаты диссертации опубликованы в 12 научных работах, в том числе 4 - в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве и приведенных а автореферате, лично соискателю принадлежат следующие результаты: [1] - алгоритм решения задачи поиска кратчайшего пути на карте между двух точек, [2] - разработка геоинформационной компоненты в составе подсистемы маршрутизации, [5] -анализ использования ГИС в составе АИС транспортной логистики, [6] - методы решения задач маршрутизации транспортной логистики, [3, 4, 7] - алгоритм решения задачи маршрутизации для парка автотранспортных средств, [8] - разработка специального программного обеспечения, [9] - муравьиный алгоритм как алгоритм локального поиска при решении задач маршрутизации. Материалы диссертации отражены также в 3 научно-технических отчетах НИОКР.

Структура и объем работы. Диссертация состоит из введения, четырех глав и заключения, изложенных на 133 страницах, списка литературы из 164 наименований, содержит 33 рисунка и 3 таблицы.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Плотников, Олег Александрович

Основные результаты работы состоят в следующем:

1. Проанализированы задачи и функции систем транспортной логистики, а также методы решения задач маршрутизации. На основе анализа выявлена необходимость разработки специального математического и программного проблемно-ориентированного обеспечения, решающего задачи многоальтернативной маршрутизации. Анализ географических информационных систем в составе информационных систем транспортной логистики показал необходимость реализации геоинформационной составляющей в составе системы маршрутизации.

2. Разработан алгоритм решения задачи поиска оптимального пути между вершинами дорожного графа с нерегулярным весом ребер. Данный алгоритм основан на алгоритме А*. Реализован метод контроля оценки эвристического приближения для ускорения поиска решения за счет более направленного поиска в глубину.

3. Разработан алгоритм поиска глобального плана задачи маршрутизации транспорта, основанный на использовании меметических алгоритмов. В ходе работы данный алгоритм использует метод введения «транспопуляций», метод динамической селекции и метод исключения неиспользуемых транспортных средств, для обеспечения более эффективной и надежной работы.

4. В качестве локального поиска модифицированного меметического алгоритма используется алгоритм муравьиной колонии, адаптированный к поставленной задаче, отличающийся использованием дорожного графа с не

118 регулярной средней скоростью в течение дня и учитывающий необходимость доставки «точно в срок».

5. На основе разработанных алгоритмов реализовано специальное программное обеспечение для решения задачи маршрутизации парка автотранспортных средств с ограничениями грузоподъемности при использовании дорожного графа с нерегулярным весом ребер с учетом условия доставки «точно в срок».

6.Помимо алгоритмов, решающих основную задачу, в системе маршрутизации реализована база данных и инструменты работы с ней, геоинформационная составляющая: визуализатор и редактор электронных карт, модуль визуальных настроек и отображения результатов работы модифицированного меметического алгоритма, модуль автоматического обновления. Специальное программное обеспечение построено с учетом архитектуры МУС и отвечает современным требованиям к программному обеспечению.

7. Зарегистрирован программный модуль «Подсистема создания интерактивной карты в системе маршрутизации автотранспорта» в ФАП ВНТИЦ, № 14353890.00440 и программный модуль «Интерактивная АИС комплексного решения задач транспортной логистикой» в ФГНУ ЦИТИС, № госрегистрации 2012618764 от 26.09.2012.

ЗАКЛЮЧЕНИЕ

Итогом диссертационного исследования стала разработка специального математического и программного проблемно-ориентированного обеспечения решения задач маршрутизации транспорта. Данная система решает задачи маршрутизации для парка автотранспортных средств с учетом ограничений грузоподъемности, нерегулярной средней скорости движения в течение дня, и выполнения условия доставки «точно в срок».

Список литературы диссертационного исследования кандидат технических наук Плотников, Олег Александрович, 2012 год

1. В.А. Гудков, Л.Б. Миротин A.B. Вельможин Теория организации и управления автомобильными перевозками: Логистический аспект формирования перевозочных процессов — Волгоград: Политехник, 2001.

2. М. А. Гайдес Общая теория систем (системы и системный анализ) //. — Винница, 2005. — с. 201.

3. К. И. Плужников С. В. Милославская Мультимодальные и интермодальные перевозки //, 2001.

4. Холопов К.В Экономика и организация внешнеторговых перевозок //. — Москва, 2000.

5. Тарабанько В.В. Левиков Г.А. Смешанные перевозки (состояние, проблемы, тенденции) //. — Москва, 2004.

6. Транспортное обеспечение внешнеторговых операций. Справочник. Кига 1 //. — Санкт-Петербург, 1998.

7. Е. Дрозд Интермодальные перевозки: мировой опыт // Гражданская авиация. — 2006

8. В. Никифоров Мультимодальные перевозки и транспортная логистика — Москва: РосКонсульт, 2007. — 272 с.

9. Николашин В.М. Сервис на транспорте: Учебное пособие — Москва: Academia, 2004.

10. Т. И. Семенович Автомобильные перевозки — s.l.: ИНФРА-М, 2009. — 224 с.

11. Л.Б. Миротин Учебник для транспортных вузов / Под общей редакцией Л.Б. Миротина //. — Москва, 2003. — с. 512.

12. В. В. Беднарский М. Е. Майборода Грузовые автомобильные перевозки — s.l.: Феникс, 2008. — 448 с.

13. Седюкевич В.Н Ванчукевич В.Ф. Автомобильные перевозки — s.l.: Дизайн ПРО, 1999.

14. Акулиничев В.М. Организация перевозок на промышленном транспорте — s.l.: Высшая школа, 1983.

15. Горев А.Э. Грузовые автомобильные перевозки — Москва: ИД Академия, 2008.

16. С. И. Коновалов, Ф. П. Касаткин Э. Ф. Касаткина Организация перевозочных услуг и безопасность транспортного процесса — Москва: Академический проект, 2005. — 352 с.

17. Гудков В.А, Миротин Л.Б., Куликов А.В. Вельможин А.В. Грузовые автомобильные перевозки — s.l.: Горячая линия Телеком, 2006. — 560 с.

18. Гаджинский А.М. Логистика: Учебник для высших и средних специальных учебных заведений.- 2-е изд. — Москва: Информационно-внедренческий центр "Маркетинг", 1999. — 228 с.

19. Логистический подход к управлению материальными потоками // сайт. URL: http://www.mybntu.com/techno/production/logisticheskij-podxod-k-upravleniyu-materialnymi-potokami.html (дата обращения: 05/11/2010).

20. Кузнецов В.Г. Николайчук В.Е. Теория и практика управления материальными потоками (логистическая концепция). Монография — Донецк: «КИТИС», 1999. — 413 с.

21. Т.В. Алесинская Основы логистики. Функциональные области логистического управления — Таганрог: Издательство ТТИ ЮФУ, 2010. — 116 с.

22. В.Г. Дегтяренко Основы логистики и маркетинга — Москва: Гардарика, 1996, —120 с.

23. Автоматизированная информационная система // Seopedia. URL: http://www.seobuilding.ru/wiki/aвтoмaтизиpoвaннaяинфopмaциoннaяcиcтeмa (дата обращения: 06/11/2010).

24. A Guide to Understanding Data Remanence in Automated Information Systems // The Rainbow Books. URL: http://www.fas.org/irp/nsa/rainbow/tg025-2.htm (дата обращения: 06/11/2010).

25. Ы.Э. Ташбаев Л.Б. Миротин Логистика для предпринимателя —- Москва: Инфра-М, 2002.

26. Маглинец Ю.А. Анализ требований к автоматизированным информационным системам: Учебное пособие — s.l.: s.n., 2008.

27. Раджив Мотвани, Джеффри Ульман Джон Хопкрофт Введение в теорию автоматов, языков и вычислений — Москва: Вильяме, 2002.

28. Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Томас X. Кормен Алгоритмы: построение и анализ. — 2-е изд. — Москва: Вильяме, 2006. — 1296 с.

29. Дональд Кнут Искусство программирования, том 1. Основные алгоритмы.3.е изд. — Москва: Вильяме, 2006. — 720 с.

30. Колмогоров А. Н. Теория информации и теория алгоритмов — Москва: Наука, 1987. —304 с.

31. Нагорный Н. М. Марков А. А. Теория алгоритмов, изд. 2 — Москва: ФАЗИС, 1996.

32. Подвальный С.Л. Обзор и классификация многоальтернативных систем // Информационные технологии моделирования и управления. — №74., Выпуск 2. — 2012. — с. 104-121

33. Подвальный С.Л. Многоальтернативные системы: обзор и классификация // Системы управления и информационные технологии. — №48., Выпуск 2.2012. —с. 4-13

34. Динамическое программирование // Яндекс словари. URL: Ьйр://з1оуап.уапс1ех.ги/Динамическоепрограммирование (дата обращения: 10/11/2011).

35. Динамическое программирование // Википедия. URL: http://ru.wikipedia.0rg/wiki^HHaMH4ecK0enp0rpaMMHp0BaHHe (дата обращения: 10/11/2011).

36. Christos Н. Papadimitriou, Umesh Vazirani Sanjoy Dasgupta Algorithms — 1e изд. — s.l.: McGraw-Hill Science/Engineering/Math, 2006. — 336 c.

37. Стенли P. Перечислительная комбинаторика — M: Мир, 1990. — 440 с.

38. Холл М. Комбинаторика — М: Мир, 1970. — 424 с.

39. Рыбников К. А. Введение в комбинаторный анализ. — 2-е изд. —М: Изд-воМГУ, 1985,—309 с.

40. А. Н. Land and A. G. Doig An automatic method of solving discrete programming problems — s.l.: s.n. — 497-520 c.

41. Murty K.G., Sweeney D.W., and Karel C. Little J.D.C. An algorithm for the traveling salesman problem // Operations Research. — 1963. — c. 972-989

42. Финкельштейн Ю.Ю. Корбут А.А. Дискретное программирование — M: Наука, 1969.

43. Jens Clausen Branch and Bound Algorithms Principles and Examples — s.l.: s.n., 1999.

44. R. E. Moore Global optimization to prescribed accuracy // Computers and Mathematics with Applications. — 1991. — c. 25-39

45. Stephen Boyd and Jacob Mattingley Branch and Bound Methods. Notes for EE364b, Stanford University //. — 2007

46. Michael A. Trick. Branch and Bound // Michael Trick's Operations Research Page. URL: http://mat.gsia.cmu.edu/classes/integer/nodel3.html (дата обращения: 15/11/2011).

47. B.J. Lageweg, Jan K. Lenstra, James B. Orlin, Leen Stougie Koen M.J. De Bontridder Branch-and-Bound Algorithms for the Test Cover Problem //.

48. D. S. Johnson M. R. Garey Computers and Intractability: A Guide to the Theoryof NP-completeness — San Francisco: Freeman, 1979.

49. J. K. Lenstra A. W. J. Kolen Combinatorics in operations research — Amsterdam: Elsevier, 1995.

50. Дикин И. И. 747-748. Итеративное решение задач линейного и квадратичного программирования //. —№174., Выпуск 4. — 1967

51. Акулич И.Л. Математическое программирование в примерах и задачах — М: Высшая школа, 1986. — 319 с.

52. J. Е. Beasley Advances in Linear and Integer Programming — Oxford: Oxford Science, 1996.

53. Katta G. Murty Linear programming — New York: John Wiley & Sons, Inc., 1983.

54. Evar D. Nering and Albert W. Tucker Linear Programs and Related Problems — s.l.: Academic Press, 1993.

55. Голыитейн Е.Г. Юдин Д.Б. Линейное программирование. Теория, методы и приложения — s.l.: s.n., 1969.

56. Д.Э.Хопкрофт, Д.Д.Ульман А.В.Ахо Структуры данных и алгоритмы — М: Вильяме, 2001.

57. Эвристический алгоритм // Википедия. URL: http://ru.wikipedia.org/wiki/Эвpиcтичecкийaлгopитм (дата обращения: 17/11/2011).

58. A. Yeo and A. Zverovich G. Gutin Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP // Discrete Applied Mathematics. — 2002. — c. 81-86

59. G. Bendall and F. Margot Greedy Type Resistance of Combinatorial Problems // Discrete Optimization. — №3. — 2006. — c. 288-298

60. Greedy algorithm // Wikipedia. URL: http://en.wikipedia.org/wiki/Greedyalgorithm (дата обращения: 18/11/2011).

61. Алфёрова З.В. Теория алгоритмов — М: Статистика, 1973.

62. Jon L. Bentley Experiments on traveling salesman heuristics // Proc. 1st ACM-SIAM Symp. Discrete Algorithms (SODA). — 1990. — c. 91-99

63. A. B. Kahng and S. Reda Match Twice and Stitch: A New TSP Tour Construction Heuristic // Operations Research Letters. — №6., Выпуск 32. — 2004. —с. 499-509

64. Shen Lin,В- W. Kernighan An Effective Heuristic Algorithm for the Traveling-Salesman Problem I I Operations Research. — №2., Выпуск 21. — 1973. — с. 498-516

65. К. Helsgaun An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic // European Journal of Operational Research. — №1., Выпуск 126. —2000,—с. 106-130

66. David S. Johnson,Lyle A. McGeoch The Traveling Salesman Problem: A Case Study in Local Optimization // Local Search in Combinatorial Optimization. — 1997. —c. 215-310

67. H.H. and Stutzle T. Hoos Stochastic Local Search: Foundations and Applications //. — 2005

68. Vijay Arya and Naveen Garg and Rohit Khandekar and Adam Meyerson and Kamesh Munagala and Vinayaka Pandit Local Search Heuristics for k-Median and Facility Location Problems // Siam Journal of Computing. —№3., Выпуск 33. — 2004

69. IO. А. Кочетов, А. В. Плясунов H. И. Глебов Методы оптимизации. Учебное пособие //. — 2000. — с. 105

70. The TSP package for R // The TSP package for R. URL: http://tsp.r-forge.r-project.org/ (дата обращения: 23/11/2011).

71. Gilbert Babin, Stéphanie Deneault, Gilbert Laportey Improvements to the Or-opt Heuristic for the Symmetric Traveling Salesman Problem — Montreal: Cahiers du GERAD, 2005.

72. D. L. Applegate и др. The Traveling Salesman Problem: A Computational Study — s.l.: Princeton University Press, 2006.

73. D. E. Goldberg Genetic Algorithms in Search, Optimization & Machine Learning — New York: Addison-Wesley, 1989.

74. E. L. Lawler и др. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization — s.l.: John Wiley & Sons, 1985.

75. Fogel David B. Evolutionary Computation: The Fossil Record — New York: IEEE Press, 1998.

76. Курейчик В. В., Курейчик В. М. Емельянов В. В. Теория и практика эволюционного моделирования —М: Физматлит, 2003. —432 с.

77. Лебедев Б. К., Лебедев О. К. Курейчик В. М. Поисковая адаптация: теория и практика — М: Физматлит, 2006. — 272 с.

78. Курейчик В. В., Курейчик В. М. Гладков Л. А. Генетические алгоритмы: Учебное пособие. — 2-е изд. — М: Физматлит, 2006. — 320 с.

79. Курейчик В. В, Курейчик В. М. и др. Гладков Л. А. Биоинспирированные методы в оптимизации: монография — М: Физматлит, 2009. — 384 с.

80. Пилиньский М., Рутковский Л. Рутковская Д. Нейронные сети, генетические алгоритмы и нечеткие системы. — 2-е изд. — М: Горячая линия-Телеком, 2008. — 452 с.

81. Wolfgang Banzhaf и др. Genetic Programming An Introduction — San Francisco: Morgan Kaufmann, 1998.

82. Robert R Bies и др. A Genetic Algorithm-Based, Hybrid Machine Learning Approach to Model Selection // Journal of Pharmacokinetics and Pharmacodynamics. — 2006. — c. 196-221

83. David В Fogel Evolutionary Computation: Toward a New Philosophy of Machine Intelligence. Third Edition — Piscataway: IEEE Press, 2006.

84. John Koza Genetic Programming: On the Programming of Computers by Means of Natural Selection — s.l.: MIT Press, 1992.

85. X. S. Chen и др. A Multi-Facet Survey on Memetic Computation // IEEE Transactions on Evolutionary Computation. — №5., Выпуск 15. — 2011. — с. 591-607

86. X. S. Chen, Y. S. Ong, M. H. Lim Research Frontier: Memetic Computation -Past, Present & Future // IEEE Computational Intelligence Magazine. — №2., Выпуск 5. — 2010. — с. 24-36

87. Kendall G. and Soubeiga E. and Cowling P. Choice function and random hyperheuristics // 4th Asia-Pacific Conference on Simulated Evolution and Learning SEAL. — 2002. — c. 667-671

88. Ong Y. S. and Keane A. J. 99-110 Meta-Lamarckian learning in memetic algorithms // IEEE Transactions on Evolutionary Computation. — №2., Выпуск 8. — 2004

89. Ong Y. S. and Lim M. H. and Zhu N. and Wong K. W. Classification of Adaptive Memetic Algorithms: A Comparative Study // IEEE Transactions on Systems Man and Cybernetics. —№1., Выпуск 36. — 2006. — с. 141-156

90. E. Ozcan Memes, Self-generation and Nurse Rostering // Lecture Notes in Computer Science. — 2007. — c. 85-104

91. E. Ozcan,C. Basaran "A Case Study of Memetic Algorithms for Constraint Optimization // Soft Computing: A Fusion of Foundations, Methodologies and Applications. — №8., Выпуск 13. —2009.— с. 871-882

92. S., Yang, Z. Areibi Effective memetic algorithms for VLSI design automation = genetic algorithms + local search + multi-level clustering //, Evolutionary Computation. — №3., Выпуск 12. — 2004. — с. 327-353

93. Chi-Keong Goh, Yew-Soon Ong, Kay Chen Tan Multi-Objective Memetic Algorithms — s.l.: Springer, 2009. — 416 c.

94. Ананий В. Левитин Алгоритмы: введение в разработку и анализ — М: Вильяме, 2006.

95. Е. W. Dijkstra A note on two problems in connexion with graphs // Numerische Mathematik. — 1959. — c. 269-271

96. F. Benjamin Zhan,Charles E. Noon Shortest Path Algorithms: An Evaluation Using Real Road Networks // Transportation Science. — №1., Выпуск 32. — 1998. —с. 65-73

97. Лорьер Ж.-Л. Системы искусственного интеллекта / Пер. с фр. и ред. В. Л. Стефанюка //. — 1991

98. Норвиг, П. Рассел С. Дж. Искусственный интеллект: современный подход = Artificial Intelligence: A Modern Approach / Пер. с англ. и ред. К. А. Птицына. — 2-е изд. — М: Вильяме, 1973.

99. R., Pearl, J Dechter Generalized best-first search strategies and the optimalityof A* //Journal of the ACM. —№32., Выпуск 3. — 1985.-е. 505 — 536127

100. Sven Koenig,Yaxin Liu, David Furcy Maxim Likhachev Incremental heuristic search in AI // AI Magazine. — №2., Выпуск 25. — 2004. — с. 99-112

101. Judea Pearl Heuristics: intelligent search strategies for computer problem solving//. — 1984

102. Patrick Lester. A* Pathfinding for Beginners // Policy Almanac. URL: http://www.policyalmanac.org/games/aStarTutorial.htm (дата обращения: 23/12/2011).

103. A* ALGORITHM TUTORIAL // I-Ieyes-Jones.com. URL: http://www.heyes-jones.com/astar.html (дата обращения: 15/12/2011).

104. S. Ghose, A. Acharya and S.C. de Sarkar P.P. Chakrabarti Heuristic search in restricted memory // Art. Intell. — 1989. — c. 197-221

105. R.E. Korf Depth-first iterative-deepening: An optimal admissible tree search //Art. Intell. —№1., Выпуск 27. — 1985. —с. 97

106. S. Ghosh, D.S. Nau, A.K. Pal and L. Kanal A. Mahanti Performance of IDA* on trees and graphs // 10th Nat. Conf. on Art. Int. — 1992. — c. 539-544

107. B.G. Patrick Binary iterative-deepening A*: An admissible generalization of IDA* search // Procs. 9th Canadian Conf. on Art. Intell. — 1992. — c. 54

108. S. Russell Effcient memory-bounded search methods", // Procs. European AI Conf. — 1992.—c. 1-5

109. Recursive Best First Search // Artifical Intelligence. URL: http://intelligence.worldofcomputing.net/ai-search/recursive-best-first-search.html (дата обращения: 17/11/2011).

110. Weixiong Zhang State Space Search: Algorithms, Complexity, Extensions, and Applications — s.l.: Springer, 1999.

111. Rong Zhou and Eric A. Hansen Memory-Bounded A* Graph Search // 15th International FLAIRS Conference Pensacola. — 2002

112. S. Russell Efficient memory-bounded search methods // In Proceedings of the 10th European Conference on Artificial intelligence. — 1992. — c. 1-5

113. SMA* // Wikipedia. URL: http://en.wikipedia.org/wiki/SMA* (дата обращения: 06/12/2011).

114. Шайтура С. В. Журкин И. Г. Геоинформационные системы — Москва: КУДИЦ-ПРЕСС, 2009. — 272 с.

115. Самардак А. С. Электронный учебник "Геоинформационные системы" //Электронный ресурс.

116. Подвальный Е.С. Плотников О.А. Использование геоинформационных систем: проблемы и перспективы развития // Новые технологии в научных исследованиях, проектировании, управлении, производстве, НТ-2009: Труды Всероссийской конференции. — с. 7-8

117. В. С. Тикунов Моделирование в картографии: Учебник — М: Изд-во МГУ, 1997.

118. Кулагин В.П., Тихонов А.Н., Цветков В.Я. Иванников А. Д. Геоинформатика — М: МАКС Пресс, 2001. — 349 с.

119. Кошкарев А.В., Тикунов B.C. и др. Капралов Е.Г. Основы геоинформатики —М: Издательский центр «Академия», 2004. —352 с.

120. Amit Patel. Implementation notes // Stanford Theory Group. URL: http://theory.stanford.edU/~amitp/GameProgramming/ImplementationNotes.html#s et-representation (дата обращения: 11/12/2011).

121. Kingsley Sage. Data Structures // University of Sussex. URL: http://www.informatics.susx.ac.ukycourses/dats/dats.html (дата обращения: 11/12/2011).

122. Robert Ronngren Rassul Acm A Comparative Study of Parallel and Sequential Priority Queue Algorithms //. — №7., Выпуск 2. — 1997. — с. 157— 209

123. Data Structures in С++ Case Study: Priority Queues // University of Minnesota Duluth. URL: http://www.d.umn.edu/~tcolburn/cs251 l/lectures/pqueue/pq0.htm (дата обращения: 11/12/2011).

124. Ricardo Baeza-Yates Gaston H. Gonnet. Handbook of Algorithms and Data Structures // Universidad de Chile. URL:http://users.dcc.uchile.cl/~rbaeza/handbook/hbook.html (дата обращения: 12/12/2011).

125. Class HashMap // Oracle. URL: http://docs.oracle.eom/javase/6/docs/api/java/util/HashMap.html (дата обращения: 12/02/2012).

126. Class Hashtable // Oracle. URL: http://d0cs.0racle.c0m/javase/6/d0cs/api/java/util/Hashtable.html (дата обращения: 12/02/2012).

127. Подвальный Е.С. Плотников O.A. Решение задачи поиска оптимального пути между двумя точками на графе с нерегулярным весом ребер // Вестник ВГТУ. — №8., Выпуск 6. — 2012. — с. 22-27

128. Андерсон Джеймс Дискретная математика и комбинаторика — Москва: Вильяме, 2006. — 960 с.

129. Hans Kellerer, Ulrich Pferschy, David Pisinger Knapsack Problems — s.l.: Springer, 2004.

130. Липский В. Комбинаторика для программиста — M: Мир, 1988. — 213 с.

131. Dan Graur,Wen-Hsiung Li Fundamentals of Molecular Evolution: Second Edition — Sunderland, Massachusetts: Sinauer Associates, Inc, 2000.

132. Thomas Stützle Marco Dorigo Ant colony optimization — s.l.: A Bradford book, 2004.

133. Штовба С.Д. Муравьиные алгоритмы // Математика в приложениях. — 2003. —с. 70-75

134. Батищев Д.И. Решение дискретных задач с помощью эволюционно-генетических алгоритмов — Н-Новгород: ННГУ, 2011. — 199 стр с.

135. Карл И. Вигерс Разработка требований к программному обеспечению — s.l.: Русская редакция, 2004.

136. Р. Хелм, Р. Джонсон, Дж. Влиссидес Э. Гамма Приемы объектно-ориентированного проектирования. Паттерны проектирования — Спб.: Питер, 2011.—368 с.

137. Сергей Рогачев. Обобщенный Model-View-Controller // RSDN. URL: http://rsdn.ru/article/patterns/generic-mvc.xml (дата обращения: 12/02/2012).

138. Мартин Фаулер Шаблоны корпоративных приложений — Москва: Вильяме, 2009. — 544 с.

139. Грег Уилсон Энди Орам Идеальный код — Спб: Питер, 2011. — 624 с.

140. Documentation // Oracle. URL: http://docs.oracle.com/ (дата обращения: 12/02/2012).

141. Netbeans // Netbeans. URL: http://netbeans.org/ (дата обращения: 12/02/2012).

142. Heiko Bock The Definitive Guide to NetBeans Platform 7 — s.l.: Apress, 2011.

143. Joshua Bloch Effective Java (2nd edition) — s.l.: Addison-Wesley, 2008. — 259-312 с.

144. С. J. Date Date on Database: Writings 2000-2006 — s.l.: Apress, 2006. — 566 c.

145. Ульман Дж., Уидом Дж. Гарсиа-Молина Г. Системы баз данных. Полный курс — Москва: Вильяме, 2003. — 1088 с.

146. Дейт К. Дж. Введение в системы баз данных. — 8-е изд. — Москва: Вильяме, 2005. — 1328 с.

147. Когаловский М.Р. Энциклопедия технологий баз данных — Москва: Финансы и статистика, 2002. — 800 с.

148. Бегг К. Коннолли Т. Базы данных. Проектирование, реализация и сопровождение. Теория и практика. — 3-е изд. — Москва: Вильяме, 2003. — 1436 с.

149. Кузнецов С. Д. Основы баз данных. — 2-е изд. — Москва: Интернет-университет информационных технологий БИНОМ. Лаборатория знаний, 2007. —484 с.

150. Ерош И. Л. Дискретная математика. Комбинаторика — СПб: СПбГУАП, 2001.

151. Оре О. Теория графов — М: Наука, 1968. — 336 с.

152. A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs // Math. Program. — 2005. — c. 251-282

153. Melanie Mitchell An Introduction to Genetic Algorithms — Cambridge: MIT Press, 1996.

154. R., Langdon, W. В., McPhee, N. F. Poli A Field Guide to Genetic Programming — s.l.: Lulu.com, freely available from the internet, 2008.

155. Lothar M Schmitt Theory of Genetic Algorithms // Theoretical Computer Science. —2001. — c. 1-61

156. Michael D Vose The Simple Genetic Algorithm: Foundations and Theory — Cambridge: MIT Press, 1999.

157. Роберт Седжвик Фундаментальные алгоритмы на С++. — 3-е изд. — Санкт-Петербург: ДиаСофт, 2002. — 688 с.

158. Silvano Martello,Paolo. Toth Knapsack problems: Algorithms and computer interpretations — s.l.: Wiley-Interscience, 1990.

159. A. Kulanoot, 47 (2001) L. Caccetta Computational Aspects of Hard Knapsack Problems // Nonlinear Analysis. — 2001. — c. 5547-5558

160. Подвальный E.C. Плотников О. А. Разработка алгоритма для комплексного решения задач АСУ транспортной логистики // Вестник ВГТУ. — №7., Выпуск П. —2011. —с. 102-105

161. Неравенство треугольника // Wikipedia. URL: http://ru.wikipedia.org/wiki/Hepaвeнcтвoтpeyгoльникa (дата обращения: 02/10/11).

162. Первый проректор ФГБОУ ВПО "ВГТУ"1. В. Сафонов 2012 г.м.п.1. АКТо внедрении результатов диссертационной работы в учебный процесс Воронежского государственного технического университета

163. Результаты диссертационной работы:

164. Вид внедрения результатов зарегистрированная программа для ЭВМкомплекс, машина, система, прибор, инструмент, технология,

165. Интерактивная АИС комплексного решения задач транспортной логистики»методика, зарегистрированные программы для ЭВМ, базы данных, и т.д.)

166. Область внедрения лабораторный практикум и лекционные курсы по дисциплине «Нелинейное программирование»; специальность «Вычислительные машины, комплексы, системы и сети»специальност!., дисциплина, вид учебной нагрузки)

167. Форма внедрения описание лабораторной работы, материалы лекционного курсаучебник, учебное пособие, курс лекций, м.у. и т.д., с указанием выходных данных)

168. Технический уровень НИР свидетельствоподаны заявки на объекты промышленной собственности, получены

169. ФГБУ ФИПСрег. №2012618764 от 26.09.2012г.положительные решения, патенты России, дипломы, медали и др. их № и дата)

170. Публикации по материалам НИР: 11 публикаций, из них 4 в изданиях из списка ВАКколичество, где опубликованы)

171. Эффект от внедрения (ожидаемый, фактический)а) социальный----------------улучшение условий труда, оздоровление окружающей среды и др.)б) годовой экономический эффект-----------тыс. руб.прописью)

172. При наличии годового экономического эффекта прилагается рассчет утвержденный Ректором и гл. Бухгалтером.1. Согласовано:

173. Руководитель основного научного направления Ш4?/Л »oq1. D9 2012 г.

174. Отдел методического обеспечения учебношдроцесса УМУ

175. ООО Научно-производственное предприятие1. Орт»394026, г. Воронеж, Московский пр. 22, тел/факс [phone] e-mail: [e-mail], www.ort-vrn.ru

176. Председатель комиссии Члены комиссии:

177. В настоящее время программная система «Интерактивная АИС комплексного решения задач транспортной логистики» находится на опытной эксплуатации.'1. Главный инженер1. Дорофеев А.Н.