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

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

ГИНДУЛЛИН Рамиз Вилевич

ОПТИМИЗАЦИЯ МАРШРУТА ДОСТАВКИ ОДНОРОДНОГО ГРУЗА ОТ МНОЖЕСТВА ПРОИЗВОДИТЕЛЕЙ МНОЖЕСТВУ ПОТРЕБИТЕЛЕЙ

Специальность: 05.13.01 - Системный анализ, управление и обработка информации (в промышленности)

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

Уфа-2014

^МАЙщ

005549080

Работа выполнена в ФГБОУ ВПО «Уфимский государственный авиационный технический университет» на кафедре вычислительной математики и кибернетики

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

Официальные оппоненты:

д.ф.-м.н., профессор Бронштейн Ефим Михайлович

д.ф.-м.н., с.н.с.

Сервах Владимир Вицентьевич

Омский филиал ФГБУН Института математики им. С.Л. Соболева СО РАН, лаборатория дискретной оптимизации старший научный сотрудник

д.ф.-м.н., доцент

Мухаметзяпов Ирик Зирягович

ФГБОУ ВПО «Уфимский государственный нефтяной технический университет» профессор кафедры математики

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

ФГБОУ ВПО «Южно-Уральский государственный университет» (национальный исследовательский университет)

Защита диссертации состоится 17 июня 2014 г. в Ю00 часов на заседании диссертационного совета Д-212.288.06 при ФГБОУ ВПО «Уфимский государственный авиационный технический университет» по адресу: 450000, г. Уфа, ул. К. Маркса, 12.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Уфимский государственный авиационный технический университет» и на сайте http://www.ueatu.ac.ru

Автореферат разослан «16» апреля 2014 года.

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

Г. Т. Булгакова

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

Актуальность темы. Транспортная промышленность необходима для обеспечения производства сырьем и доставки готового товара потребителям. Особое внимание уделяется задачам, связанным с планированием маршрутов. По разным оценкам от 30% до 50% всех затрат на логистику связано с транспортными издержками.

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

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

Степень разработанности темы исследования. В работе рассматривается разновидность задачи маршрутизации транспортных средств при перевозке грузов - VRP (Vehicle Routing Problem) - SVRPPD - задача транспортной маршрутизации с вывозом и доставкой одним транспортным средством. Первая задача транспортной маршрутизации была сформулирована Г. Данцигом и Дж. Рамсером в 1959 году, ее постановка инициировала важный класс задач оптимизации. Наиболее часто встречающиеся постановки задач данного класса предполагают доставку однородных грузов из пункта производства или склада потребителям. Предполагается, что целью является минимизация стоимости транспортировки. Встречаются задачи и с другой целевой функцией (например, временем доставки грузов), но их, как правило, можно переформулировать таким образом, что целевая функция будет носить экономический смысл. Как правило, задачи данного класса относятся к Л^Р-трудным, точное решение которых при сколько-нибудь значительной размерности требует огромного времени. На сегодняшний день сформулировано множество вариантов данной задачи, в которых учитываются различные реальные ограничения, разработан ряд алгоритмов приближенного поиска оптимальных решений. Это связано с тем, что развитие логистических процессов и потребность в учете новых факторов ведут к постановке новых задач, требующих, в свою очередь, применения новых методов решения. Создана европейская рабочая группа VeRoLog (Vehicle Routing and Logistics), которая активно занимается задачами транспортной маршрутизации.

Необходимо указать на отличие задачи в рассматриваемой постановке от классической задачи маршрутизации транспортных средств. Особенностями рассматриваемой задачи являются наличие множественных пунктов-производителей, из которых производится вывоз груза. Поставленная задача может быть сформулирована как целочисленная линейная оптимизационная задача, и является обобщением двух известных задач: задачи коммивояжера и задачи о загрузке рюкзака. Менее 10% работ, посвященных задачам транспортной маршрутизации, рассматривают данный вариант задачи. Результаты по близким задачам получены Archetti С., Cordeau J.-F., Desrosiers J., Laporte G., Mingozzi A., Pankratz G., Renaud J., Ченцовым А.Г., Гимади Э.Х. и другими.

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

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

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

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

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

4. Реализация разработанных методов на ЭВМ, экспериментальная проверка эффективности работы предложенных алгоритмов.

Научная новизна. Получены следующие основные результаты, обладающие научной новизной:

