2. Метод функции «выгоды».

Метод функции «выгоды» предложен английскими специалистами Кларком и Райтом для решения задач маршрутизации автомобильных мелкопартионных перевозок с одним отправителем (получателем). Метод основан на понятии эффекта ( «выгоды»), который получается при объединении двух маршрутов в один. Пусть есть 2 маршрута O-a-b-…i-O и O-j-r-….O. каждый из них начинается и заканчивается в пункте О, который в случае развоза груза является поставщиком, а в случае сбора груза получателем. Будем условно называть этот пункт центральным складом.

Эффект от объединения двух маршрутов в один ( определяется по формуле:

- ,(1)

где: - расстояние от пункта i до центрального склада;

- расстояние от центрального склада до пункта j;

- расстояние между пунктами i и j ; i ,j-пункты, расстояние до которых от центрального склада, мы объединяем в один маршрут.

При объединении двух маршрутов отпадает необходимость в возврате с первого маршрута на склад и в следовании транспорта со склада на второй маршрут, но добавляется пробег от первого маршрута до второго. На основании данного рассуждения делается естественный шаг к решению всей задачи : при наличии некоторых начальных маршрутов их можно укрупнить, объединяя в соответствии с величиной «выгоды». Если в первую очередь использовать наибольшие значения «выгоды» для всех возможных объединений, то можно надеяться на получение хорошего решения, близкого к оптимальному. Решение должно заканчиваться тогда, когда дальнейшее объединение маршрутов станет невозможным. Это может быть по двум причинам: либо не осталось ни одного положительного значения «выгоды» (объединять невыгодно), либо для выполнения объединенного маршрута не находится подходящего автомобиля. Пусть дана сеть, состоящая из 9 точек, в одной из которых расположен центральный склад О, а в восьми других –получатели (рисунок 1);

Рисунок 1

Количество ввозимого в каждый пункт груза заносим в первый столбец таблицы 1, количество вывозимого груза во второй столбец. В последующих столбцах приведем кратчайшее расстояние между пунктами. Построим систему из 8 маятниковых маршрутов вида 0-i-0(i=1,2,3…..8).

Для выполнения таких маршрутов, а/м недостаточно, но возможен вариант, что при объединении количество маршрутов значительно сократиться. В таблице 2 приведены значения эффектов экономии расстояния, полученные при объединении маршрутов в один, которые мы рассчитали по формуле 1. При построении маршрутов будем отдельно учитывать количество ввозимого и вывозимого груза, а так же то, что автомобиль должен быть загружен не менее, чем 70%, то есть а/м грузоподъемностью 100ед., должен быть загружен не менее, чем на 70 ед.. а/м в 200ед, не менее, чем на 140ед., а/м в 300 ед. не менее, чем на 210ед.,

Таблица №1«Кратчайшее расстояние между пунктами»

Вв	Выв	0
75	55	20	1
88	60	7	4	2
38	40	18	6	10	3
48	52	27	18	19	9	4
58	42	20	9	13	3	12	5
28	38	25	24	18	8	13	5	6
40	48	23	12	16	6	15	3	8	7
42	54	35	24	28	18	20	15	10	16	8

Таблица №2 «Значение эффекта экономии расстояния»

Вв	Выв
75	55	1
88	60	23	2
38	40	32	15	3
48	52	29	15	36	4
58	42	31	14	35	35	5
28	38	21	14	35	39	40	6
40	48	31	14	35	35	40	40	7
42	54	31	14	35	42	40	50	42	8

Рассчитываем систему маршрутов.

Из таблицы 2 выделяем максимальные эффекты разной величины, и за счет их объединения составляем маршруты, находим их суммарное количество, а также полученные результат подставляем для загрузки автомобилей.

1.0-6-8-0

=28+42=70ед.

38+54=92ед.

2.0-6-8-7-0

=70+40=110ед.

=92+48=140ед.

3. 0-5-6-8-7-0

=110+58=168ед.

=140+42=182ед.

4. 0-4-5-6-8-7-0

=182+52=234ед.

5. 0-3-4-5-6 -8-7-0

=216+38=254ед.

234+40=274ед.ч

Для нас подходит автомобиль с грузоподъемностью 300ед.

1.0-1-2-0 = 75+88=163ед.

= 55+60=115ед.

Для нас подходит автомобиль с грузоподъемностью 200 ед. Окончательно полученная система маршрутов приведена в таблице 3.

Таблица № 3 «Сформированная система маршрутов»

№ маршрута	Маршрут	Загрузка а/м,ед			Грузовмес тимость а/м,ед.		Пробег, км
		ввоз	вывоз
1	0-3-4-5-6- -8-7-0	254	274	300			98
2	0-1-2-0	163	115	200			31
итого						129

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