Содержание к диссертации
Введение
1 Обзор задач транспортной маршрутизации 9
1.1 Задачи транспортной маршрутизации 9
1.2 Методы решения задач транспортной маршрутизации 21
1.3 Задача коммивояжера (TSP, Traveling salesman problem) 24
1.4 Выводы 33
2 Математическая модель монономенклатурной оптимизационной задачи маршрутизации транспортных средств 34
2.1 Задача 1 34
2.2 Задача 2 37
2.3 Задача 3 45
2.4 Задача 4 52
3 Постановка численных экспериментов, исследование результатов 56
3.1 Точные решения задачи 2 56
3.2 Зависимость длины оптимального маршрута от вместимости транспортного средства 58
3.3 Сравнение эффективности эвристик для решения задачи 2 60
3.4 Сравнение эффективности эвристик для решения задачи 3 65
3.5 Сравнение эффективности жадных алгоритмов для решения задачи 3 68
Заключение 72
Список использованной литературы 74
- Задачи транспортной маршрутизации
- Задача коммивояжера (TSP, Traveling salesman problem)
- Зависимость длины оптимального маршрута от вместимости транспортного средства
- Сравнение эффективности жадных алгоритмов для решения задачи
Введение к работе
Актуальность темы. Транспортная промышленность необходима для обеспечения производства сырьем и доставки готового товара потребителям. Особое внимание уделяется задачам, связанным с планированием маршрутов. По разным оценкам от 30% до 50% всех затрат на логистику связано с транспортными издержками.
Формирование рациональных маршрутов при строгом соблюдении сроков поставок помогает добиться не только минимизации затрат на эксплуатацию, на перевозку людей, но и сократить товарно-производственные запасы на складах.
Задачам в области формирования оптимальных транспортных маршрутов посвящены многочисленные исследования в разных странах мира. Особую актуальность приобретают работы, позволяющие точно вычислять объемы грузоперевозок, рассчитывать количество единиц транспорта, необходимых для обеспечения грузопотоков, определять рациональные маршруты движения, а также сократить суммарные затраты на транспортировку. Эти обстоятельства подтверждают актуальность темы диссертации.
Степень разработанности темы исследования. В работе рассматривается разновидность задачи маршрутизации транспортных средств при перевозке грузов – VRP (Vehicle Routing Problem) – SVRPPD – задача транспортной маршрутизации с вывозом и доставкой одним транспортным средством. Первая задача транспортной маршрутизации была сформулирована Г. Данцигом и Дж. Рамсером в 1959 году, ее постановка инициировала важный класс задач оптимизации. Наиболее часто встречающиеся постановки задач данного класса предполагают доставку однородных грузов из пункта производства или склада потребителям. Предполагается, что целью является минимизация стоимости транспортировки. Встречаются задачи и с другой целевой функцией (например, временем доставки грузов), но их, как правило, можно переформулировать таким образом, что целевая функция будет носить экономический смысл. Как правило, задачи данного класса относятся к NP-трудным, точное решение которых при сколько-нибудь значительной размерности требует огромного времени. На сегодняшний день сформулировано множество вариантов данной задачи, в которых учитываются различные реальные ограничения, разработан ряд алгоритмов приближенного поиска оптимальных решений. Это связано с тем, что развитие логистических процессов и потребность в учете новых факторов ведут к постановке новых задач, требующих, в свою очередь, применения новых методов решения. Создана европейская рабочая группа VeRoLog (Vehicle Routing and Logistics), которая активно занимается задачами транспортной маршрутизации.
Необходимо указать на отличие задачи в рассматриваемой постановке от классической задачи маршрутизации транспортных средств. Особенностями рассматриваемой задачи являются наличие множественных пунктов-производителей, из которых производится вывоз груза. Поставленная задача может быть сформулирована как целочисленная линейная оптимизационная задача, и является обобщением двух известных задач: задачи коммивояжера и задачи о загрузке рюкзака. Менее 10% работ, посвященных задачам транспортной маршрутизации, рассматривают данный вариант задачи. Результаты по близким задачам получены Archetti C., Cordeau J.-F., Desrosiers J., Laporte G., Mingozzi A., Pankratz G., Renaud J., Ченцовым А.Г., Гимади Э.Х. и другими.
Цель и задачи исследования. Целью работы является исследование и
разработка эффективных методов решения монономенклатурных
оптимизационных задач маршрутизации транспортных средств с ограничениями на перевозку.
Для достижения цели работы поставлены и решены следующие задачи:
-
Формализация оптимизационных задач монономенклатурной маршрутизации с одним транспортным средством и несколькими пунктами производства и потребления.
-
Разработка точных алгоритмов решения поставленных задач маршрутизации, в том числе в целочисленном варианте.
-
Разработка эвристических алгоритмов решения поставленных задач маршрутизации.
-
Реализация разработанных методов на ЭВМ, экспериментальная проверка эффективности работы предложенных алгоритмов.
Научная новизна. Получены следующие основные результаты,
обладающие научной новизной:
-
Формализация поставленных задач (в том числе в виде задач целочисленного линейного программирования, булева квадратичного программирования и линейного булева программирования) оптимизационных задач маршрутизации транспортных средств, в которых производится вывоз груза от множества производителей к множеству потребителей (п. 2 паспорта специальности 05.13.01). Исследование данных моделей позволило получить оценки минимальной допустимой вместимости транспортного средства в случае, когда транспортное средство может посетить каждый пункт один раз.
-
Доказательство того, что для любого допустимого способа перевозки грузов по некоторому маршруту при целых исходных данных задачи, существует способ перевозки по тому же маршруту, в котором все веса загружаемого и выгружаемого груза являются целыми. Существование загрузки транспортных средств грузами с целочисленными весами позволило разработать точный алгоритм локальной оптимизации для целочисленного случая задачи (п. 3
паспорта специальности 05.13.01).
-
Методы и алгоритмы решения задачи маршрутизации транспортных средств с учетом различных ограничений. Разработаны и программно реализованы эвристические алгоритмы решения задачи (п. 5 паспорта специальности 05.13.01).
-
Проведены серии вычислительных экспериментов для оценки эффективности предложенных алгоритмов. Получена эмпирическая зависимость длины оптимального маршрута от вместимости транспортного средства.
Практическая и теоретическая значимость. Теоретическая значимость заключается в формализации и решении монономенклатурной оптимизационной задачи маршрутизации транспортных средств с одним транспортным средством c несколькими пунктами производства и потребления с возможностью раздельных доставок и использования складов, относящейся к классу VRP. Предложенные методы и алгоритмы могут применяться для решения родственных задач организации транспортировки грузов.
Практическую ценность работы составляет определение наименьшей
допустимой вместимости транспортного средства и плана перевозок с
минимальными затратами на транспортировку при заданной вместимости
транспортного средства. Это делает возможным применение разработанных
методов построения кратчайшего маршрута и, как следствие, применение их
программной реализации для решения реальных транспортно-логистических
задач на производстве. Программное обеспечение, разработанное в рамках
диссертационной работы, зарегистрировано Федеральной службой по
интеллектуальной собственности, патентам и товарным знакам, свидетельство № 2011615572 «Решение задач транспортной маршрутизации различными методами».
Методология и методы исследования. В работе применяются методы
математического программирования, теории графов, комбинаторной
оптимизации, формализация, алгоритмизация, моделирование и вычислительный эксперимент.
На защиту выносятся следующие результаты:
-
Математические модели оптимизационных задач семейства монономенклатурной маршрутизации транспортных средств с одним транспортным средством и забором и доставкой грузов при различных ограничениях.
-
Точные и эвристические алгоритмы построения решения оптимизационных задач семейства монономенклатурной маршрутизации с одним транспортным средством и забором и доставкой грузов.
-
Сравнительный анализ эффективности предложенных алгоритмов.
Степень достоверности и апробация результатов:
-теоретические положения работы подтверждаются математическими доказательствами;
-адекватность предложенных моделей подтверждается получением
совпадающих результатов при использовании различных подходов и формализаций на широком классе примеров.
Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на:
-
Всероссийской зимней школе-семинаре аспирантов и молодых ученых «Актуальные проблемы науки и техники», Уфа, 2010.
-
Всероссийской конференции «Математическое программирование и приложения», Екатеринбург, ИММ УрО РАН, 2011.
-
Международной научной конференции «Математическое моделирование, оптимизация и информационные технологии», Кишинеу, 2012.
-
Международной конференции «Дискретная оптимизация и исследование операций», Новосибирск, 2013.
-
Второй ежегодной конференции Европейской рабочей группы VeRoLog, Саутгемптон, 2013.
-
Научных семинарах в Уфимском государственном авиационном техническом университете, в Башкирском государственном университете и Институте математики Уфимского научного центра РАН.
Работа выполнена при поддержке РФФИ (проекты № 10-06-00001 и № 13-01-00005).
Публикации. 4 публикации в рецензируемых изданиях из списка ВАК, 5 публикации в других изданиях, 1 свидетельство о регистрации программы.
Структура и объем диссертации. Диссертационная работа состоит из введения, 3 глав, разбитых на параграфы, основных результатов работы, библиографического списка литературы, включающего 206 источников, приложения, содержит 8 таблиц, 11 рисунков. Общий объем – 148 страниц.
Задачи транспортной маршрутизации
Задачи маршрутизации являются одним из наиболее важных классов задач транспортной логистики. Целью данных задач является минимизация стоимости, расстояния или времени транспортировки грузов.
История задач маршрутизации насчитывает более полувека. Первая работа, посвященная данному типу задач, появилась в 1959 году, когда была опубликована статья Г. Данцига и Дж. Рамсера [65], в которой была сформулирована группа задач, впоследствии названная VRP – Vehicle Routing Problem. В данной работе рассматривалась задача нахождения оптимального маршрута доставки парком бензовозов продукта от конечной станции магистрального трубопровода до большого количества обслуживающих терминалов (задача диспетчеризации грузовиков). Используя методы, опирающиеся на формулировки линейного программирования, предложенные ручные вычисления давали решение, близкое к оптимальному, для задач с количеством маршрутов 4 и количеством станции 12. Типичная постановка задачи приведена на рисунке 1.1. Рисунок 1.1 Типичная постановка задачи транспортной маршрутизации и ее решение. Задачи транспортной маршрутизации являются обобщением задачи коммивояжера, поэтому, как правило, относятся к классу NP-сложных задач (однако, некоторые частные варианты задачи могут решаться за полиномиальное время, например, [21]). На текущий момент, имеется множество вариантов задач маршрутизации [38, 164, 165, 8]. В целом, задачи маршрутизации можно разделить по следующим характеристикам [8]:
1. Пункты производства
а) Пункт производства один. Это характерно для ситуации, когда имеется склад (база) с которого осуществляются поставки различным потребителям.
б) Пунктов несколько. Такая ситуация чаще всего возникает, если грузы перевозятся от нескольких производителей к потребителям. Еще один пример - перевозка пассажиров (например, при организации работы таксопарка) В этом случае пункт посадки каждого пассажира можно считать пунктом производства.
2. Пункты потребления.
а) Пункт один. В частности это так, если продукция из разных мест должна доставляться на склад или в пункт сертификации. б) пунктов несколько Эта ситуация наиболее распространенная. Содержательная интерпретация аналогична 1б.
3) Сеть дорог.
а) Дорога характеризуется одним параметром.
б) Дорога характеризуется несколькими параметрами (стоимость перевозки, расстояние, пропускная способность по весу, габариты, ограничения по скорости и др.).
-Все учитываемые характеристики аддитивно зависят от пути.
-Среди характеристик есть неаддитивные (например, пропускная способность).
4) Количество груза.
а) Количество груза характеризуется вещественным числом (непрерывная задача).
-Одним.
-Несколькими.
б) Количество груза характеризуется целым числом (дискретнаязадача).
-Одним.
-Несколькими.
5) Базы ТС (депо).
а) База одна.
б) Баз несколько.
в) Базы совпадают с пунктами производства.
6) Вид груза. а) Задачи с однородным грузом.
б) Многопродуктовые задачи.
7) Характер ТС.
Capacitated VRP (CVRP, задача маршрутизации транспортных средств с учетом грузоподъемности). Базовый вариант задач транспортной маршрутизации, который и был описан в работе Данцига и Рамсера. Парк транспортных средств одинаковой вместимости находятся в одном депо. Задача состоит в нахождении минимальных по затратам (денежным, времени или расстоянию) замкнутых маршрутов, которые полностью обслужат всех клиентов, таких чтобы выполнялось условие не превышения вместимости ТС на каждом из маршрутов. При этом, каждый потребитель обсуживается ТС только один раз, поэтому вместимость ТС должна превышать потребность любого из клиентов. Кристофидесом в 1979 году была дана формализация в виде задачи линейного программирования [58].
Задача коммивояжера (TSP, Traveling salesman problem)
Задача заключается в поиске кратчайшего (самого дешевого) замкнутого маршрута в графе, который проходит через все вершины графа, хотя бы один раз.
Впервые данная задача была сформулирована в руководстве успешного коммивояжера в 1832 году [156]. Также там был представлен оптимальный замкнутый маршрут, проходящий через 45 городов Германии (рисунок 1.2). Общая постановка задачи впервые была сделана в 20 годах 20 века, судя по всему [184], Карлом Менгером [146], который формализовал задачу, названную им впоследствии задачей посланника (messenger problem). Доработанная формализация задачи была дана им в 1929 г. [148]. Далее, он рассмотрел алгоритм полного перебора маршрутов, а также указал на то, что использование эвристик, основанных на поиске ближайшего соседа, в общем случае, может не привести к нахождению оптимального маршрута [145].
В 1931 году, Менгер посетил с лекциями Гарвард. В результате, Whitney поставил задачу о нахождении кратчайшего замкнутого маршрута, проходящего через 48 штатов США. [137]
В 1937 были отмечены связи задачи коммивояжера с играми Гамильтона [137].
Начиная с 40 годов 20 века, несколько изменилось наполнение работ, посвященных задаче коммивояжера. В данных работах впервые были указаны характеристики данной задачи.
Менгер в [147] вернулся к вопросу нахождения кратчайшего пути, походящего через заданное множество точек в метрическом пространстве. Он следует за работой Milgram [150], посвященной нахождению кратчайшей Жордановой кривой, которая проходит через заданное, не обязательно конечное, множество точек в пространстве. И так как множество может быть бесконечным, кратчайшая кривая может и не существовать.
Fejes [79] исследует задачу задачу нахождения кратчайшей кривой, проходящей через п точек в единичном квадрате. Впоследствии, Verblunsky
[200] показал, что ее (кривой) длина меньше 2 + 72.8-n. Дальнейшие работы в этом направлении включают [33, 80].
Нижние границы ожидаемого значения кратчайшего пути через n случайных точек на евклидовой плоскости были изучены Mahalanobis [138], для оценки стоимости выборочной оценки площади земли под джут в Бенгалии. Данное исследование проводилось в 1938 году. Основная доля затрат легла на транспортировку людей и оборудования, в связи с чем и возникла необходимость решения задачи коммивояжера. Mahalanobis дал оценку минимальной длины путиn , однако доказательство приводить не стал.
Данное исследование было продолжено Джессеном [116], который эмпирически получил похожий результат для манхэттенской метрики.
В [137] упоминается, что в 1948 году начали предприниматься попытки связывания задачи линейного программирования с задачей коммивояжера. Robinson [177] сделала неудачную попытку решить задачу коммивояжера, рассмотрев в качестве релаксации задачу о назначениях. В результате, был получен метод сокращения циклов. Связь состояла в том, что задача о назначениях в качестве результата требует оптимальную перестановку, а задача коммивояжера - оптимальную циклическую перестановку. Данный доклад Робинсон для RAND может считаться самым ранним использованием термина "задача коммивояжера".
Beckmann и Koopmans [34] показали, что задача коммивояжера может быть сформулирована, как квадратичная задача о назначениях, для которой, однако, неизвестно быстрых методов решения.
Существенный прогресс был достигнут в работе Dantzig, Fulkerson и Johnson [64]. В ней было предложено несколько новых методов для решения задачи коммивояжера, которые в данный момент считаются базовыми в комбинаторной оптимизации.
По теореме Birkhoff [42], выпуклая оболочка строк матрицы перестановок п хп в точности повторяет дважды стохастические матрицы, то есть неотрицательные матрицы у которых сумма по столбцам и строкам равна 1.
Это позволяет решить задачу о назначениях как задачу линейного программирования. Для этого, необходимо описание в линейных неравенствах многогранника задачи коммивояжера - выпуклой оболочки матриц цикличных перестановок. Это позволяет добавить неравенства, убирающие подциклы.
Предполагалось, что этих неравенств достаточно, чтобы отсечь нецикличные перестановки. Однако, в 1953 году было показано, они не отсекают все подциклы при n5 [111].
Впрочем, эти неравенства могут быть полезными для задачи коммивояжера, так как может быть получена нижняя граница длины оптимального маршрута. Расчет нижней границы производится с помощью симплекс метода с использованием неравенств в качестве секущих плоскостей. Таким образом, авторы смогли получить кратчайший путь через избранные города 48 штатов США, что оказалось близко к упомянутым выше задачам Whithey и Robinson. Ранние исследования многогранника задачи коммивояжера приведены Heller [108, 109, 110, 111, 112, 113], Kuhn [121], Norman [158], Robacker [175]. В последней работе также приведены расчетные исследования, показывающие вероятность того, что случайному набору исходных данных понадобятся неравенства, убирающие подциклы. В [160] было показано, что оптимальный маршрут задачи коммивояжера на евклидовой плоскости не пересекает сам себя.
Позднее были предложены следующие подходы:
- линейное программирование с эвристикой 3-exchange [153]
- метод графического решения [31], который является схемой для перебора вариантов с целью получения решения, близкого к оптимальному. Также в данной работе был приведен разбор задачи из 10 пунктов, которая была решена данным методом от руки, что показало практическую применимость метода для решения малоразмерных задач. Dantzieg, Fulkerson и Johnson [64] показали, что их метод уступает данной эвристике.
Зависимость длины оптимального маршрута от вместимости транспортного средства
Анализировалась влияние роста вместимости ТС на длину пути – целевую функцию. Для решения задачи 1 был использован пакет MATLAB 2011 с установленным расширением lpsolve 5.5.2.0. Затем с помощью линейного булева алгоритма решалась задача 2 (использован пакет MATLAB 2011 с установленным расширением cplex 12.2) при минимальной вместимости ТС – решении задачи 1, при увеличении вместимости ТС по сравнению с минимальной в 1,1; 1,2;…2,5 раз. Для числа пунктов от 4 до 12 было сформировано по 100 примеров, длины усреднялись. Часть результатов приведена на рис 3.1.
Из приведенного графика можно сделать выводы о том, что:
- повышение грузоподъемности транспортного средства более, чем в1,7-1,8 раз в сравнении с минимально допустимой не приводит в среднем к сокращению длины маршрута;
- при увеличении числа пунктов (до n=10) рост грузоподъемности ТС приводит в среднем к большему сокращению длины цикла. Для n10 дальнейшее сокращение длины цикла уже не происходит. 3.3 Сравнение эффективности эвристик для решения задачи 2
Для заданного числа пунктов п
- генерируем с помощью датчика случайных чисел величины а(1),…,а(п-1) из промежутка [-5, 5], принимаем a(0) = - a(i);
- равномерно и независимо генерируем п+\ вещественных чисел координаты пунктов ( (/), y(i)) (i=0,…,ri) на отрезке [-5,5], расстояния Су принимаются равными евклидовым расстояниям между точками.
Для гарантированной допустимости задачи (предложение 1) вместимость ТС принимается равной 2 max{я(/):/=0,…,«}.
Для каждого п генерировались 100 задач.
К каждой полученной задаче применялись описанные алгоритмы.
Сводка полученных результатов приведена в таблицах 3.3 и 3.4. Таблица 3.3Средняя длина маршрута относительно оптимального и среднее время решения задачи алгоритмами (точность 5%)
В ячейках таблицы приведены два числа: средняя длина цикла относительно минимального (принята за 1), и средняя продолжительность работы алгоритма (в секундах). Алгоритм 2.5 использовался при значениях к, равных 1, 2 и 3. В алгоритме 2.1 процесс прекращался, если после числа итераций, равного 20 п, не происходило улучшения рекордного значения.- Несмотря на то, что стратегия «оставь или забери как можно больше» не является оптимальной, ее применение при просмотре на один шаг вперед в среднем дает хороший результат и для n=17 средний маршрут на 21% длиннее оптимального. Просмотр на два и три шага вперд ухудшает результат и при n=17 средний маршрут на 30-40% длиннее оптимального;
- эвристика 2.4, основанная на методе Прима, дает результат наиболее близкий к оптимальному. Для n=17 средний маршрут на 17% длиннее оптимального. Затраты времени, при этом, несущественны и для 10 случайных примеров при n=50 метод 2.4 дал решение, потратив в среднем 951 секунду на пример. Исключением является случай, когда образуется отрезок с большим количеством пунктов (от 12 пунктов). Пример №1351 (n=17; см. таблицу А.1) иллюстрирует данный случай. Метод 2.4 и метод 2.5 (k=1) дают один и тот же маршрут (рисунок 3.2), но затраты времени по эвристике 2.4 составляют порядка 77 тыс. секунд или 1,851010 итерации. Затраты времени по методу 2.5 несущественны. Если исключить данный пример, то среднее время решения задачи при n=17 алгоритмом 2.4 составит 8,16 секунд или 1,03106 итерации. На решение данного примера линейным булевым программированием уходит порядка 5 секунд (см. рисунок 3.3).
- эвристики 2.2 и 2.3 имеют схожие результат и затраты времени. Для n=17 средний маршрут на 35%-40% длиннее оптимального. В среднем, на решение задачи уходит до 350 секунд.
- наихудший результат среди эвристик дают случайный поиск (метод 2.1). Для n=17 средний маршрут на 90-95% длиннее оптимального. 3.4 Сравнение эффективности эвристик для решения задачи 3
Так как задача является трудоемкой, вычислительный эксперимент ставился при n=4-8 рассмотрены 33 типа задач (таблица 3.5), в которых были заданы веса грузов в каждом пункте. Расстояния между пунктами определяются следующим образом: генерация координат пунктов (x(i), y(i)) (i=1,…,n) аналогично численным экспериментам задачи 2, за базу принимается точка (0,0), расстояния Ci,j принимаются равными евклидовым расстояниям между точками. Вместимость ТС принималась равной 3 единицам.
Сравнение эффективности жадных алгоритмов для решения задачи
Для заданного числа пунктов n
- генерируются с помощью датчика случайных чисел целочисленные величины a (1),…, a ( n) из заданного промежутка (см. ниже), принимаем i=1 - аналогично генерируются 2п вещественных чисел - координаты пунктов (х(і\у(і)) (/=1,…,и), за базу принимается точка (0,0), расстояния Си принимаются равными евклидовым расстояниям между точками. - Вместимость ТС, S, считается целочисленной и задается случайным образом в указанном промежутке (см. ниже). С помощью датчика случайных чисел производилась генерация трех групп задач: Для каждого n є 4; 25 в каждой группе генерировались 100 примеров. К каждой полученной задаче применялся алгоритм 2.2 при к равном 1, 2, 3 или 4. Длины полученных маршрутов сравниваются c результатом алгоритма при к=\.
На основании полученных данных можно сделать следующие выводы:
- во всех группах задач при n =6 алгоритм 2.2 при k=1 имеет лучший результат по длине маршрута и затраченному времени (число операций), чем при других значениях k;
- средняя длина маршрута, полученная при k=2 близка к аналогичному результату при k=3 и k=4, но временные затраты существенно ниже;
- разница в расстояниях найденных маршрутов, в среднем, находится в пределах 10%, а у группы задач II – в пределах 1%. С увеличением количества пунктов эта величина сохраняется;
- группа задач II (значительные веса потребителей при небольшой вместимости ТС) является самой трудоемкой с точки зрения затрат времени, что объясняется необходимостью многократного посещения каждого пункта. ЗАКЛЮЧЕНИЕ
1. Сформулированы математические модели поставленных оптимизационных монономенклатурных задач маршрутизации транспортных средств:
- задача 1: линейная частично целочисленная модель. Дополнительно были получены точные оценки решения задачи;
- задача 2: квадратичная булева, линейная целочисленная и линейная булева модели;
- задача 3: модель, в которой неизвестными являются пары, состоящие из номера вершины и величины груза. Дополнительно было доказано существование целочисленного решения задачи при целых исходных данных;
- задача 4: модель задачи 3 с дополнительными ограничениями.
2. Для задач 1, 2, 3 и 4 разработаны точные алгоритмы решения:
- для задачи 1: решение линейной частично целочисленной задачи;
- для задачи 2: метод ветвей и границ, решение квадратичной булевой задачи, линейной целочисленной задачи, линейной булевой задачи;
- для задач 3 и 4 в целочисленном случае реализован переборный алгоритм.
3. Для задач 2 и 3 разработаны эвристические алгоритмы, основанных
на различных методах построения маршрутов.
- для задачи 2: случайный перебор, разбиение маршрута на отрезки в двух вариантах, на основе остовного дерева Прима, поиск ближайшего допустимого пункта;
- для задачи 3: поиск ближайшего допустимого пункта со стратегией «оставь или забери как можно больше», построение двух циклов, на основе остовного дерева Прима (для целочисленной задачи), случайный перебор (для целочисленной задачи). 4. Предложенные алгоритмы программно реализованы.
Вычислительный эксперимент показал, что:
-в задаче 2 из точных методов наиболее эффективным является использование модели линейного булева программирования;
-в задаче 2 увеличение вместимости более, чем в 1,8-1,9 раз по сравнению с минимально допустимой (результат решения задачи 1) не сокращает длину маршрута;
-при решении задачи 2 наиболее эффективным из предложенных эвристических алгоритмов является использование алгоритма на основе построения остовного дерева Прима;
-при решении задачи 3 наиболее эффективным из предложенных эвристических алгоритмов является использование алгоритма на основе построения остовного дерева Прима.