1. Формализация поставленных задач (в том числе в виде задач целочисленного линейного программирования, булева квадратичного программирования и линейного булева программирования) оптимизационных задач маршрутизации транспортных средств, в которых производится вывоз груза от множества производителей к множеству потребителей (п. 2 паспорта специальности 05.13.01). Исследование данных моделей позволило получить оценки минимальной допустимой вместимости транспортного средства в случае, когда транспортное средство может посетить каждый пункт один раз.

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

паспорта специальности 05.13.01).

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

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

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

Практическую ценность работы составляет определение наименьшей допустимой вместимости транспортного средства и плана перевозок с минимальными затратами па транспортировку при заданной вместимости транспортного средства. Это делает возможным применение разработанных методов построения кратчайшего маршрута и, как следствие, применение их программной реализации для решения реальных транспортно-логистических задач на производстве. Программное обеспечение, разработанное в рамках диссертационной работы, зарегистрировано Федеральной службой по интеллектуальной собствешюсти, патентам и товарным знакам, свидетельство №2011615572 «Решение задач транспортной маршрутизации различными методами».

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

На защиту выносятся следующие результаты:

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

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

3. Сравнительный анализ эффективности предложенных алгоритмов.

Степень достоверности и апробация результатов:

-теоретические положения работы подтверждаются математическими доказательствами;

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

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

1. Всероссийской зимней школе-семинаре аспирантов и молодых ученых «Актуальные проблемы науки и техники», Уфа, 2010.

2. Всероссийской конференции «Математическое программирование и приложения», Екатеринбург, ИММ УрО РАН, 2011.

3. Международной научной конференции «Математическое моделирование, оптимизация и информационные технологии», Кишинеу, 2012.

4. Международной конференции «Дискретная оптимизация и исследование операций», Новосибирск, 2013.

5. Второй ежегодной конференции Европейской рабочей группы Саутгемптон, 2013.

6. Научных семинарах в Уфимском государственном авиационном техническом университете, в Башкирском государственном университете и Институте математики Уфимского научного центра РАН.

Работа выполнена при поддержке РФФИ (проекты № 10-06-00001 и № 13-01-00005).

Публикации. 4 публикации в рецензируемых изданиях из списка ВАК, 5 публикации в других изданиях, 1 свидетельство о регистрации программы.

Структура и объем диссертации. Диссертационная работа состоит из введения, 3 глав, разбитых на параграфы, основных результатов работы, библиографического списка литературы, включающего 206 источников, приложения, содержит 8 таблиц, 11 рисунков. Общий объем -148 страниц.

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

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

Глава 1. Обзор задач транспортной маршрутизации. В главе 1 произведен литературный обзор задач транспортной маршрутизации. В

разделе 1.1 приведены общие сведения о задаче транспортной маршрутизации. Дана общая постановка задачи, показана вычислительная сложность задач транспортной маршрутизации, указаны возможные варианты задач. Отмечено, что задачи с вывозом и доставками в литературе, посвященной задачам маршрутизации, исследуются относительно редко. В разделе 1.2 приведена сводная таблица методов решения задач транспортной маршрутизации. В разделе 1.3 рассмотрена задача коммивояжера, исторически предшествовавшая УЯР. Приведены вычислительная сложность задачи, оценки минимального расстояния, методы решения, а также линейная формализация задачи.

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

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

Транспортное средство (ТС), с вместимостью Я. ТС начинает своё движение из депо.

0,1 ... п - нумерация пунктов, при этом депо присваивается номер 0.

а, - объем груза в пункте производства (в этом случае ар*0) или потребность в пункте потребления (тогда а,<0). Депо может совпадать с пунктом

п

производства, в противном случае а0=0. Задача сбалансирована: =0.

^пй, - минимальная вместимость ТС, при которой перевозки возможны.

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

Задача 1 сводится к задаче линейного булева программирования.

Вводится матрица булевых переменных X: А'}=1 (/,/=0,1 ... п), если ТС на шаге г посещает пункт/ и 0 в противном случае. Вводится в качестве переменной 5 - вместимость ТС. Должны выполняться следующие условия:

