Методы оптимизации в системах автоматизированного проектирования трасс линейных сооружений

Валерий Струченков

Введение

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

Известно, что в одних и тех же условиях, располагая одной и той же информацией, разные специалисты предлагают различные варианты решений при проектировании трасс железных, автомобильных дорог и других линейных сооружений. В связи с этим интуитивное назначение вариантов в интерактивном режиме не гарантирует соответствия их оптимальному конечному результату. Даже небольшие изменения положения трассы на местности могут привести к существенным изменениям затрат на строительство и эксплуатацию дороги [1,2]. Следовательно, проблема разработки адекватных математических моделей и математически корректных алгоритмов оптимизации трасс новых дорог по­прежнему актуальна в научном плане. Однако из­за отсутствия заинтересованного потребителя на практике остается невостребованной. Тем не менее это направление наиболее перспективно в совершенствовании САПР линейных сооружений.

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

Опыт разработки и применения проектирующих программ

Целесообразность оптимизации проектов строительства таких дорогостоящих сооружений, как железные и автомобильные дороги, с использованием математических моделей, алгоритмов и компьютерных программ была установлена более 40 лет тому назад [3,4]. В частности, в условиях пересеченного рельефа и сложной геологии затраты на строительство и последующую эксплуатацию дороги могут быть существенно снижены при оптимальном расположении трассы на местности.

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

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

Существенные успехи были достигнуты при решении частной задачи: проектирования оптимального продольного профиля при заданном положении трассы в плане [3,4,5]. Решение этой частной задачи не только позволяет объективно сравнивать варианты плана трассы, назначаемые проектировщиками, но и имеет самостоятельное значение, поскольку при проектировании дорог в обжитых районах план трассы, как правило, определяется условиями землепользования.

Еще в начале 1960­х годов в Институте кибернетики АН УССР был разработан метод последовательного анализа вариантов [4], основанный на идеях динамического программирования. Первые реализации метода для проектирования продольного профиля новых железных дорог в силу упрощений, принятых из­за недостаточных возможностей ЭВМ того времени, оказались не вполне удачными. Тем не менее к 1976 году метод был реализован в чистом виде, были созданы работоспособные программы, проектирующие продольный профиль новой железной дороги для равнинного и пересеченного рельефов. Однако динамическое программирование при оптимизации по критерию минимума строительных затрат на участках, где грунты выемок используются для сооружения насыпей, применить не удалось из­за того, что возникает дополнительная взаимосвязь элементов искомой проектной линии в насыпях и выемках [5].

Более успешным было применение методов нелинейного программирования.

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

Программы, проектирующие продольный профиль, получившие практическое применение еще в 1970­х годах [5], были основаны на простых математических моделях:

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

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

Программа для БЭСМ­4, разработанная в 1971 году, могла проектировать локальные участки (до 5 км) [6], так как объем оперативной памяти ЭВМ был всего 4096 ячеек (45­разрядных), а решалась задача квадратического программирования размерностью до 100 переменных и 400 ограничений.

На реальных объектах, в частности при проектировании продольного профиля по вариантам трассы БАМ, была установлена высокая экономическая эффективность применения математических методов оптимизации и проектирующих программ. Достигалось снижение строительных затрат, зависящих от положения проектной линии, на 7­10% по сравнению с проектированием вручную. Конкретные примеры и их анализ приведены в книге [5].

 В то время снижение затрат труда и средств в строительстве за счет повышения качества проектов было актуальным, поэтому проектными институтами Мосгипротранс, Ленгипротранс и Сибгипротранс в плановом порядке использовалась соответствующая система «Профиль». Несмотря на крайне ограниченные возможности ЭВМ БЭСМ­4 только по вариантам трассы БАМ в 1970­х годах было запроектировано более 1200 км продольного профиля.

 В 80­х годах прошлого века широкое практическое применение получила и система «Профиль 2А» для проектирования новых автодорог и ее аналог — система «Профиль 2Р» для проектирования реконструкции автодорог [7]. С использованием этих систем к 1985 году на ЕС ЭВМ в РСФСР, УССР и УзССР было запроектировано более 3000 км новых автодорог и более 3800 км дорог, находящихся в состоянии капитального ремонта и реконструкции.

