2.2. Классическая постановка ЗМТ
Постановка: ЗМТ заключается в построении замкнутых маршрутов для нескольких ТС, проходящих через заданное множество целевых вершин, причем все маршруты должны начинаться и заканчиваться в одной точке называемой депо. Через каждую вершину должен проходить только один маршрут. Цель задачи – минимизировать общую стоимость объезда маршрутов.
Математическая постановка классической ЗМТ:
G (V,E) – граф с набором вершин (V) и ребер (E).
V = {v0, v1, . . . , vn} – множество всех вершин, где v0 – депо (вершина, в которой начинаются и заканчиваются маршруты).
V' = V \{v0} – множество из n целевых вершин.
C – матрица стоимостей передвижения между вершинами, где cij - стоимость переезда между вершинами vi и vj.
m – количество ТС.
Ri = {vi, vj, vk,….} – маршрут i-ого ТС.
С(Ri) – стоимость маршрута Ri.
Задача маршрутизации состоит в определении такого множества маршрутов m с минимальной общей стоимостью, чтобы каждая вершина множества V была посещена только одним ТС и только один раз. Все маршруты должны начинаться и заканчиваться в депо. Целевая функция:  .
3.3. Локальные особенности ЗМТ
Анализ компаний, занимающихся транспортной логистикой и экспедированием, показывает, что большинство предприятий можно разделить на три группы, причем основным критерием группировки является масштаб обслуживания клиентов:
крупные международные компании, занимающиеся мультимодальными перевозками с использованием различного вида транспорта – железнодорожный, авиационный, морской, автомобильный и другие;
региональные компании, занимающиеся перевозками грузов преимущественно внутри одного макрорегиона/страны;
городские компании, осуществляющие доставку/забор грузов в пределах одного города или небольшой области. К таким компаниям можно отнести интернет-магазины, сетевые продуктовые и непродовольственные магазины и другие организации.
В данной работе акцент сделан на компаниях регионального и городского типа, так как мультимодальные перевозки, как правило, планируются экспертами с учетом многих параметров, основанных на принципиально других ограничениях.
Рассмотрим подробнее этапы перевозки компаний регионального типа:
первым этапом цепочки доставки является забор груза от клиентов и доставка в распределительные центры, в которых товар разбивается по регионам доставки, после чего формируется парк ТС, из имеющихся в наличии на данный момент;
далее, как правило, происходит доставка грузов в крупные промежуточные пункты (склады) погрузки/разгрузки для совмещения различных маршрутов в рамках одного ТС, тем самым сокращается расстояние доставки, за счет чего происходит уменьшение затрат на решение ЗМТ;
третьим этапом является доставка грузов из промежуточных пунктов в города клиентов, после чего начинают работу компании городского типа.
Можно заметить, что на каждом этапе задача маршрутизации транспорта решается отдельно.
Рассмотрим этапы перевозки компаний городского типа:
первым этапом осуществляется забор груза с одного или нескольких складов (заводов),
вторым этапом является доставка грузов конечным потребителям (магазинам).
Проанализировав потребности и физические ограничения компаний регионального и городского типа можно прийти к следующему выводу – методы работы большинства компаний, занимающихся транспортной логистикой очень схожи, поэтому можно создать универсальный алгоритм решения ЗМТ для разного типа компаний. Различия между компаниями заключатся в значениях определенных параметров, влияющих на скорость и качество расчета путей следования, а также в некоторых физических особенностях и ограничениях по доставке.
С учетом вышесказанного, приведем наиболее востребованные и актуальные локальные особенности задачи.
4.3.1 Учет характеристик ТС и перевозимого товара
В классической постановке задачи используется только однородный транспорт, таким образом, для реализации классической задачи на практике необходимо иметь автопарк одинакового транспорта.
Каждое транспортное средство характеризуется набором параметров: габариты кузова и/или общий объем, грузоподъемность, разрешенный перечень типов перевозимых грузов. Введение данной особенности обусловлено физическими различиями ТС и является неотъемлемой частью решения задачи. Загрузка ТС товаром, который физически не может быть размещен по причине своей массы, размера или несовместимостью с другими товарами не имеет смысла, потому как решение ЗМТ окажется физически не осуществимым.
Необходимо заметить тот факт, что ТС характеризуется также и стоимостью эксплуатации, значительную часть которой составляет расход топлива. В связи с этим, в характеристику ТС добавлен параметр стоимости передвижения на 1 км.
Для транспортируемого товара важны две характеристики – масса и объем. Именно эти параметры вводятся в постановку ЗМТ как дополнительные характеристики.
5.3.2 Множество депо и незамкнутый маршрут
Логистические компании, как правило, используют собственный и наемный транспорт, который может быть рассредоточен по всей территории, соответственно, может размещаться в разных автопарках. Часто возникает ситуация, при которой владельцем транспорта является физическое лицо на личном автомобиле, что предполагает абсолютно свободную дислокацию ТС. В связи с этими факторами актуальной особенностью постановки задачи является наличие множества депо, при котором начальным пунктом транспортировки товара может являться несколько мест, чаще всего складов.
Кроме того, возврат транспорта обратно в депо пустым становится совершенно невыгодным действием во многих отношениях. Учет этого факта является очень важным для работы, потому как значительно снижает издержки транспортных компаний на транспортировку груза. Поэтому весьма востребованной особенностью ЗМТ является возможность построения незамкнутого маршрута. В связи с этим, места выезда и возврата ТС могут не совпадать.
Постановка задачи с учетом данной особенности требует количества депо равного или меньшего количеству ТС. Каждое ТС в начальный момент времени может находиться в определенном пункте следования или являться самостоятельным пунктом, в котором не производится загрузка/выгрузка товара, причем прямой связи между транспортными средствами в матрице расстояний нет. Также для каждого ТС добавляется дополнительный признак, характеризующий необходимость возврата в пункт отправления, что влечет в некоторых случаях решение незамкнутой задачи коммивояжера (ЗК).
6.3.3 Возможность частичной загрузки/разгрузки ТС в пунктах следования
Данная особенность охватывает тех клиентов, которые перевозят сборные грузы, то есть перевозчик может, как забирать товар и транспортировать его на склад, так и принимать товар от других клиентов или со склада по пути следования. К примеру, крупные сетевые магазины могут перераспределять товар между точками продажи с учетом его потребности в определенный момент времени. Региональные компании могут использовать данную особенность для перераспределения грузов между ТС в промежуточных пунктах – складах комплектации грузов.
Для использования данного дополнения к постановке ЗМТ каждый пункт следования должен иметь два набора характеристик – грузы к отправлению из пункта и грузы к получению.
Стоит отметить, что при такой постановке ЗМТ появляется потребность в решении задачи распределения товаров, потому как удовлетворить потребности пунктов можно несколькими способами. Это связано с тем, что товар, в котором нуждается данный пункт, может находиться в нескольких местах.
7.3.4 Транспортировка мультиноменклатурного груза
В классической постановке задачи используется только одна номенклатура для перевозки, что часто не соответствует действительности, потому как транспортируемый товар может быть различным. Это обусловлено тем, что чаще всего осуществляется перевозка сборных грузов, при которой один груз включает в себя товары от многих производителей, собранных в единых распределительных центрах.
В связи с этим, в постановке задачи используются такие характеристики товара, как название (код), масса, объем и тип товара.
8.3.5 Учет приоритета обслуживания пункта
Потому как в данной постановке задачи рассматривается различный, не однородный товар и ограниченное количество ТС, то при обслуживании пунктов необходимо учитывать приоритет их посещения за определенный временной интервал. Это обусловлено сроком годности товаров, срочностью выполнения заказа и другими факторами. В связи с тем, что количество ТС ограниченно, в некоторых случаях не удается посетить все пункты в рамках отведенного времени. Для решения данной проблемы можно использовать приоритет обслуживания.
В данной работе не делается акцент на семантическое наполнение термина приоритет. Для продовольственного товара приоритет может означать близость окончания срока реализации этого товара (0 – товар на складе, 1 – товар подлежит списанию), для промышленного, например, сезонная необходимость смены товара. Понятие приоритета может быть расширено для нужд каждого предприятия в отдельности.
Учитывая это, в каждом пункте следования каждый груз для приема/отправки имеет свой приоритет обслуживания.
За счет введения в задачу приоритета обслуживания суммарная стоимость транспортировки грузов может быть уменьшена. Это может достигаться за счет добавления грузов с более низким приоритетом в ТС, которые загружены не полностью, тем самым, стоимость километра передвижения ТС из-за дополнительной загрузки ТС увеличивается незначительно, но прирост экономического эффекта является существенным.
9.3.6 Взаимосвязь с транспортной задачей
Учитывая все вышеперечисленное, можно отметить, что такая постановка задачи является комбинацией двух задач – транспортной задачи в классической постановке и задачи маршрутизации транспорта. В первой задаче делается акцент на распределении товаров между пунктами, во второй задаче происходит построение оптимальных маршрутов для определенного набора ТС. Рассмотрим постановку транспортной задачи в классическом виде.
Постановка: транспортная задача — задача об оптимальном плане перевозок однородного продукта из однородных пунктов отправления в однородные пункты назначения.
Математическая постановка классической ТЗ:
A1,A2,…,Am – пункты отправления,
B1,B2,….Bn – пункты назначения,
С – матрица стоимости, где сij – стоимость перевозки единицы груза из i-го пункта отправления в j-й пункт назначения,
ai – запас товара в i-м пункте отправления,
bj – потребность в товаре в j–м пункте назначения,
X – матрица транспортировки, где xij – количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения,
Цель – необходимо удовлетворить спрос потребителей (магазинов) за счет запаса товара на складах при минимальных затратах на перевозку. Целевая функция: 
Рассмотрим комплексную транспортную задачу (КТЗ). Первым этапом решения будет формирование заказов грузоотправителей, в которых будет определен перечень товаров к перевозке, пункты отправления и назначения, даты отправления и доставки грузов. Вторым этапом будет формирование рейсов, в которые будут включены либо части заказов, в том случае, когда заказ не может быть помещен целиком в ТС, либо несколько заказов целиком, в том случае, если заказы небольшие и могут поместиться в одно ТС. В рейсе (маршрутном листе) ТС может, как выгружать товар в пунктах следования, так и загружать.
Разделение данных задач на составляющие ограничивает ее применение. В связи с этим, целесообразно рассматривать данные задачи в комплексе для решения более широкого круга различных задач транспортировки грузов. Следует учесть тот факт, что с помощью КТЗ можно значительно уменьшить стоимость транспортировки товаров, потому как в некоторых случаях решение задачи будет экономически выгодным при одновременном решении двух частей, так как в одном случае основополагающим этапом будет решение ТЗ, а в некоторых ЗМТ будет определять часть решения ТЗ. Таким образом, решая ЗМТ, мы можем перестраивать решение ТЗ, если это приносит дополнительный экономический эффект.
Стоит отметить, что постановка задачи, описываемая в данной работе, предусматривает рассмотрение нескольких видов транспортной задачи в совокупности.
При снятии ограничения на виды пунктов задача принимает вид сетевой транспортной задачи, в которой каждый пункт может быть как получателем, так и отправителем грузов.
При снятии ограничения на однородность товара задача становится многопродуктовой транспортной задачей, в которой каждый пункт может содержать или требовать несколько различных товаров.
В связи с фактами, перечисленными выше, появилась потребность описать транспортную задачу, которая включает в себя задачу маршрутизации транспорта и использует множество локальных особенностей двух задач для приближения постановки к практическому применению.
Для простоты изложения данную задачу будем обозначать комплексной транспортной задачей (КТЗ).
|
