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

САНКТ-ПЕТЕРБУРГСКИИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Перцовский Александр Константинович

На правах рукописи

АДАПТИВНЫЕ МОДЕЛИ II АЛГОРИТМЫ МАРШРУТИЗАЦИИ

05.13.18 - математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

18 АПР 2013

005052026

Санкт-Петербург - 2013

005052026

Работа выполнена на кафедре математического моделирования энергетических систем Факультета прикладной математики - процессов управления Санкт-Петербургского государственного университета.

Научный руководитель: доктор физико-математических наук, профессор

Захаров Виктор Васильевич

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

Андрианов Сергей Николаевич, (СПбГУ, ф-т ПМ-ГГУ)

кандидат физико-математических наук, Гасратов Майсур Габибулахович (Северо-Западный филиал ОАО «МегаФон»).

Ведущая организация: Государственный университет

морского и речного флота имени адмирала С.О. Макарова, г. Санкт-Петербург.

Защита состоится «24» апреля 2013 г. в _ часов на заседании диссертациошюго

совета Д.212.232.50 по защите диссертаций на соискание ученой степени кандидата наук, на соискание ученой степени доктора наук при Санкт-Петербургском государственном университете по адресу: 199034, Санкт-Петербург, В.О., Университетская наб., 7/9, Менделеевский Центр.

С диссертацией можно ознакомиться в научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, В.О., Университетская наб., 7/9. Автореферат размещен на сайте www.spbii.ni.

Автореферат разослан «

йълз. ко а_

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

Г.И. Курбатова

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Согласно проведенному исследованию недавних публикаций (работы Лукинского B.C., Плетневой Н.Г.), в течение последних лет идет активный поиск эффективных решений данной проблемы. Особенный интерес представляет методика решения транспортной задачи и маршрутизации транспорта большой размерности. Однако удовлетворительный по временным затратам точный алгоритм решения задачи маршрутизации, не основанный на полном переборе, до сих пор не был предложен.

В западных источниках задачи маршрутизации транспорта (Vehicle Routing Problem)

исследуются с 1960х годов. Впервые VRP сформулирована Г. Данцигом и Дж. Рамзером в

1959. Впоследствии, Я. Ленстра и А. Ринной Канн доказали, что VRP является NP-полной

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

3

маршрутизации транспорта заложили в своих работах Г. Кларк, Дж. Райт, М. Соломон, Б. Джиллет, Л. Миллер. В качестве важнейшего способа оценки эффективности эвристических алгоритмов практически все исследователи используют результаты тестирования на специально разработанных и размещенных в интернете тестовых примерах (например, http://www.ihsmith.umd.edu/faculty/bgolden/vTp_data.htm).

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

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

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

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

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

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

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

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

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

4

транспортной доступности был выбран CityGuide Server с возможностью использования Open Street и Google.Maps для получения растровой подкладки карт. В виду требуемой гибкости и масштабируемости программного комплекса разработка внутренней архитектуры производилась в соответствии с паттернами проектирования «делегирование», «интерфейс» и «фабрика объектов».

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

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

учетом временных окон и массогабаритных ограничений;

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

транспортным средством.

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

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

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

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

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

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

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

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

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

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

Результаты данного исследования были представлены на следующих конференциях: Процессы управления и устойчивость: XXXIX международная научная конференция аспирантов и студентов (СР8'2008), Процессы управления и устойчивость: ХЫП международная научная конференция аспирантов и студентов (СР5'2012), 12-я конференция Высокие технологии, фундаментальные исследования, экономика.

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

Публикации. Основные результаты исследования отражены в 5 печатных работах, одна из которых опубликована в журнале, входящем в Перечень изданий, рекомендованных ВАК РФ.

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

СОДЕРЖАНИЕ РАБОТЫ.

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

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

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

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

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

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

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

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

• множество заданий на доставку;

• множество доступного транспорта.

Задание на доставку обладает следующими характеристиками:

•PL - пункт доставки, в котором производится загрузка груза;

• PD - пункт доставки, в котором производится разгрузка;

• И, - временной интервал, в течение которого может быть произведена загрузка;

• TD - временной интервал, в течение которого может быть произведена разгрузка;

• CL - категория груза (например, сыпучий, жидкий, Koirreraiep) ;

*tl — время, затрачиваемое на загрузку (то есть проведенное в пункте загрузки);

• td - время, затрачиваемое на разгрузки (то есть проведенное в пункте разгрузки);

• w - вес доставляемого груза;

• v - объем доставляемого груза.

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

Транспортные средства обладают следующими параметрами:

• ТА - временной интервал доступности транспортного средства;

• V - вместимость транспортного средства по объему;

• W - грузовместимость транспортного средства;

• CV - категории грузов, перевозимых транспортным средством.

Далее вводится ряд основных понятий.

Пара вида (g, t) называется элементом расписания доставки, где g - географическая точка, at- время ее посещения.

В качестве допустимого решения принимается множество пар Routes следующего вида: (Route, v), здесь v € Vehicals, где Vehicals - множество транспортных средств, а Route представляет собой упорядоченную конечную последовательность элементов расписания доставки.

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

Элементы допустимого множества рейсов должны удовлетворять следующим ограничениям:

1. {Routet, i = 1.. m}, U( Routet = S, где S - множество заданий на доставку.

S

Vi j-.Routei n Routej = 0, т.е. U( Routet полностью покрывает исходное множество заданий на доставку, и при этом одна доставка содержится в одном и только одном рейсе.

Сформулируем условия, которым обязана удовлетворять функция /(■):

2. Если Vi = f(Routet), то выполняются следующие два условия:

^ w(r) < W(Vi)

rtRoutei

£ Кг)<Пг()

V r6ROUt££

3. Соответствие категории груза транспортному средству:

2 (J Cir

TZRvutet

4. Условия соответствия расписания:

V/, Vr 6 RouLet: L(r) 6 TA(vt), В (г) € TA(vt), где DfrJ и Z/r) - являются функциями, заданными на множестве доставок: D(r): 5 -> Time (время отправления из пункта разгрузки), L(г):5 -> Time (время прибытия в пункт загрузки). Здесь Time - временной интервал, для которого производится планирование.

На значения функций D(r) и Цг) можно наложить следующие ограничения:

5. Vi, Vr е Router. D(r) 6 TD(r), L(r) £ Щг) В данной модели в качестве целевого функционала принимается суммарная длина рейсов в полученном разбиении, определяемая по географическим расстояниям между точками доставки.

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

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

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

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

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

