Arxiv/An Empirical Investigation of Four Well-Known Polynomial-Size VRP Formulations 2018 1810.00199 — различия между версиями

«An Empirical Investigation of Four Well-Known Polynomial-Size VRP Formulations 2018 1810.00199»^{скачать}

Представлен углубленный вычислительный анализ четырех хорошо известных Формулировки задачи о маршрутизации емкостного транспортного средства (CVRP) с полиномиальным числом ограничений исключения субтуров: формулировка на основе узлов и три составы на основе дуги (одно-, двух- и многопродуктовые потоки).

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

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

Обширный вычислительный анализ охватывает 121 экземпляры с количеством клиентских узлов до 100. Мы считаем, что наши выводы могут быть полезно для практиков, а также исследователей, разрабатывающих алгоритмы для CVRP.