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

УДК 519.682.1

Пожидаев Михаил Сергеевич I,. £

АЛГОРИТМАМ РЕШЕНИЯ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТА

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

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

- 2 ЛЕК 2010

Томск - 2010

004615589

Работа выполнена в Томском государственном университете.

Научный руководитель:

доктор технических наук, профессор Костюк Юрий Леонидович

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

профессор Смагин Валерий Иванович

кандидат технических наук Замятин Александр Владимирович

Ведущая организация:

ГОУ ВПО "Кузбасский государственный технический университет"

Защита состоится 2 декабря 2010 г. в 10:30 на заседании диссертационного совета Д 212.267.08 при Томском государственном университете по адресу: 634050, г. Томск, пр. Ленина, 36, корп. 2, ауд. 102.

Отзывы на автореферат (в двух экземплярах), заверенные гербовой печатью организации, просим направлять по адресу: 634050, г. Томск, пр. Ленина, 36, учёному секретарю ТГУ Буровой Н. Ю.

С диссертацией можно ознакомиться в научной библиотеке Томского государственного университета по адресу: 634050, г. Томск, пр. Ленина, 34а.

Автореферат разослан 2 ноября 2010 г.

Ученый секретарь

диссертационного совета Д212.267.08 доктор технических наук, профессор

А. В. Скворцов

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

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

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

Математическая формулировка этой задачи широко известна как задача маршрутизации транспорта (ЗМТ). Существует ряд разновидностей ЗМТ с различными дополнительными условиями, позволяющими учитывать грузоподъёмность транспортных средств и другие ограничения для более полного представления деталей реальной действительности. ЗМТ является обобщением известной задачи коммивояжёра (ЗК) на случай построения сразу нескольких замкнутых маршрутов, проходящих через некоторую общую вершину, называемую депо. ЗМТ и ЗК принадлежат к классу задач дискретной оптимизации и являются NP-трудными. Не существует методов нахождения их точных решений и проверки оптимальности приближённых за полиномиальное время. Известен точный алгоритм решения ЗМТ на основе метода ветвей и границ, но в силу чрезмерно быстрого роста времени вычислений его невозможно применять для задач с более чем 25-30 вершинами.

Один из первых приближённых алгоритмов решения ЗМТ был предложен в 1964 г. (G. Clarke и J. W. Wright). В 1970-х и 1980-х годах исследования были продолжены, и полученные результаты составили группу так называемых классических алгоритмов (J. .В. Bramel, N. Christofides, В. .Е. Gillett, J. Renaud и др.). Эти алгоритмы заложили основные типы подходов к приближённому решению ЗМТ. С середины 1990-х годов исследования сосредоточились в направлении так на-

зываемых метаэвристик. Название метаэвристик указывает на то, что они не являются законченными эвристиками, готовыми для применения, а только представляют собой некоторый метод для построения законченной эвристики для конкретной задачи. Большинство из них основаны на наблюдениях за явлениями живой и неживой природы. Важной их особенностью является способность к преодолению точки локального минимума для продолжения поиска, поэтому потенциально они способны находить более качественные решения по сравнению с классическими эвристиками. Наибольший интерес вызывают следующие методы: поиск с исключениями (M. Gendreau, A. Hertz, G. Laporte, I. H. Osman и др.), моделируемый и детерминированный отжиг (I. H. Osman и др.), генетический алгоритм (J. L. Blanton, G. Jeon и др.), алгоритм на основе муравьиных колоний (В. Bullnheimer и др.) и нейронные сети (Y. Matsuyama и др.). В последние десять лет исследования уклонились в основном в сторону обработки сложных видов ограничений. В отечественной научной литературе решением задач маршрутизации транспорта занимались: А. О. Алексеев, М. Ю. Ахлебинский, И. И. Меламед, С. И. Сергеев, И. X. Сигал и др.

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

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

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

Целью настоящей работы является получение приближённых алгоритмов решения ЗМТ, способных выполнять построение маршрутов для входных данных, содержащих до 1000 вершин и более при использовании матрицы стоимостей переездов и до 1000000 вершин при использовании геометрической информации. В рамках указанной цели были поставлены следующие задачи:

1. Разработка и исследование эффективных приближённых алгоритмов, дающих сбалансированное по количеству вершин в отдельных маршрутах решение ЗМТ при заранее указанном количестве транспортных средств.

2. Разработка и исследование эффективных приближённых алгоритмов, дающих решение ЗМТ с учётом грузоподъёмности транспортных средств и/или с ограничением количества вершин в одном маршруте, а также в случае нескольких депо и для случая несимметричной матрицы расстояний.

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

Научная новизна работы.

1. Предложена модификация приближённого метода двухфазного решения ЗМТ, использующая на этапе кластеризации алгоритм сбалансированного дихотомического деления вершин на группы и позволяющая строить приближённые алгоритмы, обладающие трудоёмкостью порядка 0(п2), показывающие при математическом моделировании снижение времени работы и улучшения качества решений

для задач, содержащих 200 вершин и более, по сравнению с распро-

странёнными метаэвристиками. На основе предложеной модификации приближённого метода двухфазного решения ЗМТ разработаны и реализованы алгоритмы решения сбалансированной ЗМТ, ЗМТ с учётом грузоподъёмности и/или с ограничением количества вершин в каждом маршруте, ЗМТ для нескольких депо.

2. Предложена модификация алгоритма сбалансированного деления вершин на группы с использованием геометрической информации, обладающая трудоёмкостью 0(nlog2n) и позволяющая решать сбалансированную ЗМТ, ЗМТ с учётом грузоподъёмности и/или с ограничением количества вершин в каждом маршруте, ЗМТ с несколькими депо для входных данных, содержащих до 1000000 вершин.

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

Теоретическая значимость работы заключается в следующем:

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

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

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

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

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

Основные защищаемые положения:

1. Модификация приближённого метода двухфазного решения ЗМТ на основе принципа сбалансированного дихотомического деления вершин на группы, а также алгоритмы, созданные на её основе, для решения сбалансированной ЗМТ, ЗМТ с учётом грузоподъёмности и/или с ограничением количества вершин в каждом маршруте, ЗМТ для нескольких депо.

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

3. Оценка погрешности замены несимметричной матрицы стоимостей переездов симметричной.

4. Реализация предложенных алгоритмов решения различных видов ЗМТ в виде библиотеки классов.

Апробация диссертационной работы. Основные положения и отдельные результаты диссертационной работы докладывались и обсуждались на следующих конференциях:

1. XLV Международной научно-студенческой конференции "Информационные технологии" в г. Новосибирске в 2007 г.

2. Международной научно-практической конференции "Информационные технологии и математическое моделирование" в г. Анжеро-Судженске в 2007 г.

3. VII всероссийской научно-практической конференции с международным участием "Информационные технологии и математическое моделирование" в г. Анжеро-Судженске в 2008 г.

4. VIII всероссийской научно-практической конференции с международным участием "Информационные технологии и математическое моделирование" в г. Анжеро-Судженске в 2009 г.

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

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

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

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

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

Гл. 1 посвящена подробному обзору ЗМТи известных методов её решения. Некоторые алгоритмы из этой главы, такие как алгоритм сбережений Кларка-Райта или алгоритм поиска с исключениями Османа, используются в вычислительном эксперименте для сравнительной оценки качества получаемых решений и затраченного времени. Два других алгоритма: алгоритм заметания и алгоритм разрезания общего маршрута приводятся для того, чтобы привести варианты этих алгоритмов для новой постановки задачи.