С помощью методов нелинейного программирования были решены задачи проектирования продольного профиля оросительных каналов (система «Профиль К»), водоводов, траншей для водо­ и газоснабжения. С применением системы «Профиль К» было запроектировано более 100 км каналов, сооружаемых методом «корыто — подушка».

 Проектирование каждого из упомянутых объектов имеет свою специфику. Это потребовало от разработчиков новых компьютерных программ для ЕС ЭВМ, которые пришли на смену БЭСМ­4 и «Минск­32». В дальнейшем, при переходе на персональные компьютеры, эти программы были полностью утрачены — в основном из­за отсутствия объектов применения. Подобные задачи могут решаться в интерактивном режиме в современных САПР, но с точки зрения качества проектных решений применение проектирующих программ представляется более предпочтительным.

В 1990­х годах из­за прекращения государственного финансирования соответствующие исследования и разработки были свернуты.

Система «Профиль 2А» к 1990 году была переработана применительно к одному из первых персональных компьютеров IBM PC IT­386 под управлением IBM PC DOS. Использовалась СУБД PARADOX­3. При переходе на современные операционные системы применение системы «Профиль 2А» прекратилось из­за резкого сокращения объемов проектирования и строительства дорог.

Методы нелинейного программирования использовались также при разработке алгоритмов и программ оптимизации трассы новой железной дороги на участках напряженного хода [8]. В этом случае проектная линия продольного профиля однозначно определяется планом трассы. Участки подъема и спуска предельными уклонами, сопрягаемые с применением максимальной разности уклонов, рассматривались совместно. При этом определялась оптимальная глубина перевальной выемки.

Экспериментальные расчеты на ЭВМ ЕС­1033 показали, что экономический эффект от оптимизации трассы на участках напряженного хода в несколько раз превосходит эффект от оптимизации только продольного профиля на участках вольного хода.

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

Проектирование трасс линейных сооружений в современных САПР

Наиболее продвинутыми из современных САПР, на наш взгляд, являются системы CAD­1 [9], CGS plus [10] и их отечественные аналоги Topomatic Robur [11] и GeoniCS [12]. В этих и подобных им системах проектное решение по положению трассы в плане и в продольном профиле, задаваемое проектировщиком, является определяющим. Проектирование плана и продольного профиля рассматривается как геометрическая задача в отрыве от решения других проектных задач, таких как проектирование поперечных профилей земляного полотна, выбор способов производства земляных работ и распределение земляных масс, проектирование водопропускных и других искусственных сооружений. В качестве дополнения к проектированию вручную предлагаются простейшие математические модели и алгоритмы оптимизации — в основном эвристические. В частности, в CAD­1 и Topomaic Robur наряду с проектированием продольного профиля вручную предлагается поиск оптимальной среднеквадратической аппроксимации профиля земли с помощью динамического программирования. Очевидно, что при этом не учитываются конструкции поперечных профилей земляного полотна, геология, наличие искусственных сооружений и др. Даже в случае математически корректного алгоритма оптимизации результат может рассматриваться как некоторое начальное приближение при проектировании в условиях пересеченного рельефа.

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

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

Характерны в этом отношении разработки компании Real Geo Project [13]. Так, для проектирования продольного профиля реконструируемых железных дорог разработана программа KORWIN, в которой «использован развитой математический аппарат. Для размещения переломов профиля используется вариантный подход на основе метода неявного (частичного) перебора» [13].

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

Идея отбраковки части допустимых вариантов реализована в таких математических методах, как динамическое программирование, метод ветвей и границ, а также в комбинированных методах [14]. Там эта отбраковка математически обоснована.

Интересна и программа AQUILA для расчета параметров элементов плана железнодорожного пути при его реконструкции [13]. В ней также реализован проектирующий алгоритм, но «при больших сдвигах по ходу расчета выводятся сообщения о промежуточных результатах, и пользователю предлагается решить, продолжать автоматический расчет или перейти к интерактивному режиму работы. В интерактивном режиме можно быстро решить практически любую проектную задачу, однако в автоматическом режиме ЭВМ иногда находит нестандартные и очень эффективные решения» [13]. Из этого утверждения можно понять, что, начиная расчет, пользователь не уверен, будет ли он завершен, либо придется решать задачу самому. При этом причины неприемлемых результатов останутся неизвестными. Математически корректный алгоритм должен дать оптимальное решение или сообщить об отсутствии допустимого решения вообще. Эффективные решения в пределах заданных пользователем норм и ограничений математически корректный алгоритм находит не иногда, а всегда. Эффективность работы такого алгоритма в сравнении с проектированием вручную или с другими алгоритмами зависит от сложности задачи и количества ограничений на искомое решение.

Новые разработки проектирующих систем

