Эвристические методы

Два основных аспекта определяют особенности транспортных задач для реальных сетей:

а) размерность задач очень велика – это означает, что существует много переменных и много ограничений;

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

Эти особенности имеют несколько важных последствий.

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

С точки зрения эвристического подхода следует рассмотреть некоторые пути упрощения исходной задачи, которые могут быть «встроены» в машинный алгоритм.

К нм можно отнести:

1) упрощение задачи за счет игнорирования некоторых ограничений или путем замены сложных ограничений более простыми;

2) расчленение задачи (основной сложной) на более легкие подзадачи;

3) игнорирование взаимозависимости подзадач;

4) отыскания начального допустимого решения;

5) попытка улучшить начальное допустимое решение в итеративном процессе (т.е. в циклическом процессе);

6) отбрасывание решений или множества решений, которые не являются перспективными.

Рассмотрим в качестве примера эвристического подхода так называемую непрерывную оптимальную корректировку задачи.

Мы будем иметь дело с задачей минимизации затрат при данной матрице поездок и при дескриптивном распределении (т.е., при распределении, оптимизируемом пользователем).

В общем виде эта задача формулируется так: требуется найти

при условиях (основные сетевые ограничения)

Или в другой постановке: требуется найти

при условиях:

- сетевые ограничения заданы;

- матрица поездок задана.

Идея непрерывной оптимальной корректировки задачи состоит в том, что попеременно игнорируются то ограничения в задаче, то сама процедура оптимизации.

Процесс расчета начинается с распределения матрицы поездок по исходной сети, что означает, что учитываются имеющиеся ограничения.

Тогда получается поток транспорта для каждой дуги . Затем решается задача без ограничений (задача безусловной оптимизации):

.

Такая процедура представляет собой не что иное, как в раз более простую математически задачу, где Е – множество дуг сети.

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

Получающаяся при этом новая сеть, характеризующаяся , далее используется как новая сеть, по которой распределяется матрица поездок.

Таким образом, теперь задача формулируется так: найти такой вектор потоков , при котором будут удовлетворяться сетевые ограничения

Этот процесс продолжается до тех пор, пока изменения в целевой функции не станут слишком малыми:

,

где ‑ заданная норма близости.

Таким образом, этот процесс ведет к достаточно хорошим решениям, но не обязательно к оптимуму.

Можно показать, что этот процесс имеет место в действительности.

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

Это – типичный пример эвристической процедуры. Он является имитацией определенного процесса принятия решения человеком, обеспечивает улучшение на каждом шаге вычислений.

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

Рисунок 26 – Дорожная сеть с тоннелем

Итак, дорога 1 короткая, но дорогая по затратам на её расширение. Дорога 2 длинная, но дешёвая по затратам на её расширение.

Предположим, что в начальном решении по методу непрерывной оптимальной корректировки присутствуют обе дороги.

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

Поэтому становится необходимым расширять дорогу 1, несмотря на то, что она дорогая.

После этого на следующем шаге вычислений дорога 1 стала еще более привлекательной для пользователей. Поэтому поток по ней снова будет расти.

Благодаря этому эффекту вновь оказывается необходимым делать капитальные вложения в дорогу 1, хотя она и дорогая.

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

В этом случае дескриптивное распределение потоков на сети превалирует над нормативным, и общество в целом терпит убытки.

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

Однако следует отметить, что все эти методы в той или иной степени используют упрощения первоначальной сети.

Эти упрощения становятся возможными в силу наличия иерархической структуры любой реальной транспортной сети.

Например, в г. Самаре можно условно выделить транспортные магистрали «первого уровня» ‑ это Московское шоссе, проспект Кирова, улица Ново-Садовая, улица Победы. К магистралям «второго уровня» можно отнести улицы Самарскую, Молодогвардейскую, Гагарина, проспект Масленникова, Волжский проспект и др. К дорогам «третьего уровня» можно, например, отнести улицы Ерошевского, Лукачёва, Льва Толстого и др.

Иерархическая структура дорог позволяет применять такие приемы как агрегирование и декомпозиция.

При агрегировании некоторые переменные объединяются в одну переменную с целью уменьшения размерности задачи.

Агрегирование может быть выполнено человеком на стадии постановки задачи или в ЭВМ, если разработан соответствующий алгоритм агрегирования.

Существуют два важных типа агрегирования в транспортных сетях:

а) агрегирование зон;

б) агрегирование дуг.

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

Агрегирование дуг означает, что мы включаем в качестве дуг сети существующие или возможные дороги не полностью, а только уменьшаем их количество.

При этом существуют два основных принципа:

а) исключение дуг;

б) объединение дуг.

Исключение дуг означает, что мы просто отбрасываем несущественные дуги сети. Объединение дуг означает укрупнение исходной сети с одновременным уменьшением общего числа дуг.