Разд. 1.1 описывает терминологию, принятую для ЗМТ. Разд. 1.2 содержит точную формулировку этой задачи. Разд. 1.3 содержит классификацию известных приближённых алгоритмов решения ЗМТ с описанием их основных свойств. Различаются классические эвристики и так называемые метаэвристики. Классические эвристики подразделяются на конструктивные алгоритмы, выполняющие полное построение решения, двухфазные алгоритмы, которые содержат фазу кластеризации (деления вершин на группы для каждого транспортного средства) и фазу решения ЗК, а также на группу улучшающих алгоритмов, которые выполняют постепенное итеративное улучшение некоторого начального решения.

Разд. 1.4 описывает ряд наиболее известных конструктивных алгоритмов. Приводится алгоритм сбережений Кларка-Райта и его расши-

рения, последовательный алгоритм вставки Моля-Джеймсона и последовательный алгоритм вставки Кристофидеса-Мингоззи-Тосса.

Разд. 1.5 посвящён описанию двухфазных алгоритмов решения ЗМТ. Эта глава особено интересна для рассмотрения, т. к. предлагаемые далее новые сбалансированные алгоритмы основаны именно на идеях двухфазной обработки. Различаются две группы двухфазных алгоритмов на основе порядка выполняемых операций: алгоритмы, в которых операция разделения вершин на группы для каждого транспортного средства (кластеризация) предшествует операции решения ЗК, и алгоритмы, в которых на первой фазе решается ЗК, а затем выполняется разрезание полученного пути на фрагменты. Описываются алгоритм заметания, алгоритм Фишера-Джекумера, алгоритм Брамела-Симчи-Леви и алгоритм лепестков. П. 1.5.5 посвящён рассмотрению варианта с решением ЗК на первой фазе. Основной вывод, предлагаемый в этом пункте, заключается в том, что процедура оптимального разрезания решения ЗК может быть сведена к задаче нахождения кратчайших путей в нециклическом графе, трудоёмкость решения которой — 0(п2).

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

Разд. 1.7 даёт общую характеристику метаэвристик. В нём описывается их природа, рассматриваются некоторые вопросы их применения на практике и ряд проблем, связанных с их использованием.

Разд. 1.8 подробно описывает алгоритм Османа поиска с исключениями. Он используется для сравнительного тестирования при постановке вычислительного эксперимента, т. к. даёт хорошее качество решений среди других метаэвристик и имеет только два дискретных параметра. Известен ряд других реализаций поиска с исключениями, адаптированных для решения ЗМТ. Они интересны для рассмотрения, но большей частью не подходят для сравнительного тестирования, т. к. предназначены для мягкой обработки ограничения грузоподъёмности, когда допускается его нарушение при системе штрафов. Описываются алгоритмы Генро-Герца-Лапорте, Тейлорда, Ксю-Келли и Риго-Рокарола,

Разд. 1.10 и разд. 1.11 описывают моделируемый и детерминированный отжиг. Моделируемый отжиг — подход к решению задач комбинаторной оптимизации, основанный на идеях, появившихся при наблюдении за процессами, происходящими в металле после достижения температуры плавления. Разд. 1.12 посвящен одному из самых современных направлений в области решения задач комбинаторных оптимизаций — генетическому алгоритму. Он ещё не способен давать решения очень высокого качества, но воспринимается многими исследователями как крайне перспективная идея, т. к. способен обрабатывать сложные виды ограничений. Последние разделы обзора — 1.13 и 1.14 посвящены двум подходам, пока мало исследованным, но потенциально способным дать интересные результаты: алгоритму на основе муравьиных колоний и нейронным сетям. Они приводятся очень кратко, т.к. пока недостаточно материала о возможности их применения для решения ЗМТ.

Разд. 1.15 содержит выводы по первой главе.

Гл. 2 содержит основное описание проведённых исследований. Содержание этой главы можно разделить на две большие части: на алгоритмы для новой постановки ЗМТ с дополнительным условием сбалансирования и на алгоритмы, предназначенные для решения ЗМТ с учётом грузоподъёмности в стандартном виде, но с тенденцией к сбалансированию.

Новая постановка ЗМТ с условием сбалансирования имеет следующий вид:

1. Пусть дано п+1 вершин (п вершин-клиентов и одна вершина-депо), симметричная матрица стоимости переезда между всеми п 4-1 вершинами и число к — желаемое количество маршрутов.

2. Вершина-депо должна входить во все результирующие маршруты.

3. Каждая вершина-клиент входит в один и только один результирующий маршрут.

4. Количество вершин для любой пары маршрутов не должно отличаться более, чем на единицу (новое условие сбалансированности).

5. Суммарная стоимость объезда всех маршрутов должна быть минимальной.

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

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

Разд. 2.2 рассматривает некоторые вопросы расчёта количества вершин для каждого транспортного средства. В разд. 2.4 приводится дихотомическая процедура кластеризации, полученная в ходе исследований алгоритмов решения сбалансированной ЗМТ и показавшая наилучшие результаты. Время работы этой процедуры — 0(п2).

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

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

Разд. 2.7 и разд. 2.8 иллюстрируют влияние условия сбалансированности на алгоритмы, предложенные ранее для обычного вида ЗМТ. Рассматриваются алгоритмы заметания и разрезания общего маршрута. В обоих случаях возможность заранее вычислить количество вершин для каждого транспортного средства приводит к заметному снижению времени работы.

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

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

Результаты вычислительного эксперимента позволяют сделать следующие выводы:

1. По качеству решения алгоритмы расположились в следующем порядке (от худшего к лучшему): "разрезание общего маршрута", "дихотомическая кластеризация по минимуму", "дихотомическая кластеризация по разности". Алгоритм заметания превзошел все остальные при к — 16 и менее, но уступил другим при больших к.

2. При решении задачи с использованием матрицы стоимости переездов наиболее перспективным представляется применение предложенного алгоритма "кластеризация по разности", который можно реализовать с трудоемкостью 0(п2).

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

Вершин / экипажей 2 4 8 16 32 64

32 1,31 1,60 - - - -

64 1,29 1,47 1,94 - - -

128 1,28 1,38 1,70 2,44 - -

256 1,26 1,33 1,55 2,06 3,14 -

512 1,25 1,29 1,44 1,79 2,54 4,11

1024 1,25 1,27 1,37 1,62 2,13 3,22

В разд. 2.10 рассказывается об особенностях сбалансированного алгоритма, предназначенного для решения ЗМТ с учётом грузоподъёмности в её общем виде, но имеющего тенденцию к сбалансированию загрузки транспортных средств.

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

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

Вершин / экипажей 2 4 8 16 32 64

32 1,59 1,98 - - - -

64 1,51 1,80 2,35 - - -

128 1,43 1,63 2,01 2,78 - . -

256 1,38 1,55 1,84 2,37 3,49 -

512 1,33 1,44 1,64 2,02 2,80 4,42

1024 1,32 1,38 1,51 1,79 2,34 3,46

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

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

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

Разд. 2.11 содержит подробное описание шагов алгоритма со всеми деталями и частными случаями. Общую трудоёмкость процедуры сбалансированной кластеризации можно оценить как 0(п2).

В разд. 2.12 приводится постановка и результаты вычислительного

Таблица 3. Результаты вычислительного эксперимента для сбалансированного алгоритма заметания. Приводится среднее значение качества решений по всем выборкам. Достоверность значений равна 0,95 с двумя значащими цифрами.

