РАЗРАБОТКА АЛГОРИТМОВ МНОГО АЛЬТЕРНАТИВНОЙ МАРШРУТИЗАЦИИ ГРУЗОПЕРЕВОЗОК В СИСТЕМАХ ТРАНСПОРТНОЙ ЛОГИСТИКИ НА ОСНОВЕ ЭВОЛЮЦИОННЫХ МЕТОДОВ

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

Характеристики

Автор Плотников Олег Александрович
Тип Кандидатская диссертация
Специальность Системный анализ, управление и обработка информации (технические и медицинские системы)

Введение........................................................................................................................... 4

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

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

транспортной логистики.................................................................................... 16

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

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

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

дорожного графа................................................................................................ 31

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

информационных систем транспортной логистики....................................... 37

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

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

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

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

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

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

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

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

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

поиска.................................................................................................................. 84

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

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

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

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

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

маршрутизации................................................................................................. 102

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

ориентированного программного обеспечения............................................ 110

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

Заключение.................................................................................................................. 118

Список литературы..................................................................................................... 120



Задать вопрос

Введение

Актуальность темы. Одним из способов экономии ресурсов при транспортировке грузов является применение систем поддержки принятия решений в области транспортной логистики. Актуальность данных задач вы­звана тем, что до 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

Вернуться к списку