Кадура (1194486), страница 11

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

Текст из файла (страница 11)

Каждое значение вычисляется через предыдущее по фор­муле

Особое значение имеют величины Т_и - так обозначается момент посеще­ния одним из локомотивов участка станции и, где нужно побывать для выпол­нения маневра. Все числа Т_и находятся среди чисел Отдельно выпишем Т_и для каждой точки и, требующей маневра. Теперь для любой пары вершин и и v, вошедших в граф приоритетов и связашшх условием непосредственного предшествования, нетрудно определить, какая из них посещена раньше, а какая - позже путем сравнения Т_и и T_v. Вершины и и v могут присутствовать как в одном маршруте, так и в различных маршрутах. Не каждое допустимое реше­ние задачи нескольких коммивояжеров, описанной во второй главе, будет яв­ляться допустимым решением развитой на случай условий предшествования задачи. Следует производить анализ на допустимость тех решений, к которым мы приходим по мере выполнения алгоритмов нахождения оптимума. В том случае, когда, к примеру, некоторый допустимый по условию задачи несколь­ких коммивояжеров набор маршрутов содержит две вершины и и v, связанные отношением порядка u«v, a T_u>T_v, данный набор объявляется не удовле­творяющим условию решаемой задачи и исключается из дальнейшего рассмот­рения. При и -< v обязано выполняться неравенство T_u<T_v, или хотя бы T_u<T_v.

Критерий J₃ качества решения R задачи нескольких коммивояжеров, со­стоящего из m маршрутов, вычисляется следующим образом.

1. Рассмотрим некоторые два маршрута с номерами i1 и i2, обозначим па­ру (i1, i2) буквой k. Общее количество всевозможных пар равно

Для всех k, k = 1 ,..,т(т -1)/2 определим величины cross^k_x по правилу

cross^k_x = min{vn(il, х), vn(i2, x)}, х = 1, size

Следовательно, каждой паре маршрутов (i1, i2) с номером k мы поставили в соответствие величины cross^k_x, равные количеству вхождений вершины х в тот маршрут из этой пары, который содержит х меньшее количество раз. Фак­тически для каждой пары маршрутов мы нашли число пересечений этих мар­шрутов в вершине х, х = 1 ,size.

1. Чтобы найти общее количество пересечений в каждой вершине, про­суммируем соответствующие минимумы. В результате получим один вектор сумм sum, элементы которого sum_x равны

3. Подлежащий минимизации критерий качества J₃ положим равным максимуму sum_x

J₃ = max{sum_l, sum₂,... ,sum_size},

в случае, когда этот максимум больше нуля и т>\. Если же максимум равен нулю (нет пересечений - маршруты не имеют общих частей), или т=1 (имеется только один маршрут), положим J₃ = 1, чтобы воспрепятствовать обращению в ноль J - свертки критериев, которая теперь будет равна

Заметим, что значение J₃ прямо пропорционально т - количеству задей- ствуемых локомотивов. Уменьшение т способствует нежелательному умень­шению значения J₃, и наоборот. Поэтому в качестве показателя важности ₃ предлагаем взять дробь 1/m. Значение критерия J₃ в степени 1/m, очевидно, указанным свойством не обладает.

Теперь покажем, как мы будем вычислять J₄.

1. Как уже было сказано, каждая вершина x G₀, вообще говоря, не­сколько раз встречается в маршруте i, либо не встречается ни разу (количество встреч содержит элемент vn(i, x)). Время прибытия локомотивов во все верши­ны мы вычислили. На основании этого при vn(i, х)>0 можно ввести следующие обозначения. Через обозначим время первого прибытия i-го локомотива в

вершину*, через - время второго прибытия и т.д. (vn(i,x)) - момент времени, в который i-й локомотив в последний раз должен посетить вершину x своего маршрута.

Для каждой пары маршрутов i1 и i2 (обозначаемой буквой k, k = 1,m(m-1) / 2) определим минимумы , х = 1, size. При vn(i1,x)>0 и vn(i2, x)>0:

При и

2. Выбираем наименьшее из всех и полагаем J₄ равным ему.

, ,

Включать в свертку, возводить в степень ₄ и максимизировать этот критерий не считаем нужным. Достаточно потребовать, чтобы значение было не меньше некоторой наперед заданной пороговой величины . Если для ре­зультирующего решения не выполняется > следует изменить время стар­та локомотивов, либо уменьшить их количество. При = 0 последнее нера­венство всегда истинно.

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

