Исследование и разработка методов решения многокритериальных задач маршрутизации транспорта на основе муравьиного алгоритма тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Кубил Виктор Николаевич

• Кубил Виктор Николаевич
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Кубил Виктор Николаевич

ВВЕДЕНИЕ

1. АНАЛИЗ ЗАДАЧ ОПТИМИЗАЦИИ МАРШРУТОВ ТРАНСПОРТНЫХ СРЕДСТВ

1.1. Классификация задач оптимизации маршрутов транспорта

1.2. Определение места задач маршрутизации транспорта в области комбинаторной оптимизации

1.3. Описание классической задачи маршрутизации транспорта

1.4. Обзор и анализ обобщений и расширений задачи маршрутизации транспорта

1.5. Исследование проблемы сбалансированности

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

1.7. Анализ методов метаэвристической оптимизации

1.8. Выводы

2. ПОСТАНОВКА МНОГОКРИТЕРИАЛЬНОЙ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТА С МНОЖЕСТВЕННЫМ ДЕПО И РАЗНОРОДНЫМ ПАРКОМ

2.1. Описание новой задачи

2.2. Построение математической модели

2.3. Определение целевых функций

2.4. Исследование пространства поиска

2.5. Выводы

3. РАЗРАБОТКА МУЛЬТИКОЛОНИАЛЬНОГО МУРАВЬИНОГО АЛГОРИТМА ДЛЯ РЕШЕНИЯ ЗАДАЧ МАРШРУТИЗАЦИИ ТРАНСПОРТА

3.1. Базовые идеи оптимизации подражанием муравьиной колонии

3.2. Имитация муравьиной колонии с помощью симулятора АйСеПБ

3.3. Исследование проблемы декомпозиции задачи маршрутизации транспорта

3.4. Разработка метода мультиколониальной муравьиной системы

3.5. Демонстрация принятия решений муравьиными колониями на конкретном примере

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

3.7. Использование элитных муравьев

3.8. Выводы

4. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ

4.1. Организация вычислительного эксперимента

4.2. Оценка сложности мультиколониального муравьиного алгоритма

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

4.4. Разработка метода комбинирования алгоритмов локального поиска

4.5. Оценка точности мультиколониального муравьиного алгоритма

4.6. Исследование целевых функций

4.7. Получение исходных картографических данных с помощью геоинформационных систем

4.8. Примеры практического применения результатов

4.9. Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК СОКРАЩЕНИЙ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ А: ИСХОДНЫЙ ТЕКСТ ПРОГРАММЫ МАРШРУТИЗАЦИИ

ТРАНСПОРТА НА ОСНОВЕ МУРАВЬИНОГО АЛГОРИТМА

ПРИЛОЖЕНИЕ Б: СВИДЕТЕЛЬСТВА О ГОСУДАРСТВЕННОЙ РЕГИСТРАЦИИ

ПРОГРАММ ДЛЯ ЭВМ

ПРИЛОЖЕНИЕ В: АКТЫ О ВНЕДРЕНИИ И ИСПОЛЬЗОВАНИИ

РЕЗУЛЬТАТОВ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

ВВЕДЕНИЕ

Транспортировка затрагивает многие этапы систем производства и распределения, и представляет собой важный компонент конечной стоимости продукта [1]. По оценкам специалистов транспортные издержки могут составить до половины всех расходов на логистику. Снижение доли этих затрат во многом достигается за счет планирования рациональных маршрутов различного назначения на транспортной сети, что часто сводится к решению определенного варианта задачи маршрутизации транспорта (англ. Vehicle Routing Problem, VRP).

VRP является хорошо известным направлением исследований в области комбинаторной оптимизации и одним из наиболее важных классов задач транспортной логистики, находя применение практически во всех областях транспортировки от сбора почты до обработки багажа в аэропорту. Целью задач данного класса обычно является минимизация стоимости, расстояния или времени, связанных с транспортировкой, за счет определения оптимальной последовательности посещения клиентов для парка транспортных средств (ТС), расположенных в условном депо. Разработка и применение методов системного анализа, управления и обработки информации для автоматизации решения VRP считается эффективным способом экономии ресурсов предприятий [2]. Высокий интерес к VRP вызван одновременно практической значимостью и значительной сложностью - большинство задач данного класса являются NP-трудными.

История задач класса VRP насчитывает более полувека [3], и исследования вокруг них ведутся все так же активно [4], однако в России данное направление развито хуже, чем за рубежом, и представлено в основном в рамках специализированных производств [5]. Классическая постановка задачи, ее базовые модели, а также наиболее известные обобщения и расширения были предложены различными зарубежными авторами, на опыт которых ссылаются современные исследователи, в том числе российские.

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

ограничениями, накладываемыми на получаемое решение. Однако они основаны на моделях, как правило, не позволяющих в полной мере учесть множество факторов, определяющих качество и стоимость получаемых маршрутов. Новая тенденция исследований в данной области в основном сосредоточена на многофакторых реальных жизненных ситуациях, в связи с чем возникают более сложные и обобщенные варианты VRP [6]. В настоящее время наиболее интересными для исследований считаются комплексные VRP (англ. «Rich VRP»), комбинирующие различные реальные условия и ограничения. В частности, рассматриваемая в данной работе VRP характеризуется многокритериальностью, множественным депо и разнородным парком транспортных средств, что приближает ее ко многим существующим транспортно-логистическим задачам распределения. Хотя, такие варианты постановки лучше согласуются с практикой, они, как правило, требуют поиска новых подходов к решению, поскольку известные методы ограничены в применении и ориентированы лишь на базовые разновидности VRP.

В последние годы в качестве инструмента оптимизации в различных сферах, таких как наука, коммерция и инженерия, активно используются метаэвристики [7]. Их отличительной особенностью является детальное изучение пространства поиска, определяющее множество допустимых решений - объектов комбинаторной оптимизации. Вклад в исследование современных метаэвристических методов внесли Ф. Гловер, Дж. Холланд, Э. Талби, Дж. Кеннеди, Р. Эберхарт, М. Дориго, Д. Карабога, С. Янг, С. Деб, C. Смит, М. Эгерстедт, С. Люк, А.П. Карпенко, Ю.А. Скобцов, Е.Е. Федоров, С.Д. Штовба, В.М. Курейчик, В.В. Курейчик, Л.А. Гладков, Ю.А. Кочетов, А.В. Пантелеев и др. Одними из наиболее перспективных считаются метаэвристики роевого интеллекта, инспирированные природными системами и описывающие коллективное поведение децентрализованных самоорганизующихся систем [8, 9]. Цель роевого интеллекта состоит в том, чтобы смоделировать простые поведения агентов, их локальные взаимодействия с окружением и другими агентами так, чтобы получить более сложные поведения для решения сложных проблем, главным образом

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

Актуальность исследования. Большое число реальных приложений широко показало, что использование методов оптимизации и автоматизированных процедур при решении задач класса VRP дает существенную экономию в глобальных транспортных расходах [11], что, с учетом высокой доли транспортного сектора в ВВП, имеет важное значение в масштабах российской экономики: согласно обзору Организации экономического сотрудничества и развития (ОЭСР) повышение эффективности транспортного сектора на 10% приведет к ожидаемому росту ВВП России на 0,8%. В связи с этим формализация задач VRP и разработка перспективных методов для их решения является актуальным направлением исследований в области комбинаторной оптимизации. Кроме того, интеллектуализация транспортно-логистических систем за счет разработки и внедрения новых эффективных алгоритмов маршрутизации способствует связанности территорий и относится к одному из приоритетных направлений научно-технологического развития Российской Федерации -«Связанность территории Российской Федерации за счет создания интеллектуальных транспортных и телекоммуникационных систем, а также занятия и удержания лидерских позиций в создании международных транспортно -логистических систем, освоении и использовании космического и воздушного пространства, Мирового океана, Арктики и Антарктики» (указ Президента РФ «О стратегии научно-технологического развития Российской Федерации» № 642 от 01.12.2016). Задачи маршрутизации являются ключевыми в областях транспортных перевозок, перемещения и логистики и представляют огромный практический интерес.

Цель работы заключается в исследовании и разработке эффективных методов решения многокритериальных задач VRP на основе технологии

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

- формализация новой VRP с учетом многокритериальности, асимметричности, множественности депо и разнородности парка ТС, в виде обобщенной математической модели;

