Задачи маршрутизации при транспортировке: обзор моделей, методов и алгоритмов.Часть 1.

Оцените материал
(0 голосов)

Опубликовано №4 (93) август 2019 г.

АВТОРЫ:  

ГОНЧАРОВА Ю.А. - к.т.н., инженер-программист, Научно-производственный центр  «ГеоТэк» (Уфа, Россия)

Валеева А.Ф. 

Валеев Р.С. 

РУБРИКИ:  Обзоры и аналитика Оптимизация и экономико-математическое моделирование Транспортировка в логистике

Аннотация 

Статья посвящена обзору известных задач маршрутизации (Vehicle Routing Problem, VRP), являющихся неотъемлемой частью управления транспортировкой в логистике. Приводятся математические модели различных классов задач маршрутизации: с учетом грузоподъемности транспортных средств (ТС), с временными окнами, с раздельной доставкой, с заданным временным горизонтом планирования (периодическая задача), с возвратом заказа, с возможностью дозагрузки. Поскольку задачи маршрутизации являются NP-трудными задачами комбинаторной оптимизации, для их практического применения в сфере транспортировки разрабатываются различные эвристические методы. В статье излагаются известные метаэвристики, представляющие собой как алгоритмы локального поиска оптимума, так и конструктивные алгоритмы, а именно: генетический алгоритм, эволюционные стратегии, серия алгоритмов муравьиной колонии, алгоритм поиска с переменной окрестностью. При этом уделяется внимание кодировке решения и некоторым операциям построения окрестности решения, необходимых для разработки некоторых метаэвристических алгоритмов. Поскольку на практике задачи маршрутизации тесно связаны с задачей размещения грузов внутри ТС (задача трехмерной упаковки), описываются приближенные алгоритмы, позволяющие получить карту упаковки грузами ТС. Приведенный обзор различных классов задач маршрутизации и эффективных методов их решения поможет в решении практических задач поиска эффективных маршрутов для доставки грузов различным клиентам. Так, в Части 2 статьи описываются математическая модель и методы решения одной практической задачи маршрутизации, решаемой совместно с задачей трехмерной упаковки грузов в автомобильные ТС 

Электронная версия

Ключевые слова: 

 

Прочитано 298 раз

Контакты

Работа с авторами 

Левина Тамара

моб. 8(962) 965-48-54

E-mail: levina-tamara@mail.ru

Распространение

Алямовская Наталия

моб. 8(916) 150-07-21

E-mail: nalyamovskaya@mail.ru

Адрес 

125319, Москва, ул. Черняховского, д.16

тел./факс (495) 771 32 58

ISSN 2587-6775

Издается с 2004 г.

Включен в перечень ВАК с 2008 г.

ИНДЕКСИРОВАНИЕ ЖУРНАЛА