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

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

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

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2016
Автори: Васянин, В.А., Ушакова, Л.П.
Формат: Стаття
Мова:Russian
Опубліковано: Інститут телекомунікацій і глобального інформаційного простору НАН України 2016
Назва видання:Математичне моделювання в економіці
Теми:
Математичні та інформаційні моделі в економіці
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/131865
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Задачи построения доставочных и сборочных маршрутов перевозки мелкопартионных грузов во внутренних зонах иерархической автотранспортной сети / В.А. Васянин, Л.П. Ушакова // Математичне моделювання в економіці. — 2016. — № 3-4(7). — С. 102-131. — Бібліогр.: 52 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-131865
record_format dspace
spelling irk-123456789-1318652018-04-05T03:03:09Z Задачи построения доставочных и сборочных маршрутов перевозки мелкопартионных грузов во внутренних зонах иерархической автотранспортной сети Васянин, В.А. Ушакова, Л.П. Математичні та інформаційні моделі в економіці В работе приведены основные принципы и схемы организации перевозок мелкопартионных грузов во внутренних зонах обслуживания магистральных узлов иерархической транспортной сети. Обсуждаются технические и экономические аспекты обработки и транспортировки грузов. Проведен обзор задач маршрутизации и методов и алгоритмов их решения. Предложено несколько математических формулировок задач построения доставочных и сборочных маршрутов для перевозки мелкопартионных грузов с использованием неограниченного и ограниченного неоднородного парка транспортных средств и дополнительными ограничениями. Отмечается возможность решения сформулированных задач с помощью известных пакетов смешанного и целочисленного линейного программирования. У роботі наведені основні принципи і схеми організації перевезень дрібнопартіонних вантажів у внутрішніх зонах обслуговування магістральних вузлів ієрархічної транспортної мережі. Обговорюються технічні та економічні аспекти обробки і транспортування вантажів. Проведено огляд задач маршрутизації і методів і алгоритмів їх розв’язку. Запропоновано декілька математичних формулювань задач побудови постачальних і збірних маршрутів для перевезення дрібнопартіонних вантажів з використанням необмеженого і обмеженого неоднорідного парку транспортних засобів і додатковими обмеженнями. Відзначається можливість розв’язання сформульованих задач за допомогою відомих пакетів змішаного і цілочисельного лінійного програмування. The paper presents the basic principles and schemes of organization transportation of smalllots of cargo in the internal service areas of trunk nodes of hierarchical of transport network. Discusses the technical and economic aspects of processing and transportation cargo. The review of the vehicle routing problems and methods and algorithms their solve is conducted. The several mathematical formulations of Heterogeneous Fleet Vehicle Routing Problem with delivery and collection of small-lot cargo and limited or unlimited fleet and additional restrictions are suggested. It is marked the possibility of solving formulated problems by known packages of mixed and integer linear programming. 2016 Article Задачи построения доставочных и сборочных маршрутов перевозки мелкопартионных грузов во внутренних зонах иерархической автотранспортной сети / В.А. Васянин, Л.П. Ушакова // Математичне моделювання в економіці. — 2016. — № 3-4(7). — С. 102-131. — Бібліогр.: 52 назв. — рос. 2409-8876 http://dspace.nbuv.gov.ua/handle/123456789/131865 519.854.2 ru Математичне моделювання в економіці Інститут телекомунікацій і глобального інформаційного простору НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
topic Математичні та інформаційні моделі в економіці
Математичні та інформаційні моделі в економіці
spellingShingle Математичні та інформаційні моделі в економіці
Математичні та інформаційні моделі в економіці
Васянин, В.А.
Ушакова, Л.П.
Задачи построения доставочных и сборочных маршрутов перевозки мелкопартионных грузов во внутренних зонах иерархической автотранспортной сети
Математичне моделювання в економіці
description В работе приведены основные принципы и схемы организации перевозок мелкопартионных грузов во внутренних зонах обслуживания магистральных узлов иерархической транспортной сети. Обсуждаются технические и экономические аспекты обработки и транспортировки грузов. Проведен обзор задач маршрутизации и методов и алгоритмов их решения. Предложено несколько математических формулировок задач построения доставочных и сборочных маршрутов для перевозки мелкопартионных грузов с использованием неограниченного и ограниченного неоднородного парка транспортных средств и дополнительными ограничениями. Отмечается возможность решения сформулированных задач с помощью известных пакетов смешанного и целочисленного линейного программирования.
format Article
author Васянин, В.А.
Ушакова, Л.П.
author_facet Васянин, В.А.
Ушакова, Л.П.
author_sort Васянин, В.А.
title Задачи построения доставочных и сборочных маршрутов перевозки мелкопартионных грузов во внутренних зонах иерархической автотранспортной сети
title_short Задачи построения доставочных и сборочных маршрутов перевозки мелкопартионных грузов во внутренних зонах иерархической автотранспортной сети
title_full Задачи построения доставочных и сборочных маршрутов перевозки мелкопартионных грузов во внутренних зонах иерархической автотранспортной сети
title_fullStr Задачи построения доставочных и сборочных маршрутов перевозки мелкопартионных грузов во внутренних зонах иерархической автотранспортной сети
title_full_unstemmed Задачи построения доставочных и сборочных маршрутов перевозки мелкопартионных грузов во внутренних зонах иерархической автотранспортной сети
title_sort задачи построения доставочных и сборочных маршрутов перевозки мелкопартионных грузов во внутренних зонах иерархической автотранспортной сети
publisher Інститут телекомунікацій і глобального інформаційного простору НАН України
publishDate 2016
topic_facet Математичні та інформаційні моделі в економіці
url http://dspace.nbuv.gov.ua/handle/123456789/131865
citation_txt Задачи построения доставочных и сборочных маршрутов перевозки мелкопартионных грузов во внутренних зонах иерархической автотранспортной сети / В.А. Васянин, Л.П. Ушакова // Математичне моделювання в економіці. — 2016. — № 3-4(7). — С. 102-131. — Бібліогр.: 52 назв. — рос.
series Математичне моделювання в економіці
work_keys_str_mv AT vasâninva zadačipostroeniâdostavočnyhisboročnyhmaršrutovperevozkimelkopartionnyhgruzovvovnutrennihzonahierarhičeskojavtotransportnojseti
AT ušakovalp zadačipostroeniâdostavočnyhisboročnyhmaršrutovperevozkimelkopartionnyhgruzovvovnutrennihzonahierarhičeskojavtotransportnojseti
first_indexed 2025-07-09T16:19:30Z
last_indexed 2025-07-09T16:19:30Z
_version_ 1837186915417194496
fulltext ~ 102 ~ Математичне моделювання в економіці, №3-4, 2016 УДК 519.854.2 В.А. ВАСЯНИН, Л.П. УШАКОВА ЗАДАЧИ ПОСТРОЕНИЯ ДОСТАВОЧНЫХ И СБОРОЧНЫХ МАРШРУТОВ ПЕРЕВОЗКИ МЕЛКОПАРТИОННЫХ ГРУЗОВ ВО ВНУТРЕННИХ ЗОНАХ ИЕРАРХИЧЕСКОЙ АВТОТРАНСПОРТНОЙ СЕТИ Аннотация. В работе приведены основные принципы и схемы организации перевозок мелкопартионных грузов во внутренних зонах обслуживания магистральных узлов иерархической транспортной сети. Обсуждаются технические и экономические аспекты обработки и транспортировки грузов. Проведен обзор задач маршрутизации и методов и алгоритмов их решения. Предложено несколько математических формулировок задач построения доставочных и сборочных маршрутов для перевозки мелкопартионных грузов с использованием неограниченного и ограниченного неоднородного парка транспортных средств и дополнительными ограничениями. Отмечается возможность решения сформулированных задач с помощью известных пакетов смешанного и целочисленного линейного программирования. Ключевые слова: задачи комбинаторной оптимизации, математические модели маршрутизации транспортных средств, автотранспортные перевозки, мелкопартионные грузы. Введение Как правило, существующие и проектируемые автотранспортные сети имеют иерархическую структуру и состоят из децентрализованной магистральной сети и внутренних сетей магистральных узлов. В данной работе предполагается, что многоуровневая структура автотранспортной сети перевозок мелкопартионных грузов уже определена и известны географическое расположение магистральных узлов и их внутренние зоны обслуживания [1]. Здесь и далее под мелкопартионными грузами понимаются тарно-штучные грузы унифицированного размера. Во внутренней зоне каждого магистрального узла находятся доставочные и сборочные узлы, которые могут обмениваться грузами между собой и со всеми другими узлами иерархической сети только через этот магистральный узел. Возникает задача построения рациональных кольцевых маршрутов транспортных средств с центральным магистральным узлом. В работе рассматриваются вопросы организации перевозок во внутренних зонах магистральных узлов, приводятся основные принципы и схемы, заложенные в основу построения маршрутов. Обсуждаются технические и экономические особенности и характеристики реальных транспортных процессов, которые должны быть учтены при формировании целевых функций математических моделей задач маршрутизации на уровнях долгосрочного и текущего планирования и оперативного управления. Приводятся классификация задач маршрутизации по основополагающим признакам и библиографический обзор литературы, Ó В.А. Васянин, Л.П. Ушакова, 2016 ~ 103 ~ Математичне моделювання в економіці, №3-4, 2016 посвященной их решению. Предложено несколько вариантов математических постановок задачи, которые основаны на известных типовых моделях и могут быть использованы при проектировании рабочего парка и маршрутов транспортных средств для обслуживания узлов во внутренней зоне магистрального узла. Обсуждаются методы и алгоритмы, применяемые в настоящее время для решения задач подобного класса. Предложенные математические модели для решения рассматриваемых задач включены в состав математического обеспечения автоматизированной информационно- аналитической системы поддержки принятия решений (АИАС ППР), которая разрабатывается в Институте телекоммуникаций и глобального информационного пространства НАН Украины [2]. 1. Основные принципы и схемы перевозок При изложении материала используются сокращения: транспортное средство (ТС) – автомобили и автомобильные прицепы; депо и клиенты – места размещения парка ТС и обслуживаемые узлы во внутренней зоне магистрального узла. Приведем основные принципы организации внутриузловых перевозок: - для выполнения перевозок используются только кольцевые (замкнутые, циклические) маршруты ТС с одним или несколькими депо во внутренней зоне магистрального узла; - каждый клиент может обслуживаться только одним ТС (возможно с одним или двумя прицепами); - кузова автомобилей и прицепов должны быть оборудованы так, чтобы давать возможность погрузки и выгрузки грузов с боковых бортов и заднего борта кузова; - все ТС и грузовые поддоны после обслуживания клиентов должны возвращаться в депо. Загруженный в магистральном узле прицеп может быть оставлен на некоторое время в местах дислокации клиентов для выгрузки и погрузки больших объемов грузов. Загруженный клиентом прицеп возвращается в магистральный узел и депо тягловым ТС при очередном посещении клиента; - могут использоваться ТС разных типов с разной грузоподъемностью и начальной продажной стоимостью, т. е. допускается неоднородность (гетерогенность) рабочего парка транспортных средств (РП ТС); - в течение рабочего дня одно и то же ТС может быть использовано для перевозки грузов несколько раз и не обязательно по одному и тому же маршруту; - в отдельных случаях при оперативном перераспределении потоков грузов и маршрутов ТС из-за возникновения временных перегрузок и непредвиденных ситуаций в сети перевозок допускается обслуживание любого клиента несколькими ТС; - магистральный узел сортирует грузы (поступающие в него из магистральной сети и адресованные во внутреннюю зону узла) по местам дислокации клиентов во внутренней зоне. Отсортированные грузы могут быть сгруппированы и погружены на поддоны для каждого клиента. Грузы на поддонах перевозятся только в грузовых отсеках автомобиля, доступ к ~ 104 ~ Математичне моделювання в економіці, №3-4, 2016 которым возможен со всех бортов. Для мелких партий грузов, перевозимых без поддонов, должна применяться погрузка по правилу «последний пришел, первый вышел» (Last Input, First Output, LIFO). Большие партии грузов, предназначенные одному клиенту, перевозятся общей массой (навалом), без упорядочения; - клиенты не сортируют грузы по адресам назначения, а отправляют их в магистральный узел, загружая ТС общей массой (навалом), поэтому обмен грузами между клиентами во внутренней зоне возможен только через магистральный узел этой зоны; - все грузы из магистрального узла к клиентам и все грузы от клиентов в магистральный узел должны быть доставлены в течение 24 часов (принимается восьмичасовой рабочий день водителей в дневную и ночную смену). Здесь предполагается, что во внутреннюю зону каждого магистрального узла включены только такие клиенты, которые могут быть обслужены в течение рабочего дня водителя с учетом времени возвращения ТС в депо; - могут быть заданы жесткие временные горизонты (временные окна – Time Window, TW) для отправления и получения грузов в магистральном узле и для получения и отправления грузов в местах дислокации клиентов. Для организации перевозок во внутренних зонах магистральных узлов можно применять в основном следующие три схемы перевозки грузов на проектируемых маршрутах ТС: - доставочные маршруты для перевозки грузов из магистрального узла к клиентам; - сборочные маршруты для перевозки грузов от клиентов к магистральному узлу; - комбинированные маршруты, на которых разрешено выгружать и погружать грузы в местах дислокации клиентов. На рис. 1 проиллюстрированы фрагменты внутриузловой сети, схематично показаны циркулирующие потоки и пример кольцевых маршрутов. а) б) в) Рисунок 1 – а) внутриузловая сеть с центральным магистральным узлом и депо, места дислокации клиентов закрашены черным цветом, а транзитные дорожные узлы – серым, участки дорог показаны линиями; б) входящие и исходящие магистральные потоки (широкая стрелка), и внутриузловые ~ 105 ~ Математичне моделювання в економіці, №3-4, 2016 потоки к клиентам и от клиентов (простая стрелка); в) два циклических маршрута транспортных средств 2. Функции затрат и содержательная постановка задачи В этом разделе обсуждаются вопросы, связанные с методикой расчета приведенных затрат при решении задачи маршрутизации внутриузловых перевозок на долгосрочные и среднесрочные периоды времени. Целью решения такой задачи является определение общего количества и состава транспортных средств по типам и грузоподъемности, необходимого для выполнения всех перевозок во внутренней зоне магистрального узла при минимизации капитальных затрат на приобретение транспортных средств и эксплуатационных расходов на транспортировку грузов. При решении задачи нужно определить рабочий парк неоднородных транспортных средств (гетерогенный рабочий парк) и найти схему распределения потоков грузов и маршрутизации транспортных средств во внутриузловой сети перевозок. В зарубежной литературе эти задачи принято называть Fleet Size and Mix Vehicle Routing (FSMVRP) и Heterogeneous Fleet Vehicle Routing Problem (HFVRP) в зависимости от ограничений на количество транспортных средств каждого типа. В дальнейшем будем использовать эти аббревиатуры для краткости изложения материала по всем вопросам решения таких задач. Для транспортных предприятий (компаний) ключевыми факторами при расчете затрат являются ожидаемые объемы перевозок, цены на транспортные средства и себестоимость перевозок. Транспортные средства с большей грузоподъемностью, как правило, имеют более низкую себестоимость перевозки единицы груза, чем транспортные средства с меньшей грузоподъемностью, при условии, что коэффициент загрузки транспортного средства достаточно высок. Следует учитывать и то, что для подержанных транспортных средств затраты на амортизацию ниже, а затраты на содержание выше, чем у новых. Объемы перевозок и цены на транспортные средства изменяются во времени, поэтому у транспортных предприятий возникает и задача управления размером рабочего парка не только на периоды текущего планирования, но и на перспективу. Чрезмерно большой парк при снижении спроса на перевозки вынуждает продавать или сдавать в аренду излишек транспортных средств, увеличение спроса приводит к необходимости приобретения новых транспортных средств или их аренды. В любом случае при долгосрочном планировании ожидаемые доходы должны быть больше ожидаемых затрат. Регулирование размера рабочего парка, зависящего от приведенных и других случайных факторов, должно осуществляться при решении динамических стохастических задач долгосрочного планирования, математические модели которых более агрегированные, чем у задач текущего планирования. Соответственно в этом случае используются и более агрегированные функции приведенных затрат. В математических моделях текущего (тактического) планирования, как правило, рассматриваются усредненные потоки и цены для заданных периодов времени на протяжении года, рассчитанные статистическими методами. Неопределенность в этом случае уменьшается, и задача маршрутизации должна рассматриваться на более детальном уровне с учетом всех значимых факторов. Как и при долгосрочном планировании, в условиях колебания спроса, основные решения связаны с приобретением и арендой ~ 106 ~ Математичне моделювання в економіці, №3-4, 2016 транспортных средств или с продажей и сдачей в аренду имеющихся излишек. Однако при принятии тактических решений следует больше уделять внимания корректировке грузоподъемности транспортных средств. Поэтому при решении задач маршрутизации на среднесрочные периоды, как правило, создаются резервы грузоподъемности транспортных средств на всех маршрутах транспортировки грузов, т. е. может быть задан коэффициент максимальной загрузки транспортного средства. Это приводит к использованию транспортных средств с большей грузоподъемностью и увеличению капитальных и эксплуатационных затрат, но позволяет выполнять заказы клиентов в условиях колебания спроса в определенных пределах. Задача состоит в определении «золотой середины». При текущем планировании точно известны размер и состав РП ТС, подробная схема распределения потоков грузов и транспортных средств по маршрутам движения. Известны также заключенные контракты и тарифы на перевозку грузов и другие виды операций, влияющих на текущее финансовое состояние транспортного предприятия. В этой связи при неопределенном колебании спроса может быть поставлена задача оптимизации РП ТС и портфеля заказов – необходимо отобрать наиболее выгодные контракты так, чтобы их можно было бы выполнить при имеющемся потенциале провозных возможностей транспортного предприятия. Следует отметить, что не во всех случаях при текущем планировании нужно объединять решение задачи определения РП ТС с решением задачи управления активами и портфелем заказов транспортного предприятия, так как последняя может быть решена независимо при известных колебаниях нагрузок в сети перевозок. На оперативном уровне задача транспортного предприятия, как правило, состоит в перераспределении потоков и реоптимизации схемы маршрутизации при превышении провозной возможности или возникновении отказов у клиентов и на маршрутах движения, а также при различных непредвиденных ситуациях и стихийных бедствиях. В этом случае может быть использован внутренний резерв транспортных средств или привлечены арендные транспортные средства. Для транспортных предприятий чрезвычайно важно, чтобы при решении задач текущего планирования они могли бы получить реальные оценки транспортных издержек. Поэтому в математических моделях, используемых для текущего планирования перевозок, в функциях затрат должны отражаться основные статьи эксплуатационных расходов, связанные с содержанием парка транспортных средств и транспортировкой грузов. В большинстве зарубежных и отечественных работ, посвященных решению задач замкнутой маршрутизации (построению циклических маршрутов), авторы рассматривают затраты на дугах маршрута как заданные константы и предполагают, что эти затраты не зависят от типа и грузоподъемности транспортного средства. Более того, принимается также, что затраты одинаковы при прохождении транспортной дуги в прямом и обратном направлении. Однако такие допущения не реалистичны. На практике затраты на дугах зависят от длины, состояния и географических особенностей участков дороги, типа и грузоподъемности транспортного средства, его текущей загрузки и скорости движения. Все это, в свою очередь, влияет на расход топлива. Кроме того, при транспортировке грузов нужно учитывать дополнительные издержки, связанные со случайными ~ 107 ~ Математичне моделювання в економіці, №3-4, 2016 факторами – вынужденными простоями транспортных средств из-за непредвиденных ситуаций на дороге, стихийных проявлений природы и др. Дополнительные издержки на практике обычно проявляются в виде штрафных санкций за нарушение сроков доставки грузов, их утерю или повреждение. В задачах построения циклических маршрутов всегда известна начальная и конечная точка маршрута, поэтому будут найдены все узлы и дуги, через которые проходит маршрут. Это дает возможность, при условии аддитивности затрат, задавать их на дугах ),( ji и в узлах i функциями k ijf и k if для каждого ТС типа k . В эти функции, кроме основных параметров, определяющих длину дуги, грузоподъемность и скорость движения ТС, должны быть включены коэффициенты, отражающие фактическую загрузку ТС на дуге и ее географические особенности (например, подъем или спуск соответствующего участка дороги). Функции k ijf могут зависеть и от одного, обобщенного параметра – расхода топлива на дуге ),( ji . Вычисляемые в процессе решения задачи значения этих функций должны определять реальные эксплуатационные затраты на перевозку грузов по всему маршруту, проходящему по физическим участкам дорог (см. рис. 1а, в). Ясно, что расходы на приобретение, содержание и эксплуатацию рабочего парка транспортных средств при решении задачи маршрутизации должны рассчитываться только с учетом тех параметров, которые явно или неявно входят в математическую модель задачи. Поэтому эти расходы будут составлять только часть себестоимости перевозок транспортного предприятия. Напомним, что себестоимость перевозок – это выраженная в денежной форме величина эксплуатационных расходов транспортного предприятия, приходящихся в среднем на единицу продукции транспорта. На грузовом автомобильном транспорте себестоимость перевозок определяется, как правило, за перевезенную тонну грузов на один километр (т/км) или за использование одного автомобиля в час (а/ч). Расчет себестоимости необходим для определения тарифов на перевозку грузов и ожидаемой прибыли предприятия. Оптимизация маршрутов перевозки грузов позволяет снизить себестоимость перевозок в основном за счет устранения нерациональных маршрутов, увеличения коэффициента загрузки и уменьшения потребляемого топлива и порожнего пробега ТС, уменьшения времени доставки грузов потребителю. Поскольку после решения задачи известны капитальные затраты на приобретение РП ТС, то возникает вопрос: какие статьи эксплуатационных затрат на перевозку нужно учитывать в общей формуле расчета приведенных затрат при решении задачи? Представляется разумным, что для расчета эксплуатационных затрат в формуле необходимо учитывать только те статьи затрат, которые непосредственно связаны с перевозкой грузов, а общехозяйственные (накладные) расходы предприятия можно не учитывать. Перечислим основные статьи этих затрат: топливо, смазочные и прочие эксплуатационные материалы; техническое обслуживание и ремонт подвижного состава (автомобилей и прицепов); амортизация по восстановлению подвижного состава; износ и ремонт автомобильной резины; заработная плата водителей вместе с отчислениями на социальные нужды. ~ 108 ~ Математичне моделювання в економіці, №3-4, 2016 Помимо перечисленных, в расчетной общей формуле приведенных затрат могут быть учтены и другие статьи эксплуатационных затрат, связанные с движением (дорожные сборы, оплата платных дорог и пр.). Главное – чтобы величина эксплуатационных затрат, рассчитанная по выведенной формуле при решении задачи, была бы как можно ближе сопоставима (адекватна) с величиной той части затрат, которые были фактически понесены предприятием только на перевозку грузов по оптимизированным маршрутам движения транспортных средств. Определение общей формулы расчета приведенных затрат представляет отдельную, непростую задачу для экономистов транспортного предприятия, которая должна быть решена до проведения численного решения задачи нахождения состава и количества транспортных средств, распределения потоков грузов и маршрутизации транспортных средств. Во многих практических случаях функции приведенных затрат нелинейные, несепарабельные и неаддитивные, и это следует учитывать при построении математической модели конкретно рассматриваемой задачи. 3. Классификация задач маршрутизации, краткий обзор методов и алгоритмов их решения Трудно утверждать, что единственная формулировка задачи будет достаточной для всех реальных приложений. В частности, как уже упоминалось, для долгосрочного планирования из-за неопределенности информации существует большая вероятность принятия различных решений о возможном составе РП ТС. Для таких задач должны использоваться более агрегированные модели распределения потоков грузов и маршрутизации ТС. В задачах текущего планирования и оперативного управления детализация моделей маршрутизации должна увеличиваться для получения оценок приведенных затрат, адекватных затратам, понесенным на процессы обработки и транспортировки грузов в реальных сетях. В большинстве известных работ, посвященных решению задач маршрутизации на транспорте, рассматриваются идеализированные (академические) математические модели, в которых не учитываются многие факторы, присущие реальным процессам обработки и транспортировки грузов. Например, такие важные параметры, как расстояние, время поездки, транспортные расходы, время обслуживания и другие, присутствуют в некотором абстрактном виде. Во многих моделях принимается евклидово расстояние между узлами сети перевозок, когда выполняется правило треугольника. Скорость и затраты, за немногими исключениями стохастических моделей, моделируются константами. В реальной жизни для внутриузловых перевозок должны рассчитываться действительные расстояния, время и приведенные затраты на транспортировку грузов. В частности, в городских районах, представляющих внутреннюю сеть перевозок, время в пути является весьма неопределенным, так как скорость транспортных средств может изменяться с течением времени из-за перегрузки улиц. Поэтому для расчета времени доставки грузов представляется разумным использовать среднюю скорость движения транспортных средств, однако надо учитывать, что с увеличением средней скорости на объездных дорогах могут возрасти эксплуатационные затраты. В ~ 109 ~ Математичне моделювання в економіці, №3-4, 2016 любом случае в моделях внутриузловых перевозок нужно учитывать зависимость между скоростью и затратами. Кроме того, при расчете времени доставки клиентам необходимо учитывать время на сортировку и погрузку мелкопартионных грузов в магистральном узле и время на разгрузку и погрузку грузов в местах дислокации клиентов. Часто рассматриваются задачи, в которых рабочий парк транспортных средств является однородным. На практике, как правило, транспортные предприятия имеют неоднородный парк транспортных средств. Есть и другие важные производственные особенности помимо неоднородности парка, так, например, задача маршрутизации должна рассматриваться вместе с задачей оптимизации распределения водителей между транспортными средствами с учетом ограничений на длительность рабочего дня. В классической постановке задачи маршрутизации существует единое депо, где каждое транспортное средство начинает и заканчивает движение. При этом для каждого транспортного средства допускается только один циклический маршрут (тур) движения. В реальных задачах транспортировки грузов может быть несколько депо, и водители могут выполнять множество различных туров в день. Приведенные особенности характерны для внутриузловых перевозок, когда транспортные средства доставляют грузы между магистральным узлом и клиентами внутренней зоны и наоборот и, возможно, между различными клиентами внутренней зоны. Можно условно выделить несколько основных классов задач маршрутизации на транспорте, которые наиболее часто рассматриваются в литературе: – классическая задача маршрутизации транспортных средств (The Vehicle Routing Problem, VRP) и ее разновидности: простая пикап-доставка (Vehicle Routing Problem with Pickup and Delivery, VRPPD); доставка с упорядочением загружаемых грузов по правилу «последним пришел, первым вышел» (VRPPD with LIFO); доставка с временными окнами (Vehicle Routing Problem with Time Windows, VRPTW); доставка с ограниченной грузоподъемностью транспортных средств на маршрутах или с ограниченной пропускной способностью дуг сети (Capacitated Vehicle Routing Problem, CVRP или Capacitated Arc Routing Problem, CARP); доставка с одновременной сборкой грузов для депо (Vehicle Routing Problem with Simultaneous Delivery and Pick-up, VRPSDP); доставка с неоднократным посещением клиентов (Split Delivery Vehicle Routing Problem, SDVRP); доставка, когда одни и те же транспортные средства могут использоваться многократно на разных маршрутах (Vehicle Routing Problem with Multiple Trips, VRPMT); доставка, когда транспортные средства могут иметь более одного депо (Vehicle Routing Problem with Multiple Depots, VRPMD); открытая задача маршрутизации, когда транспортные средства не обязаны возвращаться в депо (Open Vehicle Routing Problem, OVRP); ~ 110 ~ Математичне моделювання в економіці, №3-4, 2016 задача маршрутизации грузовика с прицепом (The Truck and Trailer Routing Problem, TTRP); задача маршрутизации транспортных средств с прицепами, когда прицепы могут оставаться в узлах под разгрузку и погрузку (The Rollon-Rolloff Vehicle Routing Problem, RRVRP). – обобщенная задача формирования (определения размера и состава) гетерогенного рабочего парка транспортных средств и схемы распределения потоков грузов и маршрутизации транспортных средств (Heterogeneous Fleet Vehicle Routing Problem, HFVRP или The Fleet Size and Mix Vehicle Routing Problem, FSMVRP) и ее разновидности в зависимости от ограничений на размер парка; – обобщенная задача формирования гетерогенного рабочего парка транспортных средств, размещения депо и схемы распределения потоков грузов и маршрутизации транспортных средств (The Fleet Size and Mix Location Routing Problem, FSMLRP); – задача проектирования сети (Network Design Problems, NDP) и задача сервисного обслуживания сети (Service Network Design problems, SND), в которой маршрутизация связана с частотой, режимами и графиками проведения сервисных работ. Второй класс задач иногда обобщают под названием – Fleet Composition and Routing Problems, FCRP. На практике все эти задачи могут быть связаны между собой и образовывать различные гибриды в зависимости от необходимости учета фактических ограничений. Рассмотренные классы задач можно разделить и упорядочить по нескольким основополагающим признакам. Например, таким как количество депо и клиентов, технические характеристики ТС и физические характеристики сети дорог и перевозимых грузов (непрерывные и дискретные потоки, однородные и смешанные грузы), схемы и условия перевозки грузов, ограничения по времени и т. п. Впервые задача VRP была сформулирована в 1959 г. Данцигом и Рамсером (G.B. Dantzig, J.H. Ramser) и впоследствии стала называться классической. Эта задача является обобщением широко известной NP-трудной задачи коммивояжера (Traveling Salesman Problem, TSP), для которой до сих пор неизвестны методы и алгоритмы, позволяющие за полиномиальное время находить точные или приближенные решения с заданной оценкой погрешности [3] (теорема S. Sahni, T. Gonzalez, 1976 г.). Для метрической TSP в 1976 г. Кристофидесом (N. Christofides) [4] был предложен алгоритм с оценкой погрешности не более 50%, и этот результат пока не улучшаем (однако имеются аномальные примеры, когда алгоритм Кристофидеса дал отклонение от точного решения на 150% [5]). NP-трудность классической задачи VRP была доказана в 1981 г. Ленстрой и Каном (J.K. Lenstra, A.H.G. Rinnooy Kan) [6]. Поэтому в настоящее время утвердилось мнение, что для большинства разновидностей задачи VRP и общей задачи TSP не существует полиномиальной и, более того, полностью полиномиальной приближенной схемы решения (Polynomial and Fully Polynomial Time Approximation scheme, PTAS and FPTAS), если только P¹NP. Напомним, что PTAS определяет класс алгоритмов, которые для любого наперед заданного вещественного 0>e , позволяют находить e+1 константное приближенное решение за полиномиальное время от размера ~ 111 ~ Математичне моделювання в економіці, №3-4, 2016 входа любой индивидуальной задачи (экземпляра оптимизационной задачи) и e . Аппроксимационные алгоритмы PTAS могут быть экспоненциальными по e/1 . Алгоритмы класса FPTAS находят e+1 приближенное решение за полиномиальное время от размера входа любой индивидуальной задачи и от e/1 . В 1964 г. Кларком и Райтом (G. Clarke and J. W. Wright) впервые был предложен приближенный алгоритм для решения задачи VRP. В последующие годы началось интенсивное исследование методов и алгоритмов решения этой задачи и ее разновидностей [7]. Для задач с небольшим числом клиентов 135£n были разработаны точные алгоритмы, основанные на методах динамического программирования и ветвей и границ (1981, Christofides, Mingozzi, Toth); ветвей, отсечений и цен (branch-and-cut, branch-and-cut-and-price – 1985, Laporte, Nobert, Desrochers; 1994, Fisher, Ralphs et al., Augerat et al.; 2000, Blasum, Hochstättler; 2006, Fukasawa et al.; 2008, Baldacci, Christofides, Mingozzi); сетевых методах (2004, Baldacci, Hadjiconstantinou, Mingozzi). К классическим приближенным (эвристическим) алгоритмам можно отнести [8, 9]: конструктивные алгоритмы, которые постепенно наращивают решение без последующего этапа его улучшения; двухэтапные кластерные алгоритмы, сочетающие группировку клиентов в кластер для построения маршрута и решение задачи TSP для каждого кластера (существуют две разновидности – TSP решается для всего множества клиентов и затем строятся маршруты, и наоборот, когда сначала определяются кластеры, а затем маршруты); улучшающие алгоритмы, в которых находится начальное допустимое решение, а затем оно улучшается на множестве комбинаторных перестановок узлов и дуг для одного или нескольких проектируемых маршрутов. Среди этих алгоритмов наиболее известными являются: savings (1965, Clarke, Wright); sweep (1974, Gillett, Miller); cluster first, route second (1981, Fisher, Jaikumas); intra-route improvement methods based on TSP heuristics (interchanges – 1993, Osman; cyclic exchanges – 1993, Thompson, Psaraffis; edge exchange schemes – 1997, Kindervater, Savelsbergh; ejection chains –1996, 1998, Xu, Kelly, Rego, Roucairol; very large neighbourhood search – 2003, Ergun et al.; SERR – 2004, De Franceschi, Fischetti, Toth). С середины 1990-х годов и по настоящее время для решения различных задач VRP активно разрабатываются метаэвристические алгоритмы. В эти алгоритмы заложена способность преодоления локальных экстремумов для расширенного поиска наилучшего решения. Поэтому в отдельных случаях и для некоторых индивидуальных задач они могут оказаться эффективнее (по быстродействию и точности получаемого решения) по сравнению с классическими алгоритмами. Принято разделять метаэвристические алгоритмы на три основные группы [10, 11]: локального поиска (local search) – моделируемый отжиг (Simulated Annealing, SA), детерминированный отжиг (Deterministic Annealing, DA), поиск с запретами (Tabu Search, TS); эволюционные (population search), основанные на генерации популяций особей – процедуры с адаптивной (адаптивным управлением) памятью (adaptive memory procedures), генетические (genetic search, Genetic Algorithms, GA); самообучающиеся (learning mechanisms) – нейронные сети (neural networks), муравьиные ~ 112 ~ Математичне моделювання в економіці, №3-4, 2016 колонии (ant colony systems). К основным метаэвристикам относят также процедуру жадного адаптивного рандомизированного поиска (Greedy Randomized Adaptive Search Procedure, GRASP) и поиска (спуска) с чередующимися окрестностями (Variable Neighborhood Search (Descent), VNS, VND). Исследованием метаэвристических алгоритмов занимались очень многие зарубежные ученые, поэтому выделим только некоторых из них: поиск с запретами, моделируемый и детерминированный отжиг – Willard (1989), Gendreau, Hertz, Laporte (1991), Taillard, Osman (1993), Gendreau, Hertz, Laporte (1994), Cordeau, Laporte, Mercier (2001), Toth, Vigo (2003), Li, Golden, Wasil (2004); эволюционные алгоритмы – Rochat, Taillard (1995), Rego, Roucairol (1996), Tarantilis, Kiranoudis (2002), Prins, Mester and Bräysy (2004), Mester, Bräysy (2005); самообучающиеся алгоритмы – Reinmann, Doerner, Hartl (2004); комбинированные алгоритмы – Very large neighbourhood search (Ergun, Orlin, Steele-Feldman, Ergun et al., 2003, 2006), Attribute based hill climbing (Derigs, Kaiser, 2007), Genetic search + very large neighbourhood search (Mester, Bräysy, 2007), Guided very large neighbourhood search (Kytöjoki et al., 2007), Adaptive very large neighbourhood search (Pisinger, Ropke, 2007), Memetic algorithm (Nagata, 2007), Local search limitation strategies (Nagata, Bräysy, 2008), Memetic algorithm (Nagata, Bräysy, 2009), Greedy Randomized Adaptive Search Procedure (GRASP) + Evolutionary search (Prins, 2009). В странах СНГ исследованиями задач маршрутизации занимались И.И. Меламед, И.Х. Сигал, С.И. Сергеев, А.А. Лазарев, Е.М. Бронштейн, Э.Х. Гимади, Л.Ф. Гуляницкий, Д.И. Соломон, А.В. Панишев и др. Среди последних работ ближнего зарубежья, посвященных исследованию задач VRP, отметим диссертации М.С. Пожидаева, С.В. Чернышева, Р.В. Гиндуллина, А.К. Перцовского и А.В. Хмелева [12–16]. Различные варианты классификации задач VRP и более поздние обзоры по методам, алгоритмам и программам их решения можно найти в статьях [17-25], монографиях [26, 27] и на сайте http://neo.lcc.uma.es/vrp/bibliography-on-vrp/. В отличие от классической задачи VRP и ее разновидностей, задачи семейства FCRP изучались менее интенсивно. В этих задачах рассматриваются не только транспортные расходы, но и расходы, связанные с приобретением неоднородного (гетерогенного) рабочего парка транспортных средств, и они наиболее интересны для проектирования перевозок во внутренних зонах магистральных узлов. В зарубежной литературе принято разделять задачи с неоднородным парком в зависимости от ограниченности или неограниченности количества транспортных средств каждого типа, учета фиксированной стоимости транспортных средств и переменной стоимости транспортировки грузов, а также от того, зависят ли цены на транспортировку от типа транспортных средств. Согласно зарубежной классификации выделено пять основных классов задач FCRP: Heterogeneous VRP with Fixed Costs and Vehicle Dependent Routing Costs (HVRPFD) – ограниченный парк, фиксированная и переменная стоимость учитываются, цены зависят от типа транспортного средства; ~ 113 ~ Математичне моделювання в економіці, №3-4, 2016 Heterogeneous VRP with Vehicle Dependent Routing Costs (HVRPD) – ограниченный парк, учитывается только переменная стоимость, цены зависят от типа транспортного средства; Fleet Size and Mix VRP with Fixed Costs and Vehicle Dependent Routing Costs (FSMFD) – неограниченный парк, фиксированная и переменная стоимость учитываются, цены зависят от типа транспортного средства; Fleet Size and Mix VRP with Fixed Costs (FSMF) – неограниченный парк, фиксированная и переменная стоимость учитываются, цены не зависят от типа транспортного средства; Fleet Size and Mix VRP with Vehicle Dependent Routing Costs (FSMD) – неограниченный парк, учитывается только переменная стоимость, цены зависят от типа транспортного средства. Первыми исследованиями задач FCRP принято считать работы G.B. Dantzig, D.R. Fulkerson (1954) [28] и D. Kirby (1959) [29]. В 1984 г. вышла обзорная статья B.L. Golden, A. Assad и др. [30], где обсуждаются возможные модели и методы исследования операций, применимые к решению задач FCRP. В частности, в этой работе рассматривается задача с неограниченным парком транспортных средств, известная также как Fleet Size and Mix (FSM), в которой определяются оптимальные состав и схема маршрутизации транспортных средств. Для решения задачи авторами предложены два эвристических алгоритма, основанных на savings-алгоритме Кларка и Райта (G. Clarke и J. W. Wright) [31] и построении большого тура коммивояжера. Они также сформулировали математическую модель для задачи FSMF и представили некоторые нижние границы ее решения. Обзор ранних работ по задачам FCRP приведен S. Salhi и G.K. Rand в 1993 г. [32]. I.H. Osman и S. Salhi [33] исследовали и проанализировали работы до 1996 г., посвященные решению задач с помощью методов локального поиска. Y.H. Lee и др. (2008) [34] описывают несколько эвристических подходов к решению различных вариантов задач FCRP, основанных на методах поиска с запретами (tabu search) и разбиения множества (set partitioning). Более поздние обзоры по задачам формирования неоднородного парка транспортных средств приведены R. Baldacci и др. [35, 36] и A. Hoff и др. [37, 38]. В обзорах рассматриваются в основном работы, связанные с гетерогенным ограниченным и неограниченным размером парка транспортных средств с различным сочетанием учета фиксированной стоимости транспортных средств и переменной стоимости транспортировки грузов. При этом особое внимание уделяется методам получения нижних оценок решения задач и эвристическим алгоритмам. Методы получения нижних границ решения задачи были предложены Golden и др. (1984) [30], Yaman (2006) [39] и Choi и Tcha (2007) [40]. В работе [39] на основе методов отсечений предложена методика получения нижних границ для шести математических формулировок задачи FSMF. Для последних двух формулировок, в которых введены трехиндексные потоковые переменные для типов транспортных средств и заданной пары клиентов, получены наилучшие результаты. Для устранения подциклов, не проходящих через депо, использовались потоковые переменные, а для улучшения нижних границ вводились дополнительные ограничения в виде «правильных» отсекающих неравенств. В [40] для задачи, сформулированной на основе разбиения множества (set partitioning formulation), предложена методика ~ 114 ~ Математичне моделювання в економіці, №3-4, 2016 вычисления нижних границ решения с помощью метода генерации столбцов. В этом случае множеству генерируемых столбцов взаимно однозначно соответствует множество маршрутов, где каждый маршрут представлен циклом, включающим депо и некоторое подмножество клиентов с суммой заказов, не превышающей грузоподъемности транспортного средства, выделенного на маршрут. Используя такой подход, авторы разработали очень эффективный эвристический алгоритм, который комбинирует столбцы в оптимальном решении релаксированной задачи. В [41] для решения задач FCRP приведен робастный алгоритм ветвей, отсечений и цен (branch-cut-and- price algorithm), основанный на алгоритме Fukasawa и др. (2006) [42]. В сформулированной задаче используется метод генерации столбцов с новым семейством отсекающих неравенств, улучшающих оценки нижних границ решения. Отмечается, что алгоритм позволяет найти точное решение для многих тестовых задач, в которых число клиентов не превышает 75. Одни из последних работ R. Baldacci и др. [43–46] посвящены исследованию вопросов улучшения нижних границ, обзору точных методов и сравнению вычислительной эффективности алгоритмов решения задач VRP и FCRP. В [44] предложен один из лучших в настоящее время точный алгоритм, основанный на разбиении множеств и позволяющий находить оптимальные решения задач FCRP с числом клиентов до 100. В алгоритме используется три типа процедур лагранжевой и LP-релаксации исходной математической формулировки задачи, которые позволяют значительно сократить число переменных задачи и использовать для ее решения известные пакеты программ целочисленного линейного программирования. В статье приводятся результаты вычислений для тестовых экземпляров задач FCRP, которые показали новые лучшие нижние границы решения для отдельных индивидуальных задач, и что предложенный точный алгоритм впервые позволил решить несколько не решенных ранее тестовых примеров. Обзор метаэвристических алгоритмов для решения задач VRP и их разновидностей можно найти в работе Gendreau и др. «Metaheuristics for the Vehicle Routing Problem and Its Extensions: A Categorized Bibliography» в [26] (стр. 143–169). 4. Математические модели перевозок мелкопартионных грузов во внутренней зоне магистрального узла Пусть физическая сеть внутриузловых перевозок (см. рис. 1а) задана связным ориентированным графом )~,~(~ PNG . Множество вершин }~,...,1{},...,1{}0{~ nnnN +ÈÈ= , перенумерованное от 0 до n~ , включает вершину }0{ – депо и магистральный узел, },...,1{ n – множество клиентов и }~,...,1{ nn + – множество транзитных пунктов, связывающих отдельные участки дорог. Транзитные пункты вводятся для того, чтобы учесть особенности отдельных участков дорог, соединяющих узлы во внутренней зоне магистрального узла. Участки дорог представлены противоположно направленными ориентированными дугами ),( ji , ),( ij , Nji ~, Î , ji ¹ , одна из которых может отсутствовать (например, из-за одностороннего движения по участку дороги или запрета проезда грузовым видам транспорта). Длины ~ 115 ~ Математичне моделювання в економіці, №3-4, 2016 дуг заданы матрицей 1~1~ ~~ +´+ = nnijrR , 1~ Rrij Î , Pji ~),( Î . Пусть для дуг сети известны коэффициенты 1~ Rkij Î , 0.1~ ³ijk , характеризующие географические особенности (подъем, спуск и пр.) и физическое состояние (качество покрытия) участков дорог. Определим элементы преобразованной матрицы '~R как ijijij rkr ~~'~ = , Pji ~),( Î и построим на ней все кратчайшие пути в )~,~(~ PNG . В результате получим матрицу длин кратчайших путей 1~1~ ~~ +´+ = nnijlL и справочную матрицу 1~1~ ~~ +´+ = nnijcC , каждый элемент которой ijc~ , ji ¹ определяет номер предпоследнего узла на кратчайшем пути от i до j ‚ 0~ =iic , 1~,1 += ni . С помощью справочной матрицы можно легко определить кратчайший путь между любыми вершинами исходного графа. По матрице L~ для множества },...,1{}0{ nÈ построим полный ориентированный граф ),( ANG с множеством вершин },...,1,0{ nN = и множеством дуг },,:),{( jiNjijiA ¹Î"= с известными длинами ijl , Aji Î),( . Очевидно, что для дуг построенного графа выполняется правило треугольника ijkjik lll ³+ . В дальнейшем все задачи будем формулировать на графе ),( ANG . Пусть для каждого клиента j , nj ,1= задано среднесуточное количество 0>ja и 0>jb , +Î Zba jj , единиц мелкопартионных грузов унифицированного размера, которое нужно в течение суток доставить клиенту из магистрального узла (депо) и отправить от клиента в магистральный узел ( 000 == ba ). Принимается, что на протяжении некоторого периода текущего планирования длительностью T суток среднесуточные потоки изменяются незначительно и за T суток может быть перевезено )( 1å = + n j jj baT грузов. В депо имеется K типов транспортных средств с различной грузоподъемностью +Î ZQk , Kk ,1= . Грузоподъемность измеряется в тех же единицах, что и потоки мелкопартионных грузов. Предполагается, что Kjjj Qba £},{max , а количество транспортных средств каждого типа может быть ограничено величиной km , Kk ,1= и не ограничено. Для каждого типа транспортного средства известна стоимость его приобретения и среднестатистическая стоимость обслуживания в сутки. В стоимость обслуживания включаются расходы на смазочные и прочие эксплуатационные материалы, ремонт и амортизацию подвижного состава, износ и ремонт автомобильной резины, заработная плата водителей вместе с отчислениями на социальные нужды. Пусть для расчета этих затрат задана функция ),( kkV RSfF = , Kk ,1= , где kS – фиксированная стоимость ~ 116 ~ Математичне моделювання в економіці, №3-4, 2016 приобретения транспортного средства типа k , а kR – расходы на обслуживание одного транспортного средства типа k в сутки. После сортировки в магистральном узле грузы для каждого клиента могут перевозиться в транспортных средствах на поддонах, для погрузки и выгрузки которых необходимо использовать механизированные автопогрузчики. Грузы от клиентов в магистральный узел перевозятся «навалом». При большом объеме перевозимых грузов затраты на операции погрузки и выгрузки могут быть значительными и их необходимо учитывать при решении задачи. Для депо и клиентов задана функция затрат на погрузку- выгрузку ju грузов ),( jkL uQfF = , nj ,0= , Kk ,1= . На практике принято считать, что эта функция не зависит от типа транспортного средства, а зависит только от объема груза и наличия погрузочно-разгрузочного оборудования в депо и у клиентов. В депо затраты на погрузку и выгрузку несет транспортное предприятие, клиенты могут выполнять эти операции за свой счет. В дальнейшем предполагается, что места дислокации клиентов являются доставочными и сборочными пунктами транспортного предприятия, поэтому затраты на погрузку и выгрузку грузов у клиентов также относятся к общим затратам предприятия. Как правило, такие затраты моделируются непрерывной вогнутой функцией )( jL ufF = , nj ,0= от объема грузов. В отдельных случаях может быть принята линейная зависимость jLL ucF = , где Lc – стоимость погрузки-выгрузки единицы мелкопартионных грузов. Ясно, что если затраты на погрузку и выгрузку грузов не зависят от типа транспортного средства, то они не должны фигурировать в целевой функции задачи и могут быть вычислены независимо от переменных следующим образом: åå == +++= n i ii n i iifull bafbafF 11 )())(( или )(2 1å = += n i iiLfull bacF . Если же такая зависимость существует, то эти затраты должны быть связаны с неизвестными переменными задачи. Пусть стоимость проезда транспортного средства типа k по дуге Aji Î),( задана функцией ),,,( L k avkijM kVQlfF = , где ijl – длина дуги в километрах, k avV – средняя скорость движения (км/час), Lk – коэффициент загрузки транспортного средства на дуге. Значение ]1,0[/ Î= kijL Quk , где iju – текущая загрузка транспортного средства. По существу функция MF определяет стоимость израсходованного топлива на передвижение по дуге ),( ji для каждого транспортного средства типа k . Во многих задачах маршрутизации принимается ijkM lcF = , где kc – удельная стоимость топлива транспортного средства типа k на один километр пути. Часто рассматривается случай, когда затраты на передвижение по дуге не зависят от типа транспортного средства и одинаковы для прямого и обратного направления движения. В этом случае вводятся дополнительные условия для грузоподъемности KQQQ << ...21 и фиксированной стоимости KFFF << ...21 . ~ 117 ~ Математичне моделювання в економіці, №3-4, 2016 Все функции затрат должны быть приведены к сопоставимому виду, например, за одни сутки или за заданный период времени текущего планирования T . Если построенные функции затрат VF , LF и MF реально отражают производственные издержки, то их сумма будет достаточна близка к фактическим расходам транспортного предприятия на приобретение и эксплуатацию рабочего парка транспортных средств без учета накладных расходов. Примем, что при решении задачи эти функции рассчитываются и их соответствующие числовые значения kF , k jf и k ijf , nji ,0, = , Kk ,1= используются в целевой функции. 4.1. Формулировка задачи построения доставочных маршрутов (the Delivery Route, DR) для перевозки грузов из магистрального узла к клиентам. Однопродуктовая модель 1 Формулировка задачи основана на моделях, предложенных Gheysens и др. [47], Golden и др. [30], Baldacci и др. [35] и Salhi и Rand [32]. Задача заключается в определении множества непересекающихся по вершинам клиентов гамильтоновых циклических маршрутов, начинающихся и заканчивающихся в депо, с минимальными суммарными затратами. При этом требуется, чтобы все запросы клиентов были удовлетворены, а грузоподъемность транспортных средств на всех маршрутах не нарушалась. Обозначим },...,1{ nC = – множество клиентов, },...,1{ KV = – множество типов транспортных средств. Введем потоковые переменные ijy , определяющие количество грузов в транспортном средстве при его проезде к клиенту j после посещения клиента i , Nji Î, и булевы переменные k ijx , 1=k ijx , если транспортное средство типа k движется от клиента i к клиенту j и 0=k ijx в противном случае. Пусть å = n j k jx 1 0 представляет собой суммарное количество используемых транспортных средств типа k . Требуется найти минимум функции k ij Vk Nji k ij Vk Nj Ci k jijiij k j Vk Cj k jkDR xfxyyfxFF å ååå åå å Î ÎÎ Î ÎÎ Î +-+= , 0 ))(( , (1) при ограничениях 1=åå Î ÎVk Ni k ijx , CjÎ" , (2) 0=-åå ÎÎ Ni k ji Ni k ij xx , CjÎ" , VkÎ" , (3) åå ÎÎ = Cj j Cj j ay0 , 00 =å ÎCj jy , (4) j Ni ji Ni ij ayy =-åå ÎÎ , CjÎ" , (5) ~ 118 ~ Математичне моделювання в економіці, №3-4, 2016 å Î £ Vk k jkj xQy 00 , CjÎ" , (6) å Î -£ Vk k ijikij xaQy )( , CiÎ" , NjÎ" , ji ¹ , (7) }1,0{Îk ijx , 0³ijy и целые, Nji Î" , , VkÎ" . (8) Ограничения (7) можно записать в расширенном виде k ijikij k ijj xaQyxa )( -££ , CiÎ" , NjÎ" , ji ¹ , VkÎ" . (9) Если количество транспортных средств типа k ограничено величиной km , то к задаче могут быть добавлены условия k Cj k j mx £å Î 0 , VkÎ" . (10) При необходимости могут быть установлены ограничения на максимальную продолжительность маршрутов по времени. Для этого включим в модель временные параметры kT – максимальное время поездки транспортного средства типа k и ijt – время проезда по дуге ),( ji , а также непрерывные переменные ijr , определяющие разность между значением kT и текущим значением времени движения после проезда по дуге ),( ji . Тогда к задаче добавятся ограничения å Î £ Vk k ijkij xTr , Aji Î" ),( , (11) åå ÎÎ -= Vk k jj Vk k jkj xtxTr 0000 , CjÎ" , (12) åååå Î ÎÎÎ =- Vk Nj k pjpj Nj pj Ni ip xtrr , CpÎ" , (13) 0³ijr , Aji Î" ),( . (14) Первая часть целевой функции (1) определяет фиксированные затраты на приобретение и обслуживание используемых транспортных средств, а вторая и третья – затраты на погрузку-выгрузку и доставку всех грузов. Ограничения (2) и (3) гарантируют, что каждый клиент j посещается только один раз каким-либо транспортным средством типа k , и это транспортное средство после прибытия к клиенту и выгрузки его груза ja должно обязательно покинуть клиента. Ограничения (4) означают, что общее количество грузов на выходе из депо равно суммарным требованиям всех клиентов, и что никакие грузы не возвращаются в депо. Ограничения (5) означают, что при посещении клиента j груз ja должен быть выгружен, т. е. количество груза в транспортном средстве после посещения клиента j ~ 119 ~ Математичне моделювання в економіці, №3-4, 2016 уменьшается на величину ja . Эти ограничения обеспечивают выполнение требований всех клиентов и исключают циклы, не проходящие через депо. Ограничения (6) определяют, что количество грузов jy0 , транспортируемых до клиента j , не должно превышать грузоподъемности транспортного средства, назначенного для доставки груза этому клиенту. Ограничения (7) или (9) связывают переменные ijy и k ijx и означают, что никакие грузы не перевозятся из i в j , если ни одно транспортное средство не обслуживает связь между этими узлами, т. е. если 0=k ijx VkÎ" . Ограничения (8) устанавливают область изменения переменных. Ограничения (11) означают, что оставшееся время движения транспортного средства после проезда по дуге ),( ji не может превышать максимального времени движения транспортного средства. Условия (12) обеспечивают то, чтобы оставшееся время движения транспортного средства после выезда из депо было равно разности между максимальным временем движения и временем, необходимым для перемещения к клиенту j . Ограничения (13) указывают на тот факт, что каждый раз, когда транспортное средство проезжает между двумя клиентами, оставшееся время движения уменьшается на время проезда между этими клиентами. Для формулировки задачи (1)–(8) с ограничениями на временные окна, депо представим двумя узлами с номерами 0 и 1+n . Тогда }1{},...,1{}0{ +ÈÈ= nnN . Пусть ],[ C i S i tt и is соответственно определяют промежуток времени (временное окно), на протяжении которого возможно обслуживание, и время обслуживания клиента i , 1,, Rstt i C i S i Î . Введем переменные 1Rt k i Î , означающие точное время начала обслуживания транспортного средства типа k у клиента i . Принимается, что если транспортное средство прибывает к клиенту i ранее S it , то оно ожидает начала обслуживания. В задачу (1)-(8) добавятся – в целевую функцию слагаемое å Î + - Vk kk n tt )( 01 , и ограничения: 10 =å ÎNj k jx , 11, =å Î + Ni k nix , VkÎ" ; )1( k ijijiji k i k j xMtstt --++³ , Nji Î" , , VkÎ" , где },0max{ S jiji C iij ttstM -++= ; k i Nj k ij S i txt £å Î , å Î £ Nj k ij C i k i xtt , NiÎ" , VkÎ" ; 00 = k ix , 0=k iix , 0,1 =+ k inx , NiÎ" , VkÎ" . В записи первых ограничений предполагается, что если транспортное средство не используется, то оно совершает пустой тур, т. е. 11,0 =+ k nx , VkÎ" . ~ 120 ~ Математичне моделювання в економіці, №3-4, 2016 Кроме того, 01010 ==== ++ nn ssaa , ],[],[],[ 1100 CloseStarttttt C n S n CS == ++ , где Start и Close – время выезда и приезда в депо. Задача с временными окнами является задачей смешанного целочисленного программирования. 4.2. Формулировка задачи построения доставочных маршрутов для перевозки грузов из магистрального узла к клиентам. Однопродуктовая модель 2 Введем вместо переменных ijy булевы переменные 1=iky , если транспортное средство типа k посещает клиента или депо i , и 0=iky в противном случае. Для исключения подциклов при построении маршрутов введем целочисленные переменные 0³iku , значения которых определяют порядковый номер клиента i в маршруте транспортного средства типа k . Впервые вариант исключения подциклов был предложен в 1960 г. в работе [48]. Сформулируем задачу. Требуется найти минимум функции k ij Vk Nji k ij Vk Ci iki k ik Vk Ci i k Vk Cj k jkDR xfyafyafxFF å åååå åå å Î ÎÎ ÎÎ ÎÎ Î +++= , 000 )()( , (15) при ограничениях 1=å ÎVk iky , CiÎ" , (16) ik Nj k ij yx =å Î , ik Nj k ji yx =å Î , NiÎ" , ji ¹ , VkÎ" , (17) å Î £ Ci kiki Qya , VkÎ" , (18) 1-£+- nnxuu k ijjkik , Cji Î" , , VkÎ" , (19) }1,0{, Îik k ij yx , Nji Î" , , VkÎ" , (20) 0³iju и целые, Cji Î" , . (21) Отметим, что условия запрета подциклов можно записать в виде 1 }{\ -£å å Î Î Sx Si iSj k ij , CS Í" , 2³S , VkÎ" , (22) где S – кластер (подмножество клиентов), обслуживаемый одним транспортным средством типа k . Ограничения (16) и (17) гарантируют, что каждый клиент посещается только одним транспортным средством, и что транспортное средство после посещения клиента или депо должно его покинуть. Условия (18) и (19) или (22) устанавливают ограничения на загрузку транспортных средств и запрещают подциклы, не проходящие через депо. В задачу также можно ~ 121 ~ Математичне моделювання в економіці, №3-4, 2016 ввести дополнительные условия, ограничивающие количество транспортных средств каждого типа и временные ограничения на маршруты. 4.3. Формулировка задачи построения доставочных маршрутов для перевозки грузов из магистрального узла к клиентам. Двухпродуктовая модель Рассмотрим двухпродуктовую формулировку задачи, предложенную в [43], для случая, когда jiij k ji k ij ffff === 21 Nji Î" , , Vkk ι 21 , i k i ff = NiÎ" , VkÎ" . В модель не включаются затраты на погрузку-выгрузку, поскольку предполагается, что они не зависят от типа транспортного средства и могут быть вычислены по формуле для fullF . Пусть ),'( ENG – полный неориентированный граф, полученный из графа ),( ANG следующим образом. Множество узлов 'N включает множество узлов клиентов, K копий узла депо, ассоциированных с K типами транспортных средств, и один общий узел депо. Пусть узлы 'N занумерованы и }1{},...,1{},...,1{' ++È++È= KnKnnnN . Обозначим, как и ранее, },...,1{ nC = , },...,1{ KnnV ++= , 1' ++= Knn . Пусть )(ip , ViÎ означает транспортное средство, связанное с узлом i . Определим стоимости дуг Ecij Î следующим образом: ijij fFc 0)( += p , для )( ji Qa p£ , VjÎ , CiÎ ; ijij fc = , для Kji Qaa £+ , Cji Î, , ji < ; iin fc 0' = , для CiÎ ; +¥=ijc в противном случае. Предполагается, что 0=ia , }'{nVi ÈÎ" . В модели используются две потоковые переменные ijy и jiy , связанные с каждой дугой Eji Î),( . Переменная ijy определяет загрузку транспортного средства, а переменная ijKji yQy -= представляет свободную емкость транспортного средства с наибольшей грузоподъемностью. Значение )( kKji QQy -- означает свободную емкость транспортного средства типа k . Пусть для каждой дуги Eji Î),( определены булевы переменные 1=ijx , если дуга ),( ji включена в решение и 0=ijx в противном случае. Определим }2,:{ ³Í=W SCSS и пусть для подмножества (кластера) WÎS , SCS \= , а }:),{()( SjSiSjSiEjiS ÎÙÏÚÏÙÎÎ=d . Обозначим å Î = Si iaSa )( – суммарный поток требований клиентов в кластере S . Сформулируем задачу. Требуется найти минимум функции ij Eji ij xcå Î),( , (23) при ограничениях ~ 122 ~ Математичне моделювання в економіці, №3-4, 2016 å Î =- ' 2)( Nj iijji ayy , CiÎ" , (24) )(Cay Vi Cj ijåå Î Î = , 0' =å ÎCj jny , (25) å Î = )(},{ 2 pji ijx d , CpÎ" , (26) åå å Î Î Î = Vi Cj Cj jnij xx ' , (27) ijKjiij xQyy =+ , Eji Î" ),( , (28) å åå Î Î Î ³ )(},{ Sji Vi Cj ijij xx d , CVS ÈÍ , SV Ì , (29) )( iij Qy p£ , ViÎ" , CjÎ" , (30) 0, ³jiij yy и целые, }1,0{Îijx Eji Î" ),( . (31) Ограничения (24), (25) и (31) определяют допустимый поток. Ограничения (26) гарантируют, что в любом допустимом решении у каждого клиента будут только две инцидентных ему дуги. Условия (27) означают, что если åå Î Î = Vi Cj ijxq транспортных средств выехало из множества узлов V , то все они обязательно должны приехать в общее депо. Ограничения (28) устанавливают связь между переменными в допустимом решении задачи, а условия (29) запрещают образование простых путей, начинающихся и заканчивающихся в узлах множества V . Ограничения на грузоподъемность для различных типов транспортных средств заданы условиями (30). В [43] доказана теорема о том, что множество допустимых решений задачи (24)-(31) однозначно соответствует множеству решений задачи FSMF (задачи с независимыми ценами дуг от типа транспортного средства). 4.4. Формулировка задачи построения доставочных маршрутов для перевозки грузов из магистрального узла к клиентам. Модели на разбиении множества Рассмотрим постановки задач HVRP, предложенные в [44] и [32], основанные на ранней работе M. Balinski и R. Quandt [49]. Определим маршрут транспортного средства как пару ),( kR , где ),...,,( 21 RiiiR = , 01 == Rii , Ciii R Í- },...,,{ 132 , 1},...,,{ 132 ³-Riii представляет простой цикл, начинающийся и заканчивающийся в депо, а k – определяет тип транспортного средства, связанного с R . Ссылка на маршрут R используется для обозначения как последовательности посещаемых клиентов, так и для подмножества этих клиентов, включая депо. Маршрут ),( kR является допустимым, если суммарный запрос клиентов, посещаемых на этом маршруте, не превышает грузоподъемности транспортного средства kQ , выделенного для этого маршрута, k R h i Qa hå - = £ 1 2 . Затраты на маршруте ~ 123 ~ Математичне моделювання в економіці, №3-4, 2016 ),( kR включают kF (суммарные затраты на приобретение и обслуживание транспортного средства типа k ) и сумму затрат на дугах маршрута å - = + 1 1 1 R h k ii hh f . Пусть kR представляет множество всех возможных допустимых маршрутов для транспортного средства типа VkÎ . Для каждого маршрута kRl Î обозначим lkf – ассоциируемые маршрутные затраты (сумму затрат на дугах маршрута), k lf – затраты на выгрузку грузов клиентам на маршруте. Пусть kik RR Ì – подмножество маршрутов транспортного средства типа k , покрывающих (охватывающих) клиентов CiÎ , а lkr определяет подмножество клиентов, посещаемых на маршруте l , },...,,{ 21 hlk iiir = , Ciii h Í},...,,{ 21 . Определим å Î = lkri ilk aa , kRl Î" , VkÎ" . Введем булевы переменные 1=lkx , если и только если маршрут kRl Î включен в оптимальное решение и 0=lkx в противном случае. Требуется найти минимум åååå Î ÎÎ Î ++ Vk Rl lklk k llk Vk Rl lkk kk xafxfF )(2)( , (32) при ограничениях åå Î Î = Vk Rl lk ik x 1, CiÎ" , (33) k Rl lk mx k £å Î , VkÎ" , (34) }1,0{Îlkx , kRl Î" , VkÎ" . (35) Вторая составляющая целевой функции умножается на два, так как все выгружаемые грузы из транспортных средств типа k на маршруте l , предназначенные клиентам i , загружаются в эти же транспортные средства в депо, а затраты на погрузку и выгрузку единицы груза предполагаются одинаковыми для транспортных средств одинакового типа. Ограничения (33) гарантируют, что каждый клиент может быть обслужен только одним транспортным средством, а условия (34) ограничивают количество используемых транспортных средств каждого типа (эти условия могут отсутствовать при неограниченном рабочем парке). Приведем несколько измененную формулировку [32], в которой учитываются время обслуживания клиента и ограничения на общее время движения транспортного средства. Определим множество },...,2,1{~ KV = всех типов транспортных средств (количество транспортных средств каждого типа не ограничено), занумерованных индексом Kk ,1= . Пусть kF , kQ и ~ 124 ~ Математичне моделювання в економіці, №3-4, 2016 kT соответственно означают затраты на приобретение и обслуживание, грузоподъемность и максимальное время движения транспортного средства типа Vk ~ Î . Введем переменную решения задачи v , указывающую общее количество транспортных средств, включенных в состав рабочего парка },...,2,1{ vV = , VV ~Í . Введем переменные затраты ka и временной фактор kb в расчете на единицу расстояния для каждого типа транспортного средства Vk ~ Î . Пусть it – время обслуживания клиента CiÎ , pR – множество клиентов, обслуживаемых транспортным средством с номером VpÎ , а s – функция VV ~: ®s , однозначно отображающая множество номеров из V на множество типов транспортных средств V~ , и )( ps указывает на тип транспортного средства с наименьшей грузоподъемностью )( pQs , которое может обслужить клиентов из pR . Пусть pp является кратчайшим маршрутом коммивояжера (TSP-маршрутом) с отправной и конечной точкой в депо, который обслуживает клиентов из pR , а )(ipp указывает положение (позицию) клиента i в pp . Введем для маршрута pp обозначения: )( pD p – общее расстояние, )( pT p – общее время в пути, )( pC p – сумма переменной и фиксированной стоимости. Обозначим через ijl расстояние между клиентами i и j . Пусть S является допустимым решением и определяется как },...,{ 1 vRRS = , а P представляет множество всех маршрутов коммивояжера в S , },...,{ 1 vpp=P . Сформулируем следующую задачу оптимизации: å ÎP = Vp p vS CSC )()(min ,, p , (36) при ограничениях CR Vp p = Î U , Æ=Ç qp RR , Vqp ι" , (37) å Î £ pRi pi Qa )(s , VpÎ" , (38) å ÈÎ = }0{ )()( p p Ri iip lD pp , VpÎ" , (39) å Î £+= pRi pippp TtDT )()( )()( ss pbp , VpÎ" , (40) )()()()( )( )()( 0)( pp Ri Ri i p ii p pp DafafFC p p pap s ss s å å Î Î +++= , VpÎ" . (41) ~ 125 ~ Математичне моделювання в економіці, №3-4, 2016 Вместо слагаемого )()( pp D pas можно использовать å ÈÎ }0{ )( )( )( p p p Ri ii p iif p s p , а вместо )()( pp D pbs – )(/)( ppD sqp , где )( psq – средняя скорость движения транспортного средства типа )( ps . Целевая функция (36) определяет общую сумму затрат на всех маршрутах. Ограничения (37) и (38) означают, что каждый клиент обслуживается только одним маршрутом транспортного средства и что суммарный объем требований клиентов, обслуживаемых каждым маршрутом, не может превышать грузоподъемности выделенного транспортного средства. Уравнения (39) и (41) определяют соответственно общую длину и затраты для каждого маршрута. Ограничения (40) означают, что время проезда по каждому маршруту не должно превышать заданной максимальной величины. Как уже отмечалось, в настоящее время известны три точных алгоритма для решения задач с неоднородным парком транспортных средств. Choi и Tcha (2007) [40] для линейной релаксации исходной задачи разработали алгоритм на основе метода генерации столбцов. Они модифицировали несколько алгоритмов динамического программирования для решения классической задачи VRP с целью эффективной генерации допустимых столбцов, а затем применили процедуру ветвей и границ для получения целочисленного решения. Результаты численного экспериментирования с разработанными алгоритмами показали их превосходство по сравнению с существующими алгоритмами по качеству получаемых решений и по времени вычислений. Baldacci и Mingozzi [44] (2009) предложили универсальный точный алгоритм, использующий метод разбиения множества (set partitioning) для решения всех задач из семейства FCRPF. Ими были использованы три типа процедур, основанные на LP и лагранжевой релаксации исходной задачи, и получены новые, более точные, нижние границы решения задач. Третий точный алгоритм предложен Baldacci, Bartolini, Mingozzi и Roberti [45] (2010). Он сочетает в себе несколько итеративных двойственных процедур для генерации близко оптимальных двойственных нецелочисленных решений для множества разбиений (кластерных решений) и добавляет в координирующую задачу эффективные отсекающие неравенства для сокращения перебора в алгоритме генерации столбцов и получения целочисленного решения. Для окончательного двойственного решения определяется допустимая область, содержащая только целочисленные решения. Как утверждается в [45], этот алгоритм эффективнее всех других известных точных алгоритмов. 4.5. Формулировка задачи построения сборочных маршрутов (the Collection Route, CR) для перевозки грузов от клиентов в магистральный узел Сформулируем задачу аналогично (1)-(8). Пусть для каждого клиента j , nj ,1= задано среднесуточное количество 0>jb , +ÎZb j единиц мелкопартионных грузов унифицированного размера, которое нужно в течение суток отправить от клиента в магистральный узел (депо). Введем ~ 126 ~ Математичне моделювання в економіці, №3-4, 2016 потоковые переменные jiz , определяющие количество грузов в транспортном средстве при его проезде к клиенту i после посещения клиента j , Nji Î, , и булевы переменные k ijx , 1=k ijx , если транспортное средство типа k движется от клиента i к клиенту j и 0=k ijx в противном случае. Пусть å = n j k jx 1 0 представляет собой суммарное количество используемых транспортных средств типа k . Требуется найти минимум функции k ij Vk Nji k ij Vk Nj Ci k ijijji k j Vk Cj k jkCR xfxzzfxFF å ååå åå å Î ÎÎ Î ÎÎ Î +-+= , 0 ))(( , (42) при ограничениях 1=åå Î ÎVk Ni k ijx , CjÎ" , (43) 0=-åå ÎÎ Ni k ji Ni k ij xx , CjÎ" , VkÎ" , (44) 00 =å ÎCj jz , åå ÎÎ = Cj j Cj j bz 0 , (45) j Ni ij Ni ji bzz =-åå ÎÎ , CjÎ" , (46) å Î £ Vk k jkj xQz 00 , CjÎ" , (47) å Î -£ Vk k ijjkij xbQz )( , CiÎ" , NjÎ" , ji ¹ , (48) }1,0{Îk ijx , 0³ijz и целые, Nji Î" , , VkÎ" . (49) Ограничения (48) можно записать в виде k ijjkij k iji xbQzxb )( -££ , CiÎ" , NjÎ" , ji ¹ , VkÎ" . Так же как и в задаче (1)–(8), в постановку задачи (42)–(49) могут быть введены ограничения на используемое количество транспортных средств каждого типа, на максимальную продолжительность маршрутов по времени и временные окна. Первая часть целевой функции (42) определяет фиксированные затраты на приобретение и обслуживание используемых транспортных средств, вторая – затраты на погрузку грузов у клиентов и их выгрузку в депо, и третья – переменные затраты на доставку всех грузов в депо. Ограничения (43) и (44) гарантируют, что каждый клиент j посещается только один раз каким-либо транспортным средством типа k , и это транспортное средство после прибытия к клиенту и погрузки его груза jb должно обязательно покинуть клиента. Ограничения (45) означают, что общее количество грузов на выходе из депо равно нулю, а на входе в депо равно ~ 127 ~ Математичне моделювання в економіці, №3-4, 2016 суммарным требованиям всех клиентов. Ограничения (46) означают, что при посещении клиента j груз jb должен быть погружен, т. е. количество груза в транспортном средстве после посещения клиента j увеличивается на величину jb . Эти ограничения обеспечивают выполнение требований всех клиентов и исключают циклы, не проходящие через депо. Ограничения (47) гарантируют, что грузоподъемность транспортных средств не будет превышена. Ограничения (48) связывают переменные ijz и k ijx и означают, что никакие грузы не перевозятся из i в j , если ни одно транспортное средство не обслуживает связь между этими узлами, т. е. если 0=k ijx Vk Î" . Ограничения (49) устанавливают область изменения переменных. Отметим, что для сборочных маршрутов могут быть сформулированы и математические модели, аналогичные приведенным в подразделах 4.2–4.4. Выводы 1. Для эффективного управления процессами обработки и транспортировки мелкопартионных грузов во внутренних зонах магистральных узлов государственные и частные транспортные предприятия должны оптимизировать долгосрочные, тактические и оперативные решения, используя современные методы исследования операций, комбинаторной оптимизации и автоматизированные информационно-аналитические системы поддержки принятия решений. Уменьшение приведенных эксплуатационных затрат за счет оптимизации решений позволяет снижать тарифы на перевозку грузов, поддерживать здравую конкуренцию среди перевозчиков и постоянно повышать качество обслуживания хозяйственных предприятий и населения. 2. При определении структуры внутриузловой сети перевозок и ее математической модели должны учитываться реальные географические особенности и характеристики участков дорог транспортной сети и трудно- формализуемые внешние факторы. Модель физической структуры сети должна формироваться при участии опытных экспертов и диспетчеров транспортных перевозок для каждого магистрального узла. 3. Предложены основные принципы и схемы организации перевозок во внутренних зонах магистральных узлов и определены технические и экономические особенности реальных транспортных процессов обработки и транспортировки мелкопартионных грузов, которые должны быть учтены при формировании математических моделей задач маршрутизации на уровнях долгосрочного и текущего планирования и оперативного управления. 4. В большинстве известных работ, посвященных решению задач маршрутизации на транспорте, рассматриваются идеализированные математические модели, в которых не учитываются многие ограничения, присущие реальным процессам обработки и транспортировки грузов. Часто принимается евклидово расстояние между узлами сети перевозок, когда выполняется правило треугольника, а такие важные параметры, как расстояние, время поездки, транспортные расходы, время обслуживания и другие, присутствуют в некотором абстрактном виде и моделируются ~ 128 ~ Математичне моделювання в економіці, №3-4, 2016 константами. В постановках задач внутриузловых перевозок должны присутствовать все ограничения и параметры, которые позволят рассчитать близкие к фактическим технические и экономические показатели функционирования сети перевозок во внутренних зонах магистральных узлов. 5. Для решения задач построения маршрутов с неоднородным парком транспортных средств наиболее часто применяются классические эвристические и метаэвристические алгоритмы, что объясняется, с одной стороны, NP-трудностью решаемых задач, а с другой – относительно низкой трудоемкостью разработки таких алгоритмов. Однако следует учитывать, что большинство эвристических алгоритмов на разных экземплярах индивидуальных задач оптимизации могут дать решения, сколь угодно отличающиеся от глобального оптимума. Поэтому для решения задач большой размерности (более 100 клиентов) предпочтительнее использовать гибридные алгоритмы, в которых сочетаются в различных комбинациях точные (ветвей и границ, ветвей и отсечений, ветвей отсечений и цен, генерации столбцов, разбиения множества, динамического программирования) и многочисленные эвристические и метаэвристические методы и подходы. Сегодня можно утверждать, что разработка гибридных алгоритмов для решения NP-трудных кластерных задач маршрутизации стала общепризнанной в мировой практике [26, 27]. В последние годы наблюдается также тенденция к построению унифицированных алгоритмов и портала- сервера, способных решать большой класс задач маршрутизации с возможностью учета многих реальных ограничений и параметров [50]. 6. На основании проведенного обзора и анализа известных математических моделей разработано несколько вариантов математических постановок задачи построения доставочных и сборочных маршрутов транспортных средств для перевозки мелкопартионных грузов. Для решения поставленных задач могут быть применены точные, эвристические и метаэвристические методы и алгоритмы, реализованные в многочисленных коммерческих, например, IBM ILOG CPLEX, GAMS, AIMMS, Gurobi Optimizer [51] и некоммерческих, например, ABACUS, COIN-OR, GLPK, lp_solve [52] пакетах программ смешанного и целочисленного линейного программирования. Многие из них бесплатно доступны на сервере NEOS (https://neos-server.org/neos/). Учитывая иерархическую структуру магистральной сети перевозок и, как следствие, небольшое количество узлов во внутренних зонах магистральных узлов, предпочтение следует отдать точным и гибридным методам и алгоритмам. В частности, с успехом могут использоваться алгоритмы, предложенные R. Baldacci и др. [43-46], которые в настоящее время принято считать одними из лучших точных универсальных алгоритмов, способных находить оптимальные решения многих задач маршрутизации с числом клиентов до 100. 7. К перспективным направлениям решения задач маршрутизации следует отнести разработку стохастических моделей и алгоритмов для долгосрочного планирования, учитывающих риски вложения инвестиций в развитие парка транспортных средств, динамических моделей текущего планирования и оперативного управления для определения границ экономической эффективности уже полученных решений на заданные промежутки времени при колебании потоков грузов и изменении параметров транспортной модели. Оперативная информация в этом случае может поступать в АИАС от ~ 129 ~ Математичне моделювання в економіці, №3-4, 2016 GPS с бортов транспортных средств, системы электронных заказов по Интернет и устройств мобильной связи (сотовых телефонов, планшетов, смартфонов и т. п.). Большой интерес представляет также создание единой общенациональной базы данных в стандартизированном формате на основе одного структурированного языка (например, XML) с трудными тестовыми примерами для различных классов типовых задач маршрутизации. СПИСОК ЛИТЕРАТУРЫ 1. Васянин В.А., Трофимчук А.Н. Задача выбора иерархической структуры многопродуктовой коммуникационной сети с мелкопартионными дискретными потоками // Екологічна безпека та природокористування: Зб. наук. праць. — Київ, 2012. — Вип. 10. — С. 182-204. 2. Васянин В.А., Трофимчук А.Н. Автоматизация процессов принятия решений в многопродуктовых коммуникационных сетях с мелкопартионными дискретными потоками // Екологічна безпека та природокористування: Зб. наук. праць. — Київ, 2010. — Вип. 5. — С. 172-213. 3. Sahni S., Gonzalez T. P-complete approximation problems // J. Assoc. Comput. Mach. — 1976. — No. 23. — P. 555–565. 4. Christofides N. Worst-case analysis of a new heuristic for the travelling salesman problem // Research Report 388, Graduate School of Industrial Administration, Carnegie- Mellon University, Pittsburg, PA, 1976. — 5 p. 5. Cornuéjols G., Nemhauser G.L. Tight bounds for Christofides’ traveling salesman heuristic // Math Program. —1978. — No. 14. — P. 116-121. 6. Lenstra J.K., Rinnooy Kan A.H.G. Complexity of vehicle routing and scheduling problems // Networks. —1981. — No. 11. — P. 221-227. 7. Laporte G. Fifty Years of Vehicle Routing // Canada Research Chair in Distribution Management, HEC Montr´eal, 2009. — 23 p. 8. Laporte G., Semet F. Classical Heuristics for the Vehicle Routing Problem // Les Cahiers du GERAD, G98-54, Group for Research in Decision Analysis, Montreal, Canada, 1998. — 21 p. 9. Laporte G., Gendreau M., Potvin J-Y., Semet F. Classical and modern heuristics for the vehicle routing problem // International Transactions in Operational Research. — 2000. — Vol. 7. — Issue 4-5. — P. 285-300. 10. Gendreau M.G., Laporte G., Potvin J-Y. Metaheuristics for the vehicle routing problem // Les Cahiers du GERAD, G98-52, Group for Research in Decision Analysis, Montreal, Canada, 1998. — 27 p. 11. Gendreau M., Potvin J-Y., Bräysy O., Hasle G., Lökketangen A. Metaheuristics for the vehicle routing problem and its extensions: A categorized bibliography // CIRRELT, 2007. — Vol. 27. — 25 p. 12. Пожидаев М.С. Алгоритмы решения задачи маршрутизации транспорта: автореферат диссертации на соискание ученой степени кандидата технических наук, Томск, 2010. — 19 с. 13. Чернышев С.В. Модели, методы и алгоритмы эффективного решения задачи маршрутизации транспорта на графах больших размерностей: автореферат диссертации на соискание ученой степени кандидата физико-математических наук, Москва, 2011. — 24 с. 14. Гиндуллин Р.В. Оптимизация маршрута доставки однородного груза от множества производителей множеству потребителей: автореферат диссертации на соискание ученой степени кандидата физико-математических наук, Уфа, 2013. — 16 с. 15. Перцовский А.К. Адаптивные модели и алгоритмы маршрутизации: автореферат диссертации на соискание ученой степени кандидата физико-математических наук, Санкт-Петербург, 2013. — 16 с. ~ 130 ~ Математичне моделювання в економіці, №3-4, 2016 16. Хмелев А.В. Алгоритмы локального поиска для задач маршрутизации транспортных средств: диссертация на соискание ученой степени кандидата физико- математических наук, Новосибирск, 2015. — 119 с. 17. Berbeglia G., Cordeau J-F., Gribkovskaia I., Laporte G. Static pickup and delivery problems: a classification scheme and survey // TOP: Operations Research & Decision Theory, Springer-Verlag, 2007. — Vol. 15. — Issue 1. — P. 1-31. 18. Parragh S., Doerner K., Hartl R. A survey on pickup and delivery problems. Part I: Transportations between customers and depot // J. Betriebswirtschaft. — 2008. — V. 58. — No 1. — P. 21–51. 19. Parragh S., Doerner K., Hartl R. A survey on pickup and delivery problems. Part II: Transportations between customers and depot // J. Betriebswirtschaft. — 2008. — V. 58. — No 2. — P. 81–117. 20. Eksioglu B., Vural A.V., Reisman A. The vehicle routing problem: A taxonomic review // Computers & Industrial Engineering. — 2009. — V. 57. — No. 4. — P. 1472–1483. 21. Бронштейн Е.М., Заико Т.А. Детерминированные оптимизационные задачи транспортной логистики // Автоматика и телемеханика. — 2010. — № 10. — С. 133-147. 22. Kumar S.N., Panneerselvam R. A Survey on the Vehicle Routing Problem and Its Variants // Intelligent Information Management. — 2012. — 4. — P. 66-74. 23. De Jaegere N., Defraeyea M., Van Nieuwenhuysea I. The Vehicle Routing Problem: State of the Art Classification and Review // International Journal of Combinatorial Optimization Problems and Informatics. — 2014. — Volume 5. — No. 2. — P. 58–73. 24. Prins C., Lacomme P., Prodhon C. Order-first split-second methods for vehicle routing problems: A review // Transportation Research Part C. — 2014. — 40. — P. 179–200. 25. Braekers K., Ramaekers K., Van Nieuwenhuyse I. The vehicle routing problem: State of the art classification and review // Computers & Industrial Engineering. — 2015. — In Press. 26. Golden B.L., Raghavan S., Wasil E.A. The Vehicle Routing Problem: Latest Advances and New Challenges, Springer Science & Business Media, 2008. — 591 p. 27. Toth P., Vigo D. Vehicle Routing: Problems, Methods, and Applications, Second Edition, SIAM, 2014. — 463 p. 28. Dantzig G.B., Fulkerson D.R. Minimizing the number of tankers to meet a fixed schedule // Naval Research Logistics Quarterly. — 1954. — No. 1. — P. 217-222. 29. Kirby D. Is Your Fleet the Right Size? // Operational Research Quarterly. — 1959. — No. 10. — P. 252. 30. Golden B.L., Assad A., Levy L., Gheysens F. The Fleet Size and Mix Vehicle Routing Problem // Computers & Operations Research. — 1984. — No. 11. — P. 49-66. 31. Clarke G., Wright J.W. Scheduling of vehicles from a central depot to a number of delivery points // Operations Research. — 1964. — Vol. 12. — P. 568-581. 32. Salhi S., Rand G.K. Incorporating vehicle routing into the vehicle fleet composition problem // European Journal of Operational Research. — 1993. — No. 66. — P. 313-330. 33. Osman I.H., Salhi S. Local Search Strategies for the Vehicle Fleet Mix Problem // In Rayward-Smith V.J., Osman I.H., Reeves C.R., Smith G.D., eds., Modern heuristic search methods., John Wiley & Sons, Chichester, UK, 1996. — P. 131-153. 34. Lee Y.H., Kim J.I., Kang K.H., Kim K.H. A heuristic for vehicle fleet mix problem using tabu search and set partitioning // The Journal of the Operational Research Society. — 2008. — Vol. 59. — No. 6. — P. 833-841. 35. Baldacci R., Battarra M., Vigo D. Routing a Heterogeneous Fleet of Vehicles // Technical Report DEIS OR. INGCE 2007/1, University Bologna, Italy, 2007. — 25 p. 36. Baldacci R., Battarra M., Vigo D. Routing a heterogeneous fleet of vehicles // In Golden B.L., Raghavan S., Wasil E.A. (Eds.), The vehicle routing problem: Latest advances and new challenges. New York: Springer, 2008. — P. 1-25. http://link.springer.com/journal/11750 ~ 131 ~ Математичне моделювання в економіці, №3-4, 2016 37. Hoff A., Andersson H., Christiansen M., Hasle G., Løkketangen A. Industrial Aspects and Literature Survey: Fleet Composition and Routing // SINTEF REPORT NO. A7029. — 2008. — 49 p. 38. Hoff A., Andersson H., Christiansen M., Hasle G., Løkketangen A. Industrial aspects and literature survey: Fleet composition and routing // Computers & Operations Research . — 2010. — 37. — P. 2041–2061. 39. Yaman H. D. Formulations and valid inequalities for the heterogeneous vehicle routing problem // Mathematical Programming. — 2006. — Vol. 106. —No. 2. — P. 365-390. 40. Choi E., Tcha D. A column generation approach to the heterogeneous fleet vehicle routing problem // Computers & Operations Research. — 2007. — Vol. 34. — P. 2080- 2095. 41. Pessoa A., Uchoa E., Poggi de Aragão M. A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem // Networks. — 2009. — Vol. 54. — Issue 4. — P. 167-177. 42. Fukasawa R., Longo H., Lysgaard J., Poggi de Aragão M., Reis M., Uchoa E., Werneck R.F. Robust branch-and-cut-and-price for the capacitated vehicle routing problem // Mathematical Programming. — 2006. — Vol. 106. — P. 491-511. 43. Baldacci R., Battarra M., Vigo D. Valid inequalities for the fleet size and mix vehicle routing problem with fixed costs // Networks. — 2009. — Vol. 54. — Issue 4. — P. 178- 189. 44. Baldacci R., Mingozzi A. A unified exact method for solving different classes of vehicle routing problems // Mathematical Programming, Series A. — 2009. — Vol. 120. — Issue 2. — P. 347-380. 45. Baldacci R., Bartolini E., Mingozzi A., Roberti R. An exact solution framework for a broad class of vehicle routing problems // Computational Management Science. — 2010. — Vol. 7. — Issue 3. — P. 229-268. 46. Baldacci R., Toth P., Vigo D. Exact algorithms for routing problems under vehicle capacity constraints // Annals of Operations Research. — 2010. — Vol. 175. — Issue 1. — P. 213-245. 47. Gheysens F., Golden B.L., Assad A. A Comparison of Techniques for Solving the Fleet Size and Mix Vehicle Routing Problem // OR Spectrum. — 1984. — No. 6. — P. 207-216. 48. Miller C.E., Tucker A.W., Zemlin R.A. Integer programming formulations and traveling salesman problems // ACM. — 1960. — Vol. 7. — P. 326-329. 49. Balinski M., Quandt R. On an integer program for a delivery problem // Operations Research. — 1964. — Vol. 12. — P. 300–304. 50. Vidal T., Crainic T.G., Gendreau M., Prins C. A unified solution framework for multi- attribute vehicle routing problems // European Journal of Operational Research. — 2014. — Vol. 234. — Issue 3. — P. 658-673. 51. http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/index.html, http://www.gams.com/, http://aimms.com/, http://www.gurobi.com/. 52. http://www.informatik.uni-koeln.de/abacus/, http://www.coin-or.org/, http://www.gnu.org/software/glpk/glpk.html, http://groups.yahoo.com/group/lp_solve/info/. Стаття надійшла до редакції 26.10.16.

Схожі ресурси