Метод роя частиц и его применение в дискретных задачах.

[healton]

День добрый.
Недавно у меня возникла задача по вычислению оптимального маршрута в какой-нибудь службе доставки с несколькими агентами. Задача самая простая, безо всяких наворотов. Имеем полный граф с матрицей весов, которая генерируется из массива точек на плоскости (клиентов). Весом ребра AB является время пути из A в B (на самом деле это расстояние на плоскости, но не суть важно). Из определенной вершины (база) в момент времени $T0$ выходят m агентов и посещают всех n клиентов. Нужно найти расписание (т.е. маршруты всех агентов), в котором $T=T1-T0 \mapsto \min$, где $T1$ - момент возвращения последнего агента на базу. Никаких динамических расписаний, грузоподъемности агентов и т.д.
Задачу нужно решить Методом Роя Частиц. Тут встает главный вопрос. МРЧ оперирует с векторами в вещественном пространстве, а задача на графе является дискретной. Как же перейти от дискретной задачи к задаче в n-мерном вещественном пространстве? То есть нужно создать целевую функцию $f(x), x\in\mathbb R^N$, которую минимизирует МРЧ, и эта функция должна из вектора по какому-то правилу вычислять время $T$. Кроме того, функция должна быть довольно гладкой (насколько это возможно для функций с конечным числом значений - расписаний-то конечное число), чтобы МРЧ мог на ней адекватно работать.

У меня была идея сделать так (дальше отсебятина - можно не читать ). Вектор $x$ координат частицы делится на две части. По первой (она подчеркнута в примере) вычисляется порядок обхода клиентов, по второй - количество клиентов, которых посетит каждый агент.
Пример. Дано 4 клиентов и 2 агента. В МРЧ есть частица с координатами (0.4, -0.2, 0.6, 0.2, -0.1, 0.8, 0.1)
Сортируем массив {1, 2, 3, 4} по убыванию весов из первой части вектора. Получим порядок обхода клиентов {3, 1, 4, 2}. Сортируем вторую часть вектора: {-0.1, 0.1, 0.8}, отсюда получаем распределение клиентов по агентам. Таким образом получим, что агент A1 пойдет к клиенту C3 а агент A2 – к клиентам C1, C4 и C2. Если у нас m агентов и n клиентов, то размерность в которой должен работать МРЧ равна $N=n+m+1$, а это ужасно. Кроме того, если разбить пространство на области, в которых $f(x)$ неизменна, то всего получим $2^{N(N-1)/2}$ областей и вероятность попасть в нужную область астрономически мала. Более того, все эти области соседствуют друг с другом около начала координат и там мы имеем ужасные скачки функции.

[longstreet]

Непонятны условия задачи.