Алгоритм решения задачи моделирования транспортной системы

В ходе реализации задач данной работы целесообразно руководствоваться следующим алгоритмом:

• 1) Проанализировав предоставленную топологию автомобильных дорог, разбить участок S₀ — S_кон на оптимальное значение m шагов.
• 2) Исходя из принципа оптимальности, учесть, что путь из S₀ в S_кон разбит на m шагов, в каждом из которых машина перемещается с одной из опорных прямых (i) — (i) на следующую по порядку. Выбрать «узловые точки» (точки положения машины по итогам прохождения каждого шага) на каждой из прямых (i) — (i).
• 3) Опираясь на принципы динамического программирования, прокладывать маршрут из S_кон в S₀. Найти условное оптимальное управление для каждой точки на (6)-ом шаге, т. е. такой путь на предыдущий шаг, который, совместно с уже оптимизированным последним шагом, дает возможность достигнуть следующей опорной точки за минимальное время.
• 4) Проделать аналогичные операции для последующих шагов, кроме S₀.
• 5) Сравнивая полученные значения, выбрать оптимальный путь из точки S_кон в S₀ и нанести его на карту дорог (рисунок 4).

В соответствии с принципом оптимальности поставим задачу данной работы. Пусть нам нужно добраться на машине из пункта S₀ в пункт S_кон (рис.1). Вообще имеется целый ряд возможных вариантов пути. Они составлены из участков дорог, не равноценных по качеству. Среди них могут быть, например, участки первоклассных асфальтированных шоссе, а также менее благоустроенных и просто проселочных дорог. Кроме того, на пути нам могут встретиться перекрестки и переезды, на которых движение задерживается.

Задача состоит в том, чтобы выбрать такой путь из S₀ в S_кон, который машина пройдет за минимальное время. Несмотря на кажущуюся простоту, эта задача имеет некоторые особенности. Исходя из алгоритма решения, нам необходимо построить регулярную сетку узловых точек, через которые могла бы проходить траектория кратчайшего пути. Но в этой задаче роль такой сетки узловых точек могли бы играть естественно отмеченные «особые точки» сети дорог — перекрестки и переезды, но они расположены слишком нерегулярно, и их затруднительно «упорядочить по шагам». Для того чтобы приближенно решить нашу задачу методом динамического программирования, можно ввести в нее искусственно некоторую «поэтапность». Например, можно разделить расстояние D от S₀ до S_кон на m равных частей длиной? D = D/m (рис. 1) и считать, что за каждый «шаг» процесса перемещения из S₀ в S_кон преодолевается m-ю часть расстояния D (по направлению S₀ — S_кон). Другими словами, каждый «шаг» представляет собой перемещение с одной из опорных прямых, перпендикулярных S₀ — S_кон, на соседнюю, более близкую к S_кон.

Деля процесс на шаги таким образом, мы, естественно, должны условиться, что перемещение от шага к шагу допускается только в положительном направлении (т. е. от S₀ к S_кон, а не обратно); иными словами, после того как определенный шаг пройден, возвращение обратно, в ту же полосу между двумя опорными прямыми, не допускается. Такое ограничение представляется достаточно приемлемым для нашей задачи (в итоге каждого шага перемещаться только «туда», по направлению S₀ — S_кон, а не «обратно»), так как оно действует только от шага к шагу, не внутри шага, и к тому же только по одной оси (в случае надобности от этого ограничения можно освободиться, но при этом решение сильно усложняется).

Итак, предположим, что путь из S₀ в S_кон разбит на m шагов, в каждом из которых машина перемещается с одной из опорных прямых (i) — (i) на следующую по порядку.

(i+1) -(i+1) (i = 0,1,…m).

Проведенные нами опорные прямые пересекают дорожную сеть в каких-то точках, которые принято называть «узловыми». На рисунке 2 представлено распределение «узловых» точек на карте дорожной системы.

Рисунок 2 Карта «узловых» точек транспортной системы Для решения задачи нам должно быть известно время, требуемое для прохода каждого участка пути, а также время задержки на каждом перекрестке (переезде). На рис. 1 против каждого отрезка пути проставлено соответствующее время прохода (в минутах), а в кружке у каждого перекрестка (переезда) — время ожидания машины в данном пункте.

Согласно количеству опорных прямых на рис. 1 процесс перемещения машины из S₀ в S_кон мы разделим на семь шагов (т. е. примем m = 7) и начнем построение оптимального пути с последнего (m — 1)-го шага.

