Привет, КФ.
Возникла ИРЛ задача:
есть P(~10) точек, между каждой пары из которых известно время в пути;
есть N доставок, которые задаются точками from и to, а ещё временем появления t; есть L(~5) транспортов.
Нужно распределить доставки между транспортами чтобы время ожидание в худшем случае было как можно меньше.
Похоже, что её можно превратить в раскраску графа и там пошаманить с приближёнными решениями. Кто-нибудь умеет сводить?
Ещё будет интересно ваше мнение, какие частичные решения кажутся более точными и/или быстрыми. Постараюсь в итоге(если он будет) сравнить их.
UPD. Модифицировал условие. Теперь надо минимизировать максимальное ожидание для грузов.
А какого порядка N?
Где-нибудь 103 - 104.
По идее, оба варианта Вашей задачи (с временнЫм коридором и с минимизацией времени ожидания) — это, очевидно, обобщения задачи коммивояжера. Вот в эту сторону я бы на Вашем месте и копал.
UPD. ИМХО, лучше не тратить время впустую, а сразу искать англоязычные источники.