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

Размещено на http://www.allbest.ru/

Введение

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

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

При написании курсовой работы я использовала англоязычные статьи из научных журналов, больше всего информации было взять из “European Journal of Operational Research”.

Цель: изучить методы и виды задач транспортной маршрутизации, построить её модель и решить задачу с реальными данными.

Задачи, поставленные для достижения цели, заключаются в следующем:

-построить модель задачи транспортной маршрутизации;

- рассмотреть виды и методы решения вышеуказанной задачи;

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

Работа разделена на 2 главы: в первой рассматривается теоретическая база задачи маршрутизации. В заключительной главе приводится модель задачи “Capacitated vehicle routing problem” и решение примера, основанного на данной модели.

маршрутизация транспортный логистика математический



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

Задача транспортной маршрутизации (Vehicle Routing Problem or VRP) может быть описана как задача создания оптимальных маршрутов доставки (или сбора) товаров из одного или нескольких складов в ряд географически разбросанных городов или клиентов с учетом ограничений со стороны. Данная задача играет центральную роль в области физического распределения и логистики.

Определение:

Пусть x_ij целая переменная, которая принимает значения {0, 1}, ?{i, j} ? E\{{0, j} : j ? V} и значения {0, 1, 2}, ?{0, j} ? E, j?V. Причем x_0j = 2, когда выбранный маршрут включает только одного покупателя.

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

Minimise x_ij d_ij (1)

При условии, что:

x _ij = 1, ?i ? V , (2)

x _ij = 1, ?j ? V , (3)

x _ij ? v(S) , {S : S ? V\{1}, |S| ? 2}, (4)

x_ij ? {0, 1}, ?{i, j} ? E ; i ? j (5)

В этой формулировке условия (1), (2), (3) и (5) определяют модифицированную задачу о назначениях (т.е. назначения на главной диагонали запрещены). Ограничения (4) - это ограничения для ликвидации подмаршрутов: v(S) выступает как нижняя граница количества транспортных средств, необходимых для посещения всех вершин S в оптимальном решении. [4, 309]

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

Пусть существует граф

G = (V, А),

где V = {1, ...., N} является множеством вершин представляющих города со складами, находящимися в вершине 1, и А есть множество дуг. С каждой дугой (i, j) i ? j связана неотрицательная матрица расстояний С = (c_ij). В некоторых случаях, c_ij может быть интерпретировано как затраты на поездку или как время поездки. Когда C симметрична, часто бывает удобно заменить А на множество неориентированных ребер Е. Кроме того, предположим, есть m доступных транспортных средства на базе склада, где m_L <m <m_U. При m_L = m_U говорят, что m фиксировано. При m_L = 1 и m_U = N - 1 говорят, что m свободное. Когда m не фиксировано, часто имеет смысл связать его с фиксированными затратами на использование транспортного средства f. Ради простоты, мы будет игнорировать эти затраты и если не указано иного, предполагается, что все транспортные средства идентичны и имеют одинаковую мощность D. Задача VRP состоит из конструирования набора маршрутов наименьшей стоимости для транспортного средства таким образом, чтобы

(I) каждый город в V \ {1} был посещен только один раз и ровно одним транспортным средством;

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

(III) выполнялись некоторые побочные ограничения.

Наиболее распространенные побочные условия включают:

(I) ограничения по мощности: неотрицательный вес (или спрос) d_i прикрепляется к каждому городу i > 1 и сумма весов маршрута любого транспортного средства не может превышать мощности (грузоподъемности) этого транспортного средства. Задача транспортной маршрутизации с ограничениями по грузоподъемности в иностранной литературе называется Capacitated Vehicle Routing Problem (CVRP);

(II) количество городов на любом маршруте ограничено сверху q (это частный случай условия (I) с d_i = 1 для всех i > 1 и D = q);

(III) ограничения общего времени: длина любого маршрута не может превышать заданную величину L; эта длина состоит из времени междугородних путешествий c_ij и времени остановки д_i в каждом городе i на маршруте;

