2.2.2. Проверка полученной очередности объезда методом сумм

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

Кроме того, метод Кларка - Райта не гарантирует, что в назначенных маршрутах объезд пунктов будет выполняться по оптимальным вариантам. В связи с этим для каждого маршрута дополнительно решают задачу оптимального объезда пунктов в маршруте (иначе ее называют "задача коммивояжера"), с целью сокращения общего пробега на маршруте.

Один из наиболее простых методов решения такой задачи - метод сумм.

Определим оптимальный вариант объезда пунктов маршрута №1. Для этого построим матрицу кратчайших расстояний между пунктами маршрута (табл. 2.14), в итоговой строке которой проставим сумму расстояний по каждому столбцу.

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

Таблица 2.14.

Матрица расстояний для маршрута №1.

Пункты	0	3	6	10	11
0	-	44	2	42	43
3	44	-	52	55	56
6	2	52	-	40	41
10	42	55	40	-	1
11	43	56	41	1	-
Итоговая строка	131	207	135	138	141

Увеличение расстояния перевозок или длины маршрута

Δl = l_ik + l_kj - l_ij .(2.14)

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

k - вставляемый в маршрут пункт;

l_ik, l_kj, l_ij - расстояния между соответствующими пунктами.

Увеличение длины маршрута 0-3-11-0, если вставить дополнительно пункт 10, будет следующим:

Δ _0-3= 42+55-44=53,

Δ _3-11= 55+1-56=0,

Δ _11-0= 1+42-43=0.

Минимальное увеличение длины маршрута определяет место вставки нового пункта в маршрут, в нашем случае это вставка пункта 10 между пунктами 3 и 11 или 11 и 0, при этом Δ = 0. Назначаем маршрут 0-3-10-11-0.

Ищем минимальное увеличение длины маршрута 0-3-10-11-0, если вставить дополнительно пункт 6.

Δ _0-3=2+52-44=10 ,

Δ _3-10=52+40-55=37,

Δ _10-11=40+41-1=80,

Δ _11-0=41+2-43=0.

Получаем развозочный маршрут №1: 0-3-10-11-6-0.

Произведем аналогичную проверку порядка объезда пунктов маршрутов № 2: 0-2-9-8-1-0 и №3: 0-4-5-7-0 методом сумм. В результате которой получаем порядок объезда пунктов:

для маршрута №1: 0-3-10-11-6-0;

для маршрута №2: 0-8-9-2-1-0;

для маршрута №3: 0-5-4-7-0.

2.2.3. Проверка на минимум транспортной работы

Рассчитаем минимальный грузооборот для каждого полученного маршрута. Расчет показан для маршрута №3: 0-5-4-7-0.

₍₂₇₁₎524₍₁₃₉₎

51

₍₇₄₉₎ 0 4 7₍₀₎

Рис. 2.2. Схема движения автомобилей по маршруту №2 0-8-9-5-0

(прямое направление)

Р₁= 749*5+271*2+139*1+0*4=3745+542+139=4426л∙км.

₍₀₎524₍₄₇₈₎

51

₍₇₄₉₎ 0 4 7₍₆₁₀₎

Рис. 2.3. Схема движения автомобилей по маршруту№2 0-8-9-5-0

(обратное направление)

Р₂ =749*4+610*1+478*2+0*5=2996+610+956=4562 т∙км.

Из двух схем движения автомобилей по маршруту №3 выбираем ту, которая обеспечит минимальную величину грузооборота. Принимаем для дальнейшего проектирования системы маршрут 0-5-4-7-0.

Результаты расчета для маршрута №1 сведены в таблицу 2.15.

Таблица 2.15.

Проверка на минимум транспортной работы

Номер маршрута	Порядок объезда	Грузооборот, л∙км
1	0-3-10-11-6-0 (прямое направление)	106012
1	0-6-11-10-3-0 (обратное направление)	34986
2	0-8-9-2-1-0 (прямое направление)	38899
2	0-1-2-9-8-0 (обратное направление)	97811
3	0-5-4-7-0 ( прямое направление)	4426
3	0-7-4-5-0 (обратное направление)	4562