Вершин / экипажей 2 4 8 16 32 64

32 1,31 1,56 - - - -

64 1,26 1,41 1,92 - - -

128 1,28 1,34 1,65 2,50 - -

256 1,27 1,29 1,48 2,00 3,38 -

512 1,25 1,28 1,37 1,66 2,59 4,68

1024 1,24 1,26 1,32 1,48 2,02 3,51

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

В первой части вычислительного эксперимента алгоритмы испы-тывались на задачах (наборах данных), предложенных Кристофидесом, Мингоззи и Тоссом, на которых испытывались также многие другие алгоритмы решения ЗМТ. Всего задач 14, из них выбраны те, которые соответствуют постановке задаче маршрутизации транспорта с учётом грузоподъёмности. Для получения более высокого качества решений алгоритм Османа выполнялся многократно с изменением параметра длины списка исключений в довольно широком диапазоне в соответствии с рекомендациями автора, после чего выбирался самый лучший из полученных результатов.

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

Во второй части вычислительного эксперимента алгоритмы испы-

тывались на случайно сгенерированных наборах данных. Вершины в виде точек на плоскости размещались согласно равномерному распределению внутри единичного квадрата, депо помещалось в центре. Матрица расстояний вычислялась в виде евклидовых расстояний между точками. Веса вершин (потребности в товаре) генерировались согласно дискретному равномерному распределению в диапазоне от 1 до 10. Для наборов данных из 50 вершин алгоритмы запускались по 100 раз, для 100 вершин — 50 раз, для 150 вершин — 25 раз и для 200 вершин — 10 раз.

При времени работы в десятки раз меньшем сбалансированный алгоритм оказался хуже алгоритма Османа по качеству решения в среднем от 0.5% до 3% в случаях, когда количество вершин в каждом из полученных маршрутов было в среднем менее чем 10. На трех выборках, когда количество вершин в каждом из полученных маршрутов росло с ростом общего числа вершин, картина обратная, при этом преимущество сбалансированного алгоритма достигает более 10% при количестве вершин, равном 200. При этом сбалансированный алгоритм затрачивает на вычисления в десятки раз меньше времени. Применение же комбинации этих двух алгоритмов всегда дает выигрыш (в среднем) по сравнению с алгоритмом Османа.

Таблица 4. Качество и время работы алгоритмов на случайных выборках. Приведены отношения суммарных длин полученных маршрутов к их оценке снизу — сумме длин рёбер минимального остова на всех вершинах и длины самого длинного ребра остова. Приводятся средние величины этих отношений по всем выборкам, а также среднее время работы алгоритмов на одном наборе данных. Достоверность значений равна 0,95 с двумя значащими цифрами. Вычислительный эксперимент проводился на системе с процессором Intel Соге 2 Duo Е8400 под управлением 64-битного варианта GNU/Linux v2.6.25.

Число вершин, Алг. Османа Сбалан. алг. Комбин. алг.

грузоподъёмность

50 (50) 1,83; 0.5 с 1,84; 0,04 с 1,73; 0,5 с

100 (50) 2,19; 3,6 с 2,23; 0,2 с 2,10; 2,7 с

150 (50) 2,43; 23 с 2,52; 0,5 с 2,37; 17 с

200 (50) 2,73; 87 с 2,83; 0,9 с 2,66; 58 с

100 (100) 1,73; 5,5 с 1,60; 0,3 с 1,51; 4,1 с

150 (150) 1,66; 33 с 1,52; 0,8 с 1,43; 19 с

200 (200) 1,62; 144 с 1,45; 2,1 с 1,38; 59 с

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

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

В разд. 2.14 приводится развитие идеи дихотомического сбалансированного деления вершин на группы, позволяющее решать ЗМТ для нескольких депо. Указываются результаты тестирования для двух и четырёх депо. В разд. 2.15 описана оптимизация процедуры дихотомического деления вершин на группы с использованием геометрической информации, позволяющая снизить время работы до 0(п log2 п).

Разд. 2.16 содержит выводы по второй главе.

Гл. 3 рассматривает некоторые вопросы внедрения известных и предложенных алгоритмов решения ЗМТ в геоинформационных системах. В разд. 3.1 предлагается следующий порядок выполнения операций при решении этой задачи: загрузка основных данных карты из внешнего файла, обработка загруженных данных и построение транспортного слоя на карте приложения, построения графа транспортной сети на основе данных транспортного слоя, выбор пунктов обслуживания (клиентов для объезда), депо, указание дополнительных атрибутов решения задачи, запуск алгоритмов решения ЗМТ для вычисления маршрутов и сохранение результатов.

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

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

В разд. 3.2 рассматривается оценка стоимости решения при переходе от несимметричной матрицы стоимости переездов к симметричной. Большая часть алгоритмов не способна работать с несимметричной матрицей. Основной вывод в этом разделе показывает, что, если симметричная матрица построена путём выбора наименьшего значения стоимости среди двух направлений движения, а отклонение значений симметричной и несимметричной матрицы не более, чем в 1+£ раз, то при возврате к стоимости построенного маршрута в несимметричной матрице её значение возрастёт не более, чем в 1 + е/2 раз. Если при этом выполняется правило треугольника, то предлагается называть такой случай почти метрическим пространством расстояний с точностью е. Правило треугольника на реальных данных всегда выполняется, т. к. проезд из одного узла в другой с заездом в некоторый третий не может сократить стоимость передвижения по сравнению с проездом напрямую.

Разд. 3.3 описывает основные детали пользовательского интерфейса приложения, используемыми при решении ЗМТ на практике. Интерфейс позволяет загружать данные о карте дорог, их редактирование, определение основных параметров построения маршрутов и сохранение результатов.

В разд. 3.4 описывается вид интерфейсной части специальной БЬЬ-библиотеки, которая содержит основную реализацию алгоритмов. Эта библиотека экспортирует две функции: ЗоЬеВСУНР и ЗоЬгеУЕР для решения ЗМТ с различными наборами ограничений.

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

Разд. 3.6 содержит выводы по третьей главе.

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

1. В обзоре приведены наиболее известные виды общей задачи ЗМТ, являющейся №-трудной. Известные приближённые методы её реше-

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

2. На основе процедуры сбалансированного дихотомического деления вершин на группы разработаны эффективные приближённые алгоритмы для решения следующих видов ЗМТ: при заданном количестве транспортных средств, ЗМТ с учётом грузоподъёмности и/или с ограничением количества вершин в маршрутах, а также ЗМТ для нескольких депо. Как показал вычислительный эксперимент, разработанные алгоритмы мало уступают по качеству решений одному из лучших метаэвристических алгоритмов для ЗМТ — алгоритму Османа для малых размерностей и превосходят его при больших, обладая при этом существенно меньшей трудоемкостью (порядка 0(п2) или 0(пк^2п) при использовании геометрической информации).

3. В виду того, что большинство алгоритмов не способно работать с несимметричной матрицей стоимости переездов, можно эту матрицу симметризовать. Показано, что при отклонении значений симметричной и несимметричной матрицы не более, чем в 1 + е раз и при выполнении правила треугольника, что соответствует реальным данным, при возврате построенного маршрута к несимметричной матрице его стоимость возрастёт не более, чем в 1 + е/2 раз.

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

Список публикаций по теме диссертации:

1. Пожидаев М. С. Сбалансированная эвристика для решения задачи маршрутизации транспорта с учётом грузоподъёмности / Ю. Л. Ко-

