интересно
Предыдущая | Содержание | Следующая

Решение задачи коммивояжера с привязкой к географическим координатам

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

Простейшая постановка задачи ^коммивояжера. Допустим, имеется множество М населенных пунктов. Необходимо составить такой маршрут посещения этих пунктов, который удовлетворял бы двум требованиям:

каждый пункт необходимо посетить только один раз;

длина маршрута должна быть минимальной.

Данная постановка предполагает два взаимосвязанных, но практически невыполнимых предположения:

коммивояжер (или транспортное средство) врегда может передвигаться в данном регионе по прямой линии;

вся поверхность региона - это идеально гладкая и твердая плоскость, пригодная для движения транспортных средств.

При такой постановке задачи можно использовать следующие методы составления маршрута: линейное программирование, метод ветвей и границ, динамическое программирование и алгоритм ближайшего непосещенного города. Первые три метода при большом числе населенных пунктов требуют применения ЭВМ большой мощности и создания довольно сложных расчетных программ, а четвертый метод дает решения, которые на 20-50% хуже оптимального (в зависимости от густоты и неравномерности расстояний между пунктами).

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

Постановка задачи коммивояжера с привязкой к дорожной сети. В регионе с развитой сетью дорог имеется:

множество М населенных пунктов;

множество N перекрестков (развилок) вне населенных пунктов;

множество К участков дорог.

Участком дороги назовем дорогу от пункта А до пункта Б, причем пункт - это населенный пункт или перекресток.

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

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

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

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

каждый пункт необходимо посетить только один раз;

длина маршрута должна быть минимальной;

при определении отрезков маршрута учитывается, что поверхность Земли - эллипсоид;

на маршруте могут работать один или два вертолета (если два -то они движутся навстречу друг другу).

Задача в данной постановке может решаться теми же методами.

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

Прежде чем перейти к описанию этого алгоритма, введем два определения и сформулируем одну теорему (без доказательства). Рассмотрим рис. 6.8. Предположим, что нужно составить полетное расписание для самолета, который вылетает из Санкт-Петербурга в Москву, причем он должен пролететь по кратчайшему маршруту над одиннадцатью промежуточными населенными пунктами. Предварительное расписание было составлено вручную и выдано экипажу самолета (табл. 6.2). Траектория маршрута показана на рисунке.

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

На рис. 6.8 пунктирным контуром 1 выделен неоптимальный участок, где установлен следующий порядок движения (полета):

Рига->Вильнюс->Балтийск-Минск.

Корректировка, проведенная экипажем, заключается в изменении порядка посещения (пролета). Оптимальным будет (это заметно на рисунке):

Рига- Балтийск-^Вильнюс- Минск.

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

На рис. 6.8 пунктирным контуром 2 выделен участок, имеющий характерную петлю. Точка А (угол Пинск-А-Хойники на пересечении траекторий Минск-Хойники и Пинск-Новозыбков) действительно находится за пределами населенных пунктов, через которые проходит маршрут.

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

Исходя из этой теоремы участок маршрута внутри контура 2 неоптимален. На нем установлен порядок:

Минск-Хойники->Киев->Пинск->Новозыбков.

После корректировки порядок изменится, а длина траектории уменьшится:

Минск-Пинск->Киев->Хойники->Новозыбков. В результате двух выполненных корректировок из исходного (псевдооптимального) полетного расписания получено расписание полета по оптимальному маршруту (табл. 6.3).

Алгоритм двух вертолетов. Допустим, имеется множество М населенных пунктов, которые нужно посетить. Сначала сделаем предварительные замечания о способах измерения расстояний между населенными пунктами. Для простоты будем считать, что их два:

при планировании вертолетных работ расстояние по поверхности Земли вычисляется с помощью функции geoway;

для действий с привязкой к дорожной сети расстояние определяется с помощью матрицы достижимости

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

простейшего - с использованием обычных инструментов (циркуль, курвиметр, линейка);

компьютерного - с помощью функции geoway.

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

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

с посещением

в частном случае могут принадлежать одному и тому же населенному пункту. Это самая общая постановка задачи.

имеют специальные признаки.

на место М в массиве space.

находятся два

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

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

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

- это элементы матрицы достижимости.

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

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

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

Перейдем к процедуре составления расписания. Присвоим начальные значения пунктам старта и финиша:

Построение маршрута начнем от пункта старта (только для определенности) и предположим, что уже выполнено х - 1 шагов этой процедуры (х = 1,2,..., М-2).

- операция объединения (сложения). Причем

- операция пересечения (умножения). Рассмотрим отдельно действия для каждого вертолета на шаге х. 1. Вертолет А. В множестве Т2 выбирается пункт Л*, имеющий минимальное значение выражения:

, то

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

2. Вертолет Б. В множестве Т2 выбирается пункт Л*, имеющий минимальное значение выражения:

После определения такого пункта делаются следующие изменения:

Если текущий путь вертолета Б станет таким, что G-i 2. G, то следующий шаг составления маршрута будет производиться для вертолета А, так как считаем, что он долетел до пункта / своей зоны ответственности. В противном случае следующий шаг составления расписания делаем в отношении вертолета Б.

Процедура составления маршрута делается всего за М-2 шагов, после чего множество 7г будет пустым, а Т - Т.

Рассмотренный метод был внедрен в практику работы оперативной группы при обследовании районов Брянской области, пострадавших в результате аварии на Чернобыльской АЭС. Проведенное моделирование позволило оценить максимальный эффект (в смысле дополнительного получения информации) по сравнению с расписанием, составленным вручную методом сканирования местности в сочетании с алгоритмом ближайшего непосещенного города. Результаты представлены в табл. 6.3.

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

пилоты эвристически применяют алгоритм ближайшего не-посещенного города;

вертолет затрачивает часть времени на посадки в населенных пунктах.

Реальный эффект в течение летней экспедиционной кампании 1989 г. составил 25 -35% экономии летного времени.

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

Выводы

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

Геоинформационные системы имеют следующие свойства:

в состав ГНС входят базы данных, причем полная технология обработки информации в ГИС значительно шире, чем просто работа с базой данных;

ГИС рассчитана не просто на обработку данных, а на проведение экспертных оценок во многих ситуациях;

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

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

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

Взаимное расположение точек на поверхности Земли в средних широтах, характерных для России, стран Европы и США, рекомендуется изображать на экране монитора в виде нормальной конической проекции.

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