Содержание к диссертации
Введение
Глава 1. Задача маршрутизации с ограничениями 20
1.1 Описание предметной области 20
1.2 Возникновение транспортной задачи и этапы ее становления 24
1.3 Классическая транспортная задача 30
1.4 Цели диссертационной работы
1.4.1 Формализация предметной области 33
1.4.2 Анализ требований к решению 38
Глава 2. Математические модели доставки грузов с различными ограничениями
2.1. Задачи управления доставками 42
2.1.1 Обзор существующих моделей 43
2.1.2 Задача коммивояжера
2.2 Цели и задачи моделирования 48
2.3 Формализация предметной области. Параметры модели 50
2.4.Математическая модель доставок грузов(І) 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
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
Список литературы
- Классическая транспортная задача
- Задача коммивояжера
- Определение точки, рассматриваемой на текущей итерации построения кластерных географических районов. Метод свободной точки
- Информационно-логическая модель. Реализация схемы данных
Введение к работе
Актуальность темы исследования. Развитие информационных технологий и повсеместная доступность ЭВМ позволяют повысить эффективность принятия управленческих решений, связанных с большой вычислительной работой. В частности, для ряда отдельно взятых организаций важным является вопрос об оптимальном управлении транспортными потоками. Постоянный рост рынка транспортных услуг обостряет конкуренцию между игроками. В такой обстановке существенным преимуществом является оптимальное планирование обслуживания доставок. Решение данной задачи возможно при помощи математических методов, имитационных и эвристических алгоритмов с использованием современных вычислительных мощностей.
Исследованию и решению задач маршрутизации транспорта посвящено большое количество работ в зарубежной литературе. В виду специфики развития отечественной науки и экономики на протяжении XX века в русскоязычной литературе вопросы управления доставками и маршрутизации транспортных средств стали рассматриваться относительно недавно. Рост интереса к проблеме начался с 90х годов после перехода страны на рыночную основу экономики.
Изучением вышеописанных вопросов занимается транспортная логистика. Большинство задач, рассматриваемых в рамках данной дисциплины, являются NP-полными. Задачи такой сложности в общем случае не разрешимы точными методами, поэтому для получения решения применяются различные эвристические и генетические методы. В возникающих практических задачах указанные методы являются ресурсозатратными, и, следовательно, необходимо модифицировать их с учетом возникающих ограничений и специфики каждого класса задач. Необходимость этого обусловлена тем, что быстродействие имеющихся у организаций ЭВМ ограничено, а скорость получения плана доставок является одним из важнейших конкурентных преимуществ.
Согласно проведенному исследованию недавних публикаций (работы Лукинского B.C., Плетневой Н.Г.), в течение последних лет идет активный поиск эффективных решений данной проблемы. Особенный интерес представляет методика решения транспортной задачи и маршрутизации транспорта большой размерности. Однако удовлетворительный по временным затратам точный алгоритм решения задачи маршрутизации, не основанный на полном переборе, до сих пор не был предложен.
В западных источниках задачи маршрутизации транспорта (Vehicle Routing Problem)
исследуются с 1960х годов. Впервые VRP сформулирована Г. Данцигом и Дж. Рамзером в
1959. Впоследствии, Я. Ленстра и А. Ринной Канн доказали, что VRP является NP-полной
задачей. Основу методологии применения эвристических методов для решения задачи
маршрутизации транспорта заложили в своих работах Г. Кларк, Дж. Райт, М. Соломон, Б. Джиллет, Л. Миллер. В качестве важнейшего способа оценки эффективности эвристических алгоритмов практически все исследователи используют результаты тестирования на специально разработанных и размещенных в интернете тестовых примерах (например, ).
Указанные обстоятельства определяют актуальность проведения исследований, направленных на создание и развитие специализированных математических методов, и разработку программного обеспечения для оптимизации логистической инфраструктуры транспортного предприятия. При этом особое внимание необходимо уделить сложностям практической реализации решений задачи маршрутизации транспорта с учетом специфик транспортной отрасли и организации, а также транспортной инфраструктуры.
Цели и задачи диссертационной работы. Целью данного исследования является разработка, реализация и апробация адаптивного оптимизированного по быстродействию алгоритма решения задачи маршрутизации транспорта, учитывающего динамически изменяемые ограничения и транспортную обстановку.
Для достижения поставленных целей потребовалось решить следующие основные задачи:
исследовать, проанализировать и формализовать предметную область управления доставками с учетом требований заинтересованных лиц;
разработать и обосновать адаптивную математическую модель предметной области в виде задачи оптимизации;
разработать общую методологию математического моделирования транспортных процессов и математический метод оптимизации для решения задачи маршрутизации с гибкой системой ограничений, учитывающей динамическое изменение транспортной обстановки;
спроектировать, реализовать, оптимизировать и провести тестирование работы программного комплекса управления доставками организации.
Методы исследования. Для достижения поставленных целей в диссертационной работе используются методы математического моделирования, кластерного анализа, элементы теории графов, методы исследования операций и имитационного моделирования. Для произведения оценки сложности построенных методов использованы методы теории алгоритмов и теории информационно-логических систем.
Технологии разработки программного комплекса. При разработке программного комплекса использовались технологии платформы Microsoft .Net 4.0. В качестве системы управления базами данных использовался Postgre. В качестве поставщика графа
транспортной доступности был выбран CityGuide Server с возможностью использования Open Street и Google Maps для получения растровой подкладки карт. В виду требуемой гибкости и масштабируемости программного комплекса разработка внутренней архитектуры производилась в соответствии с паттернами проектирования «делегирование», «интерфейс» и «фабрика объектов».
Научная новизна. В данной работе проведена разработка универсального практически ориентированного математического метода решения задачи маршрутизации с динамически настраиваемыми ограничениями и его реализация для решения следующих задач:
построение оптимального рейса по имеющемуся набору заданий на доставку с учетом временных окон и массогабаритных ограничений;
группировка точек доставки для последующего обслуживания одним транспортным средством.
Программная реализация метода оптимизирована по времени работы и количеству обращений к внешней службе поставщика графа транспортной доступности.
Также в ходе исследования были проанализированы многочисленные требования, на практике предъявляемые логистами к самому решению задачи маршрутизации и к процессу его получения, особенно к быстродействию. Была протестирована возможность применения алгоритмов кластеризации для сокращения размерности задачи маршрутизации транспорта с различными ограничениями.
В ходе исследования был разработан и протестирован метод решения задачи коммивояжера с ограничениями на транспортной сети, сочетающий в себе жадный, генетический и имитационный методы построения решения. В виду того, что в методе используются принципы имитационного моделирования, он может учитывать ограничения любой сложности, дополнительно накладываемые пользователями с минимальной доработкой его программной реализации.
В данном диссертационном исследовании программный комплекс является реализацией алгоритма построения плана доставок и решения задачи маршрутизации транспорта в режиме реального времени с учетом текущей дорожной обстановки. Кроме того, он позволяет производить гибкую настройку.
Практическая и теоретическая значимость. Предложенная в диссертации математическая модель может применяться для управления доставками. Кроме того, в частном случае она позволяет минимизировать затраты на доработку метода решения задачи маршрутизации при внедрении для каждого пользователя.
Отдельно стоит отметить, что разработанная методология решения задачи позволяет легко изменять методы решения каждой подзадачи. Это упрощает процесс тестирования различных генетических и эвристических методов, отличающихся от реализованных в рамках данного исследования.
Разработанные методы могут также быть применены и адаптированы к таким задачам, как построение оптимального рейса по множеству имеющихся точек доставки, построение кластерных географических районов и кластеризация географических точек по различным критериям.
Результаты работы комплекса предлагались логистам для оценки качества полученных результатов. Кроме того учитывались замечания и пожелания целевой логистической аудитории при реализации пользовательского интерфейса.
Таким образом, программный комплекс потенциально может быть внедрен и успешно применяться в любой организации, нуждающейся в управлении доставками.
Апробация работы. Результаты работы были протестированы на нескольких базах данных, полученных от реальных пользователей. Размерность решаемых задач маршрутизации составляла от 300 до 600 заявок на доставку, а транспортный парк включал до 30 единиц техники.
Результаты данного исследования были представлены на следующих конференциях: Процессы управления и устойчивость: XXXIX международная научная конференция аспирантов и студентов (CPS'2008), Процессы управления и устойчивость: XLIII международная научная конференция аспирантов и студентов (CPS'2012), 12-я конференция Высокие технологии, фундаментальные исследования, экономика.
Также основные результаты использованы при разработке учебного курса «Моделирование и оптимизация логистических систем», читаемого автором на факультете Прикладной математики-процессов управления Санкт-Петербургского государственного университета, посвященного математическим моделям и оптимизации в логистике.
Публикации. Основные результаты исследования отражены в 5 печатных работах, одна из которых опубликована в журнале, входящем в Перечень изданий, рекомендованных ВАК РФ.
Структура работы. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы, включающего в себя 52 наименований. Объем составляет 120 страницы машинописного текста.
Классическая транспортная задача
После обоснования применимости кластеризации к решению задачи маршрутизации во второй главе производится анализ критериев оценки качества кластеризации. Задача кластеризации формулируется как оптимизационная. Выбирается вид функционала, подлежащего минимизации, а также задаются ограничения, накладываемые на построенные кластеры.
Далее внимание акцентируется на основной проблеме проведения кластеризации - неизвестном числе кластеров. Поскольку данная информация необходима для большинства методов [13], требуется использовать специальные методы оценки количества получаемых кластеров и первоначального разбиения.
Два варианта данного метода рассматриваются в пункте 3.2. Первый из них - метод дальней точки - основан на постепенном построении кластеров начиная от самой удаленной от склада точки и создании нового кластера по мере заполнения предыдущих. Второй метод основан на известном алгоритме Свира построения решения задачи коммивояжера. Он основан на упорядочивании точек по возрастанию полярного угла.
В третьей главе также производится оценка эффективности предложенных методов, определяется их сложность. Отмечается, что метод дальней точки в большинстве случаев дает лучшие результаты, но производит больше операций. Но результаты тестирования на нескольких пользовательских базах показывают, что разница во времени не является существенной для пользователей-логистов. Таким образом, итоговым результатом в данном пункте второй главы является выбор метода дальней точки в качестве метода, установленного в реализуемом программном комплексе «по умолчанию». В этом качестве был использован метод дальней точки.
Далее производится построение метода улучшения кластеризации. Данный алгоритм основан на хорошо известном методе k-средних, поэтому ему присущи многие его слабые и сильные стороны. Например, построенный метод чувствителен к «выбросам» в начальном разбиении на кластеры. В работе анализируются способы предотвращения появления выбросов в начальном и промежуточных разбиениях. Анализируется также проблема массогабаритных ограничений. Данная проблема вызвана тем, что кластер может быть заполнен точками, лежащими на стыках с другими кластерами. Из-за этого в виду массогабаритных ограничений, введенных в пункте 3.3 настоящей работы, точки, наиболее удаленные от соседних кластеров, не смогут в него попасть, что приводит к образованию лишнего кластера, содержащего не более 5ти точек, или кластера, выпуклая линейная оболочка которого пересекается с выпуклыми линейными оболочками других кластеров. Эти выводы были получены в результате тестирования алгоритма на пользовательских данных. Поскольку полученные кластеры в дальнейшем будут использоваться для построения множества рейсов, то формирование лишних кластеров недопустимо, так как это приведет к образованию лишнего рейса и росту целевого оптимизационного функционала.
Для устранения проблемы переполнения кластеров предлагается при определении рассматриваемой точки каждый раз производить решение задачи максимизации функционала Нд) = d2 - d±. Здесь д принадлежит множеству нераспределенных точек, a d1, d2 -расстояния до двух ближайших к точке д имеющихся кластеров.
Далее во второй главе производится разработка имитационного итеративного метода построения рейса по имеющимся заданиям на доставку. Данная задача формулируется в виде задачи оптимизации функционала с массогабаритными ограничениями, возможностью дозагрузки и ограничениями по расписанию. В основе каждой итерации разработанного метода лежит имитационный алгоритм, достраивающий рейс по известному началу, используя, по возможности, все имеющиеся задания на доставку.
Поскольку метод является имитационным, то на каждой итерации можно гарантировать получение допустимых в смысле всех ограничений рейсов. Итерации заключаются в постепенном увеличении начала рейса, пока все точки не попадут в него.
Отдельной проблемой является случай, когда по тем или иным причинам полный, то есть содержащий все задания на доставку рейс построить невозможно, то есть задача не имеет решения. Такое возможно, так как оценка кластеров на удовлетворение ими расписания производится приблизительным методом ради повышения быстродействия программного комплекса, или же если задача построения рейса была применена к вручную созданному набору заданий на доставку, так как такая возможность была предоставлена конечным пользователям.
Требования к программному комплексу со стороны целевой аудитории таковы, что если в случае несовместности постановки задачи на формирование рейса никакого результата не будет предоставлено, то это будет неприемлемо ни для вызова построения рейса при решении задачи маршрутизации, ни при вызове задачи построения рейса вручную. Для логистов также неприемлем вариант возврата в качестве решения рейса, нарушающего какие-либо ограничения. По этой причине в случае несовместности задачи построения рейса необходимо вернуть пользователю неполный допустимый рейс.
Под неполным допустимым рейсом понимается рейс, удовлетворяющий всем ограничениям, но включающий не все точки, содержащиеся в постановке задачи.
В ходе работы было рассмотрено несколько вариантов выбора неполного допустимого рейса. Данная задача была сформулирована в виде задачи оптимизации функционала при тех же ограничениях, что и в задаче построения полного рейса. Было реализовано и протестировано несколько вариантов вида данного функционала. Тестирование производилось на нескольких пользовательских базах. А результаты предъявлялись для оценки логистам.
Задача коммивояжера
Как было показано выше существует большое количество математических моделей управления доставками. Однако, согласно классификации [25], большинство из них построены таким образом, что в их рамках нельзя свести воедино широкий спектр ограничений, используемых на практике, а также, при необходимости, без пересмотра методов оптимизации добавить новые. Так, например, в задаче с временными окнами отсутствует такой важный параметр, как временной интервал работы доступного транспорта.
В рамках данной работы автор предлагает обобщенную математическую модель управления доставками, построенную таким образом, что в процессе ее применения можно интерактивно добавлять новые ограничения, не изменяя при этом общую структуру модели.
Для достижения поставленной цели во главу угла выносится понятие допустимого рейса, то есть последовательности географических точек с приписанными им моментами их посещения. Также каждому рейсу приписывается транспортное средство, осуществляющее его обслуживание.
Предложенная автором методология оптимизации издержек, связанных с обслуживанием заказов на доставку, благодаря особенностям построенной модели, не требует изменения структуры при добавлении новых ограничений. Такая адаптивность достигается за счет того, что математически формализованные ограничения накладываются на допустимый рейс и проверяются на этапе его построения.
В построенной обобщенной математической модели присутствуют следующие ограничения: 1. по расписанию работы пунктов доставки и транспортных средств; 2. массогабаритные ограничения; 3. возможность дозагрузки в процессе обслуживания маршрута; 4. возможность обслуживания одной машиной нескольких рейсов, время выполнения которых не пересекается; 5. разделение грузов на категории, в соответствии с которым разные типы грузов могут доставляться разными видами транспорта.
В качестве параметра оптимизации традиционно выступают издержки на обслуживания построенного допустимого плана доставок. В общем случае они пропорциональны суммарной протяженности построенных рейсов, поэтому этот параметр был принят в качестве целевого функционала.
В настоящей работе автором предложена дополнительная математическая модель управления доставками. Как будет показано ниже, обобщенная математическая модель управления доставками не всегда имеет допустимые решения. В этом случае автор предлагает использовать дополнительную модель. При этом автором была разработана методология, позволяющая решать поставленные в математических моделях оптимизационные задачи параллельно.
Очевидное преимущество этой методологии заключается в том, что, не решая оптимизационной задачи, поставленной в первой модели нельзя однозначно спрогнозировать наличие или отсутствие у нее допустимы решений. Таким образом, без возможности решать задачи параллельно, в виду схожести ограничений, необходимо было бы производить лишнюю вычислительную работу.
В то же самое время, требование построить неполное решение, удовлетворяющее ограничениям по расписанию и массогабаритным ограничениям, в случае отсутствия полного, то есть включающего в себя все точки доставки, допустимого решения исходило от целевой аудитории. При этом очевидно, что в этом случае транспортная компания заинтересована обслужить как можно больше заявок на доставку. Этот факт связан с тем, что отсутствие допустимого решения связано, прежде всего, с ограниченностью транспортного парка предприятия.
Приведенная в пункте 1.4 настоящего исследования постановка задачи маршрутизации не учитывает большого числа возможных ограничений, но служит основой для остальных. Автором рассматриваются следующие сущности с соответствующими параметрами: Обозначим за д = (x,y,z) географическую точку, под которой будем понимать объект, наделенный параметрами: х - широта точки; у-долгота точки; z - высота точки над уровнем моря; Географическая точка является одним из основных понятий, с которыми будет оперировать разрабатываемый программный комплекс. Вторым не менее важным объектом является пункт доставки. Пункт доставки - это географическая точка с приписанным к ней контрагентом (клиентом или складом). Q = (д, Agent), где g - географическая точка, a Agent - соответствующий ей контрагент.
Определение точки, рассматриваемой на текущей итерации построения кластерных географических районов. Метод свободной точки
Этот алгоритм является описанием итерации генетического метода построения маршрута. То есть именно при его помощи строятся допустимые решения, из которых и будет выбрано лучшее.
Теорема 3. Сложность имитационного метода решения задачи построения маршрута не превышает 0(п2 log (її)), где п - количество точек, по которым необходимо построить рейс. Доказательство. Как видно из схемы алгоритма, наибольшую сложность имеет пункт 2 (сортировка точек). Сложность данного этапа составляет 0((п —/с) log(n —/с)), где к - число точек в построенной части рейса. Данная операция будет произведена менее п раз. Таким образом, сложность метода Т имеет оценку Т 0(п- (п — /с) log(n — к)) 0(п2 log(n)). ч.т.д.
Приведем описание генетического алгоритма построения рейса по набору точек при известном транспортном средстве, приписанном к маршруту. На первом шаге алгоритма строится начальное семейство решений Routes следующим образом: 1. Проинициализировать Routesi, і — 1,... ,п, где n - размерность множества В; 2. Добавить в каждый из Routest фиксированное начало маршрута машины; 3. Для каждой точки gi Є В в случае выполнения массогабаритных ограничений, ограничений по расписанию и, если п(д{) уже добавлено в RP, добавить Qi в построенный рейс с учетом расписания, добавить gt в RP. После построения начального поколения рейсов запускается следующий итеративный алгоритм: 1. Достроим каждый из рейсов Routesk по методу, описанному выше; 2. Выберем из достроенных рейсов множество полных, то есть тех, для которых RP = В. Обозначим полученное множество полных рейсов за Г; 3. Для каждого Yi Є Г вычислим показатель ft = F(yi), где F - это функционал, показывающий оптимальность полученного рейса; 4. Упорядочим Yi по возрастанию величины ft. Далее произведем выбор первых m рейсов, где m - параметр, задаваемый пользователем. Чем больше значение т, тем более близкий к оптимальному рейсу рейс будет построен, но на его построение будет затрачено больше времени; 5. Построим поколение Routesk+1 следующим образом: a. Обозначим за начало уїЛ — 1,...,т длиной на 1 больше, чем длина элементов Routesk; b. Для каждого (t построим множество дочерних рейсов, аналогично построению начального поколения рейсов; c. Построенное множество рейсов принять за Routesk+1; 6. Перейти к шагу 1, если длина элементов Routesk+1 меньше мощности множества В или ни один из рейсов у не является полным. Отдельно стоит рассмотреть случай, когда не удается построить ни одного рейса. Поскольку алгоритм проектируется для применения логистами, то такая ситуация представляется вполне реальной, так как логисты стремятся обслужить одновременно как можно большее количество доставок.
Рассмотрим варианты построения рейса по множеству в том случае, если построить рейс, охватывающий все доставки R невозможно.
Имеется несколько подходов к решению данной задачи, выбор которых напрямую зависит от контекста вызова метода решения задачи коммивояжера. Согласно проведенным опросам целевой аудитории, при решении задачи коммивояжера приоритетнее построить рейс, включивший в себя максимальное количество точек.
При построении географических районов модуль решения задачи коммивояжера вызывается автоматически, поэтому пользователь не смолсет самостоятельно проконтролировать географические точки, не попавшие в рейс. По этой причине критерий отбора неполного рейса будет другим.
В целом задача выбора неполного допустимого рейса представляет собой задачу оптимизации на множестве допустимых рейсов в соответствии с некоторым функционалом. Из выше сказанного, очевидно, что для отдельного запуска модуля данный функционал имеет вид: Кїд = \RPil где RPt - некоторый КГР. Для решения задачи маршрутизации в виду специфики использования модуля, описанной ниже, функционал выбора неполного допустимого рейса можно сформулировать следующим образом: /(/,-) = тахр єя рср.я). Здесь вводится понятие диаметра рейса как наибольшего расстояния между двумя точками, ему принадлежащими. Таким образом, выбор оптимального неполного рейса сводится к следующей оптимизационной задаче: 1{у[) -» max, Yi Є Г, B\RPt Ф 0. С точки зрения реализации, следует на каждом шаге запоминать оптимальный на нем рейс, если полный рейс был построен. Тогда решать задачу об оптимальном неполном рейсе будет необходимо только в том случае, когда на первом шаге алгоритма не будет получено ни одного полного допустимого рейса. Из всего изложенного выше можно сделать вывод, что описанный алгоритм построения рейса по географическому району всегда вернет некоторый рейс, удовлетворяющий критериям. При этом значения целевых функционалов по умолчанию могут быть изменены пользователем, не затрагивая саму суть алгоритма.
Подводя итог выше сказанному, сформулируем следующую теорему: Теорема 4. Итеративно-имитационный алгоритм построения маршрута с учетом массогабаритпых ограничений, дозагрузки по ходу выполнения рейса и ограничений, накладываемых расписанием, всегда строит некоторый допустимый маршрут, в общем случае неполный, максимизирующий диаметр построенного рейса.
Информационно-логическая модель. Реализация схемы данных
Отметим также, что процедура сортировки оценивается в п log(n) операций, так как такую сложность имеет сортировка, реализованная в платформе .Net 4.0 (в качестве метода сортировки процедуры Sort используется быстрая сортировка qSort, имеющая такую оценку [49,50]). Поэтому наиболее затратной по процессорному времени является операция сортировки.
В таблице ниже приведены результаты сравнительного тестирования двух методов построения рейсов. Анализировались рейсы, построенные по набору КГР, полученному в результате работы алгоритма кластеризации:
База данных КГР Количество точек, попавших в рейс по методу,основанному на методе Свира. Количество точек, попавших в рейс по итеративному имитационному алгоритму Общее количество точек в КГР
Как видно из представленной выше таблицы, итеративный имитационный алгоритм на пользовательских данных дает лучшие результаты. Это связано с тем, что данный алгоритм рассматривает больше вариантов при построении рейсов, чем алгоритм, основанный на методе Свира.
Тем не менее, реализация алгоритма на основе метода Свира не была исключена, так как в среднем, по результатам испытаний, его работа занимала на 50% меньше процессорного времени. Таким образом, пользователь имеет возможность подключить его к процессу решения задачи маршрутизации для задач очень большой размерности (несколько тысяч заявок на доставку), если быстродействие метода намного критичнее качества получаемого решения. Однако по умолчанию в программном комплексе используется итеративный имитационный метод, разработанный в параграфе 3.5 настоящего исследования.
Модуль построения географических районов реализует алгоритм кластеризации, подробно описанный в параграфах 3.3, 3.4 настоящего исследования.
В результате опроса целевой аудитории программного комплекса было принято решения не предоставлять пользователям явной возможности вручную запускать данный модуль построения географических районов. Такое решение было принято в связи с тем, что логисты предпочитают иметь стационарные, один раз построенные районы. В то же время данный модуль строит их динамически для каждого решения задачи маршрутизации транспорта, поэтому данный модуль реализован в рамках сборки, отвечающей за решение задачи маршрутизации. Вопросы реализации этой сборки рассмотрены ниже.
Пространство имен модели данных включает в себя классы, инкапсулирующие информацию относительно объекта КГР (Claster). Эта сущность описана в параграфе 3.1. КГР характеризуется, прежде всего, заявками на доставку, которые в него попали. Однако при построении КГР алгоритм оперирует не в терминах заявок на доставку, а работает со множеством географических точек, поэтому для ускорения работы алгоритмов кластеризации КГР содержит в себе также список географических точек, попавших в него.
Такой подход приводит к некоторому дублированию информации, но при этом позволяет не определять каждый раз список географических точек КГР по списку попавших в него доставок. С использованием технологий, например, Linq при программной реализации сущности КГР каждое получение списка географических точек по списку попавших в КГР доставок занимает не менее 0(п2), где п - количество заявок на доставку в данном КГР, процессорного времени в терминах О-символики. Такая оценка связана с тем, что выбор точек из доставок проводится перебором каждой заявки. При рассмотрении каждой доставки необходимо проверить, не добавлена ли уже рассматриваемая точка к списку. Операция проверки занимает в среднем О(п) операций.
Пространство имен Algorithms содержит интерфейсы построения начального разбиения на КГР (IFirstStepClasterisation) и улучшения кластеризации (ISecondStepClastersation). Помимо интерфейсов данное пространство имен содержит и их реализации.
Для интерфейса IFirstStepClasterisation, содержащего метод GetFirstStep, возвращающий коллекцию КГР, создано две реализации: метод, основанный на алгоритме Свира, и метод дальней точки. Данные методы подробно рассмотрены в параграфах 3.3 и 3.4 настоящего исследования.
После реализации обоих шагов алгоритма кластеризации были проведены испытания на основании нескольких пользовательских баз. В процессе тестирования были построены разбиения на КГР методом, в котором первый шаг выполнялся по методу, основанном на алгоритме Свира, и алгоритмом, в котором первый шаг выполнялся по методу дальней точки. Второй шаг кластеризации, «улучшение КГР», оставался неизменным. Таким образом, можно сделать вывод о том, что все различия в результатах кластеризации вызваны изменением метода построения первого шага кластеризации. В ходе тестирования использовался также и второй шаг, потому что при проведении эксперимента в критерии оценки входило количество итераций, произведенных алгоритмом улучшения результатов кластеризации. Тем не менее, основным критерием являлся функционал качества кластеризации. А данном случае это была плотность КГР, понятие которой вводилось в пункте 3.2 данного исследования.
