Проблема с трассировкой емкостной дуги

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

Существует множество различных вариантов CARP, описанных в книге Трассировка по дуге: проблемы, методы и приложения» . Анхеля Корберана и Жильбера Лапорта « ^[1]

Решение CARP включает изучение теории графов, маршрутизации дуг, исследования операций и алгоритмов географической маршрутизации для эффективного поиска кратчайшего пути .

CARP — это NP-сложная задача маршрутизации дуги .

CARP можно решить с помощью комбинаторной оптимизации, включая выпуклые оболочки .

Задача крупномасштабной маршрутизации емкостной дуги (LSCARP) — это вариант задачи маршрутизации емкостной дуги, которая применяется к сотням ребер и узлов для реалистичного моделирования и моделирования больших сложных сред. ^[2]

Ссылки

^ Принс, Кристиан (05 февраля 2015 г.), «Глава 7: Проблема маршрутизации емкостной дуги: эвристика» , Arc Routing , Серия MOS-SIAM по оптимизации, Общество промышленной и прикладной математики, стр. 131–157, doi : 10.1137 /1.9781611973679.ch7 , ISBN 978-1-61197-366-2 , получено 14 июля 2022 г.
^ Мэй, Йи; Ли, Сяодун; Яо, Синь (июнь 2014 г.). «Кооперативная коэволюция с группировкой расстояний маршрутов для решения крупномасштабных задач маршрутизации емкостной дуги» . Транзакции IEEE в эволюционных вычислениях . 18 (3): 435–449. дои : 10.1109/TEVC.2013.2281503 . ISSN 1089-778X . S2CID 4851980 .

[1] Принс, Кристиан (05 февраля 2015 г.), «Глава 7: Проблема маршрутизации емкостной дуги: эвристика» , Arc Routing , Серия MOS-SIAM по оптимизации, Общество промышленной и прикладной математики, стр. 131–157, doi : 10.1137 /1.9781611973679.ch7 , ISBN 978-1-61197-366-2 , получено 14 июля 2022 г.

[2] Мэй, Йи; Ли, Сяодун; Яо, Синь (июнь 2014 г.). «Кооперативная коэволюция с группировкой расстояний маршрутов для решения крупномасштабных задач маршрутизации емкостной дуги» . Транзакции IEEE в эволюционных вычислениях . 18 (3): 435–449. дои : 10.1109/TEVC.2013.2281503 . ISSN 1089-778X . S2CID 4851980 .

[1]

[2]