Крупномасштабная проблема прокладки емкостной дуги
Крупномасштабная задача трассировки емкостной дуги ( LSCARP ) — это вариант задачи трассировки емкостной дуги , которая охватывает 300 или более ребер для моделирования сложных задач трассировки дуг в больших масштабах.
Йи Мэй и др. опубликовал алгоритм для решения крупномасштабной задачи маршрутизации емкостной дуги с использованием алгоритма кооперативной коэволюции. [1]
LSCARP можно решить с помощью алгоритма «разделяй и властвуй», применяемого для разделения маршрута. [2]
LSCARP также можно решить с помощью итеративного локального поиска, который улучшает верхние и нижние границы других методов. [3]
Алгоритм LSCARP был применен для сбора мусора в Дании с помощью быстрой эвристики FAST-CARP. [4]
Алгоритм также часто называют проблемой маршрутизации дуги с временной емкостью, часто называемой TCARP. TCARP можно решить с помощью метаэвристики за разумное время. TCARP часто возникает, когда ограничения по объему не применяются, например, показания счетчика. [5]
Чжан и др. создал метаэвристику для решения обобщения, названного крупномасштабным CARP с несколькими депо (LSMDCARP), названного кластеризацией маршрутов и эвристикой поиска. [6]
Алгоритм для LSCARP под названием «Шаг расширения и статистическая фильтрация для крупномасштабного CARP» (ESMAENS) был разработан в 2017 году. [7]
LSCARP можно расширить до крупномасштабной задачи маршрутизации транспортных средств с помощью алгоритма иерархической декомпозиции. [8] Задача LSCVRP может быть решена эволюционным методом, основанным на локальном поиске. [9] Решение LSCVRP может быть выполнено с помощью интегрированных машин опорных векторов и методов случайного леса. [10]
Алгоритм для решения LSCARP на основе моделирования отжига под названием FILO был разработан Accorsi et al. [11]
Ссылки
[ редактировать ]- ^ Мэй, Йи; Ли, Сяодун; Яо, Синь (июнь 2014 г.). «Кооперативная коэволюция с группировкой расстояний маршрутов для решения крупномасштабных задач маршрутизации емкостной дуги» . Транзакции IEEE в эволюционных вычислениях . 18 (3): 435–449. дои : 10.1109/TEVC.2013.2281503 . ISSN 1089-778X . S2CID 4851980 . Архивировано из оригинала 15 июня 2022 г. Проверено 14 июля 2022 г.
- ^ Чжан, Ючжоу; Мэй, Йи; Чжан, Бучжун; Цзян, Кэцинь (01 апреля 2021 г.). «Разделяй и властвуй, крупномасштабные задачи трассировки емкостных дуг с разложением отсечения маршрута» . Информационные науки . 553 : 208–224. arXiv : 1912.12667 . дои : 10.1016/j.ins.2020.11.011 . ISSN 0020-0255 . S2CID 209516398 .
- ^ Мартинелли, Рафаэль; Поджи, Маркус; Субраманян, Ананд (1 августа 2013 г.). «Улучшенные оценки для крупномасштабной задачи трассировки емкостной дуги» . Компьютеры и исследования операций . 40 (8): 2145–2160. дои : 10.1016/j.cor.2013.02.013 . ISSN 0305-0548 .
- ^ Вёлк, Санне; Лапорт, Гилберт (2 декабря 2018 г.). «Быстрая эвристика для решения крупномасштабных задач трассировки емкостной дуги» . Журнал Общества операционных исследований . 69 (12): 1877–1887. дои : 10.1080/01605682.2017.1415648 . ISSN 0160-5682 . S2CID 58021779 .
- ^ де Армас, Джесика; Кинан, Питер; Хуан, Анхель А.; МакГарраги, Шон (01 февраля 2019 г.). «Решение крупномасштабных задач маршрутизации дуг, зависящих от времени: от эвристики реального времени к метаэвристике» . Анналы исследования операций . 273 (1): 135–162. дои : 10.1007/s10479-018-2777-3 . ISSN 1572-9338 . S2CID 59222547 . Архивировано из оригинала 14 июля 2022 г. Проверено 14 июля 2022 г.
- ^ Чжан, Ючжоу; Мэй, Йи; Хуан, Шихуа; Чжэн, Синь; Чжан, Цуйцзюань (2021 г.). «Кластеризация маршрутов и эвристика поиска для крупномасштабной задачи маршрутизации дуг с несколькими депо» . Транзакции IEEE по кибернетике . 52 (8): 8286–8299. дои : 10.1109/TCYB.2020.3043265 . ISSN 2168-2275 . ПМИД 33531309 . S2CID 231787553 . Архивировано из оригинала 14 июля 2022 г. Проверено 14 июля 2022 г.
- ^ Шан, Жунхуа; Ду, Бинци; Дай, Кайюн; Цзяо, Личэн; Сюэ, Ю (01.06.2018). «Меметический алгоритм, основанный на шаге расширения и статистической фильтрации, для крупномасштабных задач маршрутизации емкостных дуг» . Естественные вычисления . 17 (2): 375–391. дои : 10.1007/s11047-016-9606-x . ISSN 1572-9796 . S2CID 12045910 . Архивировано из оригинала 14 июля 2022 г. Проверено 14 июля 2022 г.
- ^ Чжо, Эр; Дэн, Юньцзе; Су, Жевэй; Ян, Пэн; Юань, Бо; Яо, Синь (июнь 2019 г.). «Экспериментальное исследование проблем маршрутизации крупномасштабных транспортных средств» . Конгресс IEEE по эволюционным вычислениям (CEC) 2019 . стр. 1195–1202. дои : 10.1109/CEC.2019.8790042 . ISBN 978-1-7281-2153-6 . S2CID 199508674 . Архивировано из оригинала 14 июля 2022 г. Проверено 14 июля 2022 г.
- ^ Сяо, Цзяньхуа; Чжан, Тао; Ду, Цзинго; Чжан, Синъи (19 ноября 2019 г.). «Эволюционный многокритериальный эвристический алгоритм на основе группировки маршрутов для решения задач маршрутизации крупномасштабных транспортных средств» . Транзакции IEEE по кибернетике . 51 (8): 4173–4186. дои : 10.1109/TCYB.2019.2950626 . ISSN 2168-2275 . ПМИД 31751261 . S2CID 208227740 . Архивировано из оригинала 14 июля 2022 года . Проверено 14 июля 2022 г.
- ^ Кавальканти Коста, Жоау Гильерме; Мэй, Йи; Чжан, Мэнцзе (декабрь 2012 г.). «Критерий штрафа за обучение управляемого локального поиска для крупномасштабной задачи выбора маршрута транспортных средств» . Серия симпозиумов IEEE 2021 года по вычислительному интеллекту (SSCI) . стр. 1–8. дои : 10.1109/SSCI50451.2021.9659939 . ISBN 978-1-7281-9048-8 . S2CID 246288885 .
- ^ Аккорси, Лука; Виго, Даниэле (01 июля 2021 г.). «Быстрая и масштабируемая эвристика для решения крупномасштабных задач маршрутизации емких транспортных средств» . Транспортная наука . 55 (4): 832–856. дои : 10.1287/trsc.2021.1059 . hdl : 1871.1/afb5bb43-3ee8-4e81-8698-0e45644f89be . ISSN 0041-1655 . S2CID 234370340 . Архивировано из оригинала 14 июля 2022 г. Проверено 14 июля 2022 г.