Перекресток

Постановка задачи

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

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

Решение

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

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

Загруженностью дороги будем называть отношение числа автомобилей, проезжающих по дороге за какой-нибудь период времени, к максимально возможному числу автомобилей, которые могут проехать по этой дороге за тот же период времени. Будем считать, что для каждого направления машины прибывают на перекресток равномерно, то есть загруженность дорог в каждом направлении является постоянной. Кроме того, будем считать, что загруженность дороги Север-Юг (и дороги Запад-Восток) одинакова в обоих направлениях. Пусть загруженность дороги Север-Юг (в обе стороны) составляет \(v_1\), а дороги Запад-Восток — \(v_2\) (\(0\leq v_1, v_2 \leq 1\)). Будем считать, что дороги имеют одинаковую ширину (это предположение соответствует тому, что мы видим на картинке) и, соответственно, одинаковую максимальную пропускную способность. Тогда и максимальная пропускная способность перекрестка будет совпадать с максимальной пропускной способностью каждой из дорог.

Долю времени горения зеленого света на направлении Север-Юг обозначим за \(t_1\), долю времени горения зеленого света на направлении Запад-Восток — за \(t_2 = 1 - t_1\).

Слишком много машин

Очевидно, что если \(v_1 + v_2 > 1\), то на перекрестке будет накапливаться пробка, независимо от того, как мы отрегулируем светофор.

Максимально возможное количество машин

Если \(v_1 + v_2 = 1\), то для избежания пробки необходимо, чтобы доли времени, которые горит зеленый на дорогах Север-Юг и Запад-Восток, также составляли \(v_1\) и \(v_2\). То есть, \(t_1 = v_1\), \(t_2 = v_2\). Пусть \(T\) cекунд — период времени, за который светофор на перекрестке полностью проходит один цикл (горит красный, горит зеленый). Определим, при каком значении \(T\) среднее время ожидания машины на светофоре будет минимальным. Поскольку мы предполагаем, что машины прибывают на перекресток равномерно и рассматриваем случай, когда на светофоре не образуется пробка, то для определения среднего времени ожидания достаточно посчитать среднее время ожидания в рамках одного цикла. На дороге Запад-Восток красный горит в течение времени \(v_1 T\) секунд, после чего в течение времени \(v_2 T\) секунд горит зеленый. Пусть промежуток времени между двумя машинами на этом направлении составляет \(m_1\) секунд (он постоянен, поскольку мы предположили, что для любого направления машины прибывают на перекресток равномерно. Кроме того, заметим, что \(m_1\) однозначно определяется из показателя максимальной пропускной способности дорог и значения \(v_1\). Например, если при максимальной загруженности промежуток между двумя машинами составляет \(M\) cекунд, то \(m_1 = \frac{M}{v_1}\)). Тогда для машин, прибывающих на перекресток, пока горит красный, время ожидания будет составлять \(v_1 T, v_1 T - m_1, v_1 T - 2m_1, \dots\). Будем считать, что для машин, прибывающих на перекресток, когда горит зеленый, время ожидания равно нулю. Таким образом, суммарное время ожидания за цикл составит \[\sum\limits_{i=0}^{\left[\frac{T v_1}{m_1}\right]} (Tv_1 - im_1).\]

Проделаем некоторые преобразования:

\[\sum\limits_{i=0}^{\left[\frac{T v_1}{m_1}\right]} (Tv_1 - im_1) = \left(\left[\frac{T v_1}{m_1}\right]+1\right)Tv_1 - m_1\frac{\left[\frac{T v_1}{m_1}\right]\left(\left[\frac{T v_1}{m_1}\right]+1\right)}{2}.\]

Для простоты перейдем от \(\left[\frac{T v_1}{m_1}\right]\) к \(\frac{T v_1}{m_1}\), существенного влияния на характер этого выражения как функции от \(T\) такое преобразование не окажет: в тех точках, где \(Tv_1\) делится на \(m_1\) нацело, старая и новая функции будут совпадать.

\[\left(\left[\frac{T v_1}{m_1}\right]+1\right)Tv_1 - m_1\frac{\left[\frac{T v_1}{m_1}\right]\left(\left[\frac{T v_1}{m_1}\right]+1\right)}{2} \approx \left(\frac{T v_1}{m_1}+1\right)Tv_1 - m_1\frac{\frac{T v_1}{m_1}\left(\frac{T v_1}{m_1}+1\right)}{2} = \frac{T v_1\left(\frac{T v_1}{m_1}+1\right)}{2}\]

Количество машин, приезжающих на перекресток за \(T\) секунд, равно \(\frac{T}{m_1}\), поэтому среднее время ожидания равно

