Все выпуски

В различных приложениях возникают задачи, моделируемые уравнениями в частных производных на графах (сетях, деревьях). Для исследования данных проблем и возникающих различных экстремальных ситуаций, для задач проектирования и оптимизации сетей различных типов в данной работе построена вычислительная модель, основанная на решении соответствующих краевых задач для нелинейных уравнений в частных производных гиперболического типа на графах (сетях, деревьях). В качестве приложений были выбраны три различные задачи, решаемые в рамках общего подхода сетевых вычислительных моделей. Первая — это моделирование движения транспортных потоков. При решении данной задачи использовался макроскопический подход, при котором транспортный поток описывается нелинейной системой гиперболических уравнений второго порядка. Проведенные расчеты и полученные результаты показали, что разработанная в рамках предложенного подхода модель хорошо воспроизводит реальную ситуацию на различных участках транспортной сети г. Москвы на значительных временных интервалах, а также может быть использована для выбора наиболее оптимальной стратегии организации дорожного движения в городе. Вторая — моделирование потоков данных в компьютерных сетях. В этой задаче потоки данных различных соединений в пакетной сети передачи данных моделировались в виде несмешивающихся потоков сплошной среды. Предложены концептуальная и математическая модели сети. Проведено численное моделирование в сравнении с системой имитационного моделирования сети NS-2. Полученные результаты показали, что в сравнении с пакетной моделью NS-2 разработанная нами потоковая модель демонстрирует значительную экономию вычислительных ресурсов, обеспечивая при этом хорошую степень подобия, и позволяет моделировать поведение сложных глобально распределенных IP-сетей передачи данных. Третья — моделирование распространения газовых примесей в вентиляционных сетях. Была разработана вычислительная математическая модель распространения мелкодисперсных или газовых примесей в вентиляционных сетях с использованием уравнений газовой динамики путем численного сопряжения областей разной размерности. Проведенные расчеты показали, что модель с хорошей точностью позволяет определять распределение газодинамических параметров в трубопроводной сети и решать задачи динамического управления вентиляцией.

В статье рассматривается разработка алгоритма шумоподавления на основе анизотропной нелинейной фильтрации данных. Анализ отечественной и зарубежной литературы показал, что наиболее эффективные алгоритмы шумоподавления данных рентгеновской компьютерной томографии применяют комплекс нелинейных методик анализа и обработки данных, таких как билатеральная, адаптивная, трехмерная фильтрации. Однако комбинация таких методик редко применяется на практике ввиду большого времени обработки данных. В связи с этим было принято решение разработать эффективный и быстродейственный алгоритм шумоподавления на основе упрощенных билатеральных фильтров с трехмерным накоплением данных. Алгоритм был разработан на языке C++11 в программной среде Microsoft Visual Studio 2015. Основным отличием разработанного алгоритма шумоподавления является применение в нем улучшенной математической модели шума на основе распределения Пуассона и Гаусса от логарифмической величины, разработанной ранее. Это позволило точнее определить уровень шума и тем самым порог обработки данных. В результате работы алгоритма шумоподавления были получены обработанные данные компьютерной томографии с пониженным уровнем шума. При визуальной оценке работы алгоритма были отмечены повышенная информативность обработанных данных по сравнению с оригиналом, четкость отображения гомогенных областей и значительное сокращение шума в областях обработки. При оценке численных результатов обработки было выявлено снижение уровня среднеквадратичного отклонения более чем в 6 раз в областях, подвергшихся шумоподавлению, а высокие показатели коэффициента детерминации показали, что данные не подверглись искажению и изменились только из-за удаления шумов. Применение разработанного универсального динамического порога, принцип работы которого основан на пороговых критериях, позволил снизить уровень шума во всем массиве данных более чем в 6 раз. Динамический порог хорошо вписывается как в разработанный алгоритм шумоподавления на основе анизотропной нелинейной фильтрации, так и другой алгоритм шумоподавления. Алгоритм успешно функционирует в составе рабочей станции MultiVox, получил высокую оценку своей работы от специалистов-рентгенологов, а также готовится к внедрению в единую радиологическую сеть города Москвы в качестве модуля.

В данной работе рассматривается задача восстановления матрицы корреспонденций для наблюдений реальных корреспонденций в г. Москве. Следуя общепринятому подходу [Гасников и др., 2013], транспортная сеть рассматривается как ориентированный граф, дуги которого соответствуют участкам дороги, а вершины графа — районы, из которых выезжают / в которые въезжают участники движения. Число жителей города считается постоянным. Задача восстановления матрицы корреспонденций состоит в расчете всех корреспонденций израйона $i$ в район $j$.