- разработка и исследование нового метода решения VRP на основе принципа подражания муравьиной колонии;

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

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

- разработка метода комбинирования локального поиска с предложенным муравьиным алгоритмом для повышения эффективности последнего;

- реализация предложенных алгоритмов и методов решения многокритериальных VRP в виде программного комплекса для ЭВМ и их экспериментальное исследование.

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

Научная новизна результатов:

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

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

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

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

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

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

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

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

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

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

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

2. Метод мультиколониальной муравьиной системы и разработанный на его основе модифицированный муравьиный алгоритм, позволяющий получить приближенное решение VRP за полиномиальное время при учете многокритериальности, множественности депо и разнородности парка ТС (соответствует п. 4 паспорта специальности 05.13.01).

3. Метод настройки стохастических оптимизационных алгоритмов, позволяющий автоматически подбирать псевдооптимальные значения свободных параметров в том числе мультиколониального муравьиного алгоритма (соответствует п. 4 паспорта специальности 05.13.01).

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

5. Результаты экспериментального исследования предложенных методов и алгоритмов (соответствует п. 12 паспорта специальности 05.13.01).

Апробация работы. Основные научные и практические результаты работы докладывались и обсуждались на Международной научно-практической конференции «Теория, методы проектирования, программно-техническая платформа корпоративных информационных систем» (Новочеркасск, 2014 г.), Научно-технической конференции и выставке инновационных проектов, выполненных вузами и научными организациями ЮФО в рамках участия в реализации федеральных целевых программ и внепрограммных мероприятий, заказчиком которых является Минобрнауки России (Новочеркасск, 2014 г.), Международной научно-практической конференции «Моделирование. Теория,

методы и средства» (Новочеркасск, 2016 г.), Всероссийских научно-практических конференциях «Информационно-телекоммуникационные системы и технологии» (Кемерово, 2015, 2017 гг.), Международной молодежной научно-практической конференции «Моделирование. Фундаментальные исследования, теория, методы и средства» (Новочеркасск, 2017 г.), Международной молодежной научно-практической конференции «Фундаментальные исследования, методы и алгоритмы прикладной математики в технике, медицине и экономике» (Новочеркасск, 2017 г.), Международной молодежной научно-практической конференции «Фундаментальные основы, теория, методы и средства измерений, контроля и диагностики» (Новочеркасск, 2018 г.), Всероссийской научно-практической конференции «Интеграция науки и практики как механизм развития отечественных наукоемких технологий производства» (Каменск, 2018 г.), Международной научно-практической конференции «Фундаментально-прикладные проблемы безопасности, живучести, надёжности, устойчивости и эффективности систем» (Елец, 2018 г.), Международной конференции «International Conference on Applied Innovation in IT» (ICAIIT, Кётен, 2018 г.), Международной научно-технической конференции «Пром-Инжиниринг» (Челябинск, 2018 г.), Международной мультидисциплинарной конференции по промышленному инжинирингу и современным технологиям «Far East Con» (Владивосток, 2018 г.). Апробация работы также осуществлялась в рамках программы «УМНИК» Фонда содействия развитию малых форм предприятий в научно-технической сфере, в результате чего по государственным контрактам была реализована НИР «Разработка облачного сервиса автоматизации логистических процессов на основе алгоритма муравьиной колонии» (договоры № 5006ГУ1/2014 и № 9921ГУ2/2015).

Реализация и внедрение результатов работы. Практические и теоретические результаты работы использованы и внедрены на предприятии ООО «Альтаир» и в учебном процессе на кафедре «Программное обеспечение вычислительной техники» ЮРГПУ (НПИ).

Публикации. По теме диссертационной работы опубликовано 24 научные работы, в том числе 3 статьи в журналах из перечня ВАК, 1 статья в международной базе цитирований Scopus и 2 программы для ЭВМ с официальной государственной регистрацией.

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

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

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

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

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

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

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

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

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

1.1. Классификация задач оптимизации маршрутов транспорта

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

Для системного представления широкого множества задач оптимизации маршрутов транспорта была взята за основу иерархическая классификация их характеристик, предложенная Е.М. Бронштейном [12], и дополнена рядом других основополагающих признаков, встречаемых на практике и часто упоминаемых в отечественной и зарубежной литературе за последнее время, среди которых: многокритериальность [13, 14, 15], случайные параметры [16, 17], ограничения по расстоянию [18], ограничения по пунктам производства и потребления [19], условие сбалансированности [20, 21], периодичность планирования [22], кросс-докинг [23], топологические особенности графа [24], требование вывоза груза из пунктов потребления [19, 25]. Важность факторов, отраженных данными характеристиками, показана в соответствующих источниках. В результате были выделены следующие 23 основные характеристики задач оптимизации маршрутов транспорта:

1) Количество пунктов производства:

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

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

2) Количество пунктов потребления:

а) пункт потребления один (в частности, это так, если продукция из разных мест должна доставляться на склад или в пункт сертификации);

б) пунктов потребления несколько.

3) Количество критериев:

а) однокритериальные (при оценке оптимальности маршрутов учитывается только один критерий - либо расстояние, либо время, либо другая характеристика);

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

4) Параметры дорог:

а) дорога характеризуется одним параметром;

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

- все учитываемые характеристики аддитивно зависят от пути;

- среди характеристик есть неаддитивные (например, пропускная способность).

5) Количество груза:

а) груз отсутствует (в задаче не подразумевается перемещение каких-либо материальных предметов, веществ и пр., например, в случае выполнения сервисных работ);

б) количество груза характеризуется вещественным числом (непрерывная задача):

- одним;

- несколькими;

в) количество груза характеризуется целым числом (дискретная задача):

- одним;

- несколькими.

6) Виды груза:

а) однотипный груз;

б) многономенклатурный груз:

- все грузы разрешены;

- есть грузы, запрещенные к перевозке тем или иным ТС;

- для каждого ТС есть ограничения по различным видам перевозимых грузов;

- существуют запреты на совместную перевозку грузов некоторых видов одним ТС.

7) Количество транспортных предприятий:

а) одно (парк транспорта сосредоточен в одном месте);

б) несколько (парк транспорта территориально распределен);

в) совпадают с пунктами производства.

8) Количество ТС:

а) единственное ТС;

б) фиксированное количество доступных ТС;

в) не ограниченное количество доступных ТС.

9) Однородность парка ТС:

а) все ТС одинаковые;

б) различные типы ТС имеют отличающиеся характеристики:

- отличаются по одной характеристике (например, вместимостью);

- отличаются по множеству характеристик (грузоподъемность, стоимость использования, скорость и пр.).

10) Ограничения на вместимость ТС:

а) без ограничений (количеством груза можно пренебречь);

б) предусмотрены ограничения только по одному параметру;

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

11) Требования к перевозке:

а) при перевозке груза из каждого пункта производства в каждый пункт потребления может использоваться одно ТС независимо от перевозимого груза;

б) при перевозке груза из каждого пункта производства одно ТС может развозить грузы в различные пункты потребления;

в) в каждый пункт потребления грузы из разных пунктов производства доставляет одно ТС;

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

12) Дополнительные условия:

а) каждый вид груза должен быть доставлен из некоторого пункта производства в некоторый пункт потребления (в частности, при перевозке пассажиров);

б) не допускается порожний пробег (кроме начального и конечного отрезков маршрута);

в) каждое ТС может совершить только одну поездку;

г) некоторые пункты потребления являются также пунктами производства:

- вывоз из пунктов потребления осуществляется параллельно доставке;

- вывоз из пунктов потребления осуществляется после доставки

13) Ограничения по времени:

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

б) время непрерывного пребывания ТС в пути ограничено;

в) временные окна:

- доставка в пункты потребления осуществляется в указанный интервал времени;

Список литературы диссертационного исследования кандидат наук Кубил Виктор Николаевич, 2019 год

СПИСОК ЛИТЕРАТУРЫ

1. Rodrigue J.P., Comtois C., Slack B. The geography of transport systems. Routledge,

2013.

2. Toth P., Vigo D., eds. Vehicle routing: problems, methods, and applications. 2nd ed. MOS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics, 2014.

3. Dantzig G.B., Ramser J.H. The Truck Dispatching Problem // Management science, Vol. 6, No. 1, 1959. pp. 80-91.

