Расписание движения нескольких депо

Question

Я играю с алгоритмами и ILP для задачи диспетчеризации одного депо (SDVSP), и теперь хочу расширить свои знания в отношении задачи планирования множественного транспортного средства (MDVSP), поскольку я бы хотел использовать это знание в моем проекте.

Что касается вопроса, я нашел и реализовал несколько алгоритмов для MDSVP. Тем не менее, мне очень любопытно узнать, как определить количество необходимых складов (и мест размещения). К сожалению, мне не удалось найти какие-либо ресурсы, которые не предполагают/требуют, чтобы хранилища были установлены. Таким образом, мой вопрос будет следующим: как я смогу приблизиться к MDVSP, в котором я могу определить количество и расположение складов?

(Edit) Для уточнения: Пусть задано множество поездок T , T ... T _п, как правило, в SDVSP или MDVSP. После нескольких поездок вы можете вернуться в депо. Выход и возвращение на склады обычно происходит только в начале и в конце дня. Но в качестве дополнения к нормальным проблемам мы теперь можем определить количество и расположение наших складов, против того, чтобы установить депо.

Целью является найти решение, в котором все поездки управляются с минимальными затратами. Стоимость состоит из суммы мертвой точки (расстояние, на которое автомобиль должен путешествовать между поездками, а также от и до складов), фиксированная стоимость K за автомобиль и фиксированная стоимость C на депо.

Надеюсь, что это прояснит вопрос несколько.

Answer 1

Стандартный подход включает в себя добавление | V | двоичные переменные в ILP, по одному для каждого узла, где x_i = 1, если v_i является депо и 0 в противном случае.

Однако, как вопрос в настоящее время сформулирован, все значения x_i будут равны нулю, так как нет «преимущества» в том, чтобы сделать узел депо и общую стоимость = (другие факторы стоимости) + sum_i (x_i) * FIXED_COST_PER_DEPOT.

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