Software & Systems

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

По мере того, как мировые экономики становятся все более взаимозависимыми, эффективное распределение товаров (от сырья до готовой продукции) приобретает первостепенное значение не только для выживания многих предприятий, которые зависят от такого распределения, но, в конечном счете, для общей конкурентоспособности рынка, как внутреннего, так и внешнего. Например, в силу интеграционных процессов российской экономики, таких как вхождение во Всемирную торговую организацию в 2012 году и создание Евразийского экономического союза в 2015 году, конкурентное преимущество во многих отраслях становится более зависимым от способности предоставлять эффективные и своевременные логистические услуги. Любое ощутимое повышение логистической эффективности системы приводит к выгоде для всех потребителей, поскольку в конечном итоге именно они оплачивают расходы системы распределения как часть цены каждого приобретаемого ими продукта. Одновременно с процессами глобализации происходит развитие информационных и коммуникационных технологий, позволяющих управлять парком транспортных средств в режиме реального времени, в числе которых электронный обмен данными – electronic data interchange (EDI), геоинформационные системы – geographic information systems (GIS), системы глобального позиционирования – global positioning systems (GPS), интеллектуальные системы взаимодействия транспортных средств с дорогой – intelligent vehicle-highway systems (IVHS), датчики потока трафика и мобильная связь новых поколений. Все эти технологии значительно расширили возможности эффективной динамической маршрутизации и открыли интересные и актуальные направления для новых исследований.

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

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

–     сценарии распределения в реальном времени становятся обыденными;

–     обработка данных в реальном времени стала осуществимой и более доступной;

–     повышение эффективности логистических систем приносит значительные экономические выгоды.

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

В прошлом веке постановка такого вопроса, возможно, была неуместна, поскольку различные технологические, институциональные и экономические процессы были гораздо менее развиты. Тем не менее, в одной из ранних работ по этой теме утверждалось, что методологическая основа технологий, явно предложенных и разработанных для решения динамических задач маршрутизации транспортных средств, была скудной, а динамический эквивалент архетипической задачи маршрутизации транспортных средств (то есть задачи коммивояжера) даже не был определен, и уж тем более в то время такая задача не была сформулирована или решена [1]. Действительно, к 1988 году большинство традиционных подходов к решению динамической задачи маршрутизации транспортных средств были простейшими адаптациями статических процедур [2–4]. В этих процедурах проблема статической маршрутизации транспортного средства (с соответствующим образом определенными входными данными) решалась точно или эвристически каждый раз, когда происходило обновление входных данных.

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

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

Задача маршрутизации транспорта – vehicle routing problem (VRP) – это хорошо известная NP-полная задача комбинаторной оптимизации, которая заключается в планировании маршрутов для парка транспортных средств с целью обслуживания множества территориально разнесенных пунктов (клиентов, потребителей, складов и т.д.) при наименьших затратах [5]. Реальные условия и ограничения VRP, встречаемые на практике, определили широкое множество вариантов постановки задачи [6], большинство которых, однако, являются статическими.

Можно выделить многие динамические характеристики, которые привносят непостоянство в классическую VRP: дороги между двумя клиентами могут быть заблокированы, клиенты могут изменять свои заказы, время в пути для некоторых маршрутов может быть увеличено из-за плохих погодных условий и т.д. Присутствие подобных характеристик является признаком динамической задачи маршрутизации транспорта – dynamic VRP (DVRP).

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

DVRP фактически представляет собой набор различных задач, имеющих решающее значение в современной отрасли и составляющих немалую часть многих систем транспортировки и распределения. Различные авторы описали ряд реальных приложений, которые стимулируют исследование DVRP [8–10]. Приведем несколько важных проблем, требую- щих практического решения в реальном времени.

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

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

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

·     Системы заказа транспорта Dial-a-Ride. Системы Dial-a-Ride наиболее часто служат для реагирования на запросы по обслуживанию небольших групп или отдельных пассажиров с особыми требованиями (пожилые люди, инвалиды). Такие перевозки описываются связями «многие ко многим», когда любой клиент может служить исходным пунктом или пунктом назначения для любой услуги. Клиенты могут забронировать поездку за один день (статичные клиенты) или делать запросы в короткие сроки (динамические клиенты).

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

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

Разновидности динамических задач маршрутизации транспорта

