Адаптивные модели и алгоритмы маршрутизации тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Перцовский, Александр Константинович

• Перцовский, Александр Константинович
• кандидат физико-математических наук
• 2013

Оглавление диссертации кандидат физико-математических наук Перцовский, Александр Константинович

Оглавление

Введение

Глава 1. Задача маршрутизации с ограничениями

1.1 Описание предметной области

1.2 Возникновение транспортной задачи и этапы ее становления

1.3 Классическая транспортная задача

1.4 Цели диссертационной работы

1.4.1 Формализация предметной области

1.4.2 Анализ требований к решению

Глава 2. Математические модели доставки грузов с различными ограничениями

2.1. Задачи управления доставками

2.1.1 Обзор существующих моделей

2.1.2 Задача коммивояжера

2.2 Цели и задачи моделирования

2.3 Формализация предметной области. Параметры модели

2.4.Математическая модель доставок грузов(1)

2.5.Математическая модель доставок грузов(П)

Глава 3. Методы решения и оптимизации моделей I и II

3.1 Общая методология оптимизации в моделях I, II

3.2 Методы кластеризации при декомпозиции в процессе решения задачи маршрутизации транспорта

3.2.1 Критерии кластеризации

3.3. Построение начального разбиения

3.3.1 Метод дальней точки

3.3.2 Метод, основанный на алгоритме Свира

3.4 Алгоритм кластеризации с известным числом кластерных географических районов

3.4.1. Определение точки, рассматриваемой на текущей итерации построения кластерных географических районов. Метод свободной точки

3.4.2 Алгоритм улучшения разбиения на кластерные географические

районы

2

3.5. Метод решения задачи коммивояжера

3.6. Итерационный метод решения моделей I и II

Глава 4. Программная реализация алгоритмов решения моделей I и II

4.1 Архитектура программного комплекса

4.2 Использованные технологии

4.3 Информационно-логическая модель. Реализация схемы данных

4.4 Реализация службы кэширования графа транспортной доступности

4.5 Реализация модуля построения рейса

4.6 Реализация модуля построения кластерных географических районов

4.7 Описание интерфейса пользователя

Заключение

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

Введение диссертации (часть автореферата) на тему «Адаптивные модели и алгоритмы маршрутизации»

Введение

1. Актуальность темы исследования

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

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

Изучением вышеописанных вопросов занимается транспортная логистика. Большинство задач, рассматриваемых в рамках данной дисциплины, являются ИР-полными (к ИР-полным задачам относят задачи, которые невозможно разрешить за полиномиальное время). Задачи такой сложности в общем случае не разрешимы точными методами, поэтому для получения решения применяются различные эвристические и генетические методы. В возникающих практических задачах указанные методы являются ресурсозатратными, и, следовательно, необходимо модифицировать их с учетом возникающих ограничений и специфики каждого класса задач. Необходимость этого обусловлена тем, что быстродействие имеющихся у

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

Согласно проведенному исследованию недавних публикаций, в течение последних лет идет активный поиск эффективных решений данной проблемы [1-3]. Особенный интерес представляет методика решения транспортной задачи и маршрутизации транспорта большой размерности. Однако точный алгоритм решения задачи маршрутизации, не основанный на полном переборе, до сих пор не был предложен.

