Введение
Актуальность темы. Одним из способов экономии ресурсов при транспортировке грузов является применение систем поддержки принятия решений в области транспортной логистики. Актуальность данных задач вызвана тем, что до 50% всех затрат на логистику связано с транспортными издержками. Разработка программных пакетов, решающих задачи данной отрасли, требует проведения серьёзных научных исследований с целью получения эффективных алгоритмов, пригодных для применения в повседневной практике. Одной из ключевых функций таких систем является возможность расчёта и построения эффективных маршрутов различного назначения на транспортной сети. Работа посвящена исследованию одной из таких задач, состоящей в оптимальной маршрутизации парка транспортных средств для выполнения заданного множества заявок.
Особенно актуально решение задач маршрутизации в условиях крупных городов и мегаполисов, в виду разветвленной транспортной сети и большого количества точек доставки. Основными задачами планирования доставки являются: задача нахождения оптимальных маршрутов (задача коммивояжера) и задача оптимальной загрузки транспортных средств (задача о ранце). Задача о коммивояжере и задача о ранце исследуются в теории комбинаторной оптимизации, и относятся к классу NP-сложных задач. На практике данные задачи оказываются еще сложнее, за счет выполнения доставки парком транспортных средств с ограниченной грузоподъемностью, нерегулярной средней скорости движения в течение дня, а также необходимости выполнения доставки «точно в срок». Данная задача является задачей маршрутизации транспорта. Исследованиями в данной области занимались М.И. Смирнов, Р.З. Хайруллин, А. О. Алексеев, И. И. Меламед, С. И. Сергеев, И. X. Сигал, J. L. Blanton, G. Jeon и др.
В связи со сложностью задачи маршрутизации, ее решение требует огромных вычислительных и временных затрат. Для проблемно-ориентированных систем решения задач маршрутизации, важным фактором является время выполнения оптимизации. Вследствие чего, наиболее перспективными методами для решения данной задачи являются эволюционные алгоритмы.
Решение задачи маршрутизации позволяет решить следующие задачи планирования доставки:
- распределение транспортных средств по маршрутам с учетом их грузоподъемности;
- рациональная маршрутизация с учетом строгого соблюдения сроков доставки и нерегулярной средней скорости движения в течение дня;
- как следствие оптимального планирования доставки осуществляется минимизация количества используемых транспортных средств и связанных с ними расходов на эксплуатацию.
Для эффективного решения поставленной задачи необходима разработка специального математического и программного обеспечения. Помимо прочего, необходимо обеспечить визуальные средства просмотра и редактирования базы данных и электронной карты, настройки и отображения результатов работы алгоритмов. Специальное программное обеспечение решения задачи маршрутизации должно отвечать требованиям гибкости и масштабируемости.
Таким образом, в связи с вышеизложенным, актуальность темы продиктована необходимостью дальнейшего развития алгоритмов решения задач маршрутизации грузоперевозок в условиях сложноструктурированных транспортных систем, с учетом оптимального распределения транспортного ресурса по маршрутам доставки, а также обеспечением многоальтернативно- сти выбора.
Тематика диссертационной работы соответствует одному из основных научных направлений ФГБОУ ВПО «Воронежский государственный технический университет»: «Вычислительные комплексы и проблемно-
ориентированные системы управления».
Целью работы является разработка алгоритмов для решения задачи маршрутизации внутригородских грузоперевозок, которая заключается в определении оптимального плана маршрутов доставки для парка транспортных средств с учетом ограничений грузоподъемности, нерегулярной средней скорости движения в течение дня и выполнения условия доставки «точно в срок».
На основе алгоритмического обеспечения необходима разработка проблемно-ориентированной системы оптимального планирования доставки.
Исходя из данной цели, в работе были определены следующие задачи исследования:
- анализ задач информационных систем транспортной логистики, функционирующих в пределах города, и методов их решения;
- разработка алгоритма решения задачи поиска оптимального пути между вершинами дорожного графа с нерегулярным весом ребер;
- разработка алгоритма нахождения глобального плана маршрутизации транспорта;
- разработка проблемно-ориентированного программного обеспечения многоальтернативной маршрутизации грузоперевозок.
Методы исследования. В работе использованы методы теории эволюционных алгоритмов, комбинаторной оптимизации, системного анализа. При разработке специального программного обеспечения использована теория построения баз данных, объектно-ориентированного программирования, параллельных вычислений, а также шаблоны проектирования.
Тематика работы соответствует п. 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 таблицы.
В первой главе показана необходимость использования информационно-компьютерной поддержки для эффективного решения задачи маршрутизации транспорта. Такой поддержкой выступают информационные системы. Проведен анализ задач и требований, предъявляемых к современным информационным системам транспортной логистики.
Ставится задача нахождения оптимального по заданному критерию (минимальному суммарному времени, минимальной суммарной стоимости, максимальному коэффициенту загрузки транспортных средств) плана маршрутов для парка автотранспортных средств с ограничениями грузоподъемности на ориентированном графе с нерегулярным весом ребер с учетом выполнения концепции доставки «точно в срок».
Показано, что для решения задачи маршрутизации, необходимо решение следующих задач:
- разработка алгоритма нахождения глобального плана доставки для парка транспортных средств;
- разработка алгоритма локального поиска в составе алгоритма глобального поиска;
- разработка алгоритма нахождения оптимального пути между вершинами дорожного графа с нерегулярным весом ребер при прокладке маршрутов глобального плана доставки.
Вследствие необходимости решения указанных задач был проведен системный анализ точных и приближенных методов решения задач маршрутизации транспортной логистики. Сделаны выводы о целесообразности использования меметических алгоритмов. Проанализированы алгоритмы нахождения оптимального пути между вершинами дорожного графа. Оптимальным алгоритмом является алгоритм А* и его модификации. Также показана необходимость реализации геоинформационной компоненты в составе подсистемы оптимизации планирования доставки.
Для обеспечения надежности работы алгоритмов, необходимо, чтобы структура специального программного обеспечения отвечала принципам многоальтернативных систем (Подвальный С.Л.), т.е. была построена с использованием параллельности, многоальтернативности и многокритериальное™ выбора.
В конце главы сформулированы цели и задачи исследования.
Вторая глава посвящена разработке алгоритма, решающего задачу нахождения оптимального пути между вершинами дорожного графа с нерегулярным весом ребер, определяемым динамикой пропускной способности дорожной сети распределенной по времени суток.
При построении глобального плана доставки необходимо каждую итерацию строить маршруты для каждого транспортного средства, учитывая нерегулярную скорость движения по дорогам в течение дня. За счет того, что основной алгоритм постоянно обращается к алгоритму построения маршрутов, последний является «узким местом» процедуры оптимизации. Следовательно, для эффективного решения задачи маршрутизации необходима оптимизация алгоритма нахождения пути между вершинами дорожного графа с нерегулярным весом ребер.
Данный алгоритм построен на базе алгоритма А*, как наилучшем алгоритме для поиска оптимальных путей в различных пространствах, в частности на дорожном графе. А* является полным в том смысле, что он всегда находит решение, если таковое существует.
Исследованы различные структуры данных, которые могут применяться в работе алгоритма А*. Приведена их сравнительная характеристика. В алгоритме использованы несинхронизированные хэш-таблицы, как наиболее подходящие структуры данных в плане скорости работы, для поставленной задачи.
Алгоритм А* оптимизирован для поставленной задачи нахождения оптимального пути между двух точек на карте с ограничениями и нерегулярной средней скоростью в течение дня.
Реализован метод оптимизации графа перед началом работы алгоритма, который заключается в замене нескольких последовательных ребер с одинаковыми значениями атрибутов (например, изогнутая дорога) одним ребром.
Очередь сортировки узлов организована по принципу LTFO для организации поиска в глубину.
Исследована реализация двунаправленного поиска, однако она показала отрицательные результаты за счет введения дополнительных структур данных.
Реализован метод контроля оценки эвристического приближения, за счет чего выполняется более направленный поиск.
Результаты работы алгоритма А* проанализированы для простого и сложного случая. Оценки результатов сведены в таблицу.
В третьей главе проводится исследование модифицированного меме- тического алгоритма для решения задачи маршрутизации грузоперевозок.
В данной главе выполнена математическая постановка задачи маршрутизации. Она объединяет в себе задачу о коммивояжере, задачу о ранце, а также использует ориентированный граф с нерегулярным весом ребер и условие доставки «точно в срок».
Также в третьей главе выполнена формализация задачи таким образом, чтобы её решение было закодировано в виде генотипа. Выбрана фиксированная длина генотипа и равна количеству заявок на доставку. Размер популяции является фиксированным. Начальная популяция генерируется случайным образом. Для оценки решения в текущем поколении популяции мы используем оценку приспособленности наиболее приспособленной особи.
Оптимизация может проводиться по одному из критериев:
- минимальное время, необходимое на выполнение заявок;
- минимальный общий расход топлива транспортных средств;
- максимальный коэффициент загрузки транспортных средств.
Выбор того или иного критерия оптимизации производится лицом
принимающим решение с помощью соответствующего визуального интерфейса.
Для достижения лучших характеристик надежности и времени сходимости при решении задачи маршрутизации транспорта были использованы несколько операторов скрещивания (скрещивание в случайном соотношении, 1-точечный кроссовер; скрещивание в интервале, 2-точечный кроссовер; скрещивание выбором случайных хромосом n-точечный кроссовер, п задается генератором случайных чисел), оператор мутации, локальный поиск на основе алгоритма муравьиной колонии, динамическая селекция особей, метод исключения неиспользуемых транспортных средств, метод введения «транспопуляций».
Разработан алгоритм муравьиной колонии, как алгоритм локального поиска для меметического алгоритма. Муравьиный алгоритм адаптирован к поставленной задаче при использовании дорожного графа с нерегулярной средней скоростью движения в течение дня.
Реализован метод использования транспопуляций. Если оценка приспособленности не улучшается некоторое количество поколений , то на следующем поколении формируется несколько новых популяций, которые характеризуются малым количеством поколений. Тем самым мы вносим в основную популяцию дополнительное разнообразие.
Реализован метод исключения неиспользуемых автотранспортных средств. Так, если на протяжении нескольких поколений лучшее решение содержит транспортные средства, которые не выполняют ни одной заявки, то эти транспортные средства выводятся из рассмотрения в следующих поколениях.
Реализован метод динамической селекции особей для следующего поколения. Реализовано два метода селекции: селекция выбором наиболее приспособленных особей и турнирный отбор.
Модифицированный меметический алгоритм протестирован для различных значений размера популяции и количества поколений. Результаты сведены в таблицу.
В четвертой главе рассматриваются особенности программной реализации разработанных алгоритмов решения задач маршрутизации транспортной логистики.
Проанализированы входные и выходные данные для системы оптимизации грузоперевозок, на основе данного анализа спроектирована база данных программного средства.
Разработана модульная структура программного средства с учетом архитектуры MVC. Основные классы программного обеспечения вынесены в отдельный модуль и могут быть использованы как API для взаимодействия с разработанной подсистемой маршрутизации. Кроме того, класс, взаимодействующий с БД, работает как служба и может быть доступен из любой точки программной системы.
В подсистеме маршрутизации реализована геоинформационная составляющая, отвечающая за визуализацию решения задачи и обеспечивающая возможность редактирования картографических данных. Изучен польский формат описания картографических данных и реализован интерфейс взаимодействия с данным форматом.
Разработан модуль маршрутизации, который решает поставленные задачи планирования грузоперевозок и имеет визуальный интерфейс взаимодействия с пользователем.
Для повышения скорости работы меметического алгоритма в модуле оптимизации применяются методы параллельных вычислений. По результатам тестов сделан вывод, что оптимальное количество потоков равно количеству ядер процессора. Это также подтверждается и другими разработчиками программного обеспечения при решении различного рода задач.
Разработанная система оптимизации планирования грузоперевозок реализована на языке Java и содержит механизмы встраивания в промышленные системы, в том числе ERP-системы такие как, например, Compiere и Openbravo.
В заключении формулируются научные и практические результаты диссертационного исследования.
СПИСОК ЛИТЕРАТУРЫ
1. В.А. Гудков, Л.Б. Миротин А.В. Вельможин Теория организации и
управления автомобильными перевозками: Логистический аспект формирования перевозочных процессов — Волгоград: Политехник, 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. Автоматизированная информационная система
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. В.А. Гудков, Л.Б. Миротин А.В. Вельможин Технология, организация и управление грузовыми автомобильными перевозками — s.l.: Политехник, 2000.
26. «Бизнес и логистика-2001»: Сборник материалов Московского Международного Логистического Форума //. — Москва, 2001.
27. Ы.Э. Ташбаев Л.Б. Миротин Логистика для предпринимателя — Москва: Инфра-М, 2002.
28. Маглинец Ю.А. Анализ требований к автоматизированным информационным системам: Учебное пособие — s.l.: s.n., 2008.
29. Раджив Мотвани, Джеффри Ульман Джон Хопкрофт Введение в теорию автоматов, языков и вычислений — Москва: Вильямс, 2002.
30. Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Томас X. Кормен Алгоритмы: построение и анализ. — 2-е изд. — Москва: Вильямс, 2006. — 1296 с.
31. Дональд Кнут Искусство программирования, том 1. Основные алгоритмы.
— 3-е изд. — Москва: Вильямс, 2006. — 720 с.
32. Колмогоров А. Н. Теория информации и теория алгоритмов — Москва: Наука, 1987. —304 с.
33. Нагорный Н. М. Марков А. А. Теория алгоритмов, изд. 2 — Москва: ФАЗИС, 1996.
34. Подвальный С.Л. Обзор и классификация многоальтернативных систем // Информационные технологии моделирования и управления. — №74., Выпуск 2. — 2012. — с. 104-121
35. Подвальный С.Л. Многоальтернативные системы: обзор и классификация // Системы управления и информационные технологии. — №48., Выпуск 2.
— 2012. —с. 4-13
36. Динамическое программирование // [Яндекс словари] URL: ЬЦр://з1оуап.уапс1ех.ги/Динамическое_программирование (дата обращения: 10/11/2011).
37. Динамическое программирование
38. Christos Н. Papadimitriou, Umesh Vazirani Sanjoy Dasgupta Algorithms — 1- e изд. — s.l.: McGraw-Hill Science/Engineering/Math, 2006. — 336 c.
39. Стенли P. Перечислительная комбинаторика — M: Мир, 1990. — 440 с.
40. Холл М. Комбинаторика — М: Мир, 1970. — 424 с.
41. Рыбников К. А. Введение в комбинаторный анализ. — 2-е изд. —М: Изд- воМГУ, 1985,—309 с.
42. А. Н. Land and A. G. Doig An automatic method of solving discrete programming problems — s.l.: s.n. — 497-520 c.
43. 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
44. Финкелыптейн Ю.Ю. Корбут А.А. Дискретное программирование — M: Наука, 1969.
45. Jens Clausen Branch and Bound Algorithms - Principles and Examples — s.l.: s.n., 1999.
46. R. E. Moore Global optimization to prescribed accuracy // Computers and Mathematics with Applications. — 1991. — c. 25-39
47. Stephen Boyd and Jacob Mattingley Branch and Bound Methods. Notes for БЕЗ64b, Stanford University //. — 2007
48. 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).
49. 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 //.
50. D. S. Johnson M. R. Garey Computers and Intractability: A Guide to the Theoryof NP-completeness — San Francisco: Freeman, 1979.
51. J. K. Lenstra A. W. J. Kolen Combinatorics in operations research — Amsterdam: Elsevier, 1995.
52. Дикин И. И. 747-748. Итеративное решение задач линейного и квадратичного программирования //. —№174., Выпуск 4. — 1967
53. Акулич И.Л. Математическое программирование в примерах и задачах — М: Высшая школа, 1986. — 319 с.
54. J. Е. Beasley Advances in Linear and Integer Programming — Oxford: Oxford Science, 1996.
55. Katta G. Murty Linear programming — New York: John Wiley & Sons, Inc., 1983.
56. Evar D. Nering and Albert W. Tucker Linear Programs and Related Problems — s.l.: Academic Press, 1993.
57. Гольштейн Е.Г. Юдин Д.Б. Линейное программирование. Теория, методы и приложения — s.l.: s.n., 1969.
58. Д.Э.Хопкрофт, Д.Д.Ульман А.В.Ахо Структуры данных и алгоритмы — М: Вильямс, 2001.
59. Эвристический алгоритм // [Википедия] URL: http://ru.wikipedia.org/wiki/3BpncTH4ecKHh_anropHTM (дата обращения: 17/11/2011).
60. 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
61. G. Bendall and F. Margot Greedy Type Resistance of Combinatorial Problems // Discrete Optimization. — №3. — 2006. — c. 288-298
62. Greedy algorithm// [Wikipedia] URL: http://en.wikipedia.org/wiki/Greedy_algorithm (дата обращения: 18/11/2011).
63. Алфёрова З.В. Теория алгоритмов — М: Статистика, 1973.
64. Jon L. Bentley Experiments on traveling salesman heuristics // Proc. 1st ACM- SIAM Symp. Discrete Algorithms (SODA). — 1990. — c. 91-99
65. A. B. Kahng and S. Reda Match Twice and Stitch: A New TSP Tour Construction Heuristic // Operations Research Letters. — №6., Выпуск 32. — 2004. —c. 499-509
66. Shen Lin,В- W. Kernighan An Effective Heuristic Algorithm for the Traveling- Salesman Problem // Operations Research. — №2., Выпуск 21. — 1973. — c. 498-516
67. K. Helsgaun An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic // European Journal of Operational Research. — №1., Выпуск 126. —2000.—c. 106-130
68. 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
69. H.H. and Stutzle T. Hoos Stochastic Local Search: Foundations and Applications //. — 2005
70. 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
71. IO. А. Кочетов, А. В. Плясунов H. И. Глебов Методы оптимизации. Учебное пособие //. — 2000. — с. 105
72. The TSP package for R // [The TSP package for R] URL: http://tsp.r-forge.r- project.org/ (дата обращения: 23/11/2011).
73. Gilbert Babin, Stephanie Deneault, Gilbert Laportey Improvements to the Or- opt Heuristic for the Symmetric Traveling Salesman Problem — Montreal: Cahiers du GERAD, 2005.
74. D. L. Applegate и др. The Traveling Salesman Problem: A Computational Study — s.l.: Princeton University Press, 2006.
75. D. E. Goldberg Genetic Algorithms in Search, Optimization & Machine Learning — New York: Addison-Wesley, 1989.
76. E. L. Lawler и др. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization — s.l.: John Wiley & Sons, 1985.
77. Fogel David B. Evolutionary Computation: The Fossil Record — New York: IEEE Press, 1998.
78. Курейчик В. В., Курейчик В. М. Емельянов В. В. Теория и практика эволюционного моделирования —М: Физматлит, 2003. —432 с.
79. Лебедев Б. К., Лебедев О. К. Курейчик В. М. Поисковая адаптация: теория и практика — М: Физматлит, 2006. — 272 с.
80. Курейчик В. В., Курейчик В. М. Гладков Л. А. Генетические алгоритмы: Учебное пособие. — 2-е изд. — М: Физматлит, 2006. — 320 с.
81. Курейчик В. В, Курейчик В. М. и др. Гладков Л. А. Биоинспирированные методы в оптимизации: монография — М: Физматлит, 2009. — 384 с.
82. Пилиньский М., Рутковский Л. Рутковская Д. Нейронные сети, генетические алгоритмы и нечеткие системы. — 2-е изд. — М: Горячая линия-Телеком, 2008. — 452 с.
83. Wolfgang Banzhaf и др. Genetic Programming - An Introduction — San Francisco: Morgan Kaufmann, 1998.
84. Robert R Bies и др. A Genetic Algorithm-Based, Hybrid Machine Learning Approach to Model Selection // Journal of Pharmacokinetics and Pharmacodynamics. — 2006. — c. 196-221
85. David В Fogel Evolutionary Computation: Toward a New Philosophy of Machine Intelligence. Third Edition — Piscataway: IEEE Press, 2006.
86. John Koza Genetic Programming: On the Programming of Computers by Means of Natural Selection — s.l.: MIT Press, 1992.
87. X. S. Chen и др. A Multi-Facet Survey on Memetic Computation // IEEE Transactions on Evolutionary Computation. — №5., Выпуск 15. — 2011. — c. 591-607
88. X. S. Chen, Y. S. Ong, M. H. Lim Research Frontier: Memetic Computation - Past, Present & Future // IEEE Computational Intelligence Magazine. — №2., Выпуск 5. — 2010. — c. 24-36
89. 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
90. Ong Y. S. and Keane A. J. 99-110 Meta-Lamarckian learning in memetic algorithms // IEEE Transactions on Evolutionary Computation. — №2., Выпуск 8. — 2004
91. 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. — c. 141-156
92. E. Ozcan Memes, Self-generation and Nurse Rostering // Lecture Notes in Computer Science. — 2007. — c. 85-104
93. 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. — c. 871-882
94. S., Yang, Z. Areibi Effective memetic algorithms for VLSI design automation = genetic algorithms + local search + multi-level clustering //, Evolutionary Computation. — №3., Выпуск 12. — 2004. — c. 327-353
95. Chi-Keong Goh, Yew-Soon Ong, Kay Chen Tan Multi-Objective Memetic Algorithms — s.l.: Springer, 2009. — 416 c.
96. Ананий В. Левитин Алгоритмы: введение в разработку и анализ — М: Вильямс, 2006.
97. Е. W. Dijkstra A note on two problems in connexion with graphs // Numerische Mathematik. — 1959. — c. 269-271
98. F. Benjamin Zhan,Charles E. Noon Shortest Path Algorithms: An Evaluation Using Real Road Networks // Transportation Science. — №1., Выпуск 32. — 1998. —c. 65-73
99. Лорьер Ж.-Л. Системы искусственного интеллекта / Пер. с фр. и ред. В. Л. Стефанюка //. — 1991
100. Норвиг, П. Рассел С. Дж. Искусственный интеллект: современный подход = Artificial Intelligence: A Modem Approach / Пер. с англ, и ред. К. А. Птицына. — 2-е изд. — М: Вильямс, 1973.
101. R., Pearl, J Dechter Generalized best-first search strategies and the optimality of A* // Journal of the ACM. —№32., Выпуск 3. — 1985. — c. 505 — 536 127
102. Sven Koenig,Yaxin Liu, David Furcy Maxim Likhachev Incremental heuristic search in AI11AI Magazine. — №2., Выпуск 25. — 2004. — c. 99-112
103. Judea Pearl Heuristics: intelligent search strategies for computer problem solving//. — 1984
104. Patrick Lester. A* Pathfinding for Beginners // [Policy Almanac] URL: http://www.policyalmanac.org/games/aStarTutorial.htm (дата обращения: 23/12/2011).
105. A* ALGORITHM TUTORIAL // [Heyes-Jones.com] URL: http://www.heyes-jones.com/astar.html (дата обращения: 15/12/2011).
106. S. Ghose, A. Acharya and S.C. de Sarkar P.P. Chakrabarti Heuristic search in restricted memory // Art. Intell. — 1989. — c. 197-221
107. R.E. Korf Depth-first iterative-deepening: An optimal admissible tree search //Art. Intell. —№1, Выпуск 27.— 1985. — c. 97
108. 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
109. B.G. Patrick Binary iterative-deepening A*: An admissible generalization of IDA* search // Procs. 9th Canadian Conf. on Art. Intell. — 1992. — c. 54
110. S. Russell Effcient memory-bounded search methods", // Procs. European AI Conf. —1992.—c. 1-5
111. Recursive Best First Search // [Artifical Intelligence] URL: http://intelligence.worldofcomputing.net/ai-search/recursive-best-first-search.html (дата обращения: 17/11/2011).
112. Weixiong Zhang State Space Search: Algorithms, Complexity, Extensions, and Applications — s.l.: Springer, 1999.
113. Rong Zhou and Eric A. Hansen Memory-Bounded A* Graph Search // 15th International FLAIRS Conference Pensacola. — 2002
114. S. Russell Efficient memory-bounded search methods // In Proceedings of the 10th European Conference on Artificial intelligence. — 1992. — c. 1-5
115. SMA* // [Wikipedia] URL: http://en.wikipedia.org/wiki/SMA* (дата обращения: 06/12/2011).
116. Шайтура С. В. Журкин И. Г. Геоинформационные системы — Москва: КУДИЦ-ПРЕСС, 2009. — 272 с.
117. Самардак А. С. Электронный учебник "Геоинформационные системы" //[Электронный ресурс].
118. Подвальный Е.С. Плотников О.А. Использование геоинформационных систем: проблемы и перспективы развития // Новые технологии в научных исследованиях, проектировании, управлении, производстве, НТ-2009: Труды Всероссийской конференции.. — с. 7-8
119. В. С. Тикунов Моделирование в картографии: Учебник — М: Изд-во МГУ, 1997.
120. Кулагин В.П., Тихонов А.Н., Цветков В.Я. Иванников А.Д. Геоинформатика — М: МАКС Пресс, 2001. — 349 с.
121. Кошкарев А.В., Тикунов В.С. и др. Капралов Е.Г. Основы геоинформатики —М: Издательский центр «Академия», 2004. —352 с.
122. Amit Patel. Implementation notes // [Stanford Theory Group] URL: http://theory.stanford.edU/~amitp/GameProgramming/ImplementationNotes.html#s et-representation (дата обращения: 11/12/2011).
123. Kingsley Sage. Data Structures // [University of Sussex] URL: http://www.informatics.susx.ac.uk/courses/dats/dats.html (дата обращения: 11/12/2011).
124. Robert Ronngren Rassul Acm A Comparative Study of Parallel and Sequential Priority Queue Algorithms //. — №7., Выпуск 2. — 1997. — с. 157— 209
125. Data Structures in C++ Case Study: Priority Queues // [University of Minnesota Duluth] URL: http://www.d.umn.edu/~tcolburn/cs251 l/lectures/pqueue/pq_0.htm (дата
обращения: 11/12/2011).
126. 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).
127. Class I-IashMap //[Oracle] URL: http://docs.oracle.eom/javase/6/docs/api/java/util/HashMap.htm(дата обращения: 12/02/2012).
128. Class Hashtable // Oracle] URL:http://docs.oracle.eom/javase/6/docs/api/java/util/Hashtable.html (дата обращения: 12/02/2012).
129. Подвальный E.C. Плотников O.A. Решение задачи поиска оптимального пути между двумя точками на графе с нерегулярным весом ребер // Вестник ВГТУ. — №8., Выпуск 6. — 2012. — с. 22-27
130. Андерсон Джеймс Дискретная математика и комбинаторика — Москва: Вильямс, 2006. — 960 с.
131. Hans Kellerer, Ulrich Pferschy, David Pisinger Knapsack Problems — s.l.: Springer, 2004.
132. Липский В. Комбинаторика для программиста — М: Мир, 1988. — 213 с.
133. Dan Graur,Wen-Hsiung Li Fundamentals of Molecular Evolution: Second Edition — Sunderland, Massachusetts: Sinauer Associates, Inc, 2000.
134. Thomas Sttitzle Marco Dorigo Ant colony optimization — s.l.: A Bradford book, 2004.
135. Штовба С.Д. Муравьиные алгоритмы // Математика в приложениях. — 2003. —с. 70-75
136. Батищев Д.И. Решение дискретных задач с помощью эволюционногенетических алгоритмов — Н-Новгород: ННГУ, 2011. — 199 стр с.
137. Подвальный Е.С. Плотников О.А. Применение муравьиных алгоритмов для решения задачи коммивояжера при управлении движением парка транспортных средств // Сборник трудов 5-ой Международной научно- производственной конференции «Новые технологии управления движением технических объектов». — 2012. — с. 24-27
138. Карл И. Вигерс Разработка требований к программному обеспечению — s.l.: Русская редакция, 2004.
139. Р. Хелм, Р. Джонсон, Дж. Влиссидес Э. Гамма Приемы объектно- ориентированного проектирования. Паттерны проектирования — Спб.: Питер, 2011. —-368 с.
140. Сергей Рогачев. Обобщенный Model-View-Controller // [RSDN] URL: http://rsdn.ru/article/patterns/generic-mvc.xml (дата обращения: 12/02/2012).
141. Мартин Фаулер Шаблоны корпоративных приложений — Москва: Вильямс, 2009. — 544 с.
142. Грег Уилсон Энди Орам Идеальный код — Спб: Питер, 2011. — 624 с.
143. Documentation // [Oracle] URL: http://docs.oracle.com/ (дата обращения: 12/02/2012).
144. Netbeans // [Netbeans] URL: http://netbeans.org/ (дата обращения: 12/02/2012).
145. Heiko Bock The Definitive Guide to NetBeans Platform 7 — s.l.: Apress,2011.
146. Joshua Bloch Effective Java (2nd edition) — s.l.: Addison-Wesley, 2008. — 259-312 c.
147. C. J. Date Date on Database: Writings 2000-2006 — s.l.: Apress, 2006. — 566 c.
148. Ульман Дж., Уидом Дж. Гарсиа-Молина Г. Системы баз данных. Полный курс — Москва: Вильямс, 2003. — 1088 с.
149. Дейт К. Дж. Введение в системы баз данных. — 8-е изд. — Москва: Вильямс, 2005. — 1328 с.
150. Когаловский М.Р. Энциклопедия технологий баз данных — Москва: Финансы и статистика, 2002. — 800 с.
151. Бегг К. Коннолли Т. Базы данных. Проектирование, реализация и сопровождение. Теория и практика. — 3-е изд. — Москва: Вильямс, 2003. — 1436 с.
152. Кузнецов С. Д. Основы баз данных. — 2-е изд. — Москва: Интернет- университет информационных технологий БИНОМ. Лаборатория знаний, 2007. —484 с.
153. Ерош И. Л. Дискретная математика. Комбинаторика — СПб: СПбГУАП, 2001.
154. Оре О. Теория графов — М: Наука, 1968. — 336 с.
155. A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs // Math. Program. — 2005. — c. 251-282
156. Melanie Mitchell An Introduction to Genetic Algorithms — Cambridge: MIT Press, 1996.
157. R., Langdon, W. B., McPhee, N. F. Poli A Field Guide to Genetic Programming — s.l.: Lulu.com, freely available from the internet, 2008.
158. Lothar M Schmitt Theory of Genetic Algorithms // Theoretical Computer Science.—2001. — c. 1-61
159. Lothar M Schmitt Theory of Genetic Algorithms II: models for genetic operators over the string-tensor representation of populations and convergence to global optima for arbitrary fitness function under scaling // Theoretical Computer Science. — 2004. — с. 181 -231
160. Michael D Vose The Simple Genetic Algorithm: Foundations and Theory — Cambridge: MIT Press, 1999.
161. Роберт Седжвик Фундаментальные алгоритмы на C++. — 3-е изд. — Санкт-Петербург: ДиаСофт, 2002. — 688 с.
162. Silvano Martello,Paolo. Toth Knapsack problems: Algorithms and computer interpretations — s.l.: Wiley-Interscience, 1990.
163. A. Kulanoot, 47 (2001) L. Caccetta Computational Aspects of Hard Knapsack Problems // Nonlinear Analysis. — 2001. — c. 5547-5558
164. Подвальный E.C. Плотников О. А. Разработка алгоритма для комплексного решения задач АСУ транспортной логистики // Вестник ВГТУ. — №7., Выпуск 11. —2011. —с. 102-105
165. Неравенство треугольника // [Wikipedia] URL: http://ru.wikipedia.org/wiki/HepaBeHCTBo_TpeyroHbHHKa (дата обращения: 02/10/11).
166. Подвальный E.C. Плотников О.А. Методы оптимизации, применяемые для решения задач о коммивояжере при управлении муниципальным транспортом // Актуальные вопросы профессионального образования: Материалы VIII Всероссийской научно-практической конференции. — 2010. — с. 46-49