В работе [1] VRP определена как динамическая, когда некоторые исходные данные задачи становятся известными во время работы алгоритма. Соответственно, решение задачи должно меняться по мере того, как новая информация открывается для алгоритма и лица, принимающего решения. Атрибуты информации могут включать изменчивость (статическая/динамическая), качество (известная детерминированная/прогнозируемая/вероятностная/неизвестная), доступность (локальная/ глобальная) и обработку (централизованная/ децентрализованная). В соответствии со знаниями о входных данных можно классифицировать DVRP, разделив их, в первую очередь, на детерминированные и недетерминированные. Обе разновидности DVRP могут быть связаны с такими динамическими факторами, как временные окна, дорожные заторы, ремонт дорог, изменение погодных условий, поломка транспортных средств, дорожно-транспортные происшествия и т.д. Эти факторы часто меняют скорость движения транспортных средств и время прибытия в депо. Следовательно, они приводят к другим подвидам задачи. Рассмотрим их по отдельности.

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

Dynamic capacitated vehicle routing problem with dynamic requests (DCVRP) – динамическая задача маршрутизации транспорта с ограничением грузоподъемности и динамическими запросами. Ряд работ посвящены этому вари- анту, представляющему общепринятое опреде- ление задачи, в которой наличие всех клиентов и их расположение детерминированы, но запросы клиентов могут поступать в любое время [11–13]. Задача состоит в том, чтобы найти набор маршрутов с наименьшим пройденным расстоянием, соблюдая ограничение грузоподъемности (вместимости) транспортного средства.

Dynamic vehicle routing problem with time window (DVRPTW) – динамическая задача маршрутизации транспорта с временными окнами. Это один из наиболее изученных вариантов DVRP [14–16]. Помимо динамических запросов, поступающих в режиме реального времени, необходимо соблюдать временные окна, связанные с каждым из клиентов. Цель состоит в том, чтобы минимизировать общее или максимальное опоздание (опережение) при обслуживании множества клиентов. Частным случаем является динамическая задача коммивояжера с временными окнами, рассмотренная на примере динамического ремонтника [17]. Простая стратегия решения состоит в том, чтобы заставить транспортное средство ждать в текущем местоположении клиента до тех пор, пока сохраняется возможность обслужить другого клиента без опоздания. В других правилах может быть предложено изменить местоположение автомобиля на основании предварительной информации о будущих запросах.

Dynamic vehicle routing problem with time-dependent travel times (DVRPTT) – динамическая задача маршрутизации транспорта с динамическим временем пути. В описанной в работе [18] задаче предполагается, что время в пути от клиента i к клиенту j изменяется. Это изменение возможно из-за типа дороги, погоды и условий движения, которые могут сильно влиять на скорость транспортных средств и, следовательно, на время в пути.

Dynamic pickup and delivery vehicle routing problem (DPDVRP) – динамическая задача маршрутизации транспорта с вывозом и доставкой. Основой послужила обычная задача маршрутизации транспорта с вывозом и доставкой, в которой клиенты могут как получать, так и отправлять товары. Обычно цель состоит в том, чтобы минимизировать общую длину маршрута, то есть сумму расстояний, пройденных всеми транспортными средствами, при следующих ограничениях: все клиенты должны быть обслужены, каждый запрос полностью должен обслуживаться одним транспортным средством и вывоз всегда дол- жен предшествовать доставке. Динамическая версия DPDVRP возникает, когда не все запросы на вывоз и доставку известны зара- нее [19]. В работе [20] представлена параллельная реализация метода поиска с запретами (табу-поиск), разработанного для варианта задачи с системой Dial-a-Ride [21]. Авторами [22] разработана эвристика поиска с запретами, в которой структура соседства основана на эвристике «выбрасывания цепей», а в [23] представлена задача планирования вывоза и доставки с множеством грузовиков (предложены формулировка задачи частично-целочисленного программирования и новая стратегия повторной оптимизации для динамической версии).

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

Dynamic and stochastic capacitated vehicle routing problem (DSCVRP) – динамическая и стохастическая задача маршрутизации транспорта с ограничением грузоподъемности. В ней считается, что запросы клиентов неизвестны и выясняются с течением времени. Кроме того, местоположение клиентов и время обслуживания являются случайными переменными и реализуются динамически при выполнении плана. В работах [24, 25] рассмотрена динамическая задача со стохастическими клиентами и предложен подход с несколькими сценариями. Метод непрерывно генерирует планы маршрутизации для разных сценариев, включая известные и срочные запросы, чтобы максимизировать количество обслуживаемых клиентов. Подход был адаптирован под различную степень динамичности. Авторы [26] рассмотрели вариант, когда местонахождение клиента и его требования заранее неизвестны. Они сформулировали DSCVRP как многоэтапную задачу стохастического программирования и разработали эвристический метод для генерации маршрутов с использованием информации, собранной относительно будущих запросов клиентов.