Для восстановления матрицы предлагается использовать один из наиболее популярных в урбанистике способов расчета матрицы корреспонценций — энтропийная модель. В работе, в соответствии с работой [Вильсон, 1978], приводится описание эволюционного обоснования энтропийной модели, описывается основная идея перехода к решению задачи энтропийно-линейного программирования (ЭЛП) при расчете матрицы корреспонденций. Для решения полученной задачи ЭЛП предлагается перейти к двойственной задаче и решать задачу относительно двойственных переменных. В работе описывается несколько численных методов оптимизации для решения данной задачи: алгоритм Синхорна и ускоренный алгоритм Синхорна. Далее приводятся численные эксперименты для следующих вариантов функций затрат: линейная функция затрат и сумма степенной и логарифмической функции затрат. В данных функциях затраты представляют из себя некоторую комбинацию среднего времени в пути и расстояния между районами, которая зависит от параметров. Для каждого набора параметров функции затрат рассчитывается матрица корреспонденций и далее оценивается качество восстановленной матрицы относительно известной матрицы корреспонденций. Мы предполагаем, что шум в восстановленной матрице корреспонденций является гауссовским, в результате в качестве метрики качества выступает среднеквадратичное отклонение. Данная задача представляет из себя задачу невыпуклой оптимизации. В статье приводится обзор безградиенных методов оптимизации для решения невыпуклых задач. Так как число параметров функции затрат небольшое, для определения оптимальных параметров функции затрат было выбрано использовать метод перебора по сетке значений. Таким образом, для каждого набора параметров рассчитывается матрица корреспонденций и далее оценивается качество восстановленной матрицы относительно известной матрицы корреспонденций. Далее по минимальному значению невязки для каждой функции затрат определяется, для какой функции затрат и при каких значениях параметров восстановленная матрица наилучшим образом описывает реальные корреспонденции.

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

Традиционные методы решения задачи коммивояжера не являются эффективными для задач высокой размерности из-за их высокой вычислительной сложности. Одним из эффективных способов решения этой проблемы является декомпозиционный подход, который включает в себя три основных этапа: кластеризацию вершин, решение подзадач внутри каждого кластера и последующее объединение полученных решений в итоговое. В данной статье основное внимание уделяется третьему этапу — объединению циклов решений подзадач, поскольку этому этапу не всегда уделяется должное внимание, что приводит к менее точному итоговому решению. В статье предлагается новый модифицированный алгоритм Сигала для объединения циклов. Для оценки его эффективности проводится сравнение с двумя алгоритмами объединения циклов: метод соединения средних точек ребер и алгоритм на основе близости центроидов кластеров. Исследуется зависимость качества решения подзадач на алгоритмы объединения циклов. Модифицированный алгоритм Сигала выполняет попарное объединение кластеров, минимизируя количество пересечений и общее расстояние. Метод центроидов ориентирован на соединение кластеров на основе близости центроидов, а алгоритм с использованием средних точек оценивает расстояние между средними точками ребер. Также были рассмотрены два типа кластеризации: алгоритмы k-means и affinity propagation. Для проверки эффективности предложенного алгоритма были проведены численные эксперименты на наборе данных TSPLIB с различным количеством городов. В исследовании анализируются ошибки, вызванные порядком объединения кластеров, качеством решения подзадач и количеством кластеров. Эксперименты показали, что модифицированный алгоритм Сигала демонстрирует наименьшую медиану итогового расстояния и наиболее устойчивые результаты по сравнению с другими методами. Результаты указывают на большую устойчивость качества конечного решения, полученным модифицированным алгоритмом Сигала, от последовательности объединения кластеров. Повышение качества решения подзадачи обычно приводит к линейному улучшению конечного решения, но используемый алгоритм объединения редко влияет на степень этого улучшения.

Улично-дорожная сеть является основой инфраструктуры любой урбанистической территории. В данной статье сравниваются структурные характеристики (коэффициент сетчатости, коэффициент кластеризации) дорожных сетей центра Москвы (старая Москва), сформированных в результате самоорганизации, и сети дорог вблизи Ленинского проспекта (послевоенная Москва), которая формировалась в процессе централизованного планирования. Данные для построения дорожных сетей в виде первичных графов взяты из интернет-ресурса OpenStreetMap, позволяющего точно идентифицировать координаты перекрестков. По вычисленным характеристикам в зарубежных публикациях найдены города, дорожные сети которых имеют сходные с этими двумя районами Москвы структуры. С учетом двойственного представления дорожных сетей центров Москвы и Петербурга, изучались информационно-когнитивные свойства навигации по этим туристическим районам двух столиц. При построении двойственного графа исследуемых районов не принимались во внимание различия в типах дорог (одностороннее или двусторонне движение и т. п.). То есть построенные двойственные графы являются неориентированным. Поскольку дорожные сети в двойственном представлении описываются степенным законом распределения вершин по числу ребер (являются безмасштабными сетями), вычислены показатели степеней этих распределений. Показано, что информационная сложность двойственного графа центра Москвы превышает когнитивный порог в 8.1 бит, а этот же показатель для центра Петербурга ниже этого порога. Это объясняется тем, что дорожная сеть центра Петербурга создавалась на основе планирования и потому более проста для навигации. В заключение, с использованием методов статистической механики (метод расчета статистических сумм) для дорожных сетей некоторых российских городов, вычислялась энтропия Гиббса. Обнаружено, что с ростом размеров дорожных сетей их энтропия уменьшается. Обсуждаются задачи изучения эволюции сетей городской инфраструктуры различной природы (сети общественного транспорта, снабжения, коммуникации и т. д.), что позволит более глубоко исследовать и понять фундаментальные закономерности процесса урбанизации.

