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

Аннотация

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

Annotation

Mural D. V., Martynenko T. V., Novikov D. D. Analysis of methods for route finding when planning product transportation in urban conditions. The work is dedicated to the problem and tasks of transportation planning. The methods for solving routing problems were analyzed, based on which the ant algorithm was chosen for further development to solve the asymmetric traveling salesman problem. A mathematical model was developed to solve the problem, taking into account the peculiarities of the task of choosing the optimal route.

Общая постановка проблемы поиска оптимального маршрута транспортировок в городских условиях

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

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

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

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

Планирование перевозок необходимо разделить на подзадачи:

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


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

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

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

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

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

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

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

Математическая постановка задачи

Для обоснования выбора пути необходимо основываться на показатель предполагаемой выгоды перевозки, расчет которой можно рассчитать, как разность, стремящуюся к максимуму (1) предполагаемой прибыли от продажи (V) и предполагаемых затрат на перевозку (K). Ограничениями может выступать, что предполагаемая выгода от перевозки товара, должна быть строго положительна (2).

\[F = V - K \rightarrow \max \quad (1)\] \[F > 0 \quad (2)\]

Пусть V – это общая предполагаемая прибыль от продажи перевозимого товара, тогда ее вычисление можно представить как сумму, произведений стоимости товара на количество перевозимых единиц товара, стремящуюся к максимуму (3). Где цена определенного товара представляется как \(v_i\), а его количественная характеристика как \(y_i\).

\[V = \sum_{i=1}^{n} v_i \times y_i \rightarrow \max \quad (3)\]

Пусть K – это общие предполагаемые расходы от перевозки товара, где критериями выступают расстояние и время маршрута (4).

\[K = \sum_{i=1}^{n} \sum_{m=1}^{n} x_{im} \times \left(D \times d_{im} \times \left(\sum_{i=1}^{n} m_i \times y_i + P\right) + T \times t_{im}\right) \rightarrow \min \quad (4)\]

где x матрица маршрута перевозки и \(x \in \{0,1\}\). D – показатель стоимости перевозки за км, T – показатель стоимости перевозки за час. Матрица d – характеристики расстояний между узлами, Матрица t – временные характеристики между узлами. Также при учете расхода цены от расстояния необходимо учитывать и общий вес грузового транспорта, что отражается в формуле, где \(m_i\) вес определенного товара, \(y_i\) его количественная характеристика и P вес самого автомобиля.

Ограничениями при выборе товара и его количества выступают объем (5) и грузоподъемность транспортного средства (6), вычисляемые по следующим формулам:

\[\sum_{i=1}^{n} w_i \times y_i \leq W \quad (5)\] \[\sum_{i=1}^{n} m_i \times y_i \leq M \quad (6)\]

Анализ методов поиска оптимального маршрута между узлами

Поиск оптимального маршрута между узлами является асимметричной задачей коммивояжера. Асимметричная задача коммивояжера (Asymmetric Traveling Salesman Problem, ATSP) - это специальный случай задачи коммивояжера, где расстояния между городами могут быть разными в зависимости от направления путешествия [1]. Эта задача имеет большое практическое значение в таких областях, как логистика, транспорт и маршрутизация сетей.

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

Метод динамического программирования

Метод динамического программирования (Dynamic Programming) заключается в том, чтобы разбить задачу на более мелкие подзадачи и решать их последовательно. Для этого строится таблица, где каждый элемент представляет собой длину пути от начального города до данного города, проходящего через все промежуточные города [2]. Эти значения используются для построения более длинных путей. Метод динамического программирования обеспечивает точное решение задачи, но может потребовать значительных вычислительных ресурсов, особенно для больших задач.

Метод ветвей и границ

Метод ветвей и границ (Branch and Bound) – общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. Метод является развитием метода полного перебора, в отличие от последнего — с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений [3]. Задача разбивается на меньшие подзадачи, которые решаются независимо друг от друга. Затем определяется нижняя граница решения для каждой из подзадач, и неперспективные подзадачи отбрасываются. Затем процесс повторяется для оставшихся перспективных подзадач. Этот метод также обеспечивает точное решение задачи, но может быть неэффективен для больших задач.

Муравьиный алгоритм

Муравьиный алгоритм (Ant Colony Optimization) – это эвристический метод оптимизации, который имитирует поведение муравьев при поиске кратчайшего пути между местом источника пищи и муравейником [4]. Муравьиный алгоритм относится к классу метаэвристических алгоритмов, которые используют случайный поиск и вычислительную эффективность для поиска оптимального решения.

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

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

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

Таблица 1 - Сравнительная таблица достоинств и недостатков методов

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

Выводы

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

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

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