Dynamic and stochastic vehicle routing prob- lem with time window (DSVRPTW) – динамиче- ская и стохастическая задача маршрутизации транспорта с временными окнами. Задача была предложена в [27]. В ней каждый запрос на обслуживание генерируется в соответствии со случайным законом; как только появляется запрос на обслуживание, он остается активным в течение определенного детерминированного периода времени, а затем исчезает. Существуют некоторые вариации задачи, но общая цель состоит в том, чтобы свести к минимуму количество возможных транспортных средств и обеспечить удовлетворение каждой потребности до ее истечения [28].

Dynamic vehicle routing problem with stochastic travel time (DVRPSTT) – динамическая задача маршрутизации транспорта со случайным временем пути. Предполагается, что время движения транспортных средств подчиняется некоторому закону случайного распределения. Кроме того, время пути может постепенно меняться от одного периода к другому. Некоторые работы представляют такую версию задачи, когда время пути до следующего пункта назначения изменяется при добавлении значения, генерируемого по нормальному закону распределения [29]. Эти изменения – любые непредвиденные события, которые могут произойти во время текущей поездки. Обычно информация о таких изменениях становится известной только тогда, когда транспортное средство прибывает в ближайший запланированный пункт назначения.

Dynamic and stochastic pickup and delivery vehicle routing problem (DSPDVRP) – динамическая и стохастическая задача маршрутизации транспорта с вывозом и доставкой. В этой версии случайный процесс касается величины спроса, в соответствии с которым транспортное средство должно вывезти или доставить груз каждому клиенту. Таким образом, имеется неопределенное количество груза, который нужно забрать или доставить по месту нахождения клиента [30]. Распределение может быть смоделировано с помощью вероятностного закона, такого как, например, нормальный закон, или с помощью нечеткой логики.

Методы решения

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

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

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

–     поиск с запретами (tabu search), в том числе параллельный [19, 20];

–     переменный поиск окрестностей (variab­le neighborhood search) [31–33];

–     методы вставки (insertion methods) [34, 35];

–     метод ближайших соседей (nearest neigh­bor search) [36];

–     генерация столбцов (column generation) [37, 38];

–     генетические алгоритмы (genetic algo­rithms) [39–41];

–     муравьиные алгоритмы (ant colony opti- mization) [42–44];

–     методы роя частиц (particle swarm opti­mization) [45, 46].

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

Заключение

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

Работа выполнена при финансовой поддержке РФФИ, проект № 18-01-00314.

Acknowledgements. This paper was financially supported by the RFBR, project no. 18-01-00314.

Литература

1.    Psaraftis H.N. Dynamic vehicle routing problems. In: Vehicle Routing: Methods and Studies, 1988, vol. 16, pp. 223–248.

2.    Psaraftis H.N. A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem. Transportation Science, 1980, vol. 14, no. 2, pp. 130–154. DOI: 10.1287/trsc.14.2.130.

3.    Bell W.J., Dalberto L.M., Fisher M.L., Greenfield A.J., Jaikumar R., Kedia P., Mack R.G., Prutz- man P.J. Improving the distribution of industrial gases with an on-line computerized routing and scheduling optimizer. Interfaces, 1983, vol. 13, no. 6, pp. 4–23. DOI: 10.1287/inte.13.6.4.

4.    Brown G.G., Ellis C.J., Graves G.W., Ronen D. Real-time, wide area dispatch of mobil tank trucks. Interfaces, 1987, vol. 17, no. 1, pp. 107–120. DOI: 10.1287/inte.17.1.107.

5.    Dantzig G.B., Ramser J.H. The Truck dispatching problem. Management Science, 1959, vol. 6, no. 1, pp. 80–91. DOI: 10.1287/mnsc.6.1.80.

6.    Кубил В.Н. Обзор обобщений и расширений задачи маршрутизации транспорта // Вестн. РГУПС. 2018. Т. 70. № 2. С. 97–109.

7.    Конников П.В., Кудинов В.А. О динамических задачах комбинаторной оптимизации // Ученые записки. Электрон. науч. журн. Курского гос. ун-та. 2009. № 1. С. 45–50.

