Разработайте замкнутый кольцевой маршрут из единого центра

Согласно условию задачи, определим суммарную потребность всех пунктов потребления:
П=750+850+1300+950+500+650=5000 кг=5 т
Таким образом, суммарная потребность всех пунктов потребления соответствует грузоподъемности автомобиля и означает, что автомобиль может за один «круг» обеспечить развоз груза.
Для решения данной задачи построим матрицу кратчайших расстояний, в которой по диагонали размещены пункты, включаемые в маршрут, а в соответствующих клетках – кратчайшее расстояние между ними. В нижней строчке матрицы рассчитаем сумму по столбцам (табл. 1).
Таблица 1 – Матрица кратчайших расстояний
А 10 17 24 10 5 10
10 Б 15 16 10 15 10
17 15 В 1 7 13 7
24 16 1 Г 8 13 8
10 10 7 8 Д 5 0
5 15 13 13 5 Е 5
10 10 7 8 0 5 Ж
Σ
70 76 60 64 40 56 40
Определим первоначальный маршрут из трех пунктов, имеющих наибольшие значения величины суммы, показанной в нижней строчке матрицы. В данном случае такими пунктами являются пункт Б (76), пункт А (70) и пункт Г (63) (рисунок 2).
281876528575А
00А
31489655270525012655270500
347980023495Б
00Б
214566526035Г
00Г
250126550165
Рисунок 2. Базовый маршрут объезда
Для включения оставшихся пунктов в маршрут выбираем из них тот, которому соответствует следующая наибольшая сумма. Таким пунктом является пункт В (60). Необходимо решить между какими пунктами должен быть расположен пункт В, т. е. между пунктами А и Б, между пунктами Б и Г или между пунктами Г и А.
Для принятия данного решения для каждой пары пунктов рассчитывается приращение длины маршрута при включении в него промежуточного пункта по формуле:
δ12=R1i+R2i-R12,
δ12 – приращение длины маршрута;
R1i – кратчайшее расстояние от первого пункта до включаемого пункта;
R2i – кратчайшее расстояние от включаемого пункта до второго пункта пары;
R12 – кратчайшее расстояние между первоначальными пунктами пары.
Таким образом, рассчитаем приращение для пункта В:
А-В-Б=LАВ+LВБ-LАБ=17+15-10=23 км.
Б-В-Г=LБВ+LВГ-LБГ=15+1-16=0 км.
Г-В-А=LГВ+LВА-LГА=1+17-18=0 км.
Минимальное значение соответствует двум промежуткам, из которых выберем Б-В-Г, следовательно пункт В должен быть расположен между пунктами Б и Г . Получаем кольцевой маршрут следующего вида (рис. 3).
281876528575А
00А
31489655270525012655270500
347980023495Г
00Г
214566526035Б
00Б
314896512700025012651270002818765127000В
00В
Рисунок 3. Промежуточный кольцевой маршрут
Для включения оставшихся пунктов в маршрут выбираем из них тот, которому соответствует следующая наибольшая сумма – пункт Е (56). Далее рассчитаем приращение для пункта Е:
А-Е-Б=LАЕ+LЕБ-LАБ=5+15-10=10 км.
Б-Е-В=LБЕ+LЕВ-LБВ=15+13-15=13 км.
В-Е-Г=LВЕ+LЕГ-LВГ=13+13-1=25 км.
Г-Е-А=LГЕ+LЕА-LГА=13+5-18=0 км.
Таким образом, пункт Е должен находится между пунктами Г и А. Получаем кольцевой маршрут следующего вида (рис. 4).
2488565156210Е
00Е
2818765127000175196510160000
3517900126365Г
00Г
1459865128905А
00А
31489651879600172656518796000
2069465126365Б
00Б
2818765127000В
00В
232346517272000
Рисунок 4