Лотарев Д. Т. - Неформальные описательные модели транспортных коммуникаций, транспортных сетей и территорий в задаче о прокладке путей и коммуникаций

Сети транспортных коммуникаций

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

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

Можно выделить следующие виды сетей.

1. Сеть может быть либо древовидной, либо с циклами. Это зависит от числа видов ресурса и от числа источников. Если в сети течет ресурс
одного вида, и существует только один источник этого ресурса, то сеть имеет вид дерева. Если при одном виде ресурса имеются несколько источников, то сеть представляет собой лес, и каждый источник является корнем какого-либо дерева этого леса. Если затраты на транспортировку потока велики по сравнению с затратами на строительство путей движения потока, то каждое дерево имеет вид звезды с прямолинейными лучами (например, воздушные пути). Центром такой звезды является источник. Если в сети текут потоки различных ресурсов и имеются объекты, каждый из которых является источником одного ресурса и потребителем другого, то в оптимальной сети могут быть циклы (в данной работе сети с циклами не рассматриваются).

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

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

4. Сети могут различаться по способу организации разветвлений. Возможны два способа организации разветвлений. При первом способе разветвления допускаются только в точках размещения источников и потребителей ресурсов. При втором способе – разветвления сети допускаются в любых точках территории, в которых допустимо размещение коммуникации. В случае, когда сеть размещается на однородном участке территории, и задачу можно рассматривать на плоскости, и транспортными затратами можно пренебречь, тогда первый способ организации разветвлений определяет задачу о минимальном связывающем дереве (Minimal spanning tree – MST), а второй способ – задачу о минимальном дереве Штейнера (Steiner minimal tree – SMT).

5. Задача о минимальном связывающем дереве без потока на однородной территории легко решается. Для этого существуют два алгоритма –
алгоритм Прима и алгоритм Краскала [9]. Если территория неоднородна, но затраты на транспортировку потока по-прежнему малы, то для размещения такой сети нужно сначала для всех пар объектов построить связывающие их минимальные пути. Множество таких путей образует полный граф, для которого легко построить остовное дерево, применив алгоритм Прима или Краскала.

6. Если затратами на транспортировку потока пренебречь нельзя, то даже в случае однородной территории и при одном источнике задача раз-
мещения сети (синтеза сети) существенно усложняется. В [10] описана возможность применения для этой цели метода динамического программирования в комбинации с методом ветвей и границ.

7. Если разветвления допускаются во всех точках участка территории, а участок является однородным по условиям строительства, и транспорт-ные затраты равны нулю, то задача размещения сети принимает вид задачи Штейнера на евклидовой плоскости. Результат решения задачи Штейнера на евклидовой плоскости – дерево Штейнера на этой плоскости. Основное отличие этого дерева от минимального связывающего – наличие дополнительных вершин, которые называются точками Штейнера. Дерево Штейнера короче минимального связывающего дерева (не более чем на 13,6 %). Но эта задача более сложная, чем задача о минимальном связывающем дереве на плоскости. Это NP-сложная задача. Задача о минимальном дереве Штейнера на плоскости представляет большой научный и практический интерес.

8. Если разветвления допускаются во всех точках плоскости, но потоком пренебречь нельзя, то задача вида задачи Штейнера на евклидовой плоскости сильно усложняется [11].

9. Если разветвления допускаются во всех точках участка, а участок не является однородным, то задача Штейнера также усложняется. Она ста-
новится задачей Штейнера на неоднородной территории. Подход к решению такой задачи приведен в [12]. Сначала для неоднородного участка строится цифровая модель местности, а затем ищется решение задачи Штейнера на этой модели как на графе.

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

11. Для сети, имеющей вид дерева Штейнера, важной является трехточечная задача Штейнера, в которой необходимо связать двух потребителей с одним источником. Задача интересна тем, что восходит еще к П. Ферма. Кроме того, задача о дереве Штейнера с одним источником и несколькими потребителями и на плоскости и на неоднородной территории допускает декомпозицию на ряд взаимосвязанных трехточечных задач [12].

Список использованной литературы

1. Лотарев Д. Т. Размещение коммуникаций на неоднородной территории // Автоматика и телемеханика. 2001. № 5. С. 44–52.

2. Лотарев Д. Т. Построение цифровой модели местности для территории с равнинным рельефом // Автоматика и телемеханика. 1998. № 8. С. 53–62.

3. Лотарев Д. Т. Цифровая модель местности для задачи размещения коммуникаций // Автоматика и телемеханика. 1999. № 12. С. 41–49.

4. Донгарян Ш. С., Каган Я. М., Горбатиков В. А., Ройзрах И. Б. Оптимизация систем обустройства нефтяных месторождений. Свердловск: Средне-Ураль- ское книжное издательство, 1976.

5. Эльсгольц Л. Э. Дифференциальные уравнения и вариационное исчисление. М.: URSS, 1998.

6. Цветков В. Я. Геоинформационные системы и технологии. М.: ФиС, 1998.

7. Форд Л. Р. Фалкерсон Д. Р. Потоки в сетях. М.: Мир. 1966.

8. Дейкстра Э. Дисциплина программирования. М.: Мир. 1978.

9. Емеличев И. А., Мельников В. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука. 1990.

10. Лотарев Д. Т. Синтез транспортной сети одного класса методом динамического программирования // Автоматика и телемеханика. 1989. № 2. С. 131–141.

11. Лотарев Д. Т. К вопросу построения транспортных сетей на разбуриваемой площади // РНТС «Нефтепромысловое строительство». ВНИИОЭНГ. 1974. № 5. С. 11–15. 12. Лотарев Д. Т., Уздемир А. П. Преобразование задачи Штейнера на евклидовой плоскости к задаче Штейнера на графе // Автоматика и телемеханика. 2005. № 10. С. 80–92.