8.    Larsen A. The Dynamic Vehicle Routing Problem. Ph.D. Thes., 2000, 208 р.

9.    Beaudry A., Laporte G., Melo T., Nickel S. Dynamic transportation of patients in hospitals. OR Spectrum, 2010, vol. 32, no. 1, pp. 77–107. DOI: 10.1007/s00291-008-0135-6.

10. Schilde M., Doerner K.F., Hartl R.F. Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports. Computers & Operations Research, 2011, vol. 38, no. 12, pp. 1719–1730. DOI: 10.1016/j.cor.2011.02.006.

11. Gendreau M., Guertin F., Potvin J.Y., Taillard E.D. Parallel tabu search for real-time vehicle routing and dispatching. Transportation Sci., 1999, vol. 33, no. 4, pp. 381–390. DOI: 10.1287/trsc.33.4.381.

12. Kilby P., Prosser P., Shaw P. Dynamic VRPs: A Study of Scenarios. APES Report, 1998. URL: https:// pdfs.semanticscholar.org/19df/8728e4a9b273b6e0a6f84b7f39ff4543e565.pdf (дата обращения: 31.10.2020).

13. Montemanni R., Gambardella L.M., Rizzoli A.E., Donati A.V. A New Algorithm for a Dynamic Vehicle Routing Problem Based on Ant Colony System. 2002. URL: ftp://ftp.idsia.ch/pub/techrep/IDSIA-23-02.pdf.gz (дата обращения: 31.10.2020).

14. Alvarenga G.B., Silva R.M.A. A hybrid approach for the dynamic vehicle routing problem with time windows. Proc. 5th Int. Conf. Hybrid Intelligent Systems, IEEE, 2005, pp. 61–67. DOI: 10.1109/ICHIS.2005.8.

15. Oliveira S.M., Souza S.R., Silva M.A.L. A solution of dynamic vehicle routing problem with time window via ant colony system metaheuristic. Proc. 10th Brazilian Sympos. Neural Networks, IEEE, 2008, pp. 21–26. DOI: 10.1109/SBRN.2008.20.

16. Fabri A., Recht P. On dynamic pickup and delivery vehicle routing with several time windows and waiting times. Transportation Research, Pt. B: Methodological, 2006, vol. 40, no. 4, pp. 335–350. DOI: 10.1016/j.trb.2005.04.002.

17. Larsen A., Madsen O.B.G., Solomon M.M. Partially dynamic vehicle routing-models and algorithms. JORS, 2002, vol. 53, no. 6, pp. 637–646. DOI: 10.1057/palgrave.jors.2601352.

18. Haghani A., Jung S. A dynamic vehicle routing problem with time-dependent travel times. Computers & Operations Research, 2005, vol. 32, no. 11, pp. 2959–2986. DOI: 10.1016/j.cor.2004.04.013.

19. Mitrovic-Minic S., Krishnamurti R., Laporte G. Double-horizon based heuristics for the dynamic pickup and delivery problem with time windows. Transportation Research, Pt. B: Methodological, 2004, vol. 38, no. 8, pp. 669–685. DOI: 10.1016/j.trb.2003.09.001.

20. Attanasio A., Cordeau J.F., Ghiani G., Laporte G. Parallel tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem. Parallel Computing, 2004, vol. 30, no. 3, pp. 377–387. DOI: 10.1016/j.parco. 2003.12.001.

21. Cordeau J.F., Laporte G. A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transportation Research, Pt. B: Methodological, 2003, vol. 37, no. 6, pp. 579–594. DOI: 10.1016/S0191-2615(02) 00045-0.

22. Gendreau M., Guertin F., Potvin J.Y., Séguin R. Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries. Transportation Research, Pt. C: Emerging Technologies, 2006, vol. 14, no. 3, pp. 157–174. DOI: 10.1016/j.trc.2006.03.002.

23. Yang J., Jaillet P., Mahmassani H.S. Real-time multivehicle truckload pickup and delivery problems. Transportation Sci., 2004, vol. 38, no. 2, pp. 135–148. DOI: 10.1287/trsc.1030.0068.

24. Bent R., van Hentenryck P. Dynamic vehicle routing with stochastic requests. Proc. 18th Int. Joint Conf. on Artificial Intelligence, 2003, pp. 1362–1363.

25. Bent R.W., Van Hentenryck P. Scenario-based planning for partially dynamic vehicle routing with stochastic customers. Operations Research, 2004, vol. 52, no. 6, pp. 977–987. DOI: 10.1287/opre.1040.0124.

