Как смоделировать распределение транспортных средств для поездок, возможно, используя Linear/Integer/Mixed math?

Question

Как смоделировать распределение транспортных средств для поездок, возможно, используя Linear/Integer/Mixed math?

В городе 10 автобусных маршрутов. Необходимо совершить 50 поездок на автобусах. У нас есть 6 автобусов. Мы знаем, что в любой момент времени не более 6 рейсов одновременно. Нам нужно распределить 6 автобусов на 50 поездок таким образом, чтобы использование шин было максимальным. Мы хотим минимизировать время простоя автобусов.

Мы хотим определить автобус, который необходимо развернуть для каждой поездки. Может ли это быть смоделировано как линейная / целочисленная / смешанная целочисленно-линейная задача? Если так, как мы моделируем вышеупомянутую проблему?

Если нет, какую технику нужно использовать?

С уважением

0

mathematical-optimization linear-programming cplex constraint-programming

Источник

user764626 27 окт '15 в 05:07

1 ответ

Решение

Другие вопросы по тегам mathematical-optimization linear-programming cplex constraint-programming

user472109 28 окт '15 в 08:33 2015-10-28 08:33 · Accepted Answer · 2015-10-28 08:33

Это называется проблемой маршрутизации транспортных средств (VRP), возможно, с временными окнами (VRPTW). В обычном VRPTW клиент имеет 1 местоположение (и продолжительность обслуживания). В этом VRPTW bustrip (= клиент в оригинальном VRPTW) имеет другую точку прибытия и отправления (и большую продолжительность обслуживания), поэтому вы в основном планируете маршруты между автобусными остановками (= клиенты в оригинальном VRPTW).

Есть несколько способов решить эту проблему, см., Например, мое видео о решении VRPTW с открытой структурой метаэвристики. IIRC, академический Roadef Challenge 2010 или 2008 года, имел такую проблему с расписанием автобусов. Вы, вероятно, найдете хороший список статей по этому вопросу, чтобы подробно описать, какой алгоритм работает хорошо.