Интеллектуальные модели разработки маршрутов перевозки мелкопартионных грузов

The main results of the study developed approaches in an ABC-analysis to determine the nomenclature groups of stocks enterprise. On the basis of the provisions laid down by the definition of methodological nomenclature groups, the capabilities andfeatures of their use in practical activities of enterprises. The variants of the calculations in terms of cargo handling practices used in business. The necessity of implementing this approach in the practice of companies that enhance the efficiency of their operation.

Key words: logistics, transport, stock analysis, system nomenclature process.

Gusev Sergey Aleksandrovich, doctor of economics, docent, o051nm@yandex.ru, Russia, Saratov, Saratov State Technical University named after Yu. A. Gagarin,

Mаrosin Vladimir Sergeevich, postgraduate, marosin92@,mail. ru, Russia, Saratov, Saratov State Technical University named after Yu. A. Gagarin

УДК 656.13

ИНТЕЛЛЕКТУАЛЬНЫЕ МОДЕЛИ РАЗРАБОТКИ МАРШРУТОВ ПЕРЕВОЗКИ МЕЛКОПАРТИОННЫХ ГРУЗОВ

С. А. Гусев, В.С. Маросин

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

Ключевые слова: транспорт, логистика, маршрут, перевозка, система, технология, перевозка, процесс.

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

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

69

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

Для усиления изложенного рассмотрим следующий пример.

Математически транспортная задача формулируется следующим образом. Требуется минимизировать

от п

1 = X X СиХи

1=1 ]=\

при ограничениях

гп

^ Хц = аь, I = 1, гп)

1=1 п

^ Хц = Ьу , у = 1, п;

;=1

гп п

=

¿=1 ;=1

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

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

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

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

- часть показателей превращают в ограничения. Так, если в рассмотренном примере задано время перевозок, то его можно представить в виде ограничения, а критерием оптимальности считать стоимость перевозок. Возможна и обратная постановка задачи оптимизации: минимизировать время перевозок при заданной стоимости (при имеющихся средствах перевозки);

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

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

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

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

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

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

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

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

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

Т = 1 п + X У ^ + 1 * , ) + 1 х ,

где Ц- - время погрузки у _]-го грузоотправителя, ч.;1 ^ - время движения

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

Организация перевозочного процесса напрямую связана с режимом работы грузоотправителей и грузополучателей. Согласно изложенным подходам [2] речь идет о выполнении «точно в срок» договорных обязательств автомобильного транспорта перед клиентами (поставщиками и потребителями). Исходя из этого следует, что задача сводится к определению времени доставки заданного объема грузов точно в срок. Тогда время начала работы транспортного средства грузов можно определить по формуле

Т н = Тт .в . — Х Тоу — Тн.п . ,

у

где Ттв - время доставки договорного объема грузов "точно во время", ч.; Т^ - время на перевозку суточного объема груза, ч.; Т1н.п - время на первый нулевой пробег (от автотранспортного предприятия до первого пункта погрузки), ч.

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

к к Ту = * пу + X гргу + * ргу ) + * ху + П у + X V ,у ,

г=1 г=1

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

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

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

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

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

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

Описанное в работе [3] решение, основанное на сетях с обратными связями, является типичным в этом отношении. Однако ответ получается так быстро, что в определенных случаях метод может оказаться полезным.

Допустим, что города, которые необходимо посетить, помечены буквами A, B, C и D, а расстояния между парами городов есть dab, dbc и т.д.

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

Длина такого маршрута была бы равна dca + dad + ddb + dbc. Так как каждый город посещается только один раз, ив каждый момент посещается лишь один город, то в каждой строке и в каждом столбцеимеется по одной единице. Для задачи с п городами всего имеется п! различных маршрутов обхода.

Продемонстрируем теперь, как сконструировать сеть для решения этой NP-полной проблемы. Каждый нейрон снабжен двумя индексами, которые соответствуют городу и порядковому номеру его посещения в маршруте.

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

Первое требование удовлетворяется введением следующей состоящей из трех сумм функции энергии

А B C

е = - ЕЕ I MxíMxj + - ЕЕ Е мХ1му1 + у

2 х i yф\ 2 i х уфх 2

С \

Е Е Mxí

V х i J

n

где А, В и С - некоторые константы; М - выходной нейронный сигнал.

Этим достигается выполнение следующих условий [3].

1. Первая тройная сумма равна нулю в том и только в том случае, если каждая строка(город) содержит не более одной единицы.

2. Вторая тройная сумма равна нулю в том и только в том случае, если каждыйстолбец (порядковый номер посещения) содержит не более одной единицы.

3. Третья сумма равна нулю в том и только в том случае, если матрица содержит ровно п единиц.

2

Второе требование - предпочтение коротким маршрутам - удовлетворяется с помощью добавления следующего члена к функции энергии:

—

Е=-X XX ВхуМу^+1 + Мул

2 х уФх i

Заметим, что этот член представляет собой длину любого допустимого маршрута. Для удобства индексы определяются по модулю n, т. е. Мд+]= М], a -некоторая константа.

При достаточно больших значениях A, B и C низкоэнергетические состояния будут представлять допустимые маршруты, а большие значения D гарантируют, что будет найден короткий маршрут.

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

Wxi. yi = _ Ad ху

не допускается более одной единицы в столбце

_ Bdij

глобальное ограничение - элемент C, отвечающий за длину цикла

_ Ddxy

где, StJ = 1, если i=j, в противном случае Sv = 0. Кроме того, каждый нейрон имеет смещающий вес хг, соединенный с+1 и равный Cn.

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

Список литературы

1. Логистика автомобильного транспорта: учеб. пособие / В.С. Лукин-ский [и др.]. М.: Финансы и статистика, 2004. 368 с.

2. Модели и методы теории логистики: учеб. пособие / под ред. В. С. Лукинского. 2-е изд. СПб.: Питер, 2008. 448 с.

3. Horfield J.J., Tank D.W. 1985. Neural computation of decisions in op-timizationproblems // Biological Cybernetics. 52. P. 141 - 152.

Гусев Сергей Александрович, д-р экон. наук, доц., o051 timer yandex. ru, Россия, Саратов, Саратовский государственный технический университет им. Ю.А. Гагарина,

Маросин Владимир Сергеевич, асп., marosin92@mail. ru, Россия, Саратов, Саратовский государственный технический университет им. Ю.А. Гагарина

INTELLIGENTTRANSPORTA TION ROUTEDEVELOPMENT MODELSMALL-LOTGOODS

S.A. Gusev, V.S. Marosin

The article describes the main results of the study theoretical approaches and the development of solutions to transportation problems for transportation of LCL cargoes by motor transport. The peculiarities of development of routes of delivery of goods in small consignments, as well as the theoretical framework of the application of artificial neural networks in designing routes and direct management traffic. The proposed implementation of the transport companies algorithms for planning and management of transportation process models based on artificial neural networks as tools for intelligent control of the transportation process.

Key words: transport, logistics, itinerary, transportation, system, technology, transportation, process.

Gusev Sergey Aleksandrovich, doctor of economics, docent, o051nm@yandex.ru, Russia, Saratov, Saratov State Technical University named after Yu. A. Gagarin,

Mаrosin Vladimir Sergeevich, postgraduate, marosin92@ mail. ru, Russia, Saratov, Saratov State Technical University named after Yu. A. Gagarin