Из всех упомянутых нами проектирующих программ для ЕС ЭВМ и IBM PC 386, которые использовались ранее, к настоящему времени удалось развить и усовершенствовать только программы, предназначенные для проектирования плана и профиля новых и реконструируемых железных дорог. Разработка программ для проектирования автодорог находится в стадии завершения. В расчете на возможности современных общедоступных персональных компьютеров разработаны две системы: для проектирования трасс новых железных дорог и реконструируемых железных дорог СУБД PARADOX больше не используется. Программы разработаны в визуальной среде C++ Builder 6.

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

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

На первом этапе работы используется примитивная модель: поперечные профили земли принимаются односкатными, проектные поперечные профили —трапециевидными. Учитываются ограничения на продольные уклоны и разности уклонов смежных элементов. Ограничения на длину элементов не учитываются. Целевая функция соответствует сумме объемов насыпей и выемок. Проектная задача сводится к задаче выпуклого программирования с линейной системой ограничений, которая решается методом приведенного градиента [15,16]. Расчет на перегоне до 30 км занимает несколько минут. Полученная линия является основой для дальнейших расчетов. В зоне поиска шириной в несколько метров на каждом переломе профиля земли с заданным шагом изменения рабочих отметок проектируются проектные поперечные профили. При этом требуются задание геологии и выбор типовых правил проектирования насыпей и выемок из специально созданной библиотеки. Далее вычисляются площади проектных поперечников с учетом реальных поперечников земли и определяются параметры зависимости площадей насыпей и выемок от рабочих отметок по оси [15].

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

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

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

Далее задаются затраты в расчете на 1 м3 по видам земляных работ в соответствии с принятыми способами производства работ и распределением земляных масс. Теоретически эта задача была решена еще в 60­х годах [17].

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

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

Полученная проектная линия преобразуется к окончательному виду с помощью динамического программирования с незначительными отклонениями [15,18]. Результат рассматривается как начальное приближение для оптимизации по строительным затратам с помощью того же алгоритма нелинейного программирования.

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

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

На первом этапе с помощью динамического программирования строится начальное приближение, то есть определяется размерность задачи. На втором этапе с помощью метода нелинейного программирования второго порядка (DFP­оптимизация) [19] определяются оптимальные параметры элементов. Расчет ведется в координатной, а не в эвольвентной плоскости, как в ранних реализациях, с возможным заданием ограничений по сдвижкам существующей трассы (фиксированные точки, односторонние сдвижки и т.д.). Часть параметров может быть зафиксирована, что позволяет при повторных расчетах получать целочисленные значения радиусов, длин кривых и/или длин переходных кривых, кратных 10 м, как это принято на практике. Более того, программа позволяет избежать попадания переходных кривых на стрелочные переводы, мосты и другие заданные места, что является уникальным для программ этого назначения.

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

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

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

Заключение

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

1. Действующие САПР линейных сооружений имеют большой потенциал развития за счет использования комплексных математических моделей и современных математических методов оптимизации, в частности методов нелинейного программирования второго порядка.
2. Возможности современных вычислительных средств позволяют реализовать новую технологию совместного решения взаимосвязанных проектных задач, то есть создать системы проектирования с многочисленными обратными связями. Эта технология и соответствующие интеллектуальные САПР заменят действующую «линейную» технологию назначения вариантов положения трассы в плане и в профиле вручную с последующим решением на основе этих вариантов других проектных задач: проектирование земляного полотна, искусственных сооружений, распределения земляных масс и др. без корректировки положения трассы в плане и в профиле по результатам решения этих задач. Такая «линейная» технология с позиций системного анализа несостоятельна.
3. Решение взаимосвязанных проектных задач требует создания и использования иерархии математических моделей и методов при многократном повторении расчетов, то есть при реализации в специализированных САПР обратных связей, при наличии не только подсистемы проектирования плана трассы, продольного и поперечных профилей, но и подсистем проектирования искусственных сооружений, распределения земляных масс и др.
4. В силу наличия неформализуемых факторов творческий проектный процесс в любом случае имеет интерактивный характер, но компьютер следует использовать и для выработки проектных решений на основе математических моделей, математически корректных алгоритмов оптимизации и проектирующих программ. Использование для этой цели разного рода эвристических алгоритмов, особенно для задач, решенных ранее с помощью математически корректных алгоритмов, нецелесообразно.
5. Перспективы реализации сформулированных предложений, равно как и применение уже имеющихся программ оптимального проектирования в настоящее время сомнительны в силу сложившейся тенденции увеличения, а не снижения строительных затрат, реализации целей, далеких от экономии государственных средств, за счет которых ведется строительство, объемы которого к тому же незначительны.
6. Наличие математически корректных алгоритмов решения проектных задач позволяет путем проведения сопоставительных расчетов по идентичным входным данным получить оценку близости к оптимальному состоянию результатов, получаемых по разного рода эвристическим и генетическим алгоритмам. Предварительные результаты таких расчетов применительно к задаче проектирования плана трассы при реконструкции железных дорог (также выправке пути) показывают, что расхождения получаемых решений достаточно существенны.

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

