Дискретные задачи размещения Библиотека тестовых задач

Библиотека тестовых задач Конкурентная задача о p-медиане

Примеры с равномерным распределением

В данных примерах множество клиентов и множество возможных мест размещения предприятий совпадают: I = J, n = m = 100.  Элементы матрицы (g_ij)  выбираются случайным образом с равномерным распределением из интервала (0, 10000). 

Приведены результаты экспериментов на 10 задачах из класса Uniform. Рассмотрены два случая. Первый случай (Таблица 1), когда доход от обслудивания каждого клиента — случайная величина с равномерным распределением из интервала от [0, 200].

Второй случай (Таблица 2), когда  доход от обслудивания каждого клиента одинаковый и равен единице.

Исходные данные доступны в виде текстовых файлов. Текстовые файлы в первой таблице содержат список элементов матрицы (g_ij) по строкам и вектор величин доходов от обслуживания каждого клиента w_j ∈ [0, 200]. Во второй таблице текстовые файлы содержат только список элементов матрицы (g_ij) по строкам.

В таблицах приводятся: первый стобец — код примера, второй столбец — оптимальное значение целевой функции и доля рынка Лидера в процентах для случая с разным доходом от каждого клиента, если доход одинаковый, то доля рынка совпадает со значением целевой функции Лидера; третий столбец —  решение Лидера; четвертый столбец — решение Конкурента; пятый столбец — число итераций точного метода (размер семейства решений Конкурента), описание которого можно найти в  статьях:

 

E. Alekseeva, N. Kochetova, Y. Kochetov, A. Plyasunov. Heuristic and Exact Methods for the Discrete (r | p)-Centroid Problem // P. Cowling and P. Merz (Eds.): EvoCOP 2010, LNCS 6022,Springer, Heidelberg, 2010. pp. 11-22. (pdf.file 184 Kb)

I.A. Davydov,Yu.A.Kochetov, N. Mladenovic,and D.Urosevic. Fast Metaheuristics for the Discrete (r|p)-Centroid Problem // Automation and Remote Control, 2014, Vol. 75(4). p. 677–687.  (pdf-file 174 Kb)

 

 

Таблица 1.  n = 100, p = r = 7, wj = [0, 200]

Все примеры  COMP-Unif-1(100).zip 24 Kb

Код примера	Оптимум	Решение Лидера	Решение Конкурента	Число итераций
123	5009 (47%)	9 18 37 54 67 76 77	14 32 39 58 83 84 98	315
223	5459 (47%)	24 29 35 47 73 86 91	10 28 31 38 59 71 83	68
323	5019 (47%)	1 5 22 24 43 51 78	27 28 33 50 55 71 91	411
423	4908 (46%)	4 19 24 61 69 78 90	7 9 12 58 75 81 97	596
523	5208 (49%)	1 25 37 54 60 78 85	2 3 6 58 73 96 99	248
623	5032 (47%)	27 32 59 64 72 86 99	30 31 49 71 81 87 92	298
723	5055 (48%)	44 48 63 67 75 94 100	6 32 56 71 81 83 86	371
823	4876 (46%)	25 31 68 74 78 80 87	5 7 8 24 46 65 67	515
923	5127 (48%)	1  4  36 46 57 64 88	15  16  33  34  60 67 71	253
1023	5084 (48%)	6 9 20 25 56 75 77	14 54 59 65 71 91	573

 

Таблица 2.  n = 100, p = r = 7, wj = 1

Все примеры  COMP-Unif-2(100).zip 24 Kb

Код примера	Оптимум	Решение Лидера	Решение Конкурента	Число итераций
123	47	11 48 67 76 83 84 99	5 23 37 45 55 56 80	83
223	48	47 56 71 73 86 91 98	1 29 53 59 62 83 92	116
323	46	26 38 43 63 71 75 91	16 23 28 35 42 50 57	93
423	47	4 17 18 24 27 61 90	8 9 12 40 72 81 86	75
523	50	1 37 54 65 78 85 89	2 3 6 60 87 96 99	202
623	47	25 32 61 71 72 83 86	30 31 33 39 73 89 99	84
723	49	2 19 30 42 58 67 94	14 17 26 31 48 63 82	134
823	48	30 46 52 58 68 87 95	7 8 22 31 41 65 91	100
923	47	16 36 46 49 57 64 66	28 38 51 54 60 83 100	84
1023	49	3 6 9 25 56 71 77	14 33 56 75 79 88 95	109

 

Библиотека тестовых задач Конкурентная задача о p-медиане