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

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