(IV) временные окна: город i должен быть посещен в интервале времени [A_i,B_i] и допускается ожидание в городе i. Задача транспортной маршрутизации с временными окнами в иностранной литературе называется Vehicle Routing Problem with Time Windows (VRPTW);

(V) приоритет отношений между парами городов: город i, возможно, нужно посетить до города j.

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

* Сеть может быть симметричной, асимметричной или смешанной. Она представляется в виде графика, на котором узлы соответствуют городам, клиентам и/или складам, а дуги обозначают реальные связи (например, дороги, трубопроводы) или символические связи. На графиках со стоимостями, значение стоимости обычно представляет собой затраты на перемещения по дуге.

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

* Набор транспортных средств создает ограничения, которые влияют на маршруты. Транспортные средства могут быть одинаковыми (однородными) или разными по своим характеристикам. Набор может состоять из одного или нескольких транспортных средств, использование которых, например, может быть ограничено по мощности, времени или расстоянию. Кроме того, может быть зависимость между транспортными средствами, водителями, продуктами, узлами и/или дугами.

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

* Цели (критерии) могут быть многочисленными и разнообразными. Целевая функция может быть вычислена в течение одного или нескольких периодов. Наиболее распространенные цели включают в себя: минимизацию общего пройденного расстояния, общего требуемого времени, общей стоимости маршрута и/или количества транспортных средств, а также максимизацию качества обслуживания и/или собираемой прибыли. [1, 293-294]

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

1. Задачи, связанные с маршрутом

а) Стоимость:

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

b) Период обработки:

Хотя минимизации затрат является наиболее общей целью, эта цель нередко игнорируются. Вместо этого минимизируется период обработки (то есть минимизируется длина самого длинного маршрута). Ярким примером этого стали исследования Корборана и соавторов про задачу маршрутизации школьного автобуса в сельской местности, где, в связи с большими расстояниями между местами посадки-высадки, автобусные маршруты, как правило, долгие и автобус никогда не бывает полным. Минимизация периода обработки обеспечивает некоторую справедливость с точки зрения времени, затрачиваемого в автобусе первым подобранным учеником по сравнению со временем, затраченным последним.

с) Баланс:

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

d) Другие специфические цели:

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

В другой задаче - про транспортировку опасных (вредных) продуктов Джанникоса - существует риск, связанный с дорогой, по которому движется транспортное средство. Из-за тяжелых последствий аварии для людей и окружающей среды вблизи места аварии риск несчастных случаев должен быть сведен к минимуму на выбранных участках. Автор минимизирует общий предполагаемый риск, который выражается как взвешенная сумма индивидуальных предполагаемых рисков. Каждое поселение имеет веса и индивидуальный предполагаемый риск, рассчитанные на основе количества отходов, проходящего через территорию поселения.

2. Цели, связанные с деятельностью вершины/дуги

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

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

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

3. Цели, связанные с ресурсами

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

Другие цели, связанные с транспортными средствами, могут быть использованы для максимизации эффективности затрат на транспортное средство с точки зрения времени или мощности; в то время как цели, связанные с товарами, могут быть введены, чтобы принять во внимание характер товара. Например, последний аспект может быть введен, когда товар скоропортящийся, и таким образом можно будет избежать его порчи. [1, 301-304]

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



Таблица 1.Виды VRP