4. Курейчик В.М., Кажаров А.А. Анализ и состояние задачи маршрутизации автотранспорта // Вестник Ростовского государственного университета путей сообщения, № 4, 2013. С. 73-77.

5. Гладков Л.А., Гладкова Н.В. Особенности и новые подходы к решению динамических транспортных задач с ограничением по времени // Известия Южного федерального университета. Технические науки., № 7 (156), 2014. С. 178-187.

6. Caceres-Cruz J., Arias P., Guimarans D., Riera D., Juan A.A. Rich vehicle routing problem: Survey // ACM Computing Surveys (CSUR), Vol. 47, No. 2, 2015. P. 32.

7. Скобцов Ю.А., Федоров Е.Е. Метаэвристики: монография. Донецк: Изд-во «Ноулидж» (Донецкое отделение), 2013. 426 с.

8. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой: учебное пособие. 2-е изд. М.: Изд-во МГТУ им. НЭ Баумана, 2017. 446 с.

9. Кубил В.Н., Мохов В.А. К вопросу о применении роевого интеллекта в решении задач транспортной логистики // Проблемы модернизации инженерного образования в России : сб. науч. ст. по проблемам высшей школы. Юж.-Рос. гос. политехн. ун-т (НПИ). - Новочеркасск: ЮРГПУ(НПИ).

2014. С. 140-143.

10. Zhang S., Lee C.K., Chan H.K., Choy K.L., Wu Z. Swarm intelligence applied in green logistics: A literature review // Engineering Applications of Artificial Intelligence, Vol. 37, 2015. pp. 154-169.

11. Irnich S., Toth P., Vigo D. The family of vehicle routing problems // In: Vehicle Routing: Problems, Methods, and Applications / Ed. by Toth P., Vigo D. SIAM, 2014. pp. 1-36.

12. Бронштейн Е.М., Заико Т.А. Детерминированные оптимизационные задачи транспортной логистики // Автоматика и телемеханика, № 10, 2010. С. 133147.

13. Jozefowiez N., Semet F., Talbi E.G. Multi-objective vehicle routing problems //European journal of operational research, Vol. 189, No. 2, 2008. pp. 293-309.

14. Никонов О.Я., Подоляка О.А., Подоляка А.Н., Скакалина Е.В. Математические методы решения многокритериальной задачи о назначениях // Вестник Харьковского национального автомобильно-дорожного университета, № 55, 2011. С. 103-111.

15. Кубил В.Н., Мохов В.А. Применение муравьиного алгоритма в задачах многокритериальной оптимизации с изменяющимися условиями // Информационно-телекоммуникационные системы и технологии : сб. материалов Всерос., науч.-практ. конф. Кузбасский гос. техн. ун-т им. Т.Ф. Горбачева. - Кемерово : КузГТУ. 2015. С. 80-81.

16. Shanmugam G., Ganesan P., Vanathi D.P.T. Meta heuristic algorithms for vehicle routing problem with stochastic demands // Journal of Computer Science, Vol. 7, No. 4, 2011. P. 533.

17. Lecluyse C., Van W.T., Peremans H. Vehicle routing with stochastic time-dependent travel times // 4OR: A Quarterly Journal of Operations Research, Vol. 7, No. 4, 2009. pp. 363-377.

18. Kek A.G.H., Cheu R.L., Meng Q. Distance-constrained capacitated vehicle routing problems with flexible assignment of start and end depots // Mathematical and Computer Modelling, Vol. 47, No. 1, 2008. pp. 140-152.

19. Berbeglia G., Cordeau J.F., Gribkovskaia I., Laporte G. Static pickup and delivery problems: a classification scheme and survey // Top, Vol. 15, No. 1, 2007. pp. 1-31.

20. Zhou W., Song T., He F., Liu X. Multiobjective vehicle routing problem with route balance based on genetic algorithm // Discrete Dynamics in Nature and Society, 2013.

21. Костюк Ю.Л., Пожидаев М.С. Сбалансированная эвристика для решения задачи маршрутизации транспорта с учетом грузоподъемности // Вестник Томского государственного университета. Управление, вычислительная техника и информатика, Т. 12, № 3, 2010. С. 65-72.

22. Hemmelmayr V.C., Doerner K.F., Hartl R.F. A variable neighborhood search heuristic for periodic routing problems // European Journal of Operational Research, Vol. 195, No. 3, 2009. pp. 791-802.

23. Morais V.W.C., Mateus G.R., Noronha T.F. Iterated local search heuristics for the vehicle routing problem with cross-docking // Expert Systems with Applications, Vol. 41, No. 16, 2014. pp. 7495-7506.

24. Vigo D. A heuristic algorithm for the asymmetric capacitated vehicle routing problem // European Journal of Operational Research, Vol. 89, No. 1, 1996. pp. 108-126.

25. Parragh S.N., Doerner K.F., Hartl R.F. A survey on pickup and delivery problems // Journal für Betriebswirtschaft, Vol. 58, No. 1, 2008. pp. 21-51.

26. Clarke G., Wright J.W. Scheduling of vehicles from a central depot to a number of delivery points // Operations research, Vol. 12, No. 4, 1964. pp. 568-581.

27. Сергеев С.И., Сигал И.Х, Меламед И.И. Задача коммивояжера. Вопросы теории // Автоматика и телемеханика, № 9, 1989. С. 3-33.

28. Lenstra J.K., Kan A.H.G. Complexity of vehicle routing and scheduling problems // Networks, Vol. 11, No. 2, 1981. pp. 221-227.

29. Гольштейн Е.Г., Давид Б.Ю. Задачи линейного программирования транспортного типа. Наука, 1969.

30. Toth P., Vigo D. The vehicle routing problem. Vol 9 of SIAM Monographs on Discrete Mathematics and Applications. Philadelphia. 2002.

31. Кубил В.Н. Обзор обобщений и расширений задачи маршрутизации транспорта // Вестник РГУПС, № 2, 2018. С. 97-109.

32. Herrero R., Rodriguez A., Caceres-Cruz J., Juan A.A. Solving vehicle routing problems with asymmetric costs and heterogeneous fleets // International Journal of Advanced Operations Management, Vol. 6, No. 1, 2014. pp. 58-80.

33. Toth P., Vigo D. Models, relaxations and exact approaches for the capacitated vehicle routing problem // Discrete Applied Mathematics, Vol. 123, No. 1, 2002. pp. 487-512.

34. Christofides N., Mingozzi A., Toth P. The vehicle routing problem // In: Combinatorial Optimization. Wiley, 1979. pp. 315-338.

35. Laporte G., Desrochers M., Nobert Y. Two exact algorithms for the distance-constrained vehicle routing problem // Networks, Vol. 14, No. 1, 1984. pp. 161172.

36. Laporte G., Nobert Y., Desrochers M. Optimal routing under capacity and distance restrictions // Operations research, Vol. 33, No. 5, 1985. pp. 1050-1073.

37. Solomon M.M. Algorithms for the vehicle routing and scheduling problems with time window constraints // Operations research, Vol. 35, No. 2, 1987. pp. 254-265.

38. Cordeau J.F. The VRP with time windows // Montréal: Groupe d'études et de recherche en analyse des décisions, 2000.

39. Nagata Y., Braysy O., Dullaert W. A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows // Computers & operations research, Vol. 37, No. 4, 2010. pp. 724-737.

40. Taillard É., Badeau P., Gendreau M., Guertin F., Potvin J.Y. A tabu search heuristic for the vehicle routing problem with soft time windows // Transportation science, Vol. 31, No. 2, 1997. pp. 170-186.

41. Jindal P. Towards the solution of variants of vehicle routing problem // Global Journal of Computer Science and Technology, Vol. 11, No. 15, 2011.

42. Емельянова Т.С. Об одном генетическом алгоритме решения транспортной задачи с ограничением по времени // Известия Южного федерального университета. Технические науки, Т. 81, № 4, 2008. С. 45-50.

43. Chao I.M., Golden B.L., Wasil E. A new heuristic for the multi-depot vehicle routing problem that improves upon best-known solutions // American Journal of Mathematical and Management Sciences, Vol. 13, No. 3-4, 1993. pp. 371-406.

44. Ho W., Ho G.T., Ji P., Lau H.C. A hybrid genetic algorithm for the multi-depot vehicle routing problem // Engineering Applications of Artificial Intelligence, Vol. 21, No. 4, June 2008. pp. 548-557.

