Проектирование оптимальных трасс линейных сооружений

Линейные сооружения (железные и автомобильные дороги, каналы, магистральные трубопроводы, траншеи для водо- и газоснабжения и др.) — это такие сооружения, положение которых на местности определяется линией (трассой), то есть осью сооружения. Трасса — это трехмерная кривая, которая удовлетворяет целому ряду ограничений. Традиционно эта трехмерная кривая представляется в виде двух плоских кривых: план и продольный профиль (рис. 2.13). План — это проекция трассы на координатную плоскость XOY, а продольный профиль — это зависимость аппликаты z от длины дуги в плане. Продольный профиль получается при развертке на плоскость цилиндрической вертикальной поверхности, проходящей через трассу. У этой поверхности образующая параллельна оси OZ, а направляющая — это план трассы. Вертикальная цилиндрическая поверхность пересекает поверхность земли и при развертке на плоскость линия пересечения превращается в продольный профиль земли по трассе. Таким образом получается профиль земли и профиль трассы или исходный и проектный профиль соответственно. Задача проектирования оптимальной трассы превращается в две взаимосвязанные задачи: проектирование плана и проектирование продольного профиля. Обычно варианты плана трассы намечают вручную, по каждому из них строят продольный профиль земли и по нему проектируют продольный профиль трассы. На положение трассы влияют рельеф земли, геологические, гидрологические, климатические и другие условия. Оптимальному варианту должны соответствовать минимальные затраты на строительство и последующую эксплуатацию сооружения.

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

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

Представление трассы

Рис. 2.13. Представление трассы: а) план, Ь) продольный профиль

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

В продольном профиле. Элементы продольного профиля — это отрезки прямых, так что проектная линия ломаная, на элементы которой также накладываются ограничения. Если обозначить профиль земли H(s), а проектную линию Z(s), то в первом приближении задача состоит в следующем. По заданной H(s) найти такую ломаную Z(s), чтобы она удовлетворяла всем ограничениям и был

где Sq — длина трассы в плане, а функция F(H (s) — Z(s)) моделирует затраты на элементе длины.

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

Зная число и длины элементов (в плане) искомой ломаной, можно аналитически выразить все ограничения на продольный профиль Z(s), если принять в качестве неизвестных zx ординаты в точках перелома (i = 1,2, ..., п). Эти ограничения делятся на три группы.

1. На ординаты в отдельных точках z < Zjmax или Z > Zjmin.

2. На уклоны элементов профиля

(i = 1,2,..., п — 1). Здесь Sj — длины элементов. Это ограничение является дискретным аналогом ограничения на первую производную.

3. На разности уклонов смежных элементов

Это ограничение является дискретным аналогом ограничения на вторую производную.

Задача поиска оптимальной трассы новой железной дороги, соединяющей две заданные точки, была одной из первых задач оптимального проектирования, которую в нашей стране предлагалось решать с помощью метода динамического программирования. Эти предложения относятся к началу 60-х годов и связаны с применением метода последовательного анализа вариантов [13], который по существу отличается от метода динамического программирования только названием.

Задача проектирования оптимальной трассы в целом (план + профиль) состоит в поиске трехмерной кривой и не сводится к поиску оптимального пути на двумерной сетке.

Основной фактор, влияющий на положение трассы, — это рельеф местности. Попытки игнорировать или как-то усреднить рельеф по отдельным участкам местности, с тем чтобы свести задачу поиска пространственной кривой (трассы) к поиску ее проекции на горизонтальную плоскость (плана) не привели, да и не могли привести к практическим результатам. В этой связи приводимые в ряде работ (см., в частности, [4] с. 88—98) примеры поиска оптимальной трассы как оптимального пути на двумерной сетке следует рассматривать как учебные, не имеющие никакого отношения к реальной проектной задаче.

Проектирование трассы — пространственной кривой можно рассматривать как поиск оптимального пути на трехмерной сетке. Но при этом надо учитывать ограничения на ее элементы в плане и в профиле, которые серьезно осложняют задачу. По этой причине метод динамического программирования применялся для проектирования оптимального продольного профиля при заданном положении трассы в плане, то есть для поиска плоской кривой. Эта задача может рассматриваться как аппроксимация заданной ломаной линии (профиль земли) другой ломаной линией (проектный профиль), удовлетворяющей ряду ограничений. Если целевая функция может вычисляться последовательно по элементам (до того как построена вся ломаная), то задача распадается на ряд этапов.

Проектирование продольного профиля дороги

Рис. 2.14. Проектирование продольного профиля дороги

Очередной этап — это поиск очередного звена ломаной. В этом случае задача действительно сводится к поиску оптимального пути на двумерной сетке, располагаемой относительно профиля земли (на рис. 2.14 он показан жирной линией).

Дискретность по вертикали вводится искусственно, причем из-за наличия ограничений по уклонам и разностям уклонов смежных элементов точки на вертикалях должны располагаться достаточно часто. В данной задаче 0,01 м это значимая величина.