стаж, М. С. Пожидаев // Вестник ТГУ. УВТиИ. — 2010. — № 3.

2. Пожидаев М. С. Приближённые алгоритмы решения сбалансированной задачи к коммивояжёров / Ю. Л. Костюк, М. С. Пожидаев // Вестник ТГУ. УВТиИ. - 2008. - № 1(2). - С. 106-112.

3. Пожидаев М. С. Исследование алгоритмов приближённого решения сбалансированной задачи к коммивояжёров / Ю. Л. Костюк, М. С. Пожидаев // Информационные технологии: Материалы XIV Международной научно-студенческой конференции (10-12 апреля 2007 г.). — Новосибирск: Изд-во Новосибир. ун-та, 2007. — С. 118-119.

4. Пожидаев М. С. Исследования алгоритмов приближённого решения сбалансированной задачи к коммивояжёров // Информационные технологии и математическое моделирование (ИТММ — 2007): Материалы VI Международной научно-практической конференции (9-10 ноября 2007 г.). - Томск: Изд-во Том. ун-та, 2007. - С. 148-149.

5. Пожидаев М. С. Сбалансированная задача к коммивояжёров для нескольких баз / Ю. Л. Костюк, М. С. Пожидаев // Информационные технологии и математическое моделирование (ИТММ — 2008): Материалы VII Всероссийской научно-практической конференции с международным участием (14-15 ноября 2008 г.). — Томск: Изд-во Том. ун-та, 2008. - 41. - С. 182-184.

6. Пожидаев М. С. Сбалансированная задача маршрутизации транспортных средств и проблемы практического применения метаэвристиче-ских стратегий / Ю. Л. Костюк, М. С. Пожидаев // Информационные технологии и математическое моделирование ( ИТТМ — 2009): Материалы VIII Всерос. научн.-практ. конф. с межд. участием (13-14 ноября 2009 г.). - Томск: Изд-во Том. ун-та, 2009. - Ч. 2. - С. 233-235.

Отпечатано в ООО «НИП» . Томск, ул. Советская, 47, тел.: 53-14-70, тираж 100 экз.

Введение

1 Обзор алгоритмов решения ЗМТ

1.1 Терминология.

1.2 Постановка ЗМТ.

1.3 Классификация алгоритмов для решения ЗМТ.

1.4 Конструктивные классические алгоритмы.

1.4.1 Алгоритм Кларка-Райта.

1.4.2 Расширения алгоритма Кларка-Райта.

1.4.3 Последовательный алгоритм вставки Моля-Джеймсона

1.4.4 Последовательный алгоритм вставки Кристофидеса-Мингоззи-Тосса.

1.5 Двухфазные классические алгоритмы.

1.5.1 Алгоритм заметания.

1.5.2 Алгоритм Фишера-Джекумера.

1.5.3 Алгоритм Брамела-Симчи-Леви.

1.5.4 Алгоритм лепестков.

1.5.5 Методы с решением ЗК перед кластеризацией.

1.6 Классические улучшающие алгоритмы

1.6.1 Оптимизация отдельного маршрута.

1.6.2 Алгоритмы для улучшения нескольких маршрутов

1.7 Метазвристики.

1.8 Алгоритм Османа поиска с исключениями

1.8.1 Понятие окрестности решения.

1.8.2 Стратегия запрещения.

1.8.3 Стратегия освобождения удаления из списка исключений

1.8.4 Стратегия выбора.

1.8.5 Специальная структура данных для стратегии "наилучший подходящий".

1.8.6 Функция для определения длины списка исключений

1.8.7 Критерий остановки.

1.8.8 Общий вид алгоритма.

1.9 Другие варианты поиска с исключениями.

1.9.1 Алгоритм Генро-Герца-Л апорте.

1.9.2 Алгоритм Тейлорда.

1.9.3 Алгоритм Ксю-Келли.

1.9.4 Алгоритм Риго-Рокарола.

1.10 Моделируемый отжиг . . . .'.

1.10.1 Ранние алгоритмы моделируемого отжига для решения ЗМТ.

1.10.2 Алгоритм Османа.

1.11 Детерминированный отжиг.

1.12 Генетический алгоритм.

1.12.1 Основной вид генетического алгоритма.

1.12.2 Применение генетического алгоритма для задач упорядочивания

1.12.3 Применение алгоритма для решения ЗМТ.

1.13 Алгоритм на основе муравьиных колоний.

1.14 Нейронные сети.

1.15 Выводы.

2 Сбалансированные алгоритмы решения ЗМТ

• 2.1 Сбалансированная ЗМТ.

2.2 Вычисление количества вершин для каждого транспортного средства в СЗМТ.

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

2.4 Процедура дихотомической кластеризации для СЗМТ.

2.5 Другие варианты дихотомического алгоритма для СЗМТ

2.6 Обменная оптимизация при дихотомическом делении.

2.7 Алгоритм разрезания общего маршрута для СЗМТ.

2.8 Алгоритм заметания для СЗМТ.

2.9 Вычислительный эксперимент для СЗМТ.

2.10 Сбалансированный алгоритм кластеризации для ЗМТУГ

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

2.12 Вычислительный эксперимент для ЗМТУГ.

2.13 Дополнительные варианты сбалансированного алгоритма для ЗМТУГ.

2.13.1 Вариант сбалансированного алгоритма с бэктрекингом

2.13.2 Ограничение количество вершин в маршрутах.

2.14 Вариант сбалансированного алгоритма для нескольких депо

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

2.16 Выводы.

3 Реализация алгоритмов решения ЗМТ

3.1 Основные понятия.

3.2 Обработка несимметричных матриц.

3.3 Пользовательский интерфейс.

3.4 Интерфейс библиотеки для решения ЗМТ.

3.4.1 Описание функции 8о1уеВСУЯР.

3.4.2 Описание функции 8о1уеУ11Р.

3.5 Внутренняя структура библиотеки алгоритмов решения ЗМТ

3.6 Выводы.

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

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

Математическая формулировка этой задачи широко известна как задача маршрутизации транспорта (ЗМТ). Существует ряд разновидностей ЗМТ с различными дополнительными условиями, позволяющими учитывать грузоподъёмность транспортных средств и другие ограничения для более полного представления деталей реальной действительности. ЗМТ является обобщением известной задачи коммивояжёра (ЗК) на случай построения сразу нескольких замкнутых маршрутов, проходящих через некоторую общую вершину, называемую депо. ЗМТ и ЗК принадлежат к классу задач дискретной оптимизации и являются NP-трудными. Не существует методов нахождения их точных решений и проверки оптимальности приближённых за полиномиальное время. Известен точный алгоритм решения ЗМТ на основе метода ветвей и границ, но в силу чрезмерно быстрого роста времени вычислений его невозможно применять для задач с более чем 25-30 вершинами.