45. Кубил В.Н., Мохов В.А. Автоматизация сетей ресторанов быстрого питания с помощью муравьиного алгоритма // Теория, методы проектирования, программно-техническая платформа корпоративных информационных систем : материалы XII Междунар. науч.-практ. конф. Юж.-Рос. гос. политехн. ун-т (НПИ) им. М.И. Платова. - Новочеркасск : ЮРГПУ(НПИ). 2014. С. 44-46.

46. Daneshzand F. The vehicle-routing problem // Logistics Operations and Management, Vol. 8, 2011. pp. 127-153.

47. Crevier B., Cordeau J.F., Laporte G. The multi-depot vehicle routing problem with inter-depot routes // European Journal of Operational Research, Vol. 176, No. 2, 2007. pp. 756-773.

48. Кубил В.Н. Оптимизация деятельности курьерских служб на основе муравьиного алгоритма // Науч.-техн. конф. и выст. инновац. проектов, выполненных вузами и научными организациями ЮФО в рамках участия в реализации федеральных целевых программ и внепрограммных мероприятий, заказчиком которых является Минобрнауки России : сб. материалов конф. Юж.-Рос. гос. политехн. ун-т им. М.И. Платова. - Новочеркасск : Лик. 2014. С. 119-120.

49. Christofides N., Beasley J.E. The period routing problem // Networks, Vol. 14, No. 2, 1984. pp. 237-256.

50. Francis P., Smilowitz K., Tzur M. The period vehicle routing problem with service choice // Transportation Science, Vol. 40, No. 4, 2006. pp. 439-454.

51. Francis P., Smilowitz K. Modeling techniques for periodic vehicle routing problems // Transportation Research Part B: Methodological, Vol. 40, No. 10, 2006. pp. 872884.

52. Nagy G., Salhi S. Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries // European journal of operational research, Vol. 162, No. 1, 2005. pp. 126-141.

53. Goetschalckx M., Jacobs-Blecha C. The vehicle routing problem with backhauls // European Journal of Operational Research, Vol. 42, No. 1, 1989. pp. 39-51.

54. Wassan N.A., Nagy G., Ahmadi S. A heuristic method for the vehicle routing problem with mixed deliveries and pickups // Journal of Scheduling, Vol. 11, No. 2, 2008. pp. 149-161.

55. Belmecheri F., Prins C., Yalaoui F., Amodeo L. Belmecheri F. et al. Particle swarm optimization to solve the vehicle routing problem with heterogeneous fleet, mixed backhauls, and time windows // Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW), IEEE International Symposium on., 2010. pp. 1-6.

56. Min H. The multiple vehicle routing problem with simultaneous delivery and pickup points // Transportation Research Part A: General, Vol. 23, No. 5, 1989. pp. 377386.

57. Симоненков М.В., Салминен Э.О., Бачериков И.В. Задача маршрутизации промышленного транспорта // Инновации на транспорте и в машиностроении: сборник трудов III Международной научно-практической конференции. Санкт-Петербург. 2015. С. 106-109.

58. Psaraftis H.N. A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem // Transportation Science, Vol. 14, No. 2, 1980. pp. 130-154.

59. Savelsbergh M.W.P., Sol M. The general pickup and delivery problem // Transportation science, Vol. 29, No. 1, 1995. pp. 17-29.

60. Moura A., Oliveira J.F. An integrated approach to the vehicle routing and container loading problems // OR spectrum, Vol. 31, No. 4, 2009. pp. 775-800.

61. Cordeau, J.F., Iori M., Laporte G., Salazar González J.J. A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with LIFO loading // Networks, Vol. 55, No. 1, 2010. pp. 46-59.

62. Dror M., Laporte G., Trudeau P. Vehicle routing with split deliveries // Discrete Applied Mathematics, Vol. 50, No. 3, 1994. pp. 239-254.

63. Dror M., Trudeau P. Savings by split delivery routing // Transportation Science, Vol. 23, No. 2, 1989. pp. 141-145.

64. Archetti C., Savelsbergh M.W.P., Speranza M.G. To split or not to split: That is the question // Transportation Research Part E: Logistics and Transportation Review, Vol. 44, No. 1, 2008. pp. 114-123.

65. Gendreau M., Laporte G., Séguin R. Stochastic vehicle routing // European Journal of Operational Research, Vol. 88, No. 1, 1996. pp. 3-12.

66. Gendreau M., Laporte G., Séguin R. An exact algorithm for the vehicle routing problem with stochastic demands and customers // Transportation science, Vol. 29, No. 2, 1995. pp. 143-155.

67. Chen D., Chen D., Yang Y. Nondeterministic Vehicle Routing Problem: A Review // Advances in Information Sciences and Service Sciences, Vol. 5, No. 9, 2013. pp. 485-493.

68. Garrido P., Riff M.C. DVRP: a hard dynamic combinatorial optimisation problem tackled by an evolutionary hyper-heuristic // Journal of Heuristics, Vol. 16, No. 6, 2010. pp. 795-834.

69. Sariklis D., Powell S. A heuristic method for the open vehicle routing problem // Journal of the Operational Research Society, Vol. 51, No. 5, 2000. pp. 564-573.

70. Brandao J. A tabu search algorithm for the open vehicle routing problem // European Journal of Operational Research, Vol. 157, No. 3, 2004. pp. 552-564.

71. Choi E., Tcha D.W. A column generation approach to the heterogeneous fleet vehicle routing problem // Computers & Operations Research, Vol. 34, No. 7, 2007. pp. 2080-2095.

72. Golden B., Assad A., Levy L., Gheysens F. The fleet size and mix vehicle routing problem // Computers & Operations Research, Vol. 11, No. 1, 1984. pp. 49-66.

73. Salhi S., Rand G. K. Incorporating vehicle routing into the vehicle fleet composition problem // European Journal of Operational Research, Vol. 66, No. 3, 1993. pp. 313-330.

74. Gheysens F., Golden B., Assad A. A new heuristic for determining fleet size and composition // Netflow at Pisa. - Springer Berlin Heidelberg, 1986. pp. 233-236.

75. Gendreau M., Laporte G., Musaraganyi C., Taillard E.D. A tabu search heuristic for the heterogeneous fleet vehicle routing problem // Computers and Operations Research, No. 26, 1999. pp. 1153-1173.

76. Wassan N.A., Osman I.H. Tabu search variants for the mix fleet vehicle routing problem // Journal of the Operational Research Society, Vol. 53, No. 7, 2002. pp. 768-782.

77. Tarantilis C.D., Kiranoudis C.T., Vassiliadis V.S. A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem // European Journal of Operational Research, Vol. 152, No. 1, 2004. pp. 148-158.

78. Bard J.F., Huang L., Dror M., Jaillet P. A branch and cut algorithm for the VRP with satellite facilities // IIE transactions, Vol. 30, No. 9, 1998. pp. 821-834.

79. Setak M., Jalili Bolhassani S., Karimi H. A node-based mathematical model towards the location routing problem with intermediate replenishment facilities under capacity constraint // International Journal of Engineering, Vol. 27, No. 6, 2014. pp. 911-920.

80. Тюрин А.Ю., Зырянов В.В. Двухэшелонная система доставки продукции предприятий пищевой промышленности // Вестник Кузбасского государственного технического университета, № 2 (90), 2012. С. 124-127.

81. Bard J.F., Huang L., Jaillet P., Dror M. A decomposition approach to the inventory routing problem with satellite facilities // Transportation science, Vol. 32, No. 2, 1998. pp. 189-203.

82. Goel A., Gruhn V. A general vehicle routing problem // European Journal of Operational Research, Vol. 191, No. 3, 2008. pp. 650-660.

83. Кубил В.Н. Сравнение сбалансированной и многокритериальной задач маршрутизации транспорта // Интеграция науки и практики как механизм развития отечественных наукоемких технологий производства : сб. науч. ст. по материалам VII Всерос. науч.-практ. конф. Каменск-Шахтинский. -Новочеркасск: Лик, 2018. 2018. С. 246-252.

84. Игнатьев А.Л. Параллельные методы решения задачи коммивояжера // Труды 51-й научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук»: Часть IX. Инновации и высокие технологии. М.: МФТИ. 2008. С. 4-6.