Итак, «состояние системы» на конкретном этапе — это точка на соответствующей вертикали, а «управление» или «шаговый переход» это отрезок, соединяющий две точки на смежных вертикалях. Естественно, рассматриваются только допустимые по ограничениям точки на вертикалях и их соединения. Начиная со второй вертикали, при достижении любого из состояний несколькими путями, они сравниваются и остается путь (вариант) с меньшим значением целевой функции (сравнение «в точку»). Именно этот алгоритм был реализован еше в 60-х годах [13]. Если число точек на каждой вертикали равно к, а число проектируемых элементов равно п, то всего приходилось вычислять целевую функцию примерно на nk2 элементах, примерно столько же раз проверять выполнение ограничений и запоминать примерно 2nk чисел, что не так уж и много для реальных задач. При разработке алгоритма отмечалось, что он не вполне соответствует принципу оптимальности Р. Веллмана. Действительно, при наличии ограничений на разность уклонов, варианты, сходящиеся в точке, сравнивать нельзя, так как возможные продолжения отброшенного варианта могут не содержаться среди возможных продолжений оставшегося. На рис. 2.14 варианты, сходящиеся в точке Е, имеют разные возможности для дальнейшего участия в построении проектной линии. Продолжения варианта СЕ содержатся в секторе MCENC (показан пунктирной линией), а продолжения варианта DE в секторе MDEND (показан сплошной линией). Эти сектора не только не совпадают, но и в реальных задачах могут вообще не иметь ничего общего (не пересекаться) при малых допустимых значениях разности уклонов смежных элементов. Так, если один вариант приходит в общую точку снизу (уклон имеет знак плюс), а другой сверху (уклон имеет знак минус), то разность их уклонов может превышать удвоенную допустимую разность уклонов смежных элементов. Положительный уклон и на следующем элементе останется положительным, а отрицательный останется отрицательным. Получается, что для дальнейшего имеет значение не только «состояние системы», но и то, как оно достигнуто, то есть «предыстория». Реализация алгоритма последовательного анализа вариантов в строгом соответствии с методом динамического программирования требует другой формализации понятия «состояние системы» и, соответственно, другого правила сравнения и отбраковки вариантов. Если считать состоянием не точку, т. е. возможную вершину искомой ломаной, а элемент ломаной, то сравнимыми становятся только варианты, у которых последний элемент общий (сравнение «в отрезок»). При этом число проверяемых связей на выполнение ограничений по разности уклонов составляет примерно nk3 вместо nk2. А количество запоминаемых чисел также возрастает примерно в к раз. Естественно, можно хранить значения целевой функции только для состояний (отрезков) последнего из пройденных этапов, но для восстановления траектории при обратном развороте, связи с состояниями на предыдущих этапах надо хранить все.

Из-за большого числа запоминаемых данных даже при упрощенном правиле отбраковки вариантов («сравнение в точку») задачу приходилось решать в несколько этапов. На первом этапе использовали сетку с крупными ячейками, но относительно малым числом точек на каждой вертикали, а на втором этапе разбивали более мелкую сетку вокруг полученного решения. Это часто используемый эвристический прием, который не гарантирует нахождение оптимума [20, с. 380].

Реально число дискретов на вертикали порядка нескольких десятков. Например, при ширине зоны поиска 5 м и дискретности поиска 0,1 м (что довольно грубо) уже получаем к = 50. Поэтому переход к «сравнению в отрезок» требовал существенно более мощных ЭВМ, чем те, что были доступны в 60-х годах. Это и объясняет попытку реализации некорректного алгоритма. Предполагалось, что при этом могут получаться решения, незначительно отклоняющиеся от оптимальных. Но реально оказалось все значительно хуже, так как в условиях пересеченного рельефа при наличии многочисленных ограничений алгоритм с упрощенным правилом отбраковки вариантов вообще останавливался из-за «вырождения» вариантов. Это происходило из-за того, что при отбраковке вариантов оставались элементы с такими уклонами, что для выхода в конечную точку на заданный уклон или на фиксированную точку «не хватало места для разворота и набора высоты», то есть ограничения по разности уклонов не позволяли продолжить процесс построения элементов.

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

В дальнейшем (к 1975 г.) с ростом мощности доступных ЭВМ разработчиками метода последовательного анализа вариантов был реализован метод динамического программирования в «чистом» виде (сравнение в «отрезок») и создан работоспособный комплекс программ. Но к тому времени выяснилось, что в условиях пересеченного рельефа исходное предположение о том, что целевую функцию можно вычислять по элементам, не имея всей проектной линии, чаще всего не выполняется. Дело в том, что при строительстве дорог насыпи сооружаются из грунта выемок и, если этого грунта недостаточно, используется привозной грунт. Строительные затраты существенным образом зависят не только от объемов работ, но и от соотношения объемов насыпей и выемок, грунт которых можно использовать. Но это соотношение меняется при вариациях проектной линии. Оптимум чаще всего соответствует балансу грунтов. При оптимизации не объемов работ, а стоимостей нужно задать единичные затраты (на 1 м3) по насыпям и выемкам, которые различны при различном соотношении объемов грунта в насыпях и в выемках. Оказалось, что при задании единичных затрат в расчете на использование только грунта выемок для соружения насыпей, как правило, получается вариант с недостатком грунта в выемках и наоборот — при задании единичных затрат в расчете на привозной грунт для сооружения насыпей в результате оптимизации получается вариант проектной линии, по которому объемы выемок больше объемов насыпей, и привозной грунт не нужен. Другими словами, результат не соответствует исходным предположениям и единичным затратам, то есть исходным данным. Получается, что для вычисления значения целевой функции нужно иметь проектную линию полностью, вычислить соответствующие ей объемы работ и только потом строительные затраты. Это означает неприменимость динамического программирования при решении задачи с учетом данного фактора, который никак нельзя считать второстепенным. Именно поэтому задача была решена методами нелинейного программирования, которые на каждой итерации имеют дело с проектной линией как с единым целым [18].

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

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

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >