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

Аннотация

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