Платформа для разработки интеллектуальных мульти-агентных интернет-сервисов (стр. 3 )

Библиографические ссылки

1.  М. ванн Стеен Распределенные системы. Принципы и парадигмы. – СПб.: 2003. – 877 с.

2.   Б.,  В. Метод повышения функциональной надежности и точности вычислительных устройств. - Л.: ЛДНТП, 1964. – 10 с.

УДК 519.157

© , , 2013

ЗАДАЧА МАРШРУТИЗАЦИИ ТРАНСПОРТНЫХ СРЕДСТВ

С ВРЕМЕННЫМИ ОКНАМИ

− мл. науч. сотр. (ВЦ ДВО РАН), e-mail: [e-mail]; – канд. физ.-мат. наук, ст. науч. сотр. (ВЦ ДВО РАН), e-mail: [e-mail]

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

Задача маршрутизации транспортных средств – Vehicle Routing Problem (VRP) является ключевой в областях транспортных перевозок, перемещения и логистики. VRP является комбинаторной задачей глобальной оптимизации и относится в общем случае к классу NP-трудных задач [1].

В настоящей работе рассматривается VRP с дополнительными ограничениями на интервалы времени обслуживания: задача маршрутизации транспортных средств с временными окнами – Vehicle Routing Problem with Time Windows (VRPTW).

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

Требуется найти график движения K транспортных средств для выполнения всех заказов с минимальными затратами.

Пусть – последовательность обслуживания клиентов в маршруте k, . Пусть – время прибытия к клиенту в маршруте k, то

(1)

Обслуживание клиента не может быть ранее чем , поэтому

(2)

Если транспортное средство прибывает к клиенту раньше, чем , то появляется время ожидания, чтобы начать обслуживание :

(3)

Время обслуживания всех клиентов в маршруте k определяется как

(4)

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

(5)

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

В настоящей работе предложен гибридный метаэвристический алгоритм, в котором последовательно работают макси-минный метод муравьиных систем (MAX-MIN Ant System – MMAS) [2] и локальный поиск. Метод MMAS вводит нижнюю и верхнюю границу для возможных значений феромона. Также данный метод отличается от других муравьиных алгоритмов способом инициализации.

На каждой итерации разработанного гибридного алгоритма выполняются следующие операции:

·  Построение муравьями возможных решений .

·  Применение методов локального поиска к полученным решениям.

·  Выбор лучшего решения (5) из всех полученных муравьями. Если достигнуто улучшение, то обновляется глобальное лучшее решение.

·  Обновление следов феромона.

Критерий останова данного алгоритма зависит от режима работы: завершение заданного числа итераций или максимального времени работы программы, отсутствие улучшения значений целевой функции (ЦФ) (5) на протяжении заданного числа итераций, достижение известного оптимального значения ЦФ в экспериментальном режиме работы.

Каждый из m искусственных муравьев одной колонии составляет маршруты транспортных средств. Чтобы определить следующего клиента для его включения в текущий маршрут, рассчитывается вероятность перехода к j-ому клиенту, когда муравей находится у i-ого клиента [3]:

(6)

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

– эвристическая информация о том, насколько хорошим кажется посещение клиента j после клиента i. Этот параметр вычисляется для каждого клиента-кандидата по правилу где

(7)

где – расстояние между объектами i и j; – время ожидания начала обслуживания клиента j; , где – время прибытия к клиенту i.

След феромона, показывающий насколько "хорошим" для клиента j оказалось обслуживание после клиента i, удовлетворяет условию: . В MMAS используется интервал значений феромона . В настоящей работе для вычисления значений и используются предложенные в [3] формулы:

(8)

(9)

где – коэффициент испарения феромона; – значение ЦФ при лучшем пока решении , найденном с начала работы алгоритма (глобально лучшем); N – число клиентов.

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

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

Если в решении для обновления после клиента i обслуживается клиент j, то , где t – номер итерации, – значение ЦФ при таком решении. Для всех дуг, не принадлежащих этому решению, применяется только процедура испарения феромона: . После обновления если , то ; если , то .

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

Для 2-opt и 2-opt* характерно удаление пары несмежных ребер и объединение новых маршрутов по определенному правилу.

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