85. Кубил В.Н. Пространство решений задач коммивояжера и маршрутизации транспорта // Фундаментальные исследования, методы и алгоритмы прикладной математики в технике, медицине и экономике : материалы 16-ой Междунар. молодежн. науч.-практ. конф. ЮРГПУ (НПИ) им. М.И. Платова. - Новочеркасск : Лик. 2017. С. 33-39.

86. Kubil V.N., Mokhov V.A, Grinchenkov D.V. Modelling the generalized multi-objective vehicle routing problem based on costs // Proceedings of the 6th international conference on applied innovations in IT. Perm National Research Polytechnic University Anhalt University of Applied Sciences. - Koethen. 2018. pp. 29-35.

87. Fisher M.L. Optimal solution of vehicle routing problems using minimum k-trees // Operations research, Vol. 42, No. 4, 1994. pp. 626-642.

88. Mitchell J.E. Branch-and-cut algorithms for combinatorial optimization problems // Handbook of applied optimization, 2002. pp. 65-77.

89. Пожидаев М.С. Алгоритмы решения задачи маршрутизации транспорта : дисс. ... канд. техн. наук, Томск, [Электронный ресурс] / Режим доступа : http://www.marigostra.ru/materials/disser.html, 2010. 134 с.

90. Shvaiko P., Euzenat J. A survey of schema-based matching approaches // Journal on data semantics IV. - Springer, Berlin, Heidelberg, 2005. pp. 146-171.

91. Fisher M.L., Jaikumar R. A generalized assignment heuristic for vehicle routing // Networks, Vol. 11, No. 2, 1981. pp. 109-124.

92. Gillett B.E., Miller L.R. A heuristic algorithm for the vehicle-dispatch problem // Operations research, Vol. 22, No. 2, 1974. pp. 340-349.

93. Ryan D.M., Hjorring C., Glover F. Extensions of the petal method for vehicle routeing // Journal of the Operational Research Society, Vol. 44, No. 3, 1993. pp. 289-296.

94. Osman I.H. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem // Annals of operations research, Vol. 41, 1993. pp. 421451.

95. Prosser P., Shaw P. Study of greedy search with multiple improvement heuristics for vehicle routing problems, University of Strathclyde, Department of Computer Science, Glasgow, Research Report 96/201 1996.

96. Glover F. Future paths for integer programming and links to artificial intelligence // Computers & Operations Research, Vol. 13, No. 5, 1986. pp. 533-549.

97. Щербина О.А. Метаэвристические алгоритмы для задач комбинаторной оптимизации. // Таврический вестник информатики и математики, № 1, 2014. С. 56-72.

98. Blum C., Roli A. Metaheuristics in combinatorial optimization: Overview and conceptual comparison // ACM computing surveys (CSUR), Vol. 35, No. 3, 2003. pp. 268-308.

99. Amberg A., Domschke W., Voss S. Multiple center capacitated arc routing problems: A tabu search algorithm using capacitated trees // European Journal of Operational Research, Vol. 124, No. 2, 2000. pp. 360-376.

100. Arbelaitz O., Rodriguez C., Zamakola I. Low cost parallel solutions for the VRPTW optimization problem // Proceedings International Conference on Parallel Processing Workshops. - IEEE Computer Society. 2001. pp. 176-181.

101. Alba E., Dorronsoro B. Solving the vehicle routing problem by using cellular genetic algorithms // European Conference on Evolutionary Computation in Combinatorial Optimization. Berlin, Heidelberg. 2004. Vol. 3004. pp. 11-20.

102. Bullnheimer B., Hartl R.F., Strauss C. Applying the ant system to the vehicle routing problem // Meta-heuristics: Advances and trends in local search paradigms for optimization. Boston: Kluwer. 1999. pp. 285-296.

103. Ghaziri H.E.L. Solving routing problems by a self-organizing map. In In T. Kohonen, K. Makisara, O. Simula, J. Kangas, editors // Artificial neural network. - North-Holland, Amsterdam, 1991. pp. 829-834.

104. Штовба С.Д. Муравьиные алгоритмы // Exponenta Pro. Математика в приложениях, № 4, 2003. С. 70-75.

105. Gravel M., Price W.L., Gagné C. Scheduling continuous casting of aluminum using a multiple objective ant colony optimization metaheuristic // European Journal of Operational Research, Vol. 143, No. 1, 2002. pp. 218-229.

106. Кубил В.Н. Подходы к моделированию задачи маршрутизации транспорта // Моделирование. Фундаментальные исследования, теория, методы и средства : материалы 17-ой Междунар. науч.-практ. конф. Юж.-Рос. гос. политехн. унт им. М.И. Платова. - Новочеркасск : Лик. 2017. С. 147-151.

107. Li H., Lim A. A metaheuristic for the pickup and delivery problem with time windows // International Journal on Artificial Intelligence Tools, Vol. 12, No. 2, 2003. pp. 173-186.

108. Гринченков Д.В., Кущий Д.Н. Принципы построения программного продукта для поддержки процесса принятия решений на основе интегрированных

экспертных оценок // Известия высших учебных заведений. Электромеханика., № 5, 2012. С. 69-73.

109. Липский В. Комбинаторика для программистов. Москва: М.: Мир, 1989. 213 с.

110. Рейнгольд Э.М., Нивергельт Ю., Део Н. Комбинаторные алгоритмы: Теория и практика (Пер. с англ. под ред. В.Б.Алексеева). М.: Мир, 1980. 476 с.

111. Bremermann H.J. Optimization through evolution and recombination // Yovits M.C., Jacobi G.T. and Goldstein G.D. (Eds.), Self-Organizing Systems, 1962. pp. 93-106.

112. Schultz T.R. In search of ant ancestors // Proceedings of the National Academy of Sciences, 2000. pp. 14028-14029.

113. Goss S., Aron S., Deneubourg J.-L., Pasteels J.M. Self-organized shortcuts in the Argentine ant // Naturwissenschaften, Vol. 76, No. 12, 1989. pp. 579-581.

114. Котенко И.В., Шоров А.В., Нестерук Ф.Г. Анализ биоинспирированных подходов для защиты компьютерных систем и сетей // Труды СПИИРАН, Т. 3, № 18, 2011. С. 19-73.

115. Dorigo M. Optimization, learning and natural algorithms, Politecnico di Milano, Ph.D. Thesis 1992.

116. Dorigo M., Stutzle T. Ant colony optimization: overview and recent advances // Handbook of metaheuristics. Springer, Cham, 2019. pp. 311-351.

117. Кубил В.Н., Мохов В.А. Параметры муравьиного алгоритма на примере задачи поиска пути на графе решетке // Фундаментальные исследования, методы и алгоритмы прикладной математики в технике, медицине и экономике : материалы 17-ой Междунар. молодежн. науч.-практ. конф. ЮРГПУ (НПИ) им. М.И. Платова. - Новочеркасск : Лик. 2018. С. 100-109.

118. Кубил В.Н., Мохов В.А. Имитационное моделирование для исследования возможностей муравьиного алгоритма // Моделирование. Теория, методы и средства : материалы 16-ой Междунар. науч.-практ. конф., посвящ. 110-летию Юж.-Рос. гос. политехн. ун-та (НПИ) им. М.И. Платова. Юж.-Рос. гос.

политехн. ун-т (НПИ) им. М.И. Платова. - Новочеркасск : ЮРГПУ. 2016. С. 199-201.

119. Кубил В.Н. Проблема декомпозиции многокритериальной задачи маршрутизации транспорта // Информационно-телекоммуникационные системы и технологии : сб. материалов Всерос. науч.-практ. конф. Кузбасский гос. техн. ун-т им. Т.Ф. Горбачева. - Кемерово: КузГТУ. 2017. С. 436-437.

120. Кубил В.Н. Многоколониальный муравьиный алгоритм // Фундаментально -прикладные проблемы безопасности, живучести, надёжности, устойчивости и эффективности систем: материалы II междунар. науч.-практ. конф. - Елец: Елецкий государственный университет им. И. А. Бунина. 2018. С. 305-311.

121. Кубил В.Н., Мохов В.А. Многоколониальный муравьиный алгоритм с модификациями для решения многокритериальных задач маршрутизации транспорта // Известия высших учебных заведений. Электромеханика, Т. 61, № 6, 2018. С. 94-109.

122. Глушко С.И. Иерархические нечеткие многоколониальные муравьиные алгоритмы и комплекс программ оптимизации телекоммуникационных сетей нефтетранспортных предприятий : дисс. ... канд. техн. наук, Смоленск, 2013. 145 с.