№ п/п	Сокращение	Название	Описание
1	CVRP	Capacitated VRP	Маршрутизация с ограничением по грузоподъемности (классическая)
2	VRPTW	VRP with Time Windows	Маршрутизация с временными окнами
3	MDVRP	Multiple Depot VRP	Маршрутизация с несколькими складами
4	VRPPD	VRP with Pick-Ups and Delivering	Маршрутизация с немедленным возвратом товаров
5	VRPB	VRP with Backhauls	Маршрутизация с возвратом товаров после полной доставки
6	SDVRP	Split Delivery VRP	Маршрутизация с разбиением заказа на несколько машин
7	HVRP	Heterogeneous VRP	Маршрутизация с различным транспортом
8	FSMVRP	Fleet Size and Mix VRP	Маршрутизация c неограниченным размером и составом набора транспортных средств
9	PVRP	Periodic VRP	Периодическая маршрутизация
10	SVRP	Stochastic VRP	Маршрутизация со случайными данными
11	DVRP	Dynamic VRP	Динамическая маршрутизация
12	VRPSF	VRP with Satellite Facilities	Маршрутизация с возможностью дозагрузки
13	PDP	Pickup-and-delivery problems	Доставка из одного места в другое
14	CARP	Capacitated arc routing problems	Обслуживание клиентов в пути (на участках дорог)
15	LRP	Location-routing problems	Маршрутизация с определением локаций (склад и т.п.)
16	IRP	Inventory routing problems	Задачи распределения товара

А сейчас дадим краткую характеристику сущности и некоторых особенностей приведенных задач:

1. Маршрутизация с ограничением по грузоподъемности (Capacitated VRP, CVRP)

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

Цель: минимизировать количество транспортных средств, необходимых для выполнения задания, а также общее время выполнения задачи.

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

2. Маршрутизация с ограничением по времени (VRP with Time Windows, VRPTW)

В этой задаче для каждого клиента v_i существует известный промежуток времени, определенный как интервал [e_i,l_i] -- намеченный горизонт (scheduling horizon), в течение которого этот клиент может быть посещен, иначе транспортному средству придется ожидать.

Цель: минимизировать количество машин, общее время пути и ожидания, необходимое для выполнения запросов клиентов в назначенные интервалы времени.

Отличия по сравнению с классической VRP:

? решение неприемлемо, если клиент обслуживается после верхней временной границы;

? машина, прибывшая ранее нижней временной границы, ожидает ее наступления;

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

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

3. Маршрутизация с несколькими складами (Multiple Depot VRP, MDVRP)

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

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

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

4. Маршрутизация с немедленным возвратом товаров (VRP with Pick-Ups and Deliveries, VRPPD)

Здесь, помимо стандартных условий доставки товаров клиентам, некоторое количество товаров возвращается назад от потребителей на склад и происходит обмен товарами между потребителями и складом. Однако количество товара «склад > потребители» и «потребители > склад» не должно превышать вместимость машины ни в одной точке маршрута (т.е. товары, которые вернут потребители, должны уместиться в машине).

Для простоты вводят дополнительные ограничения:

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

2) отмена ограничения, что все клиенты должны посещаться только один раз.

Цель: минимизировать набор транспорта и общее время движения.

5. Маршрутизация с возвратом товаров после полной доставки (VRP with Backhauls, VRPB)

Отличие этой задачи от VRPPD в том, что возврат товаров происходит только после того, как завершена доставка (т.к. перестановка грузов в машине неприемлема). Количество товара, который необходимо доставить и принять, фиксировано и известно заранее. Сохраняется ограничение по поводу того, что объем товаров при доставке и при возврате не должен превышать грузоподъемности машины.

Цель: найти такой набор маршрутов, чтобы минимизировать общее пройденное расстояние.

6. Маршрутизация с разбиением заказа на несколько машин (Split Delivery VRP, SDVRP)

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

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

Далее ее можно свести к VRP разбиением каждого заказа на несколько неделимых заказов (несколько машин доставляют весь заказ частями).

Цель: минимизировать набор транспорта и общее время обслуживания всех клиентов.

7. Маршрутизация c различным типом транспорта (Heterogeneous VRP, HVRP): Набор состоит из разнородных типов транспортных средств.

8. Маршрутизация c неограниченным размером и составом набора транспортных средств (Fleet Size and Mix VRP, FSMVRP): Набор состоит из машин различного типа и вместимости.

9. Периодическая маршрутизация (Periodic VRP, PVRP)

Если в классической VRP период планирования -- один день, то в PVRP он расширяется до нескольких дней.