Наметим на опорной прямой (m-1) — (m-1) все возможные положения машины в момент окончания предпоследнего ((m-1)-го) шага. Это будут гипотезы о состоянии машины после (m-1)-го шага, для каждой из которых мы должны найти условное оптимальное управление на m-м шаге. На рис. 1 эти возможные положения отмечены кружком с точкой внутри. Из каждого такого положения мы должны выбрать оптимальный (кратчайший по времени) путь в точку S_кон.

Рассмотрим сначала первую (сверху) из отмеченных точек — точку, А на прямой (m — 1) — (m-1). Из нее в точку S_кон (в пределах полосы m-го шага) ведет один-единственный путь, занимающий по времени:

(минуты).

Выбор этого пути представляет собой условное оптимальное управление при условии, что предыдущий шаг привел нас в точку А. Отметим на рисунке 2 этот оптимальный путь черной жирной линией, а у точки, А выставим «флажок» с записанным на нем обозначением A₆.

Жирная линия вместе с флажком означают следующее: если, перемещаясь из S₀ в S_кон, мы какими-то судьбами оказались в точке А, то из нее мы должны двигаться дальше по отмеченному черной линией маршруту и на достижение точки S_кон затратим A₆ минут.

Переходим к следующей точке (В) на прямой (m- 1) — (m- 1). Из нее в точку S_кон ведет один-единственный путь, на который требуется:

(минут).

Индекс B₆ также записываем на флажке рядом с точкой В.

Для точки С путь снова единственный и продолжается:

(минут).

Решение, полученное нами на данном этапе, изобразим на рисунке 3.

Рисунок 3 Расчет оптимального управления на первом шаге Из точки D в S_кон есть два пути. Скорейший из них отмечаем жирной линией и записываем минимальное время на флажке у точки D.

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

После того как это выполнено, переходим к планированию (m — 1)-го шага. Гипотезы о том, где может находиться машина после предпредпоследнего (m — 2)-го шага, отмечены треугольниками на прямой (m — 2) — (m — 2).

Для каждой из отмеченных точек мы должны найти условное оптимальное управление, т. е. такой путь с прямой (m-2) — (m- 2) на прямую (m-1) — (m-1), который, совместно с уже оптимизированным последним шагом, дает возможность достигнуть S_кон за минимальное время. Чтобы найти это условное оптимальное управление, мы должны для каждой точки на прямой (m-2) — (m-2) перебрать все возможные способы перехода на прямую (m-1) — (m-1) и время, потребное на этот переход, сложить с минимальным временем последнего шага, записанным на флажке. Из всех возможных путей выбирается тот, для которого это суммарное время минимально; путь отмечается черной линией, а время записывается на флажке у соответствующей точки.

В результате цепочки таких построений, перемещаясь шаг за шагом с одной опорной прямой на другую, мы, наконец, дойдем до исходной точки S₀. Для нее мы определим оптимальный путь на прямую (1) — (1) и запишем соответствующее минимальное время на флажке у точки S₀. Таким образом, все данные для построения оптимального пути есть, так как для каждой из намеченных точек (какими бы судьбами мы в ней ни оказались) известно оптимальное продолжение пути. Чтобы построить оптимальный путь из S₀ в S_кон, нужно просто перемещаться по участкам дорог, отмеченным жирными линиями. На рисунке 4 оптимальная траектория из S₀ в S_кон отмечена жирной линией.

Важным моментом при решении задач методом динамического программирования является выбор числа шагов. Кажется, что для простоты решения, желательно было бы разбить дорогу на меньшее число шагов. Однако это не совсем так. Чем крупнее шаг, тем труднее находить оптимальное решение на этом шаге, тем больше существует вариантов перемещения с прямой на прямую. В предельном случае, если бы мы рассмотрели только один шаг (m= 1), перед нами встала бы исходная задача перебора всех возможных путей из S₀ в S_кон во всей ее сложности. Однако это не значит, что требуется увеличение числа шагов. Выведение его за какие-то разумные пределы только усложнило бы процедуру построения решения.

Рисунок 4 Оптимальный путь из S0 в Sкон В том, что выбранное нами число шагов (m = 7) довольно разумно, можно убедиться по тому, что нам нигде не приходилось перебирать большого числа вариантов перехода с прямой на прямую — этих вариантов оказывалось один, два, редко три, и найти среди них оптимальный было не слишком трудно. Если бы мы сильно увеличили число шагов, т. е. чрезмерно измельчили участки перехода, то в подавляющем большинстве случаев с прямой на прямую вел бы один-единственный путь, и никакой оптимизации не было бы. В конечном итоге мы построили бы ту же оптимальную траекторию, но путем более сложных расчетов.