123. Middendorf M., Reischle F., Schmeck H. Multi colony ant algorithms // Journal of Heuristics, Vol. 8, No. 3, 2002. pp. 305-320.

124. Stutzle T., Hoos H.H. MAX-MIN ant system // Future generation computer systems, Vol. 16, No. 8, 2000. pp. 889-914.

125. White T., Kaegi S., Oda T. Revisiting elitism in ant colony optimization // InGenetic and Evolutionary Computation Conference. Springer, Berlin, Heidelberg. 2003. pp. 122-133.

126. Beiranvand V., Hare W., Lucet Y. Best practices for comparing optimization algorithms // Optimization and Engineering, Vol. 18, No. 4, 2017. pp. 815-848.

127. Королюк В.С., Портенко Н.И., Скороход А.В., Турбин А.Ф. Справочник по теории вероятностей и математической статистике. М.: Наука, 1985. 640 с.

128. Holgate P. The lognormal characteristic function. // Communications in Statistics-Theory and Methods, 1989. pp. 4539-4548.

129. Dorigo M., Gambardella L.M. Ant colonies for the travelling salesman problem // BioSystems, Vol. 43, No. 2, July 1997. pp. 73-81.

130. Линник Ю.В. Метод наименьших квадратов и основы математико-статистической теории обработки наблюдений. М.: Физматгиз, 1962. 352 с.

131. Елисеева И.И., Юзбашев М.М. Общая теория статистики: Учебник. 5-е изд. Москва: Финансы и статистика, 2004.

132. Карпенко А.П., Свианадзе З.О. Метод мета-оптимизации поисковых алгоритмов оптимизации // Наука и образование: научное издание МГТУ им. НЭ Баумана 01, 2011.

133. Кубил В.Н., Мохов В.А., Туровский Ф.А., Филатов В.С. К вопросу о классификации методов повышения эффективности роевых метаэвристик // Науч.-техн. конф. и выст. инновац. проектов, выполненных вузами и научными организациями ЮФО в рамках участия в реализации федеральных целевых программ и внепрограммных мероприятий, заказчиком которых является Минобрнауки России : сб. материалов конф. Юж.-Рос. гос. политехн. ун-т им. М.И. Платова. - Новочеркасск : Лик. 2014. С. 116-118.

134. Кубил В.Н. Подходы к оптимизации муравьиных алгоритмов на примере задачи поиска пути // Студенческая научная весна - 2014 : материалы регион. науч.-техн. конф. (конкурса науч.-техн. работ) студен-тов, аспирантов и молодых ученых вузов Рост. обл. Юж.-Рос. гос. политехн. ун-т (НПИ) ; Отв.ред. О. А. Кравченко. - Новочеркасск : ЮРГПУ (НПИ). 2014. С. 33-35.

135. Кочетов Ю.А. Методы локального поиска для дискретных задач размещения. Модели и алгоритмы. Saarbrucken: Lambert Academic Publishing, 2011. 259 с.

136. Панишев А.В., Плечистый Д.Д., Шевченко В.А. Процедуры локального поиска в комбинированных алгоритмах решения общей задачи коммивояжера // Искусственный интеллект, № 3, 2005. С. 465-470.

137. Lin S. Computer solutions of the traveling salesman problem // Bell System Technical Journal, Vol. 44, No. 10, 1965. pp. 2245-2269.

138. Fischetti M., Toth P., Vigo D. A branch-and-bound algorithm for the capacitated vehicle routing problem on directed graphs // Operations Research, Vol. 42, No. 5, 1994. pp. 846-859.

139. Stutzle T., Holger H.H. Analyzing the run-time behaviour of iterated local search for the TSP // Proc. III Metaheuristics International Conference. Angra dos Reis. 1999. pp. 1-18.

140. Mladenovic N., Hansen P. Variable neighborhood search // Computers & operations research, Vol. 24, No. 11, 1997. pp. 1097-1100.

141. Kubil V.N., Mokhov V.A., Grinchenkov D.V. Measurement of objective functions influence on vehicle routing problems solution // International Multi-Conference on Industrial Engineering and Modern technologies (FarEastCon2018). Vladivostok, Far Eastern Federal University (FEFU). 2018.

142. Кубил В.Н. Анализ влияния целевых функций на решение многокритериальной задачи маршрутизации транспорта // Фундаментальные основы, теория, методы и средства измерений, контроля и диагностики: материалы 19-ой Междунар. молод. науч.-практ. конф. ЮРГПУ (НПИ) М.И. Платова. - Новочеркасск: Лик. 2018. С. 117-123.

143. Географическая информационная система [Электронный ресурс] // ГИС-Ассоциация: [сайт]. URL: http://www.gisa.ru/13058.html (дата обращения: 17.01.2015).

144. Бучатский П.Ю., Бучатская В.В. Инструментальные средства геоинформационных систем для анализа информационной поддержки этапов системного анализа // естник Адыгейского государственного университета. Серия 4: Естественно-математические и технические науки., № 4 (147), 2014.

145. Струков В.Б. Выбор веб-ГИС для представления сведений о земельных участках // Кадастр недвижимости и мониторинг природных ресурсов: тезисы докл. Всеросс. научно-техн. интернет-конф. [Электронный ресурс]. URL:

http://kadastr.org/conf/2010/pub/infoteh/vybor-webgis-zem-uch.htm (дата

обращения: 17.08.2015).

146. JavaScript API: Набор компонентов для размещения интерактивных Яндекс.Карт на страницах сайта или в веб-приложении [Электронный ресурс] // Официальный русскоязычный сайт проекта Яндекс.Карт: [сайт]. URL: https://tech.yandex.ru/maps/jsapi/ (дата обращения: 17.08.2015).

147. Струков В.Б. Использование API Яндекс.Карт для отображения пространственной информации в рамках реализации веб-ГИС приложения // Кадастр недвижимости и мониторинг природных ресурсов: тезисы докл. Всеросс. научно-техн. интернет-конф. [Электронный ресурс]. URL: http:// kadastr.org/conf/2012/pub/infoteh/yandex-api-'webgis.htm (дата обращения: 17.08.2015).

148. Кьяер О.Ю. Очерёдность событий и синхронизация в JavaScript. [Электронный ресурс]. URL: http://javascript.ru/tutorial/events/timing (дата обращения: 17.08.2015).

149. Современный учебник JavaScript: Порядок обработки событий [Электронный ресурс] // JAVASCRIPT.RU: [сайт]. URL: https://learn.javascript.ru/events-and-timing-depth (дата обращения: 17.08.2015).

150. Мохов В.А., Кубил В.Н., Кузнецова А.В., Георгица И.В. Рекурсивный алгоритм синхронизации API-запросов к ГИС-сервису Яндекс. Карты // Фундаментальные исследования, Т. 1, № 9, 2015. С. 33-38.

151. Кубил В.Н. Облачный сервис маршрутизации транспорта на основе муравьиного алгоритма // Научные исследования - 2017: теоретическая часть. Коллективная монография. Под редакцией Л.Г. Миляевой. Москва, 2017. С. 57-67.

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

%% МАРШРУТИЗАЦИЯ ТРАНСПОРТА НА ОСНОВЕ МУРАВЬИНОГО АЛГОРИТМА % Исходный код тестировался с использованием пакета MATLAB R2018b

%% Условия задачи маршрутизации транспорта

nVRP = 1; % количество тестовых задач для эксперимента VRP = repmat(RandVRP([],[]), nVRP,1); for i = 1:nVRP

% Геренируются условия задачи маршрутизации транспорта на случайных % ориентированных графах с заданным количеством вершин и массивом депо VRP(i) = GenerateVRP(5 0, 1:5, 'symmetric'); % 50 вершин, 5 депо

end

Параметры мультиколониального муравьиного алгоритма

param.maxIter = 100; param.maxTime = 60; param.m = uint16(40) param.alpha = 0.75; param.beta = 2; param.epsil = 20; param.rho = 0.1; param.isFig = true;

максимальное количество итерации алгоритма

максимальное время работы алгоритма в секундах

количество межколониальных групп муравьев

вес феромона

вес эвристики

коэффициент элитарности

коэффициент испарения феромона

визуализация

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

solutions = repmat(struct('routes', [], 'cost', realmax, 'iter', 0,

'costList', 0),nVRP,1); %массив результатов TotalTime=tic; % запуск счетчика времени работы алгоритма