Цель: минимизировать набор транспорта и общее время обслуживания всех клиентов.

Ограничения:

? машина может вернуться на склад не в тот же день.

? по истечении M-дневного периода каждый клиент должен быть посещен k раз, но как минимум единожды: 1 ? k ? M. (если М = 1, то задача сводится к классической VRP)

? запросы должны быть выполнены за один визит одним автомобилем.

? ежедневный заказ клиента фиксированный.

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

10. Маршрутизация со случайными данными (Stochastic VRP, SVRP)

В такой VRP один или несколько компонентов могут иметь случайное поведение. Случайные элементы:

o клиенты: каждый клиент существует с вероятностью p и отсутствует с вероятностью p - 1.

o запросы: запрос каждого клиента - случайная величина.

o расстояния: время поездок (расстояния между потребителями) - случайные величины.

Решение SVRP происходит в два этапа:

1) решение без учета случайных переменных

2) коррекция полученного решения после того, как становятся известными случайные значения

Цель: минимизировать набор транспорта и общее время обслуживания всех клиентов.

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

11. Динамическая маршрутизация (Dynamic VRP, DVRP)

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

12. Маршрутизация с возможностью дозагрузки (VRP with Satellite Facilities, VRPSF)

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

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

Но тут добавляется ограничение: товар на складе клиента не должен заканчиваться.

Стоит заметить, что задача маршрутизации с возможностью дозагрузки является составной частью задачи распределения товара (IRP, Inventory Routing Problem).

13. Доставка из одного места в другое (Pickup-and-delivery problems, PDP)

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

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

14. Маршрутизация с ограничением по вместимости дуги (Capacitated arc routing problems CARP)

Задача в данном случае состоит не в посещении клиента для выполнения услуг, а в выполнении услуг во время путешествия (на участке дорожной сети, по ссылкам дорог).

15. Маршрутизация с определением локаций (Location-routing problems, LRP)

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

16. Задачи распределения товара (Inventory routing problems, IRP)

Каждый клиент имеет норму расхода товара, начальные запасы и емкость склада. Центральный склад должен выполнить 0 или более поставок для каждого клиента в течение периода времени (горизонта планирования) для обеспечения нормы расхода клиента. Получается, что в этой задаче нет как таковых запросов клиентов.

Цель: планировать маршруты минимальной стоимости доставки. [5, 14-19]

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

2. Пример решения задачи CVPR

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

Предположим, что общий склад корпорации Макдональдс в Беларуси находится по адресу ул. Ленинградская, 20.

Адреса ресторанов McDonalds в Минске:

1.пр.Независимости, 23

2. ул. Немига, 12/Б

3. пр. Дзержинского, 96

4. пр. Притыцкого, 28

5. ул. Сурганова, 63

6. ул. Шугаева, 2

7. Логойский тракт, 35

Эта задача относится к VRP с ограничениями по грузоподъемности. Здесь только 1 склад, 2 одинаковых автомобиля с равной грузоподъемностью в 10 ящиков и 7 точек (клиентов), куда нужно отвезти товар. Обозначим эти точки на карте Минска:

Рисунок 1 Карта Минска с ресторанами Макдональдс

В соответствии с этим рисунком можно построить граф с вершиной 0 (склад фирмы) и еще 7 вершинами (рестораны). В качестве стоимости пути будем рассматривать расстояние между точками (рассчитывалось с помощью программы “Google maps”).

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

Итак, построим граф по условиям задачи и карте, причем введем как можно больше дуг (чтобы было больше возможных вариантов) - не менее 4 для каждой вершины; однако введение каждой дуги должно было обосновано на карте соответствующим подмаршрутом. Далее занумеруем вершины графа (начиная с 0, т.е. склада) и проведенные на нем дуги (21).



Рисунок 2 Граф 1

После построения графа можно приступать непосредственно к решению самой задачи. Для нахождения ответа достаточно использовать «Поиск решения», встроенный в Microsoft Excel. Причем в этом случае модель можно не записывать - просто ввести нужные условия в окне ограничений.

