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

Моделирование пространственной динамики

Поведение исследуемой системы в пространстве моделируется с помощью узлов типа creat, delet, proc и dynam.

Логика узла" creat такова: он получает координаты порождающего транзакта, в результате происходит имитация перемещения в пространстве. Узел delet получает координаты каждого уничтожаемого транзакта, т.е. он перемещается по координатной сетке в процессе нахождения в нем поглощающего транзакта.

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

Пример 2.1 (рис. 2.10). Часть модели, состоящая из узлов queue и ргос, предназначена для моделирования движения транспортного средства. Имеется специальный массив, предварительно загруженный координатами М пунктов региона из файла или базы данных средствами моделирующей системы. На вход этой части модели в разные моменты времени поступают М транзактов, причем каждый из них читает в свои внутренние параметры координаты очередной точки. Узел ргос, моделирующий транспортное средство, в качестве одного из параметров получает скорость перемещения, которая может быть изменяемой. При поступлении каждого следующего транзакта из очереди в узел ргос с помощью функции geoway автоматически определяется расстояние по поверхности Земли от предыдущего пункта до следующего. Время обслуживания транзакта -это расстояние, деленное на скорость. По истечении времени обслуживания узел получает новые координаты того пункта, в который он попал. Порядок посещения пунктов узлом ргос - хронологический (в порядке поступления транзактов в очередь) или в соответствии с приоритетами транзактов.

Узел dynam предназначен для моделирования управляемой очереди обслуживания транзактов с динамическими пространственно-зависимыми приоритетами.

Задача оптимального расписания для обслуживания транзактов с пространственно-зависимыми приоритетами может возникнуть, например, при моделировании следующих сложных процессов и объектов:

участка гибкого автоматизированного производства с роботизированными тележками, путешествующими по цеху;

местности, подверженной какому-то бедствию, в процессе ее обследования специальной командой на вертолете и др.

Пример 2.2. Использование вертолета скорой помощи. Допустим, во время дежурства на вертолет поступают радиограммы из различных пунктов. Это радиограммы вызова к больному. Если во время работы скопилось несколько радиограмм, то путь вертолета должен быть минимальным, чтобыуменыпить среднее время ожидания больного. Более того, если полет из одного пункта к другому уже начался, то при появлении новой радиограммы из пункта, находящегося не очень далеко от курса вертолета, маршрут может быть изменен в пользу такого вызова, если суммарный путь будет минимален.

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

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

В системе Pilgrim реализован быстродействующий алгоритм оптимизации динамического расписания - правила построения динамической очереди dynam для обслуживания транзактов. Рассмотрим упрощенное описание этого алгоритма.

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

- название населенного пункта;

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

- аэродром базирования вертолета, откуда он вылетает по первому вызову;

Р(ху) - точка с координатами хну, в которой вертолет находится в момент времени г,

- расстояние от At до Aj по прямой линии.

. Обратим внимание на два обстоятельства:

в точке Р(х,у) необходимо принять решение либо о продолжении полета к намеченному пункту (т.е. к Аг), либо изменить маршрут в целях сокращения суммарного пути и лететь к новому пункту (т.е. к Ац)

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

Поскольку начиная с момента поступления

сигнала из А4 в точке А,0 до момента поступления сигнала из А% в

- номера сигналов;

ловии, что в группе сигналов сообщениям из этих пунктов присвоены номера л-1 и п после оптимизации (посещение будет производиться в порядке возрастания п, причем необязательно, чтобы j=i+[).

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

Поэтому нельзя утверждать, что выражение

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

2. Через некоторое время появятся сигналы из новых пунктов, пока неизвестных (координаты их тоже заранее неизвестны). Поэтому можно сделать вывод о том, что оперативное расписание, составляемое каждый раз при получении нового сигнала в момент времени 4 из пункта At, дает только локальный минимум в момент времени 4 для случайного набора в очереди, состоящего из транзактов Л** пунктов. Причем минимизации подлежит выражение

Однако строгий минимум не гарантирует лучшего решения для всего маршрутного пути.

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

В любом случае для оценки эффективности метода необходимо его сравнивать с простейшим методом, работающим по правилу fifo (first in - first out) - первым пришел - первым обслужен, применение которого всегда дает для выражения (2.1) следующие соотношения:

Весь путь, пройденный при использовании этого метода, всегда определяется по формуле

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

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

Транзакт в нашем случае - это формализованный сигнал, который может иметь такие параметры:

/ - хронологический номер транзакта и, соответственно, пункта;

t— момент времени получения сигнала из пункта / экипажем вертолета;

- координаты пункта на местности, из которого пришел сигнал с хронологическим номером /.

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

Введем в рассмотрение приоритет транзакта/?,: если приоритеты всех транзактов равны, то порядок транзактов в очереди (в случайной группе сигналов величиной Щ определен порядковым номером / (первым пришел - первым обслужен).

Чем больше /, тем ближе к хвосту очереди находится транзакт (т.е. всегда вновь поступивший транзакт будет последним). Если же приоритеты всех транзактов различны, то очередь всегда упорядочивается специальными диспетчерскими средствами от головы к хвосту в порядке уменьшения р„ а при совпадении приоритетов двух расположенных рядом в очереди транзактов ближе к хвосту будет находиться тот, у которого больше номер /.

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

Пополнение очереди. Допустим, что вертолет находится в точке Р(х, у), а в очереди находятся ЛУ* транзактов. Если А : - первый в

очереди транзакт, относящийся к пункту j, то длительность дооб-служивания очередного транзакта из пункта / определяется как

где v - скорость вертолета, которую можно изменять после подлета к каждому пункту.

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

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

раз одну и ту же

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

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

если n=Nic, то это означает, что транзакт нужно поставить на последнее место;

так как он попал на первое место в очереди.

. После этого при появлении нового транзакта опять можно

- это всегда последний обследованный пункт).

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

Если же очередь пуста, то в зависимости от ситуации можно, например, перейти к патрулированию местности по заранее намеченному маршруту.

Для определения эффективности данного метода проводилось имитационное моделирование большого числа возможных ситуаций в Брянской области с помощью Pilgrim-моделей. Была использована реальная информация из банка данных по Гордеевскому, Клинцов-скому, Красногорскому, Новозыбковскому и Злынковскому районам. Максимальный выигрыш от применения этого алгоритма в реальной работе вертолетных групп (т.е. не только при использовании для реализации функции dynam) находится в пределах 30-50%. Причем, чем меньше средний интервал между заявками и чем больше густота населенных пунктов, тем больше выигрыш.

В примере 2.2 рассмотрена реальная ситуация, при которой сигналы поступают в процессе полета. Однако возможен крайний случай, когда по некоторым причинам уже в момент вылета вертолета известны все М пунктов. Такая вырожденная ситуация порождает задачу коммивояжера, а рассмотренный метод превращается в разновидность известного алгоритма ближайшего непосещенного города. Он позволяет сократить путь, но не дает глобального минимума: расписания, составляемые с его помощью, хуже оптимального относительно длины маршрутного пути. Более удачный способ решения задачи коммивояжера рассмотрен в главе б.