Один из первых приближённых алгоритмов решения ЗМТ был предложен в 1964 г. (G. Clarke и J. W. Wright). В 1970-х и 1980-х годах исследования были продолжены, и полученные результаты составили группу так называемых классических алгоритмов (J. .В. Bramel, N. Christofides, В. .Е. Gillett,

J. Renaud и др.)- Эти алгоритмы заложили основные типы подходов к приближённому решению ЗМТ. С середины 1990-х годов исследования сосредоточились в направлении так называемых метаэвристик. Название метаэ-вристик указывает на то, что они не являются законченными эвристиками, готовыми для применения, а только представляют собой некоторый метод для построения законченной эвристики для конкретной задачи. Большинство из них основаны на наблюдениях за явлениями живой и неживой природы. Важной их особенностью является способность к преодолению точки локального минимума для продолжения поиска, поэтому потенциально они способны находить более качественные решения по сравнению с классическими эвристиками. Наибольший интерес вызывают следующие методы: поиск с исключениями (M. Gendreau, A. Hertz, G. Laporte, I. H. Osman и др.), моделируемый и детерминированный отжиг (I. H. Osman и др.), генетический алгоритм (J. L. Blanton, G. Jeon и др.), алгоритм на основе муравьиных колоний (В. Bullnheimer и др.) и нейронные сети (Y. Matsuyama и др.). В последние десять лет исследования уклонились в основном в сторону обработки сложных видов ограничений. В отечественной научной литературе решением задач маршрутизации транспорта занимались: А. О. Алексеев, М. Ю. Ахле-бинский, И. И. Меламед, С. И. Сергеев, И. X. Сигал и др.

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

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

Целью настоящей работы является получение приближённых алгоритмов решения ЗМТ, способных выполнять построение маршрутов для входных данных, содержащих до 1000 вершин и более при использовании матрицы стоимостей переездов и до 1000000 вершин при использовании геометрической информации. В рамках указанной цели были поставлены следующие задачи:

1. Разработка и исследование эффективных приближённых алгоритмов, дающих сбалансированное по количеству вершин в отдельных маршрутах решение ЗМТ при заранее указанном количестве транспортных средств.

2. Разработка и исследование эффективных приближённых алгоритмов, дающих решение ЗМТ с учётом грузоподъёмности транспортных средств и/или с ограничением количества вершин в одном маршруте, а также в случае нескольких депо и для случая несимметричной матрицы расстояний.

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

Научная новизна работы.

1. Предложена модификация приближённого метода двухфазного решения ЗМТ, использующая на этапе кластеризации алгоритм сбалансированного дихотомического деления вершин на группы и позволяющая строить приближённые алгоритмы, обладающие трудоёмкостью порядка 0(п2), показывающие при математическом моделировании снижение времени работы и улучшения качества решений для задач, содержащих 200 вершин и более, по сравнению с распространёнными метаэвристиками. На основе предложенной модификации приближённого метода двухфазного решения ЗМТ разработаны и реализованы алгоритмы решения сбалансированной ЗМТ, ЗМТ с учётом грузоподъёмности и/или с ограничением количества вершин в каждом маршруте, ЗМТ для нескольких депо.

2. Предложена модификация алгоритма сбалансированного деления вершин на группы с использованием геометрической информации, обладающая трудоёмкостью 0(nlog2 п) и позволяющая решать сбалансированную ЗМТ, ЗМТ с учётом грузоподъёмности и/или с ограничением количества вершин в каждом маршруте, ЗМТ с несколькими депо для входных данных, содержащих до 1000000 вершин.

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

Теоретическая значимость работы заключается в следующем:

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

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

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

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

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

Основные защищаемые положения:

1. Модификация приближённого метода двухфазного решения ЗМТ на основе принципа сбалансированного дихотомического деления вершин на группы, а также алгоритмы, созданные на её основе, для решения сбалансированной ЗМТ, ЗМТ с учётом грузоподъёмности и/или с ограничением количества вершин в каждом маршруте, ЗМТ для нескольких депо.

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

3. Оценка погрешности замены несимметричной матрицы стоимостей переездов симметричной.

4. Реализация предложенных алгоритмов решения различных видов ЗМТ в виде библиотеки классов. Апробация диссертационной работы. Основные положения и отдельные результаты диссертационной работы докладывались и обсуждались на следующих конференциях:

1. XLV Международной научно-студенческой конференции "Информационные технологии" в г. Новосибирске в 2007 г.

2. Международной научно-практической конференции "Информационные технологии и математическое моделирование" в г. Анжеро-Судженске в 2007 г.

3. VII всероссийской научно-практической конференции с международным участием "Информационные технологии и математическое моделирование" в г. Анжеро-Судженске в 2008 г.

4. VIILвсероссийской научно-практической конференции с международным участием "Информационные технологии и математическое моделирование" в г. Анжеро-Судженске в 2009 г.

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

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

Гл. 1 диссертации содержит обзор различных постановок ЗМТ и наиболее известных приближённых алгоритмов её решения. Кроме общего вида задачи, приводятся описания ЗМТ с учётом грузоподъёмности транспортных средств, ЗМТ с ограничением количества вершин в каждом маршруте, а также развитие ЗМТ для случая нескольких депо. Упоминаются некоторые дополнительные виды задачи, получившие распространение на практике, но не рассматриваемые детально в работе. В разд. 1.3 приведена детальная классификация известных приближённых алгоритмов решения ЗМТ с общей характеристикой каждой группы. Точные методы решения этой задачи не упоминаются в силу неприемлемо больших затрат вычислительных ресурсов для их применения. Описаны следующие алгоритмы: алгоритм Кларка-Райта с некоторыми расширениями, последовательный алгоритм вставки Моля-Джеймсона, последовательный алгоритм вставки Кристофидеса-Мингоззи-Тосса, алгоритм заметания, алгоритм Фишера-Джекумера, алгоритм Брамела-Симчи-Леви, алгоритм лепестков, а также приведены некоторые идеи подходов, выполняющих последовательное улучшение уже найденного решения. Перечисленные алгоритмы составляют группу так называемых классических эвристик. Известен ряд новых идей, традиционно относимых к другой группе метаэвристик. Метаэвристики являются общими методами решения задач комбинаторной оптимизации, широко известными и за пределами области алгоритмов решения ЗМТ. Их применение для ЗМТ показывает неплохие результаты, но затруднено на практике из-за недостаточно конкретной формулировки. Рассматриваются поиск с исключениями, моделируемый и детерминированный отжиг, генетический алгоритм, алгоритм fia основе муравьиных колоний и нейронные сети.

В гл. 2 изложено основное содержание проведённых исследований. Предлагается новая формулировка ЗМТ с наложенным условием сбалансирования, далее называемая сбалансированной ЗМТ. Она требует, чтобы количество вершин для каждой пары построенных маршрутов не отличалось бы более, чем на единицу. На основе нового вида задачи приведён алгоритм, выполняющий разделение вершин на группы для каждого будущего маршрута при помощи сбалансированной дихотомической процедуры. Для получения окончательного решения ЗМТ требуется решить ЗК внутри каждой группы. Кратко перечислены направления поиска, показавшие во время исследований ухудшение результатов, а также рассмотрено влияние условия сбалансирования на такие известные методы, как алгоритм заметания и разрезание общего маршрута. В каждом случае показано уменьшение времени работы алгоритмов. Приводятся результаты проведённого вычислительного эксперимента для алгоритмов решения сбалансированной ЗМТ. Развитие идеи сбалансированного дихотомического деления позволило создать новый алгоритм решения стандартной ЗМТ с учётом грузоподъёмности, показывающий хорошие результаты качества для больших наборов входных данных при сравнительно непродолжительном времени работы. Проведён вычислительный эксперимент, сравнивающий новый алгоритм с алгоритмом Османа поиска с исключениями. В вычислительном эксперименте была рассмотрена возможность запуска алгоритма Османа поверх решения, полученного алгоритмом сбалансированного дихотомического деления. Новый алгоритм показывает хорошие результаты для наборов данных с более, чем 150 вершинами. После вычислительного эксперимента описаны две разновидности сбалансированного дихотомического алгоритма: вариант с бэктрекингом, показывающий уменьшение стоимости решений в ущерб равномерности загрузки транспортных средств, и вариант, позволяющий задать явное ограничение максимального количества вершин в каждом маршруте. Дальнейшее развитие идеи сбалансированного деления позволило создать алгоритм, решающий ЗМТ для нескольких депо. Приводятся результаты вычислительного эксперимента с запуском алгоритма для задач с двумя и четырьмя депо.

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

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