for i=1:nVRP

solutions(i) = AMCO(VRP(i), param); if (nVRP>1)

% Отображение прогресса в виде стоимости последнего решения fprintf('%2i) Cost: %8.2f\n',i,solutions(i).cost);

end

end

%% Вывод результата

fprintf('Iteration: %1.2f\n',mean([solutions.iter])); % кол-во итераций fprintf('Mean cost: %1.2f\n',mean([solutions.cost])); % стоимость решения fprintf('Standart: %1.2f\n',std([solutions.cost])); % дисперсия стоимости toc(TotalTime); % время работы алгоритма beep

о ________________________________________________________________________

% ========================================================================

function VRP = GenerateVRP(n, depotVertices, mode) % ГЕНЕРАЦИЯ ВХОДНЫХ МАТРИЦ VRP

% Создает структуру из трех матриц, имитирующих для каждого ТС реальные % картографические данные о дугах, соединяющих пары пунктов, на основе % координат вершин. % Аргументы:

% nVertices - количество вершин графа

% depotVertices - массив вершин-депо каждого ТС

% mode - тип задачи 'summetric' или 'asymmetric'

nVehicles = numel(depotVertices); % количество ТС

% Метрическая задача из монографии Скобцова Ю.А. и Федорова Е.Е. if nargin == 2 || mode == "demo"

% Координаты точек на плоскости pointList = [ ...

565,575; 25,185; 345,750; 945,685; 845,655; ... 880,660; 25,230; 525,1000; 580,1175; 650,1130; ... 1605,620; 1220,580; 1465,200; 1530,5; 845,680; ... 725,370; 145,665; 415,635; 510,875; 560,365; ... 300,465; 520,585; 480,415; 835,625; 975,580; ... 1215,245; 1320,315; 1250,400; 660,180; 410,250; ... 420,555; 575,665; 1150,1160; 700,580; 685,595; ... 685,610; 770,610; 795,645; 720,635; 760,650; ... 475,960; 95,260; 875,920; 700,500; 555,815; ... 830,485; 1170,65; 830,610; 605,625; 595,360; ... 1340,725; 1740,245]; if n > size(pointList,1)

n = size(pointList,1);

end

pointList = pointList(1:n,:); % Евклидово расстояние между точками L = squareform(pdist(pointList));

% Инициализация входных матриц расстояния, времени и стоимости; % время и длина пути между точками соответствуют евклидову расстоянию D = repmat(L,1,1,nVehicles); % матрицы длины T = D; % матрицы времени

C = zeros(n,n,nVehicles); % матрицы фиксированных затрат

% Симметричная задача elseif mode == "symmetric"

% Равномерное распределение точек в квадрате 25x25 км. pointList = 25*rand(n,2); % Евклидово расстояние между точками L = squareform(pdist(pointList));

% Инициализация входных матриц расстояния, времени и стоимости; % время и длина пути между точками соответствуют евклидову расстоянию D = repmat(L,1,1,nVehicles); % матрицы длины T = D; % матрицы времени

C = zeros(n,n,nVehicles); % матрицы фиксированных затрат

% Асимметричная задача elseif mode == "asymmetric"

% Равномерное распределение точек в квадрате 25x25 км. pointList = 25*rand(n,2); % Евклидово расстояние между точками L = squareform(pdist(pointList));

% Инициализация входных матриц длины, времени и стоимости пути D = zeros(n,n,nVehicles); T = D; C = D;

% Матрицы времени и длины пути имитируют для каждого ТС реальные

% картографические данные о дугах, соединяющих пары пунктов, на основе

% евклидова расстояния L между точками

logA = 0.008174184; % log(1.019)

for i = 1:n % первая вершина дуги

for j = i+1:n % вторая вершина дуги

% Имитация значения реального расстояния D(i,j,:) = L(i,j)*(gamrnd(3.4097, 0.132)+1); D(j,i,:) = D(i,j,:) + exprnd(8.2564); % Имитация значения реального времени

T(i,j,:) = lambertw(lognrnd(0.8984,0.2819)*D(i,j,:)*logA)/logA; T(j,i,:) = lambertw(lognrnd(0.8984,0.2819)*D(j,i,:)*logA)/logA; % Значения фиксированных издержек и их связь с евклидовым % расстоянием наименее предсказуемы, поэтому в рамках данного % генератора соответствующие матрицы C оставлены нулевыми

end

end