В западных источниках задачи маршрутизации транспорта (VRP -Vehical Routing Problem) исследуются с 1960х годов. Впервые VRP сформулирована Г. Данцигом и Дж. Рамзером [4] в 1959 г. Впоследствии, Я. Ленстра и А. Ринной Канн [5] доказали, что VRP является NP-полной задачей. Основу методологии применения эвристических методов для решения задачи маршрутизации транспорта заложили в своих работах Г. Кларк, Дж. Райт [6], М. Соломон [7], Б. Джиллет, J1. Миллер [8]. В качестве важнейшего способа оценки эффективности эвристических алгоритмов практически все исследователи используют результаты тестирования на специально разработанных и размещенных в интернете тесовых примерах (например, http://www.rhsmith.umd.еёи/Гасику/Ь§оШеп/уф_с1а1а.Ь1ш).

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

2. Цели и задачи диссертационной работы

Целями данной диссертационной работы являются построение и

обоснование адаптивной математической модели управления доставками,

5

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

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

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

• Разработать и обосновать адаптивную математическую модель предметной области в виде задачи оптимизации.

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

• Спроектировать, реализовать, оптимизировать и провести тестирование работы программного комплекса управления доставками организации.

3. Методы исследования

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

4. Технологии разработки программного комплекса

При разработке программного комплекса использовались технологии

платформы Microsoft .Net 4.0. В качестве системы управления базами данных

использовался Posgres. В качестве поставщика графа транспортной

доступности был выбран CityGuide Server с возможностью использования Ореп

Street и Google Maps для получения растровой подкладки карт. В виду

б

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

5. Научная новизна

В данной работе впервые проведена разработка универсального практически ориентированного математического метода решения задачи маршрутизации с динамически настраиваемыми ограничениями и его реализация для решения следующих задач:

• Построение оптимального рейса по имеющемуся набору заданий на доставку с учетом временных окон и массогабаритных ограничений

• Группировка точек доставки для последующего обслуживания одним транспортным средством

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

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

Практические реализации решения транспортной задачи, как правило, основаны на применении генетических [9] либо мета эвристических алгоритмов [10]. Данные алгоритмы характеризуются тем, что качество их работы сильно зависит от характеристик постановки задачи [11]. В связи с этим большинство практических реализаций выполняется по заказу конкретной компании, и алгоритм настраивается именно под ее специфику. Большинство

7

существующих программных комплексов ориентированы на административный учет доставок, а не на наукоемкий подход к решению задачи маршрутизации транспорта. Типичным примером подобной программы является, например, комплекс "1С-Рарус: Транспортная логистика и экспедирование". В то время как разработанный в данном диссертационном исследовании программный комплекс является реализацией алгоритма построения плана доставок и решения задачи маршрутизации транспорта в режиме реального времени с учетом текущей дорожной обстановки. Кроме того он позволяет производить гибкую настройку.

Результаты работы, выносимые на защиту, получены впервые и являются новыми:

1. Математические модели управления доставками с учетом формализованных требований по адаптивности модели. Декомпозиция множества заданий на доставку с учетом концепции кластерных географических районов.

2. Информационно-логическая модель управления доставками с учетом динамической транспортной обстановки.

3. Алгоритм построения набора кластерных географических районов. Алгоритмы построения допустимого рейса с учетом динамически изменяющейся транспортной обстановкой.

4. Оценки сложности полученных алгоритмов решения задачи маршрутизации с учетом требований и ограничений модели (теоремы 1-4).

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

6. Практическая и теоретическая значимость

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

при внедрении для каждого пользователя.

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

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

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

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

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

7. Апробация работы

Результаты работы были протестированы на нескольких базах, полученных от реальных пользователей. Размерность решаемых задач маршрутизации составляла от 300 до 600 заявок на доставку, а транспортный парк включал до 30 единиц техники.

Результаты данного исследования были представлены на следующих конференциях: Процессы управления и устойчивость: 39-я международная научная конференция аспирантов и студентов, Процессы управления и устойчивость: 43-я международная научная конференция аспирантов и

студентов, 12-я конференция Высокие технологии, фундаментальные исследования, экономика.

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

8. Публикации

В журналах, рецензируемых ВАК:

1. Перцовский А.К. Применение Xpress Optimizer для решения задач моделирования и оптимизации. //RSDN Magazine №4 2011г -М:К-Пресс 2011. С. 12-14.

2. Перцовский А.К. Итеративно-имитационный метод построения решения задачи коммивояжера с массогабаритными ограничениями и временными окнами с учетом динамической транспортной обстановки. //RSDN Magazine №4 2012г-М:К-Пресс 2012. С. 3-4.

3. Перцовский А.К. Декомпозиция задачи маршрутизации с временными окнами. //RSDN Magazine №4 2012г-М:К-Пресс 2012. С. 5-7.

В трудах международных конференций:

1. Перцовский А.К. Применение алгоритмов кластеризации для решения задачи маршрутизации// Высокие технологии, фундаментальные исследования, экономика. Том 2/ Под редакцией А.П. Кудинова. СПб: Типография на Биржевой, 2011.

2. Перцовский А.К. Архитектура программного ядра тестового стенда для логистических алгоритмов. // Высокие технологии, фундаментальные исследования, экономика. Том 2/ Под редакцией А.П. Кудинова. СПб: Типография на Биржевой, 2011.

Выступления на международных конференциях:

1. Перцовский А.К. Применение алгоритмов кластеризации при решении транспортной задачи// Процессы управления и устойчивость: Труды 43-й международной научной конференции аспирантов и студентов / Под ред. А. С. Ерёмина, П. В. Смирнова. СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2012. С. 545-552.

2. Каганова Е.И., Перцовский А.К. Оптимизация производственно-логистической системы с использованием Xpress-optimizer // Процессы управления и устойчивость: Труды 39-й международной научной конференции аспирантов и студентов / Под ред. Н. В. Смирнова, Г. Ш. Тамасяна. СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2008. С. 546-551.

9. Структура работы

Диссертационная работа состоит из введения, трех глав, заключения, библиографического списка и приложения. Работа представлена на 127 страницах, включающих 2 таблиц, 7 рисунков, библиографический список из 52 наименований.

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

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

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

Однако решение транспортной задачи не дает детального плана

обслуживания доставок, необходимого логистам организаций. Кроме того,

методы решения классической транспортной задачи не учитывают таких

факторов, как расписание работы пунктов доставок, издержки на обслуживание

рейсов, ограниченность транспортного парка [12]. Таким образом, результаты

11

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

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

В процессе произведенных исследований проведен анализ существующих подходов к решению транспортных задач маршрутизации.

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

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

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

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

В параграфе 2.1 приводится описание существующих моделей. Параграф 2.2 посвящен проблемам существующих моделей и постановке целей построения новых авторских моделей.

Параграф 2.3 посвящен формализации предметной области. В нем вводятся основные обозначения. С учетом обозначений параграфа 2.3 в параграфах 2.4 и 2.5 осуществляется построение авторских моделей маршрутизации.

В третьей главе приводится описание предложенной общей методологии решения задачи маршрутизации, основанной на декомпозиции задачи маршрутизации на три подзадачи:

1. Определение количества рейсов, необходимых для обслуживания набора заявок на доставку,

2. Определение того, какие заявки на доставку должны быть обслужены в каждом из рейсов,

3. Упорядочивание доставок в рейсе, минимизируя оптимизационный функционал.

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

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

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

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

Два варианта данного метода рассматриваются в пункте 3.2. Первый из них - метод дальней точки - основан на постепенном построении кластеров начиная от самой удаленной от склада точки и создании нового кластера по мере заполнения предыдущих. Второй метод основан на известном алгоритме Свира построения решения задачи коммивояжера. Он основан на упорядочивании точек по возрастанию полярного угла.

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

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

В работе анализируются способы предотвращения появления выбросов в начальном и промежуточных разбиениях. Анализируется также проблема массогабаритных ограничений. Данная проблема вызвана тем, что кластер может быть заполнен точками, лежащими на стыках с другими кластерами. Из-за этого в виду массогабаритных ограничений, введенных в пункте 3.3 настоящей работы, точки, наиболее удаленные от соседних кластеров, не смогут в него попасть, что приводит к образованию лишнего кластера, содержащего не более 5ти точек, или кластера, выпуклая линейная оболочка которого пересекается с выпуклыми линейными оболочками других кластеров. Эти выводы были получены в результате тестирования алгоритма на пользовательских данных. Поскольку полученные кластеры в дальнейшем будут использоваться для построения множества рейсов, то формирование лишних кластеров недопустимо, так как это приведет к образованию лишнего рейса и росту целевого оптимизационного функционала.

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

Здесь д принадлежит множеству нераспределенных точек, а (11, с12 -расстояния до двух ближайших к точке д имеющихся кластеров.

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

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

Итерации заключаются в постепенном увеличении начала рейса, пока все точки не попадут в него.

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

Требования к программному комплексу со стороны целевой аудитории

/

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

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

В ходе работы было рассмотрено несколько вариантов выбора неполного допустимого рейса. Данная задача была сформулирована в виде задачи оптимизации функционала при тех же ограничениях, что и в задаче построения полного рейса. Было реализовано и протестировано несколько вариантов вида данного функционала. Тестирование производилось на нескольких пользовательских базах. А результаты предъявлялись для оценки логистам.

Наиболее очевидным казался выбор рейса, содержащего наибольшее

количество точек, но это решение было неприемлемым для алгоритма решения

задачи маршрутизации. Поскольку рейсы в нем строились итеративно с

16

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

Аналогично плохо себя проявил выбор наиболее загруженного рейса по весу или объему.

В конечном итоге был выбран функционал вида

где У1 - построенный рейс. Значение функционала определяется как диаметр рейса, то есть максимальное расстояние между географическими точками, попавшими в рейс.

В последнем параграфе главы 3 предлагается метод решения транспортной задачи с массогабаритными ограничениями и ограничениями по расписанию с использованием разработанного алгоритма кластеризации и метода итерационного имитационного метода построения рейса.

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

Результаты тестирования работы метода предъявлялись логистам компаний, предоставивших данные для тестирования (ММК, Ладога), и были ими одобрены. Кроме того, полученные рейсы могут быть использованы как исходные данные для работы различного рода генетических алгоритмов, поскольку уже являются допустимыми и близкими к оптимальным.

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

Отдельное внимание уделено вопросам, связанным с получением

информации о транспортной доступности географических точек. В ряде работ,

17

посвященных исследованиям генетических алгоритмов решения задачи маршрутизации [14,15,16], данный вопрос считается решенным. Существуют тестовые наборы данных для проверки новых генетических алгоритмов [17]. Однако в этих массивах данных информация о транспортной доступности заранее прокэширована и представлена в виде готовой матрицы, то есть для каждой пары точек известно расстояние между ними.

При практической же реализации алгоритма решения задачи маршрутизации необходимо динамически получать оптимальные треки переездов из одной точки в другую, что само по себе является трудной задачей на графе. Несмотря на то, что данная задача имеет полиномиальную оценку сложности [18], она требует значительного времени для решения, так как требуется получить большие по объему массивы данных о транспортной доступности на большом графе дорого. Например, в Санкт-Петербурге данный граф насчитывает более 51000 (на 2012 год) вершин [19], не считая различных перекрестков, поворотов и прочих элементов транспортной инфраструктуры.

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

Далее в третьей главе рассматриваются реализованные методы, паттерны проектирования, в соответствии с которыми производилась разработка программного комплекса.

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

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

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

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

При достижении поставленной цели был получен ряд промежуточных результатов:

• проведена формализация предметной области;

• построена информационно-логическая модель логистической схемы предприятия;

• построена оптимизационная модель для решения задачи управления транспортом;

• разработаны критерии оценки качества решения задачи маршрутизации транспорта;

• построена общая методология решения задачи маршрутизации;

• разработан алгоритм построения оптимального плана обслуживания доставок, состоящего из некоторого множества допустимых рейсов;

• спроектирована структуры и компонентов программного комплекса;

• решен вопрос о выборе плана доставок в том случае, когда не существует оптимального решения, охватывающего все поступившие задания на доставку;

• тестирование разработанных алгоритмов;

• минимизировано число обращения к службе поставщика графа транспортной доступности;

• проведена оценка влияния принятых архитектурных решений на производительность программного комплекса.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Перцовский, Александр Константинович

Заключение

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

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

• Построение информационно-логической схемы данных транспортного предприятия.

• Построение математической модели рассматриваемой предметной области.

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

• Разработка методологии двухэтапного построения решения транспортной задачи с массогабаритными ограничениями и ограничениями по расписанию и типам грузов.

• Построение оценки сложности разработанных алгоритмов.

• Проектирование универсального программного комплекса управления доставками предприятия, требующего минимальных трудовых затрат при каждом внедрении на производстве.

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

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

• Произведено тестирование разработанного программного комплекса на данных, полученных от реальных пользователей.

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

На защиту выносятся следующие результаты:

1. Математические модели управления доставками с учетом формализованных требований по адаптивности модели. Декомпозиция множества заданий на доставку с учетом концепции кластерных географических районов.

2. Информационно-логическая модель управления доставками с учетом динамической транспортной обстановки.

3. Алгоритм построения набора кластерных географических районов. Алгоритмы построения допустимого рейса с учетом динамически изменяющейся транспортной обстановкой.

4. Оценки сложности полученных алгоритмов решения задачи маршрутизации с учетом требований и ограничений модели (теоремы 1-4).

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

По результатам проведенных исследований были опубликованные следующие работы:

1. В журналах, рецензируемых ВАК: a. Перцовский А.К. Применение Xpress Optimizer для решения задач моделирования и оптимизации. //RSDN Magazine №4 2011 г -М:К-Пресс 2011.С. 12-14. b. Перцовский А.К. Итеративно-имитационный метод построения решения задачи коммивояжера с массогабаритными ограничениями и временными окнами с учетом динамической транспортной обстановки. //RSDN Magazine №4 2012г-М:К-Пресс 2012. С. 3-4. c. Перцовский А.К. Декомпозиция задачи маршрутизации с временными окнами. //RSDN Magazine №4 2012г-М:К-Пресс 2012. С. 5-7.

2. В трудах международных конференций: а. Перцовский А.К. Применение алгоритмов кластеризации для решения задачи маршрутизации// Высокие технологии, фундаментальные исследования, экономика. Том 2/ Под редакцией А.П. Кудинова. СПб:

Типография на Биржевой, 2011.

121

Ь. Перцовский А.К. Архитектура программного ядра тестового стенда для логистических алгоритмов. // Высокие технологии, фундаментальные исследования, экономика. Том 2/ Под редакцией А.П. Кудинова. СПб: Типография на Биржевой, 2011.

3. Выступления на международных конференциях: a. Перцовский А.К. Применение алгоритмов кластеризации при решении транспортной задачи// Процессы управления и устойчивость: Труды 43-й международной научной конференции аспирантов и студентов / Под ред. А. С. Ерёмина, Н. В. Смирнова. СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2012. С. 545-552. b. Каганова Е.И., Перцовский А.К. Оптимизация производственно-логистической системы с использованием Хргевз-орйпигег // Процессы управления и устойчивость: Труды 39-й международной научной конференции аспирантов и студентов / Под ред. Н. В. Смирнова, Г. Ш. Тамасяна. СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2008. С. 546-551.

Список литературы диссертационного исследования кандидат физико-математических наук Перцовский, Александр Константинович, 2013 год

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

1. Crainic TG, Laporte G. Planning models for freight transportation. European Journal of Operational Research 1997;97: 409-438.

2. Toth P, Vigo D (Eds.). The vehicle routing problem, SIAM monographs on discrete mathematics and applications. Philadelphia: SIAM, 2001.

3. Sigurd M, Pisinger D, Sig M.The pickup and delivery problem with time windows and precedences. Transportation Science 2004; 38: 197-209.

4. Dantzig G, Ramser J. The truck dispatching problem. Management Science 1959;6: 81-91.

5. Lenstra JK, Rinnooy Kan AHG. Complexity of vehicle routing and scheduling problems. Networks 1981 ;11: 221-227.

6. Clarke G, Wright JW. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research 1964;12: 568-581.

7. Solomon MM. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research 1987;35: 254-265.

8. Gillett BE, Miller LR. A heuristic algorithm for the vehicle dispatch problem. Operations Research 1974;22: 340-349.

9. Berger J, Barkaoui M, Braysy O. A route-directed hybrid genetic approach for the vehicle routing problem with time windows. INFOR 2003; 41: 179-194.

1 O.Chiang W-C, Russell RA. A reactive tabu search metaheuristic for the vehicle routing problem with time windows. INFORMS Journal on Computing 1997;9: 417-430.

11.Генетический алгоритм./ Jesse Russell, Ronald Cohn -M: Книга no Требованию, 2012.

12. Логистика. Учебное пособие/ Т.И. Савенкова -М: Омега-JI, 2006, 256 с.

13.Обзор основных методов классификации и кластеризации данных/ Д. С.Черезов, Н. А. Тюкачев // Вестник ВГУ Серия: Системный анализ и информационные технологии.-2009.-№2-С 26-29.

14.Russell RA, Chiang W-C. Scatter search for the vehicle routing problem with time windows. European Journal of Operational Research 2006; 169: 606-622.

15.Mester D, Braysy O. Active guided evolution strategies for large-scale vehicle routing problems with time windows. Computers & Operations Research 2005 ;32: 1593-1614.

16.Berger J, Barkaoui M. A parallel hybridgenetic algorithm for the vehicle routing problem with time windows. Computers & Operations Research 2004; 31: 2037-2053.

17.http://www.rhsmith.umd.edu/faculty/bgolden/vrp_data.htm

18.Ананий В. Левитин / Алгоритмы: введение в разработку и анализ. - М.: "Вильяме", 2006. - С.189-195.

19.Еженедельная газета "Недвижимость и строительство Петербурга", № 27(713) 2012-07-09, с.18.

20.Hirano, Hiroyuki and Makota, Furuya (2006), "JIT Is Flow: Practice and Principles of Lean Manufacturing", PCS Press, Inc.

21.Модели и методы теории логистики: Учебное пособие. 2-е изд./- B.C. Лукинский, В.В. Лукинский, Ю.В. Малевич и др./ Под ред. B.C. Лукинского. -СПб.: Питер, 2008, 448 с.

22.Правила дорожного движения 2012/ -М:Эксмо, 2012.

23.В.И. Мудров Задача о коммивояжере. — М.: «Знание», 1969. — С. 62.

24.Elements of the Theory of Computation/ Lewis H.R., Papadimitriou C.H. -New Jersey:Prentice-Hall, 1998, 361.

25.A Survey of Heuristics for the Vehicle Routing Problem/ Olli Braysy, Michel Gendreau, Geir Hasle, Arne L0kketangen, 2008.

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

27.Перцовский А.К. Применение Xpress Optimizer для решения задач моделирования и оптимизации. //RSDN Magazine №4 2011 г -М:К-Пресс 2011. С. 12-14.

28.Каганова Е.И., Перцовский А.К. Оптимизация производственно-логистической системы с использованием Xpress-optimizer // Процессы управления и устойчивость: Труды 39-й международной научной конференции аспирантов и студентов / Под ред. Н. В. Смирнова, Г. Ш. Тамасяна. СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2008. С. 546-551.

29.Факторный, дискриминантный и кластерный анализ: Пер с англ./Дж. - О.Ким, Ч.У.Мыоллер, У.Р.Клекка и др.; Под ред. И.С.Енюкова. - М.: Финансы и статистика, 1989. - 215с.

30.Шлезингер М., Главач В. Десять лекций по статистическому и структурному распознаванию. — Киев: Наукова думка, 2004.

31.Воронцов К.В. Алгоритмы кластеризации и многомерного шкалирования. Курс лекций. МГУ, 2007.

32.Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин JI. Д. Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989.

ЗЗ.Чубукова И.А. Курс лекций «Data Mining». — Интернет-университет информационных технологий.

34.Перцовский А.К. Применение алгоритмов кластеризации для решения задачи маршрутизации// Высокие технологии, фундаментальные исследования, экономика. Том 2/ Под редакцией А.П. Кудинова. СПб: Типография на Биржевой, 2011.

35.https://class.coursera.org/ml/auth/welcome

36.MacQueen J. (1967). Some methods for classification and analysis of multivariate observations. In Proc. 5th Berkeley Symp. on Math. Statistics and Probability, pages 281—297.

37.В. Кузютин, H. Зенкевич, В. Еремеев Геометрия -Спб: Лань, 2003, 416 С.

38.Зенкевич H.A. Губар Е.А. Практикум по исследованию операций - СПб., 2007.- 170 с.

39.Ф. А. Новиков Дискретная математика для программистов. - Санкт-Петербург, Питер, 2001, 304 е., ил.

40.Перцовский А.К. Архитектура программного ядра тестового стенда для логистических алгоритмов. // Высокие технологии, фундаментальные исследования, экономика. Том 2/ Под редакцией А.П. Кудинова. СПб: Типография на Биржевой, 2011

41.Дейт К. Дж. Введение в системы баз данных = Introduction to Database Systems. — 8-е изд. — M.: Вильяме, 2005. — 1328 с.

42.Роберт Седжвик Фундаментальные алгоритмы на С++. Часть 5. Алгоритмы на графах-М.: ДиаСофт, 2002. 496С.

43.http://www.intuit.rU/department/algorithms/ingrth/9/l.html

44.К.Д.Маннинг, П.Рагхаван, Х.Шютце. Введение в информационный поиск. -"Вильяме". 2011.

45.Томас X. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — M.: «Вильяме», 2006. — С.

46.http://help.yandex.ru/maps/?id=1053672

47.Э. Гамма, Р. Хелм, Р. Джонсон, Дж. Влиссидес Приемы объектно-ориентированного проектирования. Паттерны проектирования = Design Patterns: Eléments of Reusable Object-Oriented Software. — СПб: «Питер», 2007. — С. 366.

48.Мартин Фаулер Шаблоны корпоративных приложений = Patterns of Enterprise Application Architecture (Addison-Wesley Signature Sériés). — M.: «Вильяме», 2009. — С. 544.

49.http://msdn.microsoft.com/ru-ru/library/b0zbh7b6.aspx

50.Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — M.: «Вильяме», 2007. — С. 824.

5 l.http://msdn. microsoft.com/en-us/library/z2kcy 19k(v=vs.80).aspx

52.Перцовский А.К. Применение алгоритмов кластеризации при решении транспортной задачи// Процессы управления и устойчивость: Труды 43-й

международной научной конференции аспирантов и студентов / Под ред. А.

126

С. Ерёмина, Н. В. Смирнова. СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2012. С. 545-552.