За последнее время реализовал и протестировал алгоритм параллельного решения задачи коммивояжера.

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

Таким образом достигается возможность параллельного просмотра подзадач и ускорения процесса решения.

Что дает параллельное решение задачи коммивояжера?

1. На компьютерах с реальной многопоточностью дерево решений просматривается быстрее.

2. В большинстве рассмотренных задач сокращается время просмотра дерева решений.

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

Для тестирования использовались известные задачи. В качестве оценки решения использовались следующие показатели:

1. Затраченное на решение задачи время, как разница между моментом начала и завершения решения. Обозначение: T1, в секундах.

2. Затраченное на решение задачи время, как сумма проццерного времени, затраченное параллельными решателями. При использовании двух процессоров (ядер процессора) это время будет до двух раз больше предыдущего. Обозначение: T2, в секундах. Примечание: Уменьшение T2 с увеличением количества параллельных решателей говорит о наличии взаимопомощи решателей.

3. Количество просмотренных вершин в дереве просмотра решений. Обозначение: E.

4. Достигнутое решение (за отведенное на решение время, ограничение по первому времени). Обозначие: S.

5. Состояние пула задач: часто полон, часто свободен.

Далее по ссылке представлены результаты полученные на компьютере с двухъядровым процессором.

http://spreadsheets.google.com/pub?key=pQVK5kPuGy5Vzd5nEST5tXQ

Далее по ссылке представлены результаты полученные на компьютере с двумя двухъядровыми процессорами.

http://spreadsheets.google.com/pub?key=pQVK5kPuGy5XdUj52mzleZA

Непонятки с CVRP.

Следуя постановке задачи CVRP (http://neo.lcc.uma.es/radi-aeb/WebVRP//Problem_Descriptions/CVRPDesc.html), целевая функция задачи состоит в минимизации количества используемых транспортных средств (ТС) и суммарного растояния проезда: "Objective: The objective is to minimize the vehicle fleet and the sum of travel time, and the total demand of commodities for each route may not exceed the capacity of the vehicle which serves that route. "

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

Далее буду применять термин подмаршрут в отношении к отдельной для ТС части маршрута --- так логичнее, так как одним ТС можно последовательно проехать по всем подмаршрутам.

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

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

Для задачи E-n30-k3.vrp (в архиве http://neo.lcc.uma.es/radi-aeb/WebVRP//data/instances/Christ-Eilon/CE-VRP.zip) указывается оптимальное решение, где количество подмаршрутов = 3, общая длина = 536. В текущий момент мне известно (возможно, неоптимальное) решение с общей длиной = 506, и 4 подмаршрута (подробнее см. ниже). Если переход от одного подмаршрута к другой ничего не стоит, то первым освободившийся ТС можно направить на дополнительный подмаршрут, и в итоге, получить общую длину, которая будет короче, чем при решении с меньшим количеством подмаршрутов.

Решение E-n30-k3.vrp длиной 506, 4 маршрута (возможно, не оптимальное).

#1: 19 16 17 14 8 18 10 15 9 13 12 11 24 = {D=3625,W=139}
#2: 27 29 28 30 26 25 2 7 = {D=3300,W=184}

#3: 22 = {1500,46}
#4: 20 4 5 6 3 23 21 = {D=4325,W=137}

Коварный p43. (Именно так остается думать)
Задача сама по себе малой размерности - 43 пункта. Однако несколько часов работы метода Литтла не находят решение, включая метод с модификациями.
Рассмотрев данные, углядел, что p43 получена из задачи размерности 22 пункта путем дублирования некоторых пунктов 2, 3, а то и 4 раза. Между такими клонами пунктов нулевая стоимость, а стоимость до других пунктов копируются.
Такая простая модификация задачи вводит в ступор метод Литтла просто потому, что в дереве решений появляется очень много клонов маршрута, в которых просто переставлены порядок подряд идущих пунктов-клонов. В итоге, каждый набор клонов увеличивает просматриваемое дерево решения в число пересатоновок пунктов клонов - экспоненциальный рост.
При схлопывании пунктов-клонов задача p43 решается за секунду.
Получается, нужен какой-то метод предварительного анализа и выявления таких групп пунктов клонов, не обязательно полных дубликатов (достаточно явная группировка). Потом эти группы представить как один пункт и составить новую задачу.
Пока есть следующие трудности:

• каким способом разбить пункты на группы?
• как обеспечить корректность такой модификации задачи, чтобы оптимальное решение в новой задаче был оптимальным в исходной?

Для полных клонов, когда между клонами нулевая стоимость и строки стоимостей просто продублированы, это легко. А как быть со "слабыми клонами"? Например, пункты внутри города можно рассматривать как "слабые клоны" в объемах всего земного шара.

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

Результаты тестов на случайных несимметричных матрицах общего вида (равномерное распределение весов) при 100 пунктах показывает улучшение показателя времени в среднем около 20000 раз (бывает до нескольких сотен тысяч)!
Приведу результаты решения стандартных задач, распространенных в интернете. Время указана в секундах для компьютера Pentium 3.15GGz, 512Mb. В случае, если решение задачи тем или иным методом снималась по истечении 1 часа отведеного времени, время не указано, но указано достигнутое за это время решение. Результаты приведены только для задач, которые решились хотя бы одним методом за отведенное время - задачи ft53, ftv100, ftv110, ftv120, ftv170, td100, p43, big702, atex4, atex5, atex8, dc112, dc126, dc134, dc176, dc188, dc563, dc849, dc895, dc932 не решились за отведенное время.

Задача			Метод Литтла		Моя модификация
	размер	известное решение	время, сек	решение	время, сек	решение
ft70	70	38673		38673	149	38673
ftv33	34	1286	0,16	1286	1,1	1286
ftv35	36	1473	0,08	1473	0,05	1473
ftv38	39	1530	0,31	1530	0,05	1530
ftv44	45	1613	1,5	1613	0,08	1613
ftv47	48	1776	21	1776	0,42	1776
ftv55	56	1608	616	1608	2,4	1608
ftv64	65	1839	952	1839	2	1839
ftv70	71	1950		1963	8,4	1950
ftv90	91	1579		1611	1,5	1579
ftv130	131	2307		2474	117	2307
ftv140	141	2420		2585	108	2420
ftv150	151	2611		3048	135	2611
ftv160	161	2683		3019	3970	2683
rbg323	323	1326		1527	3	1326
rbg358	358	1163		1580	7,3	1163
rbg403	403	2465		3400	5,5	2465
rbg443	443	2720		3441	3,6	2720
td316	317	691502		722548	12	691502
td1000	1001	1242183		1263952	1228	1242183
br17	17	39	5,1	39	5,6	39
kro124p	100	36230		36352	3568	36230
ry48p	48	14422	571	14422	54	14422
atex1	16	1812	0,23	1812	0,41	1812
atex3	32	2952	0,28	2952	0,05	2952
code198	198	4541	0,23	4541	0,06	4541
code253	253	106957		106957	1261	106957