% Выходная структура задачи маршрутизации транспорта VRP = struct( ...

'pointList', pointList, ...

'depotVertices', depotVertices, ...

'inputMatrices', struct( ...

'D', D, ...

'T', T, ...

'C', C) ...

Весовые коэффициенты целевых функций (см. раздел 2.4 диссертации)

VRP.lambda = {

zeros(1, nVehicles) +

zeros(1, zeros(1, 1.0};

nVehicles) + nVehicles) +

end

весовой коэффициент lambda1 каждого ТС

весовой коэффициент lambda2 каждого ТС

весовой коэффициент lambda3 каждого ТС весовой коэффициент lambda4

function w = lambertw(x) % Функция обратная x = w*exp(w) % Начальное предположение w = ones(size(x)); v = inf*w; % Метод Галлея

while any(abs(w - v)./abs(w) > 1.e-8) v = w; e = exp(w);

f = w.*e - x; % приближение к нулю w = w - f./((e.*(w+1) - (w+2).*f./(2*w+2)));

end end

function solutionBest = AMCO(VRP, param)

%% МУЛЬТИКОЛОНИАЛЬНЫЫЙ МУРАВЬИНЫЙ АЛГОРИТМ: Ant Multi-Colony Optimization % Поиск решения (множества маршрутов и общую стоимость) на основе % муравьиного алгоритма с учетом заданных входных данных и параметров. % Аргументы:

% VRP - условия задачи маршрутизации транспорта

% param - параметры мультиколониального муравьиного алгоритма

%% Условия задачи

pointList = VRP.pointList; % координаты вершин

inputMatrices = VRP.inputMatrices; % входные матрицы

depotVertices = VRP.depotVertices; % вершины-депо

lambda = VRP.lambda; % весовые коэффициенты

Параметры алгоритма

maxIter = param.maxIter; % максимальное количество итераций алгоритма

maxTime = param.maxTime; % максимальное время работы алгоритма

m = param.m; % количество межколониальных групп муравьев

alpha = param.alpha; % вес феромона

beta = param.beta; % вес эвристики

epsil = param.epsil; % коэффициент элитарности

rho = param.rho; % коэффициент испарения феромона

isFig = param.isFig; % визуализация

%% Подготовка данных

nVertices = length(pointList); % количество вершин nVehicles = numel(depotVertices); % количество ТС

% Матрица весов дуг

W = GetWeight(inputMatrices, depotVertices, lambda);

% Матрица привлекательностей дуг в степени beta для всех колоний % рассчитывается заранее и однократно, поскольку значения не меняются в % ходе работы алгоритма Eta beta = 1./W.Abeta;

% Матрица концентраций феромона на дугах для всех колоний Tau = ones(nVertices,nVertices,nVehicles);

% Структура решения

solutionBest= struct('routes',{cell(1,nVehicles)},'cost',realmax,'iter',0); solutions = repmat(solutionBest,1,m);

costList = zeros(1,maxIter);

%% Инициализация графических объектов

if isFig

close all;

figure('WindowState', 'maximized'); % Подокно с маршрутами

gLeft = DrawVRP(pointList, num2cell([depotVertices;depotVertices],1)); gLeft.Axes.Title.String = 'Маршруты'; gLeft.Axes.Position = [0 .5 .5 .5]; % Подокно с феромоном одной из колоний

gRight = DrawVRP(pointList, num2cell([depotVertices;depotVertices],1));

gRight.Axes.Title.String = 'Феромон';

gRight.Axes.Position = [.5 .5 .5 .5];

gRight.PheroLine=gobjects(nVertices);

for i=1:nVertices

for j=i+1:nVertices

gRight.PheroLine(i,j) = ...

line([pointList(i,1),pointList(j,1)], ... [pointList(i,2),pointList(j,2)], ... 'Color',[1 0 0 1],'Visible','off');

end

end

%Динамические графики axes(...

'0uterPosition',[0 0 1 .5],... 'XLim',[1 maxIter+1],'YLim',[0,1000],... 'XGrid','on','YGrid','on',... 'XMinorGrid','on','YMinorGrid','on',... 'NextPlot','add');

gBottom.MaxLine = animatedline('MaximumNumPoints', maxlter, ...

'Color',[0 0 1 .25]); gBottom.AverLine = animatedline('MaximumNumPoints', maxlter, ...

'Color',[0 0 0 .3]); gBottom.MinLine = animatedline('MaximumNumPoints', maxlter, ...

'Color',[1 0 0 .35]); gBottom.BestLine = animatedline('MaximumNumPoints', maxlter, ...

'LineWidth', 1.5); legend('Худшая на итерации', 'Средняя на итерации', ...

'Лучшая на итерации', 'Лучшая глобально '); xlabel("\itt\rm, итерации"); ylabel("Стоимость, усл. ед.");

%% Основной цикл программы tic;

for iter=1:maxIter

% Матрица ненормализованных вероятностей выбора дуг графа для движения % муравьев разных колоний с учетом априорной привлекательносте Eta, % определяемой весом дуги, и апостериорной эффективности Tau, % определяемой концентрацией феромона на дуге P = Eta_beta.*Tau.Aalpha;

%% Формирование решений for team=1:m

% Построение решения k-ой межколониальной группы муравьев solutions(team).routes = ConstructRoutes(depotVertices, P); % Локальная оптимизация solutions(team).routes = ...

LocalInvert(solutions(team).routes, W, false); % Оценка стоимости решения solutions(team).cost = ...

CostFunction(inputMatrices,lambda,solutions(team).routes);

end

%% Обновление результатов

costMean=mean([solutions.cost]); [costMax, ~] = max([solutions.cost]); [costMin, team] = min([solutions.cost]); % Локальная оптимизация

solutions(team).routes = Local2Opt(solutions(team).routes, W, false); solutions(team).cost = ...

CostFunction(inputMatrices,lambda,solutions(team).routes); costMin = solutions(team).cost; % Обновление лучшего решения if iter>1

costList(iter) = costList(iter-l);

end

if costMin < solutionBest.cost

solutionBest = solutions(team); costList(iter) = costMin;

end

%% Обновление уровня феромона

Tau = Tau+DepositPheromone(solutions, depotVertices, nVertices);

Tau = Tau+epsil*DepositPheromone(solutionBest,depotVertices,nVertices);

Tau = Tau.*(1.0-rho); % испарение феромона

%% Визуализация

if isFig

% Рисование графиков

addpoints(gBottom.MaxLine,iter,costMax); addpoints(gBottom.MinLine,iter,costMin); addpoints(gBottom.AverLine,iter,costMean); addpoints(gBottom.BestLine,iter,solutionBest.cost); % Рисование маршрутов

if costMin == solutionBest.cost % лучшие маршруты обновились for k=1:nVehicles

gLeft.RoutesLine(k).XData = ...

pointList(solutionBest.routes{k},1)'; gLeft.RoutesLine(k).YData = ...

pointList(solutionBest.routes{k},2)'; gLeft.DepotsLine(k).XData(2) = ...

pointList(solutionBest.routes{k}(end-1),1)';

gLeft.DepotsLine(k).YData(2) = ...

pointList(solutionBest.routes{k}(end-1),2)';

end

gLeft.RoutesText.String = [ ... ' Шаг:',num2str(iter), ...

' Стоимость:', num2str(solutionBest.cost)];

end

% Рисование феромона

if rem(iter,50)==0 % каждую двадцатую итерацию k=1;

for i=1:nVertices

for j=i+1:nVertices

ph=Tau(i,j,k)+Tau(j,i,k); if ph>5000

ph=ph/10 00 0;

if strcmp(gRight.PheroLine(i,j).Visible,'off') gRight.PheroLine(i,j).Visible='on';

end

gRight.PheroLine(i,j).LineWidth=ph; if ph>1 ph=1;

end

gRight.PheroLine(i,j).Color(4)=ph;

else

if strcmp(gRight.PheroLine(i,j).Visible,'on') gRight.PheroLine(i,j).Visible='off';

end

end

end

end

gRight.Text.String = ...

['Шаг:',num2str(iter),' Феромон колонии №',num2str(k)];

end

% Обновление графического окна drawnow;

end

if toc > maxTime break;

end

end

solutionBest.routes = Local2Opt(solutionBest.routes, W, true); solutionBest.routes = LocalTranspose(solutionBest.routes, W, true); solutionBest.routes = LocalInsert(solutionBest.routes, W, true); solutionBest.cost = CostFunction(inputMatrices,lambda,solutionBest.routes); solutionBest.iter = iter; solutionBest.costList = costList'; end

о _________________________________________________________________________

% =========================================================================

function routes = ConstructRoutes(depotVertices, P) %% ПОСТРОЕНИЕ МАРШРУТОВ МУРАВЬЯМИ

% Формируется решение (множество маршрутов) для текущей группы муравьев % одновременно из нескольких депо на основе вероятностного подхода. % Аргументы:

% depotVertices - список вершин-депо

% P - матрица ненормализованных вероятностей выбора дуг

%% Формирование списка разрешенных для посещения вершин nVertices = size(P,1);

allowedVertices = setdiff(1:nVertices,depotVertices); % разрешенные вершины nAllowedVertices = length(allowedVertices); % количество разрешенных вершин nVehicles = numel(depotVertices); % количество ТС

%% Инициализация массива маршрутов

routesArray = Inf (nAllowedVertices + 2, nVehicles); % маршруты (векторы) routesArray(1,:) = depotVertices; % первая вершина каждого маршрута - депо routeLengths = ones(1, nVehicles); % количество вершин в маршрутах

%% Цикл поочередного включения вершин в маршруты

while nAllowedVertices>0

prob=zeros(nAllowedVertices, nVehicles); % массив вероятностей перехода for k = 1:nVehicles

x = routesArray(routeLengths(k),k); for j=1:nAllowedVertices

y = allowedVertices(j);

% вычисление вероятностей выбора возможных альтернатив prob(j,k) = P(x,y,k);

end

end

% Вероятностный выбор вершины j и транспортного средства k [j, k last] = ChooseAlternate(prob);

% Добавление вершины в маршрут

routeLengths(k last) = routeLengths(k last) + 1;

routesArray(routeLengths(k last), k last) = allowedVertices(j);

% Исключение вершины из списка разрешенных allowedVertices(j) = [];

nAllowedVertices = nAllowedVertices - 1;

end

%% Возврат в депо if true

for k=1:nVehicles

routeLengths(k) = routeLengths(k) + 1; routesArray(routeLengths(k), k) = depotVertices(k);

end

end

%% Преобразование массива маршрутов в ячейки разнойдлины

routes = cell(1, nVehicles); for k = 1:nVehicles

% Преобразование массива маршрутов в ячейки с векторами разной длины routes{k} = routesArray(1:routeLengths(k), k);

end end

function [j, k] = ChooseAlternate(prob) %% ВЫБОР АЛЬТЕРНАТИВЫ

% Определяется очередная вершина для посещения муравьем и маршрут, в % который она войдет на основе множества вероятностей альтрнатив. % Аргументы:

% prob - множество вероятностей альтернатв

nProb = size(prob,1); % количество вариантов nVehicles = size(prob,2); % количество ТС

probF = cumsum(prob(:)); % вычисление значений функции распределения rnd=rand*probF(nProb*nVehicles); % генерация случайного значения

% Поиск варианта, соответствующего сгенерированному значению for i = 1:nProb*nVehicles if rnd <= probF(i)

k = ceil(i / nProb); j = i - (k - 1) * nProb; return

end

end end

о _________________________________________________________________________

О-------------------------------------------------------------------------

function dTau = DepositPheromone(solutions, depotVertices, nVertices) %% НАНЕСЕНИЕ ФЕРОМОНА

% Увеличение концентрации феромона на дугах дуг маршрутов пропорционально % стоимостей решений. % Аргументы:

% Tau - матрицы феромона для всех маршрутов

% solutions - множество решений (маршрутов и стоимостей)

nVehicles = numel(depotVertices); % количество колоний dTau = zeros(nVertices,nVertices,nVehicles); for solution = solutions for k = 1:nVehicles

for i = 1:numel(solution.routes{k})-1 x = solution.routes{k}(i); y = solution.routes{k}(i + 1);