3.6 Выводы

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

1. Загрузка данных карты из внешнего файла,

2. Построение транспортного слоя карты.

3. Построение графа транспортной сети.

4. Выбор пунктов обслуживания и депо.

5. Вычисление матрицы стоимости переездов.

6. Запуск алгоритмов.

7. Сохранение результатов.

Большинство алгоритмов не способны работать с несимметричной матрицей стоимости переездов. Предлагается использовать симметричную матрицу, полученную выбором наименьшего значения стоимости среди двух направлений движения. Если отличия между симметричной и несимметричной матрицей не больше, чем в 1 + е раз, и выполняется правило треугольника, то будем говорить о почти метрическом пространстве расстояний с точностью е. При условии, что есть возможность разворота маршрута, его стоимость при возврате к несимметричной матрице возрастёт не более, чем в 1 + в/2 раз.

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

Библиотека алгоритмов решения ЗМТ создана на языке С++, имеет размер около 8200 строк исходного кода и содержит 70 классов различного назначения. Особое внимание уделено сохранению возможности конструировать на основе созданных классов приложения, способные решать более широкий круг задач, не предусмотренных на этапе проектирования. Библиотека экспортирует две функции, интерфейс которых выглядит следующим образом:

• int SolveBCVRP(sizet itemCount, const double* rawMatrix, sizet depolndex, sizet desiredVehicleCount, sizet desiredQuality, sizet* result);, t

• int SolveVRP(sizet itemCount, const double* rawMatrix, sizet depolndex, sizet desiredQuality, sizet vehicleCapacity, const sizet* quantities, sizet maxResultLen, sizet* result);

Заключение

На основании материала диссертации можно сделать следующие выводы:

1. В обзоре приведены наиболее известные варианты ЗМТ: ЗМТ в общем виде, ЗМТ с учётом грузоподъёмности, ЗМТ с ограничением количества вершин в маршрутах и ЗМТ для нескольких депо. ЗМТ является NP-трудной задачей. Точный алгоритм на основе метода ветвей и границ не применяется из-за чрезмерно большого времени вычислений. Известные приближённые методы решения ЗМТ делятся на классические эвристики и метаэвристики. К классическим эвристикам относятся конструктивные, двухфазные и улучшающие алгоритмы. Метаэвристики являются общими методами, на основе которых конструируются алгоритмы решения конкретной задачи. Они, как правило, потенциально показывают лучшее качество решений по сравнению с классическими, но их внедрение в программные пакеты затруднено наличием управляющих параметров, а также большей трудоемкостью.

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

3. На основе процедуры сбалансированного дихотомического деления вершин на группы разработаны эффективные приближённые алгоритмы для решения следующих вариантов ЗМТ: при заданном количестве транспортных средств, ЗМТ с учётом грузоподъёмности и/или с ограничением количества вершин в маршрутах, а также ЗМТ для нескольких депо. Как показал вычислительный эксперимент, разработанные алгоритмы мало уступают по качеству решений одному из лучших мета-эвристических алгоритмов для ЗМТ — алгоритму Османа для малых размерностей и превосходят его при больших, обладая при этом существенно меньшей трудоемкостью (порядка 0{п2)). Разработана модификация предложенных алгоритмов на основе геометрической информации, обладающая трудоёмкостью работы 0(п log2 п).

4. В виду того, что большинство алгоритмов не способно работать с несимметричной матрицей стоимости переездов, можно эту матрицу симметри-зовать. Показано, что при отклонении значений симметричной и несимметричной матрицы не более, чем в 1 + е раз и при выполнении правила треугольника, что соответствует реальным данным, при возврате построенного маршрута к несимметричной матрице его стоимость возрастёт не более, чем в 1 + е/2 раз.

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

1. Гэри М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон // М.: Мир, 1982.

2. Кормен Т. X. Алгоритмы: построение и анализ / Т. X. Кормен, Ч. И. Лей-зерсон, Р. Л. Ривест, К. Штайн // М.: МЦНМО, 1990. 960 с.

3. Меламед И. И. Задача коммивояжера. Приближенные алгоритмы / И. И. Меламед, С. Сергеев, И. Сигал // Автоматика и телемеханика. 1989, № 11.

4. Меламед И. К задаче нескольких коммивояжеров // Межвуз. сб. Вып. 647. М,: МИИТ, 1981.

5. Пожидаев М. С. Приближённые алгоритмы решения сбалансированной задачи к коммивояжёров / Ю. Л. Костюк, М. С. Пожидаев // Вестник ТГУ. УВТиИ. — 2008. № 1(2). - С. 106-112.

6. Пожидаев М. С. Сбалансированная эвристика для решения задачи маршрутизации транспорта с учетом грузоподъемности / Ю. J1. Костюк, М. С. Пожидаев // Вестник ТГУ. УВТиИ. 2010. - № 3.

7. Препарата Ф. Вычислительная геометрия: Введение / Ф. Препарата, М. Шеймос // М. : МИр, 1989. 478 с.

8. Alfa A.S. A 3-opt based simulated annealing algorithm for vehicle routing problems / A.S. Alfa, S.S. Heragu, M. Chen // Computers h Industrial Engineering. 1991. — № 21. — P. 635-639.

9. Aksen D. Open vehicle routing problem with driver nodes and time deadlines / D. Aksen, Z. zyurt, N. Aras // Journal of the Operational Research Society, Volume: 58, Issue: 9 (2006).

10. Altinkemer K. Parallel savings based heuristic for the delivery problem / K. Altinkemer, B. Gavish // Operations Research. — 1991. — № 39. — P. 456469.

11. Barbarosoglu G. A tabu search algorithm for the vehicle routing problem / G. Barbarosoglu, D. Ozgur. // Computers & Operations Research. — 1999. — № 26. P. 255-270.

12. Bean J.C. Genetic algorithms and random keys for sequencing and optimization // ORSA Journal on Computing. — 1994. — № 6. — P. 154-160.

13. Beasley J.E. Route-first cluster-second methods for vehicle routing // Omega. 1983. - № 11 - P. 403-408.

14. Bertsimas D.J. A new generation of vehicle routing research:Robust algorithms addressing uncertainty / D.J. Bertsimas, D. Simchi-Levi // Operations Research. — 1996. — № 44. — P. 286-304.

15. Boctor F. F. Optimal solution of column-circular set-partitioning problems / F. F. Boctor and J. Renaud //Working Paper — Faculte des sciences de 1'administration, Universite Laval, Canada — 1993. — P. 93-97.

16. Bramel J.B. A location based heuristic for general routing problems / J.B. Bramel, D. Simchi-Levi // Operations Research. — 1995. — № 43. — P. 649-660.

17. Bullnheimer B. An improved ant system for the vehicle routing problem/ B. Bullnheimer, R.F. Hartl, C. Strauss // Annals of Operations Research, 1998b. — forthcoming.

18. Christofides N' The vehicle routing problem. In N. Christofides, A. Mingozzi, P. Toth, C. Sandi, editors/ N. Christofides, A. Mingozzi, P. Toth // Combinatorial Optimization. — Wiley, Chichester, 1979. — P. 315-338.