транспорта. Действительно, построение кластерных географических районов (KIT) способно сократить размерность задачи. По построенным районам также можно создавать допустимые рейсы.

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

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

В качестве критерия оценки кластерного георайона принимается выражение Е (Cluster) = HseXcmtsP(g.o), где о - геометрический центр КГР, р(д, о) - расстояние от центра кластера до географической точки д, принадлежащей множеству географических точек рассматриваемого КГР, обозначенного как Claster.

Тогда задача оптимизации и целевой функционал определяются в виде:

E(Claster) -»min.

Claster

Постановка задачи на кластеризацию накладывает на КГР несколько ограничений:

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

• для каждого КГР среди транспорта, удовлетворяющего первому ограничению, должно существовать хотя бы одно транспортное средство, интервал работы которого содержит в себе оценку времени обслуживания КГР;

• для всех точек доставки, попавших в КГР, соответствующая точка погрузки или загрузки также должна попасть в КГР.

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

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

Отдельно рассматривается метод построения начального разбиения на КГР. Два варианта данного алгоритма рассматриваются в параграфе 5. Первый из них - метод дальней точки - основан на постепенном построении КГР, начиная с самой удаленной от склада точки, и создании нового КГР по мере заполнения предыдущих. Описанный метод является авторской разработкой. Приведем его общую схему:

1. Определить д0 - точку, доставляющую максимум функционалу р{0,д), где

О - точка депо, а д принадлежит множеству всех геоточек;

2. Создать КГР С0, добавить в него точку д0\

3. Определить точку ди доставляющую минимум функционалу Ч'Сд) = в, С;) = ттхеС1р(д, х), где д принадлежит множеству нераспределенных точек, а С1

принадлежит множеству уже созданных КГР;

4. Определить два ближайших к точке д1 КГР Сь Сз;

5. Проверить ограничения на добавление точки в КГР последовательно для С] и

Сг в порядке близости их к точке и добавить точку к первому кластеру, доя которого

ограничения выполняются;

6. В случае если ограничения не выполнены ни для одного из КГР, создать новый

и добавить рассматриваемую точку к нему;

7. Повторять шаги 3-6, пока есть нераспределенные точки;

В данном методе под расстоянием между двумя точками понимают линейное расстояние.

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

Теорема 1. Метод дальней точки имеет сложность 0(п2), где п - количество точек

доставки в рассматриваемой постановке задачи.

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

Теорема 2. Сложность алгоритма построения начального разбиения на географические районы, основанного на алгоритме Свира, составляет 0(п ■ login) + п), где п - количество различных географических точек во множестве заданий на доставку.

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

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

Первая база Вторая база

№ итерации Метод, основанный на алгоритме Свира Метод дальней точки Метод, основанный на алгоритме Свира Метод дальней точки

1 14,8847801 12,7821509 39,3275608 38,4543516

2 12,8520326 12,63429 26,4154526 22,8018818

3 10,9587820 12,3625037 21,4802351 17,7964143

4 10,4329074 - - -

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

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

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

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

Д(<7) = - ¿1,

здесь д - точка, принадлежащая множеству нераспределенных точек, а с12 - расстояния от точки д до двух ближайших к ней КГР, где расстояние от точки р до КГР С определяется по формуле: с1(р, С) = ттх еср(*,р)- Этот подход позволяет в первую очередь распределять точки доставки, лежащие далеко от границ КГР, что необходимо в виду наличия массогабаритных ограничений.

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

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

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

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

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

13

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

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

/(У() = IWil.

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

Теорема 3. Сложность имитационного метода решения задачи построения маршрута не превышает 0(п2 ■ log(n)), где п - количество точек, по которым необходимо построить рейс.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

не превышает 12 минут на базе, содержащей 500 точек доставки.

15

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

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

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

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

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

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

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

a. Перцовский А.К. Применение Xpress Optimizer для решения задач

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

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

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

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

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

Отпечатано копировально-множительным участком отдела обслуживания учебного процесса физического факультета СПбГУ. Приказ № 571/1 от 14.05.03. Подписано в печать 1S.03.13 с оригинал-макета заказчика. Ф-т 30x42/4, Усл. печ. л. 1. Тираж 100 экз., Заказ №1659. 198504, СИб, Ст. Петергоф, ул. Ульяновская, д. 3, tívi. 929-43-00.

На правах рукописи Перцовский Александр Константинович

04201358146

АДАПТИВНЫЕ МОДЕЛИ И АЛГОРИТМЫ МАРШРУТИЗАЦИИ

05.13.18 - математическое моделирование, численные методы и

комплексы программ

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель профессор Захаров В.В.

Санкт-Петербург - 2013

Оглавление

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

районы..................................................................................................................76

2

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

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

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

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

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

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

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

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

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

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

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

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

Введение

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 наименований.

Первая глава настоящего исследования н