Х(,-б{0,1},Хоо=1

(1) (2)

7=0

¡=0 7=0 5 -> тт.

(3)

(4)

(5)

Задача 1 принадлежит к классу ЛУ-трудных.

Предложение 1. Справедлива следующая оценка тах\а1\<£т!п<2-тах^Д. Верхняя оценка является точной и не улучшаемой, то есть для любого ё>0 существуют число п и последовательность ао,...,ак, для которых будет справедливо неравенство 5>(2-е)-тах|а,| (доказательство на с. 36-37 диссертации).

В разделе 2.2 рассматривается следующая задача:

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

К условиям задачи 1 добавляется матрица стоимостей С/:

Сг\Ы\ — стоимость транспортировки груза из пункта г в пункт j.

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

Квадратичная булева формализация. Матрица расстояний при перестановке пунктов в соответствии с матрицей X из задачи 1 имеет вид Сх=ХС^. Тогда, формализация задачи 2 имеет вид: найти булеву матрицу X, для которой выполняются условия (1)-(4) и при этом минимизируется общая стоимость перевозок:

+ (6)

(1) - (4), (6) это задача квадратичной булевой оптимизации.

Линейная целочисленная формализация. Вводятся булевы переменные У у (у=0,1 ... и), равные 1 тогда и только тогда, когда следующим после 1-го пункта на пути следования ТС являетсяу-й пункт. Выполняются следующие условия:

¿У, =1(/= 0,1 ...и) (7)

>0

¿^=10" = 0,1...«) (8)

Уоо=о (9)

Введем целочисленные переменные V,- (¡'=0 ... и), которые обозначают номера пунктов в порядке прохождения. На V, накладываются следующие ограничения:

1<у,<я (10)

(у,-уу)+и^ < и-1 (у=1 ... и) (11)

Справедливо следующее:

Предложение 2. Для всякого цикла, удовлетворяющего условию задачи 2, существует решение системы (7) — (11). Обратно, всякое решение системы (7) — (11) определяет цикл, содержащий все пункты.

Введем булевы переменные равные 1 тогда и только тогда, когда у1<к (¿■,¿=1 ... и). Справедливы ограничения:

2п-2^\+к-у, (х,к=\ ... п) (12)

(если правая часть положительная, то 2^=1).

+ (13)

«-1

Из условий (12) и (13) следует, что 2^=0 при у^к

Условие непереполнения и неотрицательности веса груза в ТС при посещении каждого пункта:

0* «о = (15)

Целевая функция (стоимость перевозок) имеет вид:

и п

ЕЕ^а-»1™1 (16)

»-о

Таким образом, переменные поставленной задачи (7)-(16): Уу - булевы, их (и+1)2; - булевы, их я2, V, - целочисленные, их п. Общее число ограничений имеет порядок О (и2).

Линейная булева формализация. В качестве неизвестных примем булевы переменные X*, равные 1 тогда и только тогда, когда на к-и шаге ТС переезжает из /-го пункта ву-й. Ограничения:

п • 1 п

ЕЕ (17)

к=1 1=0 П4-1 П

ХЕ4=!(!' = !•••") 08)

ЕЕ^= 1(^ = 1 •■■» + !) (19)

1=0 у=о

¿С=1 (20)

м

5Х = 1 (21)

м

Е^ = и = 0... и; * = 1... п) (22)

/=0 р= о

Предложение 3. Любое решение системы (17) —(22) порождает цикл, содержащий все вершины по одному разу (гамильтонов цикл), в котором последовательные дуги проходятся на последовательных шагах.

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

(17) — (24) - задача линейного целочисленного программирования. Число неизвестных равно («+1)3, число ограничений имеет порядок О (и2).

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

2.1 Случайно генерируемые перестановки. Перестановки генерируются случайно так, что вероятность появления каждой перестановки равна 1 / п\. Процесс прекращается в соответствий с принятыми правилами останова.

2.2 Расположим вначале положительные элементы из последовательности а(0) ... а(п) по убыванию, затем отрицательные по убыванию модулей. Если при некотором г", для которого а(Г)>0, сумма начального отрезка больше 5, причем для предыдущих индексов это не так, то находим первое из отрицательных чисел (пусть его номер /), для которых сумма начального отрезка меньше Я. Отрезок от ¡-1 до ] элементов переворачивается зеркально. Если накопленные суммы полученной последовательности принимают отрицательные значения, то действуем аналогично. Процесс продолжаем до получения допустимого решения. Выделяем зоны положительных и отрицательных значений в последовательности. Меняя пункты стыковки положительных и отрицательных отрезков, методом ветвей и границ на каждом из отрезков минимизируем длину пути.

2.3 Из положительных значений последовательности {а(Г)} выделяется подмножество с максимальной суммой, не превосходящей 5 (решается задача о наполнении рюкзака). Из отрицательных значений выделяется подмножество с минимальной суммой, при которой общая сумма обоих выделенных подмножеств неотрицательная. Процесс продолжается до исчерпания последовательности {а(/)}. Получаем зоны положительных и отрицательных значений в последовательности. Так же, как и в алгоритме 2.2, меняя пункты, в которых стыкуются положительные и отрицательные отрезки, методом ветвей и границ на каждом из отрезков минимизируем длину пути.

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

(23)

у,0 1-0

Целевой функцией является общая стоимость перевозок:

л+1 п п

(24)

>о ¡=о

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

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

В разделе 2.3 рассматривается задача 3.

a¡ (/=0,1 ... п) — вес груза в пунктах (аналогично задачам 1-2);

транспортное средство с вместимостью 5>0;

Сг\\су\\ - матрица стоимостей транспортировки груза из пунктав пункт j.

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

Необходимо найти план перевозок - последовательность пар (м(0), v(0)), (ы(1), у(1))... («(АО, у(1\Г)) (число N априори неизвестно), первый элемент каждой из которых это номер пункта, т.е. и(1')е{0,1 ... п}, второй — вес вывозимого или доставляемого груза при соответствующем Посещении пункта. Должны

(25)

(26)

(27)

(28)

(29)

Предложение 4. Задача (25) — (29) имеет решение.

Предложение 5. Пусть величины Б, aj 0=0,1 ... п) целые и (и(0), у(0)), (и(1), м(1)) ... (и(М), у(И)) — допустимый план перевозок. Тогда существует допустимый план перевозок (и(0), у'(0)), (и(1), у'(1)) ... (и(Ы), V'(Щ, в котором грузы целые (доказательство на стр. 49 диссертации).

Замечание. У целочисленной задачи могут существовать и нецелочисленные решения.

Рассмотрены следующие методы решения целочисленной задачи 3:

выполняться следующие ограничения: 2/(0)= н(ЛО=0

0<£у(0<5,(£ = 0...Аг)

/=0

I у(0 = а,и = 0...и)

0йlsNMI)=J

если н(0=_/, г=0 ... Л^-О ... п, то у(г")-а/>0 Целевая функция - длина маршрута:

N-1

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

Рассмотренные эвристические подходы:

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

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

Алгоритм 2.1 является частным случаем данной эвристики.

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

2.4 Метод основан на алгоритме Прима построения минимального остовного дерева. Разбиваем имеющиеся пункты на подпункты с весами груза (+1) или (—1) в зависимости от того, какой пункт разбиваем - производства или

потребления. Так, получаем З0^ подпунктов. Выбирается допустимый

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

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

2.5 Производится разбиение пунктов на подпункты, аналогично алгоритму 2.4. Пусть р(1)...р(£) - положительные члены последовательности (все равны +1), д(1)... д(к) — отрицательные (все равны -1). Берём максимальный допустимый начальный отрезок пунктов из первой последовательности (его длина шт{5'Д}), затем начальный отрезок пунктов из второй последовательности той же длины. Пока пункты не исчерпаны, выбираем следующие отрезки последовательностей по тому же принципу. Перестановки¿т(1) ...р(к) и д(1) ... ц{к) генерируются случайно так, чтобы вероятность появления каждой равна Мк\. Процесс прекращается в соответствии с принятыми правилами останова.

В разделе 2.4 рассмотрена задача 4.

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

Формализация задачи 4 имеет следующий вид. Аналогично задаче 3, необходимо найти последовательность пар (и(0), у(0)), (и(1), у(1)) ... (и(Щ, у{Щ), ограничения (25) —(28) должны выполняться. Добавляются значения объёмов складов Ь(к) и связанные с ними ограничения:

я(*) + £М0:ы(0 = *}-Ь(*) при£=0 ...и;/=0 ...7/ (30)

1-0

Если у(р)<0, то а(м(/7)) + ^{у(г):к(/) = и(р)}>0 при^т=0 ...ЛГ (31)

1-0

Целевая функция (29) сохраняется.

Глава 3. Численные эксперименты, исследование результатов. Раздел 3.1 посвящен сравнению эффективности четырёх точных алгоритмов решения задачи 2. Методы реализованы с помощью пакета МА'ГЪЛВ 2011 с расширением ср1ех 12.2. Для размерностей «=4... 20 генерировались случайно по 100 примеров. Как показало исследование, наиболее эффективно показало себя линейное булево программирование (см. таблицу 1).

Минимальное число пунктов, при котором хотя бы одна случайная задача 2 не была решена в течение одного часа: л=14 для метода ветвей и границ; п=9 для линейного целочисленного программирования; «=20 для линейного булева программирования; п=11 для квадратичного булева программирования.

Максимальное число пунктов, при котором хотя бы одна случайная задача 2 была решена в течение одного часа: и=15 для метода ветвей и границ; и=14 для

линейного целочисленного программирования; «=28 для линейного булева программирования; и=10 для квадратичного булева программирования.

Таблица 1. Среднее число итерации при решении случайного примера (точность 5%)

и Линейная целочисленная Квадратичная булева Ветви и границы Линейная булева

4 137 15,8 14,3 1,24

5 1,4-10' 107 47,7 20,6

6 1,47-10* 841 199 54,2

7 2,66-105 7,46-10' 911 185

8 9,31-10" 6,67-104 4,18-10' 736

9 6,54-105 1,92-104 1,98-103

10 6,98-105 1,01-Ю3 5,79-10'

11 4,63-103 1,19-104

12 2,21-10ь 3,08-104

13 1,22-10' 4,73-104

14 1,11-Ю3

15 1,39-Ю5

16 2,67-105

17 9,72-10"

18 1,03-106

В разделе 3.2 эмпирически исследована зависимость длины оптимального маршрута от вместимости ТС для п~4... 12. С помощью булева квадратичного алгоритма решалась задача 2 при минимальной вместимости ТС — решении задачи 1, и при увеличении вместимости ТС по сравнению с минимальной в 1,1; 1,2... 2,5 раз (использован пакет MATLAB 2011 с установленным расширением cplex 12.2). Сделаны следующие выводы:

- повышение грузоподъемности ТС более, чем в 1,7-1,8 раз в сравнении с минимально допустимой не приводит в среднем к сокращению длины маршрута;

- при увеличении числа пунктов до и=10 происходит сокращение длины цикла при росте грузоподъемности ТС. Для «>10 дальнейшее сокращение длины цикла уже не происходит.

В разделе 3.3 приведены результаты сравнительного исследования эвристических методов решения задачи 2. Все методы были реализованы в среде VBA в MS Excel. Для каждого числа пунктов от 4 до 17 генерировалось по 100 примеров, каждый из примеров решался каждым из методов. Сделаны следующие выводы:

-эвристика 2.4, основанная на методе Прима, дает результат наиболее близкий к оптимальному. Для «=17 в среднем маршрут на 20% длиннее оптимального. Затраты времени, при этом, несущественны;

- применение стратегии выбора ближайшего подходящего пункта при просмотре на 1 шаг вперед в среднем дает хороший результат, для л=17 средний маршрут на 25% длиннее оптимального. Просмотр на 2 и 3 шага вперёд ухудшает результат (при п=П средний маршрут на 30% - 40% длиннее оптимального);

-эвристики 2.2 и 2.3 имеют схожие результат и затраты времени. Для «=17 средний маршрут на 50% - 55% длиннее оптимального. В среднем, на решение задачи уходит до 1400 секунд;

-наихудший результат среди эвристик даёт случайный поиск (метод2.1). Для п-17 средний маршрут на 90% — 95% длиннее оптимального.

В разделе 3.4 приведены результаты сравнительного исследования методов решения задачи 3. Все методы были реализованы в среде VBA в MS Excel. Сделаны следующие выводы:

- несмотря на то, что стратегия «оставь или забери как можно больше» не является оптимальной, ее применение при просмотре на два и три шага вперед в среднем дает хороший результат. Просмотр на три шага вперед требует больших затрат времени при близком (часто большем) значении целевой функции;

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

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

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

В разделе 3.5 были отдельно исследована эффективность использования жадных алгоритмов (алгоритм 2.2, реализован в среде VBA в MS Excel) для задачи 3 между собой. Сделан вывод о том, что использование алгоритма 2.2 с просмотром на два и более шага нецелесообразно и приводит к ухудшению результата на 10% по сравнению с просмотром на один шаг вперед.

ЗАКЛЮЧЕНИЕ

1. Сформулированы математические модели поставленных оптимизационных задач монономенклатурной маршрутизации транспортных средств:

-задача 1: линейная частично целочисленная модель. Дополнительно были получены точные оценки решения задачи;

-задача 2: квадратичная булева, линейная целочисленная и линейная булева модели;

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

-задача 4: модель задачи 3 с дополнительными ограничениями.

2. Для задач 1, 2, 3 и 4 разработаны точные алгоритмы решения: -для задачи 1: решение линейной частично целочисленной задачи;

-для задачи 2: метод ветвей и границ, решение квадратичной булевой задачи, линейной целочисленной задачи, линейной булевой задачи;

-для задач 3 и 4 в целочисленном случае реализован переборный алгоритм.

3. Для задач 2 и 3 разработаны эвристические алгоритмы, основанные на различных методах построения маршрутов:

-для задачи 2: случайный перебор, разбиение пути на отрезки (2 варианта), на основе остовного дерева Прима, поиск ближайшего допустимого пункта;

-для задачи 3: поиск ближайшего допустимого пункта со стратегией «оставь или забери как можно больше», построение двух циклов, на основе остовного дерева Прима (для целочисленной задачи), случайный перебор (для целочисленной задачи).

4. Предложенные алгоритмы программно реализованы. Вычислительный эксперимент показал, что:

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

-для задачи 2 увеличение вместимости более чем в 1,8-1,9 раз по сравнению с минимально допустимой (решение задачи 1) не сокращает длину маршрута;

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

В рецензируемых журналах из списка ВАК:

1. Бронштейн, Е.М. Об одном классе задач маршрутизации / Бронштейн Е.М., Гиндуллин Р.В. // Математическое моделирование. - 2010. - Т. 23, №6.-С. 123-132.

2. Бронштейн, Е.М. Об одном классе задач маршрутизации / Бронштейн Е.М., Гиндуллин Р.В. // Научно-технические ведомости СПбГПУ. Информатика, телекоммуникации, управление. - 2013. - №1(164). — С. 63-67.

3. Бронштейн, Е.М. Об одной целочисленной задаче маршрутизации / Бронштейн Е.М., Гиндуллин Р.В. // Логистика и управление цепями поставок. -2013.-№6.-С. 85-90.

4. Бронштейн, Е.М. Точные решения некоторых оптимизационных задач транспортной логистики / Бронштейн Е.М., Гиндуллин Р.В. // Математическое моделирование.-2013. - Том 25, №11. - С. 121-127.

В других изданиях:

5. Гиндуллин, Р.В. Об одной задаче транспортной логистики / Гиндуллин Р.В. // 5-ая Всероссийская зимняя школа-семинар аспирантов и молодых ученых «Актуальные проблемы науки и техники». Уфа. 2010. С. 81-84.

6. Бронштейн, Е.М. Об одном классе задач маршрутизации / Бронштейн Е.М., Гиндуллин Р.В. // Информационный бюллетень «XIV Всероссийская конференция «Математическое программирование и приложения» (тезисы докладов)». Екатеринбург. ИММ УрО РАН. 2011. С. 156-157.

7. Бронштейн, Е.М. Оптимизационные задачи транспортной логистики / Бронштейн Е.М., Гиндуллин Р.В. // Материалы международной научной конференции «Математическое моделирование, оптимизация и информационные технологии». Кишинеу. Академия транспорта и коммуникации. 2012. С. 214-219.

8. Бронштейн, Е.М. Об одном классе оптимизационных задач маршрутизации / Бронштейн Е.М., Гиндуллин Р.В. // Материалы международной конференции «Дискретная оптимизация и исследование операций». Новосибирск. 2013. С. 127.

9. Bronstein, Е. On one class of routing optimization problem / Bronstein. E., Gindullin R. // Second Annual Conference of the EURO Working Group of Vehicle Routing and Logistics Optimization (7-10 July 2013, Southhampton, UK). Southhampton. P. 19.

Патенты и свидетельства об официальной регистрации программ для

ЭВМ

10. Свидетельство о государственной регистрации программы для ЭВМ №2011615572 «Решение задач транспортной маршрутизации различными методами» в Реестре программ для ЭВМ от 15 июля 2011 г.

ГИНДУЛЛИН Рамиз Вилевич

ОПТИМИЗАЦИЯ МАРШРУТА ДОСТАВКИ ОДНОРОДНОГО ГРУЗА ОТ МНОЖЕСТВА ПРОИЗВОДИТЕЛЕЙ МНОЖЕСТВУ ПОТРЕБИТЕЛЕЙ

Специальность: 05.13.01 - Системный анализ, управление и обработка информации (в промышленности)

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

Подписано к печати 07.04.2014 г. Формат 60x84 1/16. Бумага офсетная. Печать плоская. Гарнитура Times New Roman. Усл. печ. л. 1,0. Усл. кр.-отг. 1,0. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ №242

ФГБОУ ВПО «Уфимский государственный авиационный технический университет» Центр оперативной полиграфии 450000, Уфа-центр, ул. К.Маркса, 12

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

04201459051

ГИНДУЛЛИН Рамиз Вилевич

ОПТИМИЗАЦИЯ МАРШРУТА ДОСТАВКИ ОДНОРОДНОГО ГРУЗА ОТ МНОЖЕСТВА ПРОИЗВОДИТЕЛЕЙ МНОЖЕСТВУ ПОТРЕБИТЕЛЕЙ

Специальность 05.13.01 - Системный анализ, управление и обработка информации (в промышленности)

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

Научный руководитель -д.ф-м.н., профессор Бронштейн Е.М.

Уфа 2013

ОГЛАВЛЕНИЕ

С.

Введение................................................................................... 3

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

ПРИЛОЖЕНИЕ А........................................................................ 93

ВВЕДЕНИЕ

Актуальность темы работы. Транспортная промышленность необходима для обеспечения производства сырьем и доставки готового товара потребителям. Особое внимание уделяется задачам, связанным с планированием маршрутов. По разным оценкам от 30% до 50 % всех затрат на логистику связано с транспортными издержками.

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

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

Степень разработанности темы исследования. В работе

рассматривается разновидность задачи маршрутизации транспортных

средств при перевозке грузов - VRP (Vehicle Routing Problem) - SVRPPD -

задача транспортной маршрутизации с вывозом и доставкой одним

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

сформулирована Г. Данцигом и Дж. Рамсером в 1959 году, ее постановка

инициировала важный класс задач оптимизации. Наиболее часто

встречающиеся постановки задач данного класса предполагают доставку

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

Предполагается, что целью является минимизация стоимости

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

3

(например, временем доставки грузов), но их, как правило, можно переформулировать таким образом, что целевая функция будет носить экономический смысл Как правило, задачи данного класса относятся к NP-трудным, точное решение которых при сколько-нибудь значительной размерности требует огромного количества времени. На сегодняшний день сформулировано множество вариантов данной задачи, в которых учитываются различные реальные ограничения, разработан ряд алгоритмов приближенного поиска оптимальных решений. Это связано с тем, что развитие логистических процессов и потребность в учете новых факторов ведут к постановке новых задач, требующих, в свою очередь, применения новых методов решения. Создана европейская рабочая группа VeRoLog (Vehicle Routing and Logistics), которая активно занимается задачами транспортной маршрутизации.

Необходимо указать на отличие задачи в рассматриваемой постановке от классической задачи маршрутизации транспортных средств. Особенностями рассматриваемой задачи являются наличие множественных пунктов-производителей, из которых производится вывоз груза. Поставленная задача может быть сформулирована, как целочисленная линейная оптимизационная задача, и является обобщением двух известных задач: задачи коммивояжера и задачи о загрузке рюкзака. Менее 10% работ, посвященных задачам транспортной маршрутизации, рассматривают данный вариант задачи. Результаты по близким задачам получены Cordeau J.-F. [51], Laporte G. [61, 173], Renaud J. [173], Desrosiers J. [67], Mingozzi A. [41], Pankratz G. [163], Ченцовым А.Г. [16], Гимади Э.Х. [11] и другими учёными. Также, создана европейская рабочая группа VeRoLog (Vehicle Routing and Logistics), которая активно занимается задачами транспортной маршрутизации.

Область исследования. Задачи организации транспортировки грузов.

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

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

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

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

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

4. Реализация разработанных методов на ЭВМ, экспериментальная проверка эффективности работы предложенных алгоритмов.

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

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

На защиту выносятся следующие результаты исследований:

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

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

3. Сравнение эффективности предложенных алгоритмов.

Научная новизна. Получены следующие основные результаты, обладающие научной новизной:

1. Формализация поставленных задач (в том числе в виде задач целочисленного линейного программирования, булева квадратичного программирования и линейного булева программирования) оптимизационных задач маршрутизации транспортных средств, в которых производится вывоз груза от множества производителей к множеству потребителей (п. 2 паспорта специальности 05.13.01). Исследование данных моделей позволило получить оценки минимальной допустимой вместимости транспортного средства в случае, когда транспортное средство может посетить каждый пункт один раз.

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

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

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

Практическая и теоретическая значимость. Теоретическая

значимость заключается в формализации и решении монономенклатурной

оптимизационной задачи маршрутизации транспортных средств с одним

транспортным средством с несколькими пунктами производства и

6

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

Практическую ценность работы составляет определение наименьшей допустимой вместимости транспортного средства и плана перевозок с минимальными затратами на транспортировку при заданной вместимости транспортного средства. Это делает возможным применение разработанных методов построения кратчайшего маршрута задачи и, как следствие, применение их программной реализации для решения реальных транспортно-логистических задач на производстве. Программное обеспечение, разработанное в рамках диссертационной работы, зарегистрировано Федеральной службой по интеллектуальной собственности, патентам и товарным знакам, свидетельство № 2011615572 «Решение задач транспортной маршрутизации различными методами».

Степень достоверности и апробация результатов.

-Теоретические положения работы подтверждаются математическими доказательствами.

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

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

1. Всероссийская зимняя школа Всероссийская зимняя школа-семинар аспирантов и молодых ученых семинар аспирантов и молодых ученых семинар аспирантов и молодых ученых «Актуальные проблемы науки и техники», Уфа, 2010.

2. Всероссийская конференция «Математическое программирование и приложения», Екатеринбург, ИММ УрО РАН, 2011.

3. Международная научная конференции "Математическое моделирование, оптимизация и информационные технологии", Кишинеу, 2012.

4. Международная конференция «Дискретная оптимизация и исследование операций», Новосибирск, 2013.

5. Вторая ежегодная конференция Европейской рабочей группы УеЯоЬо§, Саутгемптон, 2013.

6. Научные семинары в Уфимском государственном авиационном техническом университете, в Башкирском государственном университете и Институте математики Уфимского научного центра РАН.

Работа выполнена при поддержке РФФИ (проекты № 10-06-00001 и № 13-01-00005).

1. ОБЗОР ЗАДАЧ ТРАНСПОРТНОЙ МАРШРУТИЗАЦИИ

1.1 Задачи транспортной маршрутизации

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

История задач маршрутизации насчитывает более полувека. Первая работа, посвященная данному типу задач, появилась в 1959 году, когда была опубликована статья Г. Данцига и Дж. Рамсера [65], в которой была сформулирована группа задач, впоследствии названная VRP - Vehicle Routing Problem. В данной работе рассматривалась задача нахождения оптимального маршрута доставки парком бензовозов продукта от конечной станции магистрального трубопровода до большого количества обслуживающих терминалов (задача диспетчеризации грузовиков). Используя методы, опирающиеся на формулировки линейного программирования, предложенные ручные вычисления давали решение, близкое к оптимальному, для задач с количеством маршрутов 4 и количеством станции 12. Типичная постановка задачи приведена на рисунке 1.1.

Рисунок 1.1 Типичная постановка задачи транспортной маршрутизации и ее

решение.

Задачи транспортной маршрутизации являются обобщением задачи коммивояжера, поэтому, как правило, относятся к классу ИР-сложных задач (однако, некоторые частные варианты задачи могут решаться за полиномиальное время, например, [21]).

На текущий момент, имеется множество вариантов задач маршрутизации [38, 164, 165, 8]. В целом, задачи маршрутизации можно разделить по следующим характеристикам [8]:

1. Пункты производства

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

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

таксопарка) В этом случае пункт посадки каждого пассажира можно считать пунктом производства.

2. Пункты потребления.

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

б) пунктов несколько Эта ситуация наиболее распространенная. Содержательная интерпретация аналогична 16.

3) Сеть дорог.

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

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

-Все учитываемые характеристики аддитивно пути.

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

4) Количество груза.

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

-Одним. -Несколькими.

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

задача).

-Одним. -Несколькими.

5) Базы ТС (депо).

а) База одна.

б) Баз несколько.

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

6) Вид груза.

(стоимость габариты,

зависят от

(например,

а) Задачи с однородным грузом.

б) Многопродуктовые задачи.

7) Характер ТС.

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

б) Все ТС одинаковые.

в) ТС различны.

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

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

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

9) Ограничения по видам перевозимых грузов.

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

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

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

10) Условия перевозки.

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

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

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

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

д) Возможность совпадения пунктов производства и потребления.

-Некоторые пункты могут быть одновременно пунктами производства и потребления. -Все пункты разные.

11) Ограничения по времени.

а) Грузы из пунктов производства должны забираться в указанные временные окна.

б) Грузы в пункты потребления должны доставляться в указанные временные окна.

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

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

д) Имеются те или иные ограничения на последовательность

перевозок.

12) Особые условия перевозки.

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

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

13) Факторы, определяющие стоимость перевозки.

а) Зависимость стоимости перевозки только от самого пути.

б) Зависимость стоимости перевозки от загрузки ТС.

-Пропорциональность зависимости стоимости от загрузки.

14) Условие возврата.

а) ТС должны возвращаться на исходную базу.

б) ТС должны завершать маршрут на какой-нибудь базе.

в) ТС могут завершать маршрут в любом месте.

15) Учет упаковки в транспортное средство (для дискретного случая постановки задачи). При этом условии в задачу вводятся ограничения

на размещение ящиков внутри транспортного средства, а также ограничение на последовательность по