Ладно, теперь о деле

anderson_mike — 14.02.2016 Многие из вас любят сложные алгоритмические задачки, олимпиадные, а также со звездочкой. Вот вам как раз такая, по информатике (ну, или математике). Весьма олимпиадная, а также принесет пользу народному хозяйству.

Имеется трамвайная линия из пункта А в пункт В, и обратно. Также на ней имеются места C, D, E, ..., где трамвай можно развернуть. Время в пути между всеми пунктами известно и для простоты не меняется. В момент времени t=0 на линии N вагнов, которые движутся с равномерными интервалами. В момент времени t=t₀ в определенной точке линии случается ДТП, и трамваи не могут ехать дальше этой точки, т.е. доехав до нее - упираются и тупо встают. Известно об этом становится в момент, равный t=t₁, t₁ > t₀. ДТП ликвидируют в момент времени t=t₂, известно об этом становится в t=t₃, t₃ > t₂.

Мы можем применять к трамваям следующие управляющие воздействия:
1) выдать команду трамваю изменить направление движения при подъезде к точкам C, D, E, ..., выставить трамваю время отправления из этих точек в обратный рейс.
2) выставить трамваю время отправления из точек А и В в следующий рейс.
Нельзя задавать время отправления раньше, чем время прибытия туда трамвая.

Там есть еще куча ограничений, связанных с трудовым кодексом, ёмкостью колец, заходом и выходом из депо, переключением на другие маршруты и с них и т.д., но это сделает задачу излишне сложной и оттого неинтересной.
Есть и более хитрые управляющие воздействия, но про них пока тоже не будем.

Задача: предложить алгоритм выдачи управляющих воздействий, при котором во время ДТП работа линии будет наиболее стабильна, а время восстановления нормальной работы линии после ДТП - минимальным. Раздача ЦУ начинается в момент времени t=t₁, когда время t₂ еще неизвестно.

Приз за лучшее решение - более лучше ходящие трамваи в нашем прекрасном городе. Да и троллейбусы с автобусами тоже, там задача весьма схожая.

Частные и вырожденные случаи, частичные решения, все что приходит в голову - кидайте в комменты.

Оставить комментарий

Популярные посты:

• Ранее
• Архив