В работе описывается двухстадийная модель равновесного распределения транспортных потоков. Модель состоит из двух блоков, где первый блок — модель расчета матрицы корреспонденций, а второй блок — модель равновесного распределения транспортных потоков по путям. Первая модель, используя матрицу транспортных затрат (затраты на перемещение из одного района в другой, в данном случае — время), рассчитывает матрицу корреспонденций, описывающую потребности в объемах передвижения из одного района в другой район. Для решения этой задачи предлагается использовать один из наиболее популярных в урбанистике способов расчета матрицы корреспонценций — энтропийную модель. Вторая модель на базе равновесного принципа Нэша–Вардропа (каждый водитель выбирает кратчайший для себя путь) описывает, как именно потребности в перемещениях, задаваемые матрицей корреспонденций, распределяются по возможным путям. Таким образом, зная способы распределения потоков по путям, можно рассчитать матрицу затрат. Равновесием в двухстадийной модели транспортных потоков называют неподвижную точку цепочки из этих двух моделей. Практически ранее отмеченную задачу поиска неподвижной точки решали методом простых итераций. К сожалению, на данный момент вопрос сходимости и оценки скорости сходимости для этого метода не изучен. Кроме того, при численной реализации алгоритма возникает множество проблем. В частности, при неудачном выборе точки старта возникают ситуации, в которых алгоритм требует вычисления экстремально больших чисел и превышает размер доступной памяти даже в самых современных вычислительных машинах. Поэтому в статье предложены способ сведения задачи поиска описанного равновесия к задаче выпуклой негладкой оптимизации и численный способ решения полученной задачи оптимизации. Для обоих методов решения задачи были проведены численные эксперименты. Авторами использовались данные для Владивостока (для этого была обработана информация из различных источников и собрана в новый пакет) и двух небольших городов США. Методом простой прогонки двух блоков сходимости добиться не удалось, тогда как вторая модель для того же набора данных продемонстрировала скорость сходимости $k^{−1.67}$.

В статье рассматривается одна из задач транспортного моделирования — поиск равновесного распределения транспортных потоков в сети. Для описания временных издержек и распределения потоков в сети, представляемой с помощью графа, используется классическая модель Бэкмана. При этом поведение агентов не является полностью рациональным, что описывается посредством введения марковской логит-динамики: в каждый момент времени водительвыбирает маршрут случайно согласно распределению Гиббса с учетом текущих временных затрат на ребрах графа. Таким образом, задача сводится к поиску стационарного распределения для данной динамики, которое является стохастическим равновесием Нэша – Вардропа в соответствующей популяционной игре загрузки транспортной сети. Так как данная игра является потенциальной, эта задача эквивалентна минимизации некоторого функционала от распределения потоков, причем стохастичностьпро является в появлении энтропийной регуляризации. Для полученной задачи оптимизации построена двойственная задача. Для ее решения применен универсальный прямо-двойственный градиентный метод. Его особенность заключается в адаптивной настройке на локальную гладкость задачи, что особенно важно при сложной структуре целевой функции и невозможности априорно оценитьг ладкость с приемлемой точностью. Такая ситуация имеет место в рассматриваемой задаче, так как свойства функции сильно зависят от транспортного графа, на который мы не накладываем сильных ограничений. В статье приводится описание алгоритма, в том числе подробно рассмотрено применение численного дифференцирования для вычисления значения и градиента целевой функции. В работе представлены теоретическая оценка времени работы алгоритма и результаты численных экспериментов на примере небольшого американского города.

В статье представлена классификация городов с учетом планировочных особенностей и возможных транспортных решений для городов различных типов. Также обсуждаются примеры различных стратегий развития городского общественного транспорта в России и странах Европейского союза с сопоставлением их эффективности. В статье приводятся примеры влияния городского планирования на мобильность граждан. Для реализации сложных стратегических решений необходимо использовать микро- и макромодели, которые позволяют сравнивать ситуации «как есть» и «как будет» для прогнозирования последствий. Кроме того, авторы предлагают методику совершенствования маршрутной сети общественного транспорта и улично-дорожной сети, которая включает определение потребностей населения в трудовых и учебных корреспонденциях, идентификацию узких мест улично-дорожной сети, разработку имитационных моделей и выработку рекомендаций по результатам эксперимента на моделях, а также расчет эффективности, включающий расчет положительного социального эффекта, экономическую эффективность, повышение экологичности и устойчивости городской транспортной системы. Для обоснования предложенной методологии были построены макро- и микромодели исследуемого города с учетом пространственной планировки и других особенностей города. Таким образом, на примере города Набережные Челны показано, что использование нашей методологии может помочь улучшить ситуацию на дорогах за счет оптимизации сети автобусных маршрутов и дорожной инфраструктуры. Результаты показали, что при реализации предложенных решений можно уменьшить транспортную нагрузку на узкие места, количество перекрывающихся автобусных маршрутов, а также плотность движения.