Список литературы

1. Shafahi Yousef, Shahbazi M.J.Optimum railway alignment http://www.uic.org/cdrom/2001/wcrr2001/pdf/sp/2_1_1/210.pdf
2. Jha M.K., Schonfeld P.M., Yong J.­C., Kim E. Intelligent Road Design. WIT Press, Southampton. 2006.
3. Ляховский В.Н., Михалевич В.С., Быков В.И. Определение на ЭВМ наивыгоднейшего положения красной линии продольного профиля на вольном ходу // Транспортное строительство. 1962. № 4.
4. Михалевич В.С., Шор Н.З. Математические основы решения задачи выбора оптимального очертания продольного профиля. Труды Всесоюзного НИИ транспортного строительства. 1964. Вып. 51.
5. Использование математических методов оптимизации и ЭВМ при проектировании продольного профиля железных дорог. Труды Всесоюзного НИИ транспортного строительства. М.: Транспорт, 1977. Вып. 101.
6. Струченков В.И., Космин В.В., Фрадков Е.Б. Проектирование продольного профиля дороги на ЭВМ // Транспортное строительство. 1971. № 4.
7. Струченков В.И., Карих Ю.С., Шварц П.С. Математические методы оптимизации в системе автоматизированного проектирования дорог // Автомобильные дороги. 1980. № 12.
8. Струченков В.И., Шейдвассер Д.М. Оптимизация на ЭВМ трассы новой железной дороги на напряженных ходах // Транспортное строительство. 1987. № 3.
9. CARD/1. URL: http://www.card­1.com/en/home/
10. http://www.youtube.com/watch?feature=player_embedded&v=cHZXvlcpaAM#!
11. Тоpomatic Robur. URL: http:// www.topomatic.ru
12. Курилко Ю., Чешева В. Geonics ЖЕЛДОР­ САПР. CADmaster. 2007. № 1(36).
13. Бучкин В. Программные разработки компании Real Geo Project // САПР и графика. 2008. № 9.
14. Struchenkov V.I. Combined Algorithms of Optimal Resource Allocation // Applied Mathematics, 2012, № 3.
15. V.I. Struchenkov Mathematical Models and Optimization in Line Structure Routing: Survey and Advanced Results // International Journal Communication, Network and System Sciences. Special Issue: Models and Algorithms for Application. 2012. № 5.
16. Струченков В.И. Методы оптимизации в прикладных задачах. М.: Солон­Пресс. 2009.
17. Нефёдов П.П., Лопухов А.Е. Современный способ решения задачи распределения земляных масс // Транспортное строительство. 1964. № 4.
18. Струченков В. И., Козлов А.Н., Егунов А.С. Динамическое программирование в проектировании трасс линейных сооружений // Информационные технологии. 2011. № 8 (1180).
19. Численные методы условной оптимизации // Под ред. Ф. Гилл и У. Мюррей. Пер. с англ. М.: Мир. 1977.

Валерий Струченков

Д.т.н., профессор Московского государственного технического университета радиотехники, электроники и автоматики (МГТУ МИРЭА), факультет кибернетики. Почетный транспортный строитель СССР. Окончил МФТИ и аспирантуру мехмата МГУ. На протяжении 30 лет работал в НИИ транспортного строительства по созданию математических моделей, алгоритмов и программ проектирования трасс дорог и других линейных сооружений. В 1988 году защитил докторскую диссертацию на тему «Основы теории и методы оптимизации трасс железных дорог и других линейных объектов». В 70­х и 80­х годах разработки автора начали активно внедряться, но в 90­х были свернуты, как и в целом проектирование и строительство дорог в России. Автор трех монографий, изданных в России и Германии. Последняя из них — «Прикладные задачи и методы дискретной оптимизации» (Lambert Academic Publishing. Germany, 2012). В России, Германии и США издано более 100 статей, в том числе на английском языке.

САПР и графика 3`2013