Выпишем длину каждой дуги ниже ее порядкового номера и выделим бинарные переменные, соответствующие количеству раз, которое автомобиль проходит по этой дуге (1 - автомобиль проезжает, 0 - не проезжает). Рядом укажем ограничения на дуги, входящие или выходящие из каждой из 8 вершин (7 ресторанов и склад). В качестве целевой функции возьмем минимизацию общего пройденного расстояния: сумму произведений ряда длин путей на ряд бинарных переменных.

Чтобы соблюсти условие, что каждая вершина должна быть посещена только один раз и только одним транспортным средством, зададим ограничения: у каждой вершины должны быть только 2 дуги, по которым будет двигаться автомобиль (через одну въезжать, через вторую выезжать). Т.е. сумма дуг у каждой вершины клиента должна быть равна 2. Однако из условия очевидно, что одна машина не может развезти все грузы - только две. Значит, у нас должно получиться 2 маршрута. Поэтому у вершины 0 сумма дуг будет равна 4 (две машины выехали и вернулись). Вот эти ограничения и записаны слева:



Шаг 1. Применяем «Поиск решения»: минимизируем общее расстояние при заданных ограничениях:

Используя данный метод, мы получили допустимое решение = 41,4:

Отобразим данное решение на графе:



Рисунок 3. Граф 2

На графе видно, что при таком распределении точек на одну из машин приходится 5 т. продукции, а на другую - 3т, а это превосходит допустимую грузоподъемность. Также один из маршрутов начинается не на складе Макдональдс, а зациклен на нескольких ресторанах. В соответствии с условиями задачи максимальная грузоподъемность каждой машины составляет 4т., т.е. первая должна развезти не более 4т. Значит, данное решение не подходит и нужно добавить ограничение, уменьшающий длинный маршрут, состоящий из 5 клиентов. Чтобы это осуществить, нужно задать условие, что сумма дуг, входящих в вершины клиентов этого подмаршрута, равна 2. Запишем это дополнительное ограничение также слева и снова запустим «Поиск решения» (Шаг 2):

В итоге получим новое решение= 46,3:



Проверим это решение на графе:

Рисунок 4. Граф 3

Данное решение удовлетворяет заданным условиям.

Из анализа графа следует следующее: машина №1 развезёт продукцию в рестораны под номерами 2,3,4. В то время, как вторая машина объедет рестораны №1,5,7,6. Общее пройденное расстояние будет равно 46,1км.

Таким образом, я привела решение примера задачи транспортной маршрутизации с ограничениями по грузоподъёмности.



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

1. Multi-objective vehicle routing problems. - Nicolas Jozefowiez, Frederic Semet, El-Ghazali Talbi // European Journal of Operational Research 189 (2008) 293-309 European Journal of Operational Research 189 (2008) (с.293-309)

2. From Single-Objective to Multi-Objective Vehicle Routing Problems: Motivations, Case Studies, and Methods - Nicolas Jozefowiez,Frederic Semet, and El-Ghazali Talbi

3. The Vehicle Routing Problem: An overview of exact and approximate algorithms - Gilbert Laporte Centre de Recherche// European Journal of Operational Research 59 (1992) (с.345-358)

4. VEHICLE ROUTING PROBLEM: MODELS AND SOLUTIONS // Journal of Quality Measurement and Analysis 4(1) 2008, (с.205-218)

5. New Magenta Papers // Сборник научных трудов, Выпуск № 1. Труды международного семинара по интеллектуальному планированию. Под ред. А.В. Иващенко - Самара: Издательство Самарского научного центра РАН, 2012. - 68 с., ил. (с.11-19)

6. Просветов Г. И. Математические методы в логистике: ЗАДАЧИ И РЕШЕНИЯ: Учебно-практическое пособие. 2-е изд., доп. --М.: Издательство «Альфа-Пресс», 2008. -- 304 с.

Размещено на Allbest.ru