\[\frac{T v_1\left(\frac{T v_1}{m_1}+1\right)}{2\frac{T}{m_1}} = \frac{v_1\left(Tv_1+m_1\right)}{2}.\]

Функция линейна по \(T\), таким образом, среднее время ожидания будет тем меньше, чем меньше \(T\).

Для дороги Север-Юг функция будет аналогичной, с заменой \(v_1\) на \(v_2\) и \(m_1\) на \(m_2\).

Дополнительным ограничением на значение \(T\) является необходимость отрегулировать пешеходный переход. Исходя из наших предположений, зеленый на нем горит тогда же, когда на дороге Север-Юг, время горения зеленого составляет \(v_1 T\) секунд. Будем считать, что любое количество пешеходов, скопившееся за время горения красного, способно перейти дорогу на зеленый, если он горит в течении времени, достаточного для перехода одного человека. Кажется разумным предположить, что 20 секунд будет достаточно для перехода дороги пешеходами.

Таким образом, время \(v_1 T\) горения зеленого на дороге Север-Юг должно составлять 20 секунд (делать меньше нельзя, потому что пешеходы могут не успеть перейти дорогу, а увеличение времени увеличит среднее время ожидания машины на перекрестке), а время горения красного (оно же время горения зеленого на дороге Запад-Восток):

\[T - v_1 T = T - 20 = \frac{20}{v_1} - 20.\]

Замерив интенсивность движения, мы можем настроить светофоры по этой формуле.

Не слишком много машин

В ситуации, когда \(v_1 + v_2 < 1\), у нас есть возможность варьировать выбор доли зеленого и красного для цикла светофора. Если обозначить за \(t_1\) долю зеленого для дороги Север-Юг, то мы получим следующее ограничение на \(t_1\):

\[v_1\leq t_1 \leq 1 - v_2\]

(в предыдущем случае оба раза имело место строгое равенство).

В качестве цели для оптимизации выберем достижение минимального значения максимума среднего времени ожидания для машин по каждому направлению (то есть если по СЮ время ожидания равно 10 а по ЗВ — 15, то это хуже, чем если время ожидания равно 13 по обоим направлениям).

Формулы для среднего значения ожидания по обеим дорогам будут такие же, как в предыдущем пункте, с поправкой на то, что мы не можем просто заменить \(t_i\) на \(v_i\). \[E_{EW}=\frac{t_1\left(Tt_1+m_1\right)}{2},\] \[E_{NS}=\frac{t_2\left(Tt_2+m_2\right)}{2}=\frac{(1-t_1)\left(T(1-t_1)+m_2\right)}{2}.\]

При фиксированном \(T\) обе функции представляют собой квадратичные параболы. На интересующем нас интервале \([v_1,1-v_2]\) функция ожидания на дороге Запад-Восток возрастает (что логично, когда увеличивается доля зеленого для второй дороги), а функция ожидания на дороге Север-Юг убывает. Точка, в которой минимизируется максимум значений этих двух функций, — это точка, в которой значения функций совпадают.

\[\frac{t_1\left(Tt_1+m_1\right)}{2}=\frac{(1-t_1)\left(T(1-t_1)+m_2\right)}{2},\] \[t_1\left(Tt_1+m_1\right)=(1-t_1)\left(T-Tt_1+m_2\right),\] \[Tt_1^2+m_1t_1 = T-Tt_1+m_2 - Tt_1 + Tt_1^2 - m_2t_1,\] \[t_1(m_1 + 2T + m_2)=T + m_2,\] \[t_1 = \frac{T + m_2}{m_1+2T+m_2}.\]

Соответственно, \(t_2 = \frac{T + m_1}{m_1+2T+m_2}.\)

Таким образом, для любого \(T\) мы можем вычислить регулировку светофора. Вспомним, что функции ожидания все еще линейны по \(T\) и чем меньше \(T\), тем меньше среднее ожидание. Для определения нижней границы, так же как и раньше, воспользуемся требованием к пешеходному переходу:

\[t_1T=20,\] \[\frac{T(T + m_2)}{m_1+2T+m_2}= 20,\] \[T^2+(m_2-40)T - 20(m_1+m_2)=0.\]

Это квадратное уравнение с одним положительным корнем, \(T_+=\frac{40 - m_2 + \sqrt{m_2^2 + 80m_1 + 1600}}{2}\). Замерив частоту проезда машин по перекрестку, мы сможем вычислить значение \(T\), а затем и значение \(t_1\), что даст нам полную информацию по настройке светофоров.

Альтернативные варианты

В альтернативных вариантах мы можем перенаправить отдельные потоки машин на другие перекрестки.

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

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

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