26. Hvattum L.M., Løkketangen A., Laporte G. Solving a dynamic and stochastic vehicle routing problem with a sample scenario hedging heuristic. Transportation Sci., 2006, vol. 40, no. 4, pp. 421–438. DOI: 10.1287/ trsc.1060.0166.

27. Pavone M., Bisnik N., Frazzoli E., Isler V. A stochastic and dynamic vehicle routing problem with time windows and customer impatience. Mobile Networks and Applications, 2009, vol. 14, no. 3, pp. 350–364. DOI: 10.1007/s11036-008-0101-1.

28. Гладков Л.А., Гладкова Н.В. Особенности и новые подходы к решению динамических транспортных задач с ограничением по времени // Изв. ЮФУ. Технич. науки. 2014. Т. 156. № 7. С. 178–187.

29. Potvin J.Y., Xu Y., Benyahia I. Vehicle routing and scheduling with dynamic travel times. Computers & Operations Research, 2006, vol. 33, no. 4, pp. 1129–1137. DOI: 10.1016/j.cor.2004.09.015.

30. Xu J., Goncalves G., Hsu T. Genetic algorithm for the vehicle routing problem with time windows and fuzzy demand. Proc. Congress on Evolutionary Computation, IEEE, 2008, pp. 4125–4129. DOI: 10.1109/CEC. 2008.4631360.

31. Schilde M., Doerner K.F., Hartl R.F. Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem. EJOR, 2014, vol. 238, no. 1, pp. 18–30. DOI: 10.1016/j.ejor. 2014.03.005.

32. Sarasola B., Doerner K.F., Schmid V., Alba E. Variable neighborhood search for the stochastic and dynamic vehicle routing problem. Annals of Operations Research, 2016, vol. 236, no. 2, pp. 425–461. DOI: 10.1007/s10479-015-1949-7.

33. Chen S., Chen R., Wang G., Gao J., Sangaiah A.K. An adaptive large neighborhood search heuristic for dynamic vehicle routing problems. Computers & Electrical Engineering, 2018, vol. 67, pp. 596–607. DOI: 10.1016/j.compeleceng.2018.02.049.

34. Campbell A.M., Savelsbergh M.W. Decision support for consumer direct grocery initiatives. Transportation Sci., 2005, vol. 39, no. 3, pp. 313–327. DOI: 10.1287/trsc.1040.0105.

35. Li J.Q., Mirchandani P.B., Borenstein D. A Lagrangian heuristic for the real-time vehicle rescheduling problem. Transportation Research, Pt. E: Logistics and Transportation Review, 2009, vol. 45, no. 3, pp. 419–433. DOI: 10.1016/j.tre.2008.09.002.

36. Sheridan P.K., Gluck E., Guan Q.M., Pickles T., Balcıog˜lu B., Benhabib B. The dynamic nearest neighbor policy for the multi-vehicle pick-up and delivery problem. Transportation Research. Pt. A: Policy and Practice, 2013, vol. 49, pp. 178–194. DOI: 10.1016/j.tra.2013.01.032.

37. Chen Z.L., Xu H. Dynamic column generation for dynamic vehicle routing with time windows. Transportation Science, 2006, vol. 40, no. 1, pp. 74–88. DOI: 10.1287/trsc.1050.0133.

38. Christiansen C.H., Lysgaard J. A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands. Operations Research Letters, 2007, vol. 35, no. 6, pp. 773–781. DOI: 10.1016/ j.orl.2006.12.009.

39. Barkaoui M., Gendreau M. An adaptive evolutionary approach for real-time vehicle routing and dispatching. Computers & Operations Research, 2013, vol. 40, no. 7, pp. 1766–1776. DOI: 10.1016/j.cor.2013. 01.022.

40. Xu H., Duan F.Y., Pu P. Solving dynamic vehicle routing problem using enhanced genetic algorithm with penalty factors. Int. J. Performability Eng., 2018, vol. 14, no. 4, pp. 611–620. DOI: 10.23940/ijpe.18.04. p3.611620.

41. Sabar N.R., Bhaskar A., Chung E., Turky A., Song A. A self-adaptive evolutionary algorithm for dynamic vehicle routing problems with traffic congestion. Swarm and Evolutionary Computation, 2019, vol. 44, pp. 1018–1027. DOI: 10.1016/j.swevo.2018.10.015.