Пусть последовательности и – порядок следования соответственно клиентов в маршруте k и клиентов в маршруте p. После применения оператора 2-opt* для пары ребер и получаем следующие новые маршруты обслуживания клиентов: и .

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

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

Предложенные алгоритмы были проверены на тестовых задачах [4] для размерности . Этот набор включает несколько групп задач: множества C1 и C2 – географическая кластеризация клиентов, R1 и R2 – случайное расположение клиентов, RC1 и RC2 – совмещение случайного и кластерного типа расположения. Задачи из множеств C1, R1 и RC1 характеризуются сжатыми временными окнами и небольшой грузоподъемностью транспортного средства. В задачах из множеств C2, R2 и RC2 большее число клиентов может быть обслужено в течение одного маршрута из-за широких временных окон и большей грузоподъемности транспортного средства.

Приведем далее результаты решения некоторых задач из этого набора последовательным алгоритмом и его параллельной реализацией. Во всех расчетах использовались следующие значения параметров: Расчеты проводились на вычислительной системе с общей памятью, микропроцессоры Intel E5-2630 2,3 ГГц. Программы написаны на языке Fortran 95.

В таблице 1 представлены минимальные, средние и максимальные значения (по 25 запускам) времени в секундах работы программы. Вычисления прекращались при достижении показанных во втором столбце значений – оптимальных или лучших известных решений. Приводятся результаты для последовательной и параллельной версий программы на 10 MPI-процессах.

Таблица 1

Время скалярного и параллельного решений

Задача		Скалярное решение	Параллельное решение
C107	828,94	0,3	0,9	0,5	0,2	0,4	0,3
C108	828,94	0,3	70	16	0,2	0,5	0,3
C109	828,94	0,4	344	59	0,3	2,2	0,8
C201	591,56	0,4	1,2	0,7	0,4	0,7	0,5

В таблице 2 показаны результаты решения более сложных задач с ограничением времени решения 100 секунд. Показаны минимальные, средние и максимальные по 25 запускам значения относительной погрешности (в %) получения значений ЦФ – .

Таблица 2

Погрешность скалярного и параллельного решений

Задача		Скалярное решение	Параллельное решение
C102	828,94	0,6	3,4	2,2	0,3	2,8	1,5
R110	1072,41	3,3	6,8	4,9	2,5	4,9	3,5
R202	1034,35	3,5	5,3	4,3	2,9	4,0	3,5
R209	859,39	2,0	5,1	3,6	0,9	3,5	2,1
RC204	786,54	1,5	5,6	3,9	1,0	3,2	2,2

Библиографические ссылки

1.  Vehicle routing problem: models and solutions / L. Choong-Yeun, I. Wan Rosmanira, O. Khairuddin, M. Zirour // Journal of Quality Measurement and Analysis. – 2008. – No. 4(1). – Pp. 205–218.

2.  Stützle T., Hoos H. The max-min ant system and local search for the traveling salesman problem // Proceedings of the IEEE International Conference on Evolutionary Computation, Indianapolis, USA, Springer-Verlag. – 1997. – Pp. 308–313.

3.  Stützle T., Hoos H. Max-Min ant system // Future Generation Computer Systems. – 2000. – No. 16(8). – Pp. 889–914.

4.  Marius M. Solomon. Algorithms for the vehicle routing and scheduling problems with time constraints // Operations Research. – 1987. – No. 35(2). – Pp. 254–265.

УДК 517.549.8

© , 2013

МЕТОД РОТЕ ЧИСЛЕННОГО МОДЕЛИРОВАНИЯ

СИСТЕМЫ ТЕПЛОВЛАГОПЕРЕНОСА В ПОЧВАХ

 В. – ст. преп. каф. математики (ФГБОУ ВПО ДВГГУ), е-mail: *****@***ru

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

Решение теплового переноса в почвах сложно для экспериментального изучения. Для его исследования применимо моделирование с помощью системы уравнений в частных производных. Рассмотрим одну из таких моделей, полученную экспериментальным путем [1].

Рассматривается задача расчета температуры Т и влажности W на определенную дату. Для этого исследуется следующая система уравнений

; (1)

; ; , (2)

с краевыми условиями

, ; (3)

, , ; (4)