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

Линейные сооружения (железные и автомобильные дороги, каналы, магистральные трубопроводы, траншеи для водо- и газоснабжения и др.) - это такие сооружения, положение которых на местности определяется линией (трассой), то есть осью сооружения. Трасса - это трёхмерная кривая, которая удовлетворяет целому ряду ограничений. Традиционно эта трёхмерная кривая представляется в виде двух плоских кривых: план и продольный профиль (рис. 3.13).

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

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

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

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

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

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

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

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

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

  • 1. На ординаты в отдельных точках Zj < Zjmax или Zj > Zjmin.
  • 2. На уклоны элементов профиля

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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