Автоматика и телемеханика, № 6, 2013
Системный анализ и исследование операций
© 2013 г. А.Л. КАЗАКОВ, д-р физ.-мат. наук, А.А. ЛЕМПЕРТ, канд. физ.-мат. наук, Д.С. БУХАРОВ
(Институт динамики систем и теории управления СО РАН, Иркутск)
К ВОПРОСУ О СЕГМЕНТАЦИИ ЛОГИСТИЧЕСКИХ ЗОН ДЛЯ ОБСЛУЖИВАНИЯ НЕПРЕРЫВНО РАСПРЕДЕЛЕННЫХ ПОТРЕБИТЕЛЕЙ1
Исследуется задача о размещении нескольких логистических объектов. Особенностью задачи является необходимость последовательной сегментации на зоны обслуживания и учета населения непрерывно распределенного по всей области. Задача сведена к задаче вариационного исчисления специального вида. Для исследования задачи разработаны численные алгоритмы, позволяющие определять оптимальное расположение логистического объекта в пределах заданного сегмента. Алгоритмы основаны на построении фронтов световой волны, выпущенной с границы выделенной области. Движение волны осуществляется внутрь области, что позволяет учесть всех жителей на данной территории. При построении решения учитывается проблема потери гладкости фронта волны. Выполнена программная реализация вычислительных алгоритмов и проведён вычислительный эксперимент на ряде модельных задач.
1. Введение
Задачи оптимизации, возникающие при математическом моделировании на транспорте и в транспортной логистике, отличаются спецификой, связанной с разнородностью и географическим расположением объектов исследования, и в ряде случаев не могут быть эффективно решены с помощью классических методов. Это приводит к необходимости разработки методики их численного решения в ситуациях, когда построение точного решения оказывается проблематичным.
В данной работе исследуется задача об оптимальном размещении нескольких логистических объектов с одновременной сегментацией логистических зон, при этом потребители непрерывно распределены на всем полигоне обслуживания. Для исследования задачи разработана модификация оптико-геометрического подхода, основанная на построении фронтов световой вол-
1 Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных исследований (проекты №№ 11-07-00245, 12-07-33045_мол_а_вед, 12-07-13116_ОФИ_м_РЖД, 12- 07-31080_мол_а).
ны в случае, когда начальным источником возбуждения является некоторое многообразие (в отличие от точечного источника в [1]).
Как правило, для решения этого класса задач успешно применяются дискретные методы, однако при исследовании некоторых прикладных задач при этом возникает ряд сложностей, например невозможность полного учета специфических условий задач (ландшафт, распределение населения, наличие естественных и искусственных барьеров). Одним из способов преодоления указанных трудностей, по мнению авторов, является рассмотрение таких задач в непрерывной постановке и применение для их исследования оптико-геометрического подхода.
Ранее в работах члена-корреспондента РАН В.Н. Ушакова и его учеников [2, 3] подобный подход применялся при решении задач управления подвижными объектами на плоскости при наличии фазовых ограничений. Численная реализация основывалась на построении множеств достижимости. В [4] оптическая аналогия использовалась при решении задач безопасности, каждая из которых сводилась к задаче маршрутизации. Такая же аналогия применялась и в [5, 6], распространение волны рассматривалось как процесс возбуждения на заданном многообразии нейронов.
Решая задачу о размещении логистических объектов с точки зрения безопасности (например, спасательные пункты, хранилища токсичных и радиоактивных отходов), требуется учитывать все населённые пункты на заданном полигоне, в том числе и с малым числом жителей, при этом потребители непрерывно распределены на всем полигоне обслуживания, т.е. плотность населения задается непрерывной функцией. Ключевой особенностью задачи является необходимость последовательной сегментации полигона и определения внутри каждого сегмента оптимального расположения логистического центра.
При решении задачи о размещении логистических объектов возникает необходимость организации средств коммуникаций (дорог, электрических сетей и информационных каналов), прокладка которых должна производиться с минимально возможными затратами, что приводит к решению задачи Штейнера [7]. В рассматриваемой задаче требуется соединить т городов дорогами (или каналами связи), суммарная длина которых минимальна. Для получения дорог минимальной суммарной длины допускается введение точек ветвления (точек Штейнера). Впервые задача для т = 3 поставлена Ферма [7, 8], а решение задачи получено Торричелли. Общий случай (т > 3) задачи исследовался геометром Штейнером. Наибольшее развитие получило решение задачи Штейнера на графах [9, 10] и разработан обширный аппарат решения задачи. В [11] отмечено совпадение структуры деревьев в задачах Штейнера на плоскости и на графе, поэтому решение задачи Штейнера на графе принимается как решение задачи на плоскости.
В настоящей работе представлены математическая постановка и численный алгоритм решения задачи о размещении нескольких логистических объектов с последовательной сегментацией на зоны обслуживания. Исследуется задача Штейнера специального вида, и представлен алгоритм ее решения. Полученные результаты являются непосредственным развитием работы [1].
2. Метод решения
При решении задачи о размещении логистических объектов при непрерывно распределенных потребителях возникает необходимость построения фронтов волны внутрь исследуемой области, граница которой образует начальное многообразие источников светового возбуждения. Опишем модификацию оптико-геометрического подхода, применяемую для конструирования фронтов волны в оптически неоднородной среде.
Оптическая среда характеризуется множеством точек, в которых определено значение коэффициента проницаемости среды /(ж, у), изменяющее скорость прохождения светового луча. Скорость света тем выше, чем больше значение проницаемости оптической среды.
Согласно принципу Гюйгенса каждая точка среды, достигнутая фронтом световой волны, становится самостоятельным источником света. Представим оптическую среду как прямоугольную систему координат ж и у. Пусть в некоторой ограниченной области Б имеется базисная кривая, на которой происходит световое возбуждение в момент времени £ = 0. От каждой точки базисной кривой перпендикулярно к ней откладывается некоторое расстояние Дз через минимальный временной интервал Д£ = е. Таким образом, строится кривая, близкая к базисной, известная как эквидистанта [12]. Построенная линия образует многообразие вторичных источников света. Аналогичное построение осуществляется до тех пор, пока не будет заполнена вся рассматриваемая область Б. В результате через каждую точку области Б будет проходить фронт световой волны.
Расстояние Дз характеризует некоторый прямолинейный отрезок пути. Так как каждый отрезок откладывается перпендикулярно к базисной кривой, то известно направление построения, обеспечивающее корректную идентификацию связей между соседними точками. Эта особенность позволяет однозначно определить маршрут передвижения.
Покажем, что определяемый таким образом маршрут дает минимум по времени. Пусть оптическая среда является неоднородной, г(ж,у) и /(ж, у) -скорость света и значение проницаемости среды в точке (ж, у) соответственно. Откладываемое от начального многообразия источников света расстояние равно Дз = гД£ (Д£ = е). Так как среда является неоднородной, то скорость света меняется от точки к точке г(ж,у) = с/(ж, у), где с - скорость света в вакууме.
Если /(ж, у) задано во всех точках области Б, то бесконечно малое расстояние Дз = с/(ж, у)Д£ можно отложить от всех точек базисной кривой, а затем многократно повторить процесс построения. Если в оптической среде Б имеется непроходимый барьер Бь € Б с проницаемостью /ь = 0, то построить фронт в области Бь не представляется возможным.
На рис. 1 изображены фронты световой волны и траектории лучей, распространяющихся в оптически неоднородной среде. Оптическая проницаемость является однородной / = еош^ Построена траектория движения луча света Гх, состоящего из совокупности отрезков, отложенных перпендикулярно к каждому фронту Ф^, г = 0,п — 1. Луч Г1 выпускается из точки М, расположенной на базисной кривой Фо, и заканчивается в точке N на кривой Фп.
Рис. 2. Фронты световой волны: а - эллипс, б - фрагмент кривой.
Построена и другая траектория Г2 с краевыми точками М и N, «промежуточные» отрезки которой проходят неперпендикулярно к фронтам Фг, г = = 0, п - 1.
Время, затрачиваемое на преодоление маршрута Г1, составляет ¿1 = в, а на преодоление маршрута Г2 требуется
¿2 =
п— 1 1
. п С08 вг
г=0
где в г - угол отклонения от перпендикуляра к линии фронта Ф г = 0, п — 1.
Так как е > 0 и вг ^ 0, г = 0,п — 1, то получаем ¿2 > ¿1- Таким образом, выпущенный из точки М перпендикулярно фронту световой луч доходит до точки N за меньшее время.
При конструировании фронта световой волны возможна потеря гладкости [12] кривой при значительном удалении от базисного многообразия. В некоторой точке фронта происходит разрыв производной, что приводит к образованию «ласточкиного хвоста» (рис. 2) и не позволяет построить перпендикуляр к фронту в текущий момент времени и сам фронт в следующий момент времени.
3. Постановка задачи об определении оптимального расположения логистического объекта в пределах заданной области
Пусть в некоторой ограниченной области О С Я2 с кусочно-гладкой границей задана оптическая проницаемость среды /(х, у) ^ 0, у(х, у) = 1//(х, у) > 0 определяет мгновенную скорость движения в точке (х,у). Если /(х,у) = 0, то в этой точке располагается непроходимый для световой волны барьер.
Минимальное время перемещения из точки М(х,у) в точку М(х1,у1) равно
(1)
Тим = плп
/
^Г
г
у(х,у)'
г
Требуется определить расположение точки N такое, чтобы суммарное время движения световой волны из данной точки до всех точек области О было минимально возможным:
Данная постановка необходима при исследовании таких прикладных задач: размещение центров захоронения радиоактивных (или токсичных) отходов, при котором обеспечивал
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.