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

Проблемно-ориентированные имитационные модели

МОДЕЛЬ ПОСЕЩЕНИЕ ПУНКТОВ МЕСТНОСТИ КОММИВОЯЖЕРОМ

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

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

из Санкт-Петербурга проводит маршрут в западном направлении (ближайший город - Рига);

поскольку на данной широте не нашлось ближайшего города западнее, то далее маршрут строится южнее в восточном направлении (ближайший город - Москва);

так как на данной широте не нашлось ближайшего города восточнее, далее маршрут строится южнее в западном направлении (ближайшая оптимальная последовательность городов - Плавск, Вильнюс, Балтийск);

поскольку на данной широте не нашлось ближайшего города западнее, то далее маршрут строится южнее в восточном направлении (ближайшая оптимальная последовательность - Минск, Яров-щина, Клинцы);

ввиду того что на данной широте не нашлось ближайшего города восточнее, далее маршрут строится южнее в западном направлении (ближайшая оптимальная последовательность - Новозыбков, Хойники, Пинск);

остался последний непосещенный город южнее - Киев; туда проводится последний отрезок маршрута.

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

Решение задачи: длина маршрута равна 4526,2 км. Вариант 2. Введем более жесткие условия:

пункт старта - Санкт-Петербург;

пункт финиша-Москва.

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

Решение задачи: длина маршрута равна 3338,2 км. На первый взгляд, это решение парадоксально: маршрут получился короче на 1188,0 км по сравнению с первым вариантом.

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

Вариант 3. Используются условия варианта 2. Применяется алгоритм двух вертолетов. Разрешена ручная корректировка неоптимальных участков. В результате получаем оптимальное маршрутное расписание (см. табл. 6.3). Далее измеряем протяженность.

Решение задачи: длина оптимального маршрута равна 2807,0 кМ. Это на 531,2 км короче по сравнению с вариантом 2 (но без варианта 2 этот маршрут нельзя было бы построить).

Далее необходимо разработать имитационную модель, которая должна обладать следующими свойствами:

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

• модель должна автоматически измерять длину маршрута (км) и время в пути (час).

Такая модель позволяет сравнивать эффективность различных алгоритмов.

Функцию накопления эта очередь не выполняет.

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

Время полета фиксируется с помощью клапана key (узел 6 Время полета). Этот клапан закрывается в начале имитации полета (операция hold из узла 2 queue при прохождении первого транзакта), а открывается в конце полета (операция rels из узла 5 term при удалении транзакта с номером М).

Рассмотрим текст модели в терминах Pilgrim:

Сделаем следующие пояснения к этому тексту: 1) общее число населенных пунктов содержится в глобальной переменной Pilgrim - npoints;

параметр транзакта t-ИиО используется для изменения маршрутов транзактов, если их номера превысят номер М;

в узле 2 выполняется привязка транзакта к населенному пункту, номер которого равен l+addr[2]-na, с помощью операции sewt;

в узле № 6 по завершении полета к последнему пункту измеряется время полета вертолета;

параметр транзакта t->tx содержит номер пункта, который посещает вертолет.