42. Dan B., Zhu W., Li H., Sang Y., Liu Y. Dynamic optimization model and algorithm design for emergency materials dispatch. Math. Problems in Eng., 2013, pp. 1–6. DOI: 10.1155/2013/841458.

43. Euchi J., Yassine A., Chabchoub H. The dynamic vehicle routing problem: Solution with hybrid metaheuristic approach. Swarm and Evolutionary Computation, 2015, vol. 21, pp. 41–53. DOI: 10.1016/j.swevo. 2014.12.003.

44. Xu H., Pu P., Duan F. Dynamic vehicle routing problems with enhanced ant colony optimization. Discrete Dynamics in Nature and Society, 2018, pp. 1–13. DOI: 10.1155/2018/1295485.

45. Yang J., Li J., Chen Y., Liu X. Multi-objective distribution model and algorithm for online shopping express logistics. JCP, 2013, vol. 8, no. 10, pp. 2558–2564. DOI: 10.4304/jcp.8.10.2558-2564.

46. Kaiwartya O., Kumar S., Lobiyal D.K., Tiwari P.K., Abdullah A.H., Hassan A.N. Multiobjective dynamic vehicle routing problem and time seed based solution using particle swarm optimization. Journal of Sensors, 2015, pp. 1–14. DOI: 10.1155/2015/189832.

47. Пантелеев А.В., Скавинская Д.В. Метаэвристические алгоритмы глобальной оптимизации. М.: Вузовская книга, 2019. 332 с.

References

1. Psaraftis H.N. Dynamic vehicle routing problems. In: Vehicle Routing: Methods and Studies, 1988,
   vol. 16, pp. 223–248.
2. Psaraftis H.N. A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem. Transportation Science, 1980, vol. 14, no. 2, pp. 130–154. DOI: 10.1287/trsc.14.2.130.
3. Bell W.J., Dalberto L.M., Fisher M.L., Greenfield A.J., Jaikumar R., Kedia P., Mack R.G., Prutz-
   man P.J. Improving the distribution of industrial gases with an on-line computerized routing and scheduling optimizer. Interfaces, 1983, vol. 13, no. 6, pp. 4–23. DOI: 10.1287/inte.13.6.4.
4. Brown G.G., Ellis C.J., Graves G.W., Ronen D. Real-time, wide area dispatch of mobil tank trucks. Interfaces, 1987, vol. 17, no. 1, pp. 107–120. DOI: 10.1287/inte.17.1.107.
5. Dantzig G.B., Ramser J.H. The truck dispatching problem. Management Science, 1959, vol. 6, no. 1, pp. 80–91. DOI: 10.1287/mnsc.6.1.80.
6. Kubil V.N. A review of the vehicle routing problem generalizations and extensions. Vestn. RGUPS, 2018, vol. 70, no. 2, pp. 97–109.
7. Konnikov P.V., Kudinov V.A. On dynamic combinatorial optimization problems. Sci. Notes: The Online Acad. J. of Kursk State Univ., 2009, no. 1, pp. 45–50.
8. Larsen A. The Dynamic Vehicle Routing Problem. Ph.D. Thes., 2000, 208 р.
9. Beaudry A., Laporte G., Melo T., Nickel S. Dynamic transportation of patients in hospitals. OR Spectrum, 2010, vol. 32, no. 1, pp. 77–107. DOI: 10.1007/s00291-008-0135-6.
10. Schilde M., Doerner K.F., Hartl R.F. Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports. Computers & Operations Research, 2011, vol. 38, no. 12, pp. 1719–1730. DOI: 10.1016/j.cor.2011.02.006.
11. Gendreau M., Guertin F., Potvin J.Y., Taillard E.D. Parallel tabu search for real-time vehicle routing and dispatching. Transportation Sci., 1999, vol. 33, no. 4, pp. 381–390. DOI: 10.1287/trsc.33.4.381.
12. Kilby P., Prosser P., Shaw P. Dynamic VRPs: A Study of Scenarios. APES Report, 1998. Available at: https://pdfs.semanticscholar.org/19df/8728e4a9b273b6e0a6f84b7f39ff4543e565.pdf (accessed October 31, 2019).
13. Montemanni R., Gambardella L.M., Rizzoli A.E., Donati A.V. A New Algorithm for a Dynamic Vehicle Routing Problem Based on Ant Colony System. 2002. Available at: ftp://ftp.idsia.ch/pub/techrep/IDSIA-23-02.pdf.gz (accessed October 31, 2019).
14. Alvarenga G.B., Silva R.M.A. A hybrid approach for the dynamic vehicle routing problem with time windows. Proc. 5th Int. Conf. Hybrid Intelligent Systems, IEEE, 2005, pp. 61–67. DOI: 10.1109/ICHIS.2005.8.
15. Oliveira S.M., Souza S.R., Silva M.A.L. A solution of dynamic vehicle routing problem with time window via ant colony system metaheuristic. Proc. 10th Brazilian Sympos. Neural Networks, IEEE, 2008,
    pp. 21–26. DOI: 10.1109/SBRN.2008.20.