Рассмотрим конкретный пример. Имеется ситуация «нет прохода» на пути ПЗ и П4, два «чужака» на пути ПЗ и «окно» на пути П4. На путях П8 и П6 находятся маневровые локомотивы. Математическое пред­ставление данной ситуации изображено на рисунке 42.

Рисунок 42- Граф для ситуации на станции

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

Рисунок 43- Граф в обслуживании

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

Пусть , все коэффициенты за­грузки равны 2. При таких исходных данных, с учетом условий предшествова­ния, получены маршруты, на рисунках 44, 45:

Рисунок 44- Маневровый локомотив на пути П8

Рисунок 45- Маневровый локомотив на пути П6

Рисунок 46- «Окно» на пути П4, «чужаки» на пути П3 и П4

[17,15, 18, 13], 9, [13, 12], 1, [12, 13, 9, 14, 10], 11, [10, 14], 3, 4, [3,9,13,12],

1. а₂, [16,15,18,13, 9,14], 10, [14, 9, 13,18,15,17], 2, [17,15, 16], b₂. Значения критериев: =661, =334, =1,414, =10, J=312221.585.

Это решение допустимо: когда второй локомотив заедет на путь ПЗ в точку 10 чтобы переставить «чужака» на путь П7 в точку 2, проход на пути ПЗ и П4 будет уже открыт благодаря первому локомотиву.

Увеличив до 12-ти, получим:

1) , [17,15, 18, 13], 9, [13, 12], 1, [12, 13, 9, 14], 10, [14, 9,13, 18, 15,17], 2, [17,15,18,13,9,14,10], 11, [10, 14], 3,4, [3, 14, 9,13, 12],

= =579, J=335241. Второй коммивояжер не задействуется. Поскольку количество маршрутов равно 1, критерии и J₄ никакой роли не играют. Без учета условий предшествования получим:

1) а₁, [17, 15, 18, 13, 9, 14, 10], 11, [10, 14], 3, 4, [3, 14], 10, [14, 9, 13, 18,17], 2, [17, 15,18, 13], 9, [13,12], 1,[12]

= =545, J=297025. Видно, что посещать точки в таком порядке практи­чески не представляется возможным.

3.4 Оптимальное упорядочение ребер графа

В главе 1 в терминах теории графов были описаны решения задачи непрерывного обхода всех городов, т.е. вершин графа, одним или не­сколькими коммивояжерами. В каждом городе обязательно должен был кто-то побывать, и в то же время длина маршрута или маршрутов должна быть мини­мальной. Тем не менее, практически могут возникать задачи несколько иного содержания. В этом параграфе мы покажем, каким образом разработанные на­ми алгоритмы следует использовать при решении задачи оптимального упоря­дочения обхода не вершин, а ребер графа. Необходимость такой постановки диктуется практической потребностью решения многих вопросов экономики транспорта: проблемы инспектирования железнодорожных линий, управления работой машин, производящих уборку улиц города, доставки готовой продук­ции потребителям и т.д. Математическая сущность подобного рода задач со­стоит в следующем. Имеется произвольный связный граф G(X,U). Во множе­стве X выделено s базовых вершин, где коммивояжеры находятся на начальном этапе пути и базовых вершин, где коммивояжеры должны находиться в конце работы. Ребрам множества и приписаны неотрицательные веса. Требуется ука­зать коммивояжерам оптимальные с точки зрения критерия качества маршруты движения, причем каждое ребро графа из множества тех ребер, по которым требуется пройти, должно содержаться хотя бы в одном из маршрутов.

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

Без потери общности будем считать, что ребра, инцидентные к базовым вершинам посещать необязательно.

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

Рассмотрим смешанный граф на рисунке 47, имеющий две базовые верши­ны начального местонахождения коммивояжеров , и а₂, и две базовые вер­шины и b₂, в которые коммивояжеры должны отправиться по окончании ра­боты. Нумеруются сначала небазовые вершины, затем базовые, и в последнюю очередь - все остальные, если таковые имеются. Для простоты положим длины всех ребер равными десяти, а показатели важности - единице. Идея предлагае­мого ниже метода заключается в том, чтобы исходный граф привести к такому преобразованному, который пригоден для отыскания оптимального плана зада­чи нескольких коммивояжеров в ее обычном виде.

Рисунок 47-Исходный смешанный граф

Характеристики

Список файлов ВКР