19. Clarke G. Scheduling of vehicles from a central depot to a number of delivery points / G. Clarke, J.W. Wright // Operations Research. — 1964. — № 12 — P. 568-581.

20. Colorni A. Distributed optimization by ant colonies. In F. Varela and P. Bourgine, editors / A. Colorni, M. Dorigo, V. Maniezzo //Proceedings of the European Conference on Artificial Life. Elsevier. — Amsterdam, 1991.

21. Colorni A. Ant system for job-shop scheduling / A. Colorni, M. Dorigo, V. Maniezzo, M. Trubian // Belgian Journal of Operations Research, Statistics and Computer Science. 1994. — № 34. - P. 39-53, 1994.

22. Costa D. Ants can colour graphs / D. Costa, A. Hertz // Journal of the Operational Research Society. — 1997. — № 48. — P. 275-305.

23. Desrochers M. A matching based savings algorithm for the vehicle routing problem / M. Desrochers, T.W. Verhoog // Les Cahiers du GBRAD G-89-04, Ecole des Hautes Etudes Commerciales de Montreal, 1989.

24. Dorigo M. Ant colony system: A cooperative learning approach for the traveling salesman problem / M. Dorigo, L.M. Gambardella // IEEE Transactions on Evolutionary Computation. — 1997. — № 1. — P. 53-66.

25. Dorigo M. Ant system: Optimization by a colony of cooperating agents / M. Dorigo, V. Maniezzo, A. Colorni // IEEE Transactions on Systems, Man and Cybernetics. — 1996. № 26. — Part B. — P. 29-41.

26. Dror M. A vehicle routing improvement algorithm. Comparison of a 'Greedy' and a 'Matching' implementation for inventory routing / M. Dror, L. Levy // Computers k Operations Research. — 1986. — № 13. — P. 33-45.

27. Dueck G. New optimization heuristics: The great deluge algorithm and the record-to-record travel // Journal of Computational Physics. — 1993. — № 104. P. 86-92.

28. Dueck G. Threshold accepting: A general purpose optimization algorithm / G. Dueck, T. Scheurer // Journal of Computational Physics. — 1990. — № 90. — P. 161-175.

29. Durbin R. An analogue approach to the travelling salesman problem using an elastic net method / R. Durbin, D. Willshaw // Nature. — 1987. — № 326. — P. 689-691.

30. Fahrion R. On a principle of chain-exchange for vehicle-routing problems (1-VRP) / R. Fahrion, W. Wrede // Journal of the Operational Research Society. 1990. - № 41. - P. 821-827.

31. Fisher M.L. A generalized assignment heuristic for vehicle routing / M.L. Fisher, R. Jaikumar // Networks. 1981. — № 11. - P. 109-124.

32. Foster B. A. An integer programming approach to the vehicle scheduling problem / B. A. Foster, D. M. Ryan // Opl Res. Q. 1976. - № 27. — P. 307-384.

33. Gambardella L.M. Ant colonies for the Quadratic Assignment Problem / L.M. Gambardella, E.D. Taillard, M. Dorigo // Technical Report IDSIA / 4-97, IDSIA. Lugano, Switzerland, 1997.

34. Gaskell T.J. Bases for vehicle fleet scheduling // Operational Research Quarterly. 1967. - № 18. - P. 281-295.

35. Gendreau M. Metaheuristics for the vehicle routing problem / M. Gendreau, G. Laporte, J.- Y. Potvin // Technical Report CRT-963, Centre de Recherche sur les Transports. — Universit de Montral, jan 1994.

36. Gendreau M. New insertion and postoptimization procedures for the traveling salesman problem / M. Gendreau, A. Hertz, G. Laporte // Operations Research. 1992. - № 40. - P. 1086-1094.

37. Gendreau M. A tabu search heuristic for the vehicle routing problem / M. Gendreau, A. Hertz, G. Laporte // Management Science. — 1994. — № 40. — P. 1276-1290.

38. Ghaziri H. Solving routing problems by a self-organizing map. In T. Kohonen, K. Makisara, O. Simula, J. Kangas, editors // Artificial Neural Networks. — North-Holland, Amsterdam, 1991. P. 829-834.

39. Ghaziri H. Algorithmes connexionnistes pour Voptimisation combinatoire : These de doctorat, Ecole Polytechnique / H. Ghaziri. — Federate de Lausanne, Switzerland, 1993.

40. Ghaziri H. Supervision in the self-organizing feature map: Application to the vehicle routing problem. In I.H. Osman and J.R Kelly, editors // Meta-Heuristics: Theory and Applications. — Kluwer, Boston, 1996. — P. 651-660.

41. Gillett B.E. A heuristic algorithm for the vehicle dispatch problem / B.E. Gillett, L.R. Miller // Operations Research. — 1974. № 22. - P. 340349.

42. Glover F. Tabu search: part I // ORSA J. Comp. vl. 1989. - P. 190-206.

43. Glover F. Tabu search: part II // ORSA J. Comp. v2. — 1990. — P. 4-32.

44. Glover F. Tabu search methods for optimization // Feature Issue of Europen J.Oper. Res. V.106. - 1998. - № 2-3.

45. Glover F. Tabu search./ F. Glover, M. Laguna // Boston: Kluwer Acad. Publ., 1997.

46. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, MA, 1989.

47. Goldberg D.E. Alleles, loci and the traveling salesman problem. In J.J. Grefenstette, editor, D.E. Goldberg and R. Lingle // Proceedings of the First International Conference on Genetic Algorithms. — Lawrence Erlbaum, Hillsdale, NJ, 1985. — P. 154-159.

48. Golden B.L. Implementing vehicle routing algorithms / B.L. Golden, T.L. Magnanti, H.Q. Nguyen // Networks. — 1977. — № 7. — P. 113-148.

49. Haimovich M. Bounds and heuristics for capacitated routing problems / M. Haimovich, A.H.G. Rinnooy Kan // Mathematics of Operations Research. — 1985. № 10. - P. 527-542.

50. Holland J. H. Adaptation in Natural and Artificial Systems / J.H. Holland. — The University of Michigan Press, Ann Arbor, MI, 1975.

51. Hopfield J.J. Neural computation of decisions in optimization problems / J.J. Hopfield, D.W. Tank // Biological Cybernetics. 1985. — № 52. — P. 141152.

52. Jeon G. A vehicle routing problem solved by using a hybrid genetic algorithm / G. Jeon, H. Leep, J. Shim // Computers Industrial Engineering, Volume: 53, Issue: 4 (2007).

53. Johnson D. S. The Traveling Salesman Problem: A Case Study in Local Optimization. Local Search in Combinatorial Optimization / . S. Johnson, L. A. McGeoch // Aarts E. H. L., Lenstra J. K. (eds.). N. Y.: John Willey k Sons, 1995.

54. Johnson D.S. The traveling salesman problem: A case study. In E.H.L. Aarts and J.K. Lenstra, editors, / D.S. Johnson, L.A. McGeoch // Local Search in Combinatorial Optimization. — Wiley, Chichester, 1997. — P. 215-310.

55. Kawamura H. Cooperative search on pheromone communication for vehicle routing problems / H. Kawamura, M. Yamamoto, T. Mitamura, K. Suzuki, A. Ohuchi // IEEE Transactions on Fundamentals, E81-A. 1998. - P. 10891096.