16. Fabri A., Recht P. On dynamic pickup and delivery vehicle routing with several time windows and waiting times. Transportation Research, Pt. B: Methodological, 2006, vol. 40, no. 4, pp. 335–350. DOI: 10.1016/j.trb.2005.04.002.
17. Larsen A., Madsen O.B.G., Solomon M.M. Partially dynamic vehicle routing-models and algorithms. JORS, 2002, vol. 53, no. 6, pp. 637–646. DOI: 10.1057/palgrave.jors.2601352.
18. Haghani A., Jung S. A dynamic vehicle routing problem with time-dependent travel times. Computers & Operations Research, 2005, vol. 32, no. 11, pp. 2959–2986. DOI: 10.1016/j.cor.2004.04.013.
19. Mitrovic-Minic S., Krishnamurti R., Laporte G. Double-horizon based heuristics for the dynamic pickup and delivery problem with time windows. Transportation Research Pt. B: Methodological, 2004,
    vol. 38, no. 8, pp. 669–685. DOI: 10.1016/j.trb.2003.09.001.
20. Attanasio A., Cordeau J.F., Ghiani G., Laporte G. Parallel tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem. Parallel Computing, 2004, vol. 30, no. 3, pp. 377–387. DOI: 10.1016/j.parco.2003. 12.001.
21. Cordeau J.F., Laporte G. A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transportation Research Pt. B: Methodological, 2003, vol. 37, no. 6, pp. 579–594. DOI: 10.1016/S0191-2615(02)00045-0.
22. Gendreau M., Guertin F., Potvin J.Y., Séguin R. Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries. Transportation Research Pt. C: Emerging Technologies, 2006, vol. 14, no. 3, pp. 157–174. DOI: 10.1016/j.trc.2006.03.002.
23. Yang J., Jaillet P., Mahmassani H.S. Real-time multivehicle truckload pickup and delivery problems. Transportation Sci., 2004, vol. 38, no. 2, pp. 135–148. DOI: 10.1287/trsc.1030.0068.
24. Bent R., van Hentenryck P. Dynamic vehicle routing with stochastic requests. Proc. 18th Int. Joint Conf. on Artificial Intelligence, 2003, pp. 1362–1363.
25. Bent R.W., Van Hentenryck P. Scenario-based planning for partially dynamic vehicle routing with stochastic customers. Operations Research, 2004, vol. 52, no. 6, pp. 977–987. DOI: 10.1287/opre.1040.0124.
26. Hvattum L.M., Løkketangen A., Laporte G. Solving a dynamic and stochastic vehicle routing problem with a sample scenario hedging heuristic. Transportation Sci., 2006, vol. 40, no. 4, pp. 421–438. DOI: 10.1287/
    trsc.1060.0166.
27. Pavone M., Bisnik N., Frazzoli E., Isler V. A stochastic and dynamic vehicle routing problem with time windows and customer impatience. Mobile Networks and Applications, 2009, vol. 14, no. 3, pp. 350–364. DOI: 10.1007/s11036-008-0101-1.
28. Gladkov L.A., Gladkova N.V. Features and new approaches to the decision of dynamic vehicle routing problems with time windows. Izv. SFU. Eng. Sci., 2014, vol. 156, no. 7, pp. 178–187.
29. Potvin J.Y., Xu Y., Benyahia I. Vehicle routing and scheduling with dynamic travel times. Computers & Operations Research, 2006, vol. 33, no. 4, pp. 1129–1137. DOI: 10.1016/j.cor.2004.09.015.
30. Xu J., Goncalves G., Hsu T. Genetic algorithm for the vehicle routing problem with time windows and fuzzy demand. Proc. Congress on Evolutionary Computation, IEEE, 2008, pp. 4125–4129. DOI: 10.1109/
    CEC.2008.4631360.
31. Schilde M., Doerner K.F., Hartl R.F. Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem. EJOR, 2014, vol. 238, no. 1, pp. 18–30. DOI: 10.1016/j.ejor.
    2014.03.005.
32. Sarasola B., Doerner K.F., Schmid V., Alba E. Variable neighborhood search for the stochastic and dynamic vehicle routing problem. Annals of Operations Research, 2016, vol. 236, no. 2, pp. 425–461. DOI: 10.1007/s10479-015-1949-7.
33. Chen S., Chen R., Wang G., Gao J., Sangaiah A.K. An adaptive large neighborhood search heuristic for dynamic vehicle routing problems. Computers & Electrical Engineering, 2018, vol. 67, pp. 596–607. DOI: 10.1016/j.compeleceng.2018.02.049.
34. Campbell A.M., Savelsbergh M.W. Decision support for consumer direct grocery initiatives. Transportation Sci., 2005, vol. 39, no. 3, pp. 313–327. DOI: 10.1287/trsc.1040.0105.
35. Li J.Q., Mirchandani P.B., Borenstein D. A Lagrangian heuristic for the real-time vehicle rescheduling problem. Transportation Research, Pt. E: Logistics and Transportation Review, 2009, vol. 45, no. 3,
    pp. 419–433. DOI: 10.1016/j.tre.2008.09.002.
36. Sheridan P.K., Gluck E., Guan Q.M., Pickles T., Balcıog˜lu B., Benhabib B. The dynamic nearest neighbor policy for the multi-vehicle pick-up and delivery problem. Transportation Research. Pt. A: Policy and Practice, 2013, vol. 49, pp. 178–194. DOI: 10.1016/j.tra.2013.01.032.
37. Chen Z.L., Xu H. Dynamic column generation for dynamic vehicle routing with time windows. Transportation Sci., 2006, vol. 40, no. 1, pp. 74–88. DOI: 10.1287/trsc.1050.0133.
38. Christiansen C.H., Lysgaard J. A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands. Operations Research Letters, 2007, vol. 35, no. 6, pp. 773–781. DOI: 10.1016/
    j.orl.2006.12.009.
39. Barkaoui M., Gendreau M. An adaptive evolutionary approach for real-time vehicle routing and dispatching. Computers & Operations Research, 2013, vol. 40, no. 7, pp. 1766–1776. DOI: 10.1016/j.cor.2013.
    01.022.
40. Xu H., Duan F.Y., Pu P. Solving dynamic vehicle routing problem using enhanced genetic algorithm with penalty factors. Int. J. of Performability Eng., 2018, vol. 14, no. 4, pp. 611–620. DOI: 10.23940/ijpe.18.04.
    p3.611620.
41. Sabar N.R., Bhaskar A., Chung E., Turky A., Song A. A self-adaptive evolutionary algorithm for dynamic vehicle routing problems with traffic congestion. Swarm and Evolutionary Computation, 2019, vol. 44, pp. 1018–1027. DOI: 10.1016/j.swevo.2018.10.015.
42. Dan B., Zhu W., Li H., Sang Y., Liu Y. Dynamic optimization model and algorithm design for emergency materials dispatch. Math. Problems in Eng., 2013, pp. 1–6. DOI: 10.1155/2013/841458.
43. Euchi J., Yassine A., Chabchoub H. The dynamic vehicle routing problem: Solution with hybrid metaheuristic approach. Swarm and Evolutionary Computation, 2015, vol. 21, pp. 41–53. DOI: 10.1016/j.swevo. 2014.12.003.
44. Xu H., Pu P., Duan F. Dynamic vehicle routing problems with enhanced ant colony optimization. Discrete Dynamics in Nature and Society, 2018, pp. 1–13. DOI: 10.1155/2018/1295485.
45. Yang J., Li J., Chen Y., Liu X. Multi-objective distribution model and algorithm for online shopping express logistics. JCP, 2013, vol. 8, no. 10, pp. 2558–2564. DOI: 10.4304/jcp.8.10.2558-2564.
46. Kaiwartya O., Kumar S., Lobiyal D.K., Tiwari P.K., Abdullah A.H., Hassan A.N. Multiobjective dynamic vehicle routing problem and time seed based solution using particle swarm optimization. Journal of Sensors, 2015, pp. 1–14. DOI: 10.1155/2015/189832.
47. Panteleev A.V., Skavinskaya D.V. Metaheuristic Global Optimization Algorithms. Moscow, 2019,
    332 p. (in Russ.).