56. Kinderwater G.A.P. Vehicle routing: Handling edge exchanges. In E.H.L. Aarts, J.K. Lenstra, editors / G.A.P. Kinderwater and M.W.P. Savelsbergh // Local Search in Combinatorial Optimization. — Wiley, Chichester, 1997. P. 337-360.

57. Kohonen T. // Self-Organization and Associative Memory. — Springer, Berlin, 1988.

58. Laporte G. Classical Heuristics for the Vehicle Routing Problem / G. Laporte, F. Semet // Les Cahiers du GERAD, G98-54, Group for Research in Decision Analysis. — Montreal, Canada, 1998.

59. Lin S. Computer solutions of the traveling salesman problem // Bell System Technical Journal. — 1965. № 44. - P. 2245-2269.

60. Lin S. An effective heuristic algorithm for the traveling salesman problem / S. Lin and B. Kernighan // Operations Research. — 1973. — № 21. — P. 498516.

61. Little J. D. C. An algorithm for the traveling salesman problem / J. D. C. Little, K. G. Murty, D. W. Sweeney, C. Karel // Operations Research, vll (1963), pp 972-989.

62. Manolis N. Kritikos The balanced cargo vehicle routing problem with time windows / Manolis N. Kritikos, George Ioannou // International Journal of Production Economics, vol. 123, Issue 1, pages 42 51. January 2010.

63. Matsuyama Y. Self-organization via competition, cooperation and categorization applied to extended vehicle routing problems //In Proceedings of the International Joint Conference on Neural Networks. — Seattle, WA, 1991. P. 385-390.

64. Or. I. Traveling salesman-type combinatorial optimization problems and their relation to the logistics of regional blood banking. Ph.D. dissertation. — Northwestern University, Evanston, IL, 1976.

65. Osman I.H. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem // Annals of Operations Research. — 1993. — № 41. P. 421-451.

66. Osman I. H. A comparison of heuristics for the generalised assignment problem // Working paper, University of Kent, Canterbury, UK, 1990.

67. Paessens H. The savings algorithm for the vehicle routing problem // European Journal of Operational Research. — 1988. — № 34. — P. 336-344.

68. Pisinger D. A general heuristic for vehicle routing problems / D. Pisinger, S. Ropke // Computers &; Operations Research, Volume: 34, Issue: 8 (2007).

69. Potvin J.-Y. The vehicle routing problem with time windows-Part I: Tabu Search / J.-Y. Potvin, T. Kervahut, B.L. Garcia, J.-M. Rousseau // INFORMS Journal on Computing. 1992. — № 8. — P. 158-164.

70. Potvin J.-Y. Genetic algorithms for the traveling salesman problem // Annals of Operations Research. 1996. — № 63. — P. 339-370.

71. Potvin J.-Y. A genetic algorithm for vehicle routing with backhauling / J.Y. Potvin, C. Duhamel, F. Guertin // Applied Intelligence. — 1996. № 6. -P. 345-355.

72. Potvin J.-Y. The vehicle routing problem with time windows / J.-Y. Potvin and S. Bengio // INFORMS Journal on Computing. — Part II: Genetic search. 1996. - № 8. - P. 165-172.

73. Renaud J. A fast composite heuristic for the symmetric traveling salesman problem / J. Renaud, F.F. Boctor, G. Laporte // INFORMS Journal on Computing. 1996. - № 8. - P. 134-143.

74. Rego C. A subpath ejection method for the vehicle routing problem // Management Science. — 1998. — № 44. — P. 1447-1459.

75. Rego C. A parallel tabu search algorithm using ejection chains for the vehicle routing problem In I.H. Osman and J.P. Kelly, editors / C. Rego, C. Roucairol // Meta-Heuristics: Theory and Applications. — Kluwer, Boston, 1996. — P. 661-675.

76. Renaud J. An improved petal heuristic for the vehicle routing problem / J. Renaud, F. F. Bostor, G. Laporte // Journal of Operational Research Society 1996. — № 47. - P. 329-336.

77. Robuste F. Implementing vehicle routing models/ F. Robuste, C.F. Daganzo, R. Souleyrette II // Transportation Research, 24B. —1990. — P. 263-286.

78. Ryan D. M. Extension of the petal method for vehicle routing / D. M. Ryan, C. Hjorring, F. Glover //J. Opl Res. Soc. 1993. - № 44. - P. 289-296.

79. Schmitt L.J. An empirical computational study of genetic algorithms to solve order based problems: An emphasis on TSP and VRPTC : Ph.D. Dissertation / L.J. Schmitt; Fogelman College of Business and Economics. — University of Memphis, 1994.

80. Schmitt L.J. An evaluation of a genetic algorithmic approach to the vehicle routing problem // Working paper, Department of Information Technology Management. — Christian Brothers University, Memphis, 1995.

81. Stewart W.R. A Lagrangean relaxation heuristic for vehicle routing / W.R. Stewart Jr and B.L. Golden // European Journal of Operational Research. 1984. - № 15. - P. 84-88.

82. Salhi S. Improvements to vehicle routing heuristics / S. Salhi, G.K. Rand //Journal of the Operational Research Society. — 1987. — № 38. — P. 293-295.

83. Taillard E.D. Parallel iterative search methods for vehicle routing problems // Networks. 1993. - № 23. - P. 661-673.

84. Thangiah S.R. Vehicle routing with time windows using genetic algorithms // Technical report SRU- CpSc-TR-93-23. — Slippery Rock University, Slippery Rock, PA, 1993.

85. Tang J. Vehicle routing problem with fuzzy time windows / J. Tang, Z. Pan, R. Fung, H. Lau // Fuzzy Sets and Systems, Volume: 160, Issue: 5 (2009).

86. Thangiah S.R. Algorithms for the vehicle routing problem with time deadlines / S.R. Thangiah, I.H. Osman, R. Vinayagamoorthy, T. Sun // American Journal of Mathematical and Management Sciences. — 1993. — № 13. — P. 323355.

87. Thompson P.M. Cyclic transfer algorithms for the multivehicle routing and scheduling problems / P.M. Thompson, H.N. Psaraftis // Operations Research. — 1993. — № 41. P. 935-946.

88. Ulusoy G. The fleet size and mix problem for capacitated arc routing // Eur. J. Opl Res. 1985. - № 22. - P. 329-337.

89. Van Breedam A. An analysis of the behavior of heuristics for the vehicle routing problem for a selection of problems with vehicle-related, customer-related, and time-related constraints. Ph.D. dissertation. — University of Antwerp, 1994.

90. Vigo D. A heuristic algorithm for the asymmetric capacitated vehicle routing problem // European Journal of Operational Research. — 1996. — № 89. — P. 108-126.

91. Volgenant A. The symmetric traveling salesman problem and edge exchange in minimal 1-trees / A. Volgenant, R. Jonker // European Journal of Operational Research. — 1983. — № 12. — P. 394-403.

92. Wren A. Computers in Transport Planning and Operation. — Ian Allan, London, 1971.

93. Wren A! Computer scheduling of vehicles from one or more depots to a number of delivery points / A. Wren and A. Holliday // Operational Research Quarterly. 1972. - № 23. - P. 333-344.

94. Xu J. A network flow-based tabu search heuristic for the vehicle routing problem / J. Xu, J.P. Kelly // Transportation Science. — 1996. № 30. -P. 379-393.

95. Yellow P. A computational modification to the savings method of vehicle scheduling // Operational Research Quarterly. — 1970. — № 21. — P. 281-283.