Методы оптимизации кольцевых развозочных маршрутов

 

Решение подобных задач рассмотрим на следующем примере развозки товаров. В соответствии с заказами потребителей городская овощная база обязуется 24.06.2012 г. обеспечить доставку овощей и фруктов согласно схеме представленной на рисунке 6.4. При этом известно, что удовлетворение потребностей соответствующих потребителей, которые отражены в таблице 6.8, будут осуществляться посредством автотранспорта грузоподъемностью 4 тонны. Требуется найти m замкнутых путей l₁, l₂, …, l_k, …, l_m из единственной общей точки К, чтобы выполнялось следующее условие:

 

 

 

 

Рисунок 6.4 – Схема взаимного размещения

овощной базы и потребителей:

К – овощная база; М₁– М₁₂ – потребители

 

 

Таблица 6.8 – Потребности заказчиков в овощах и фруктах

Пункты назначения	Потребность, тонн	Пункты назначения	Потребность, тонн
М1		М7
М2		М8
М3		М9
М4		М10
М5		М11
М6		М12

 

Подчеркнем, что существует несколько методов решения подобных задач: математического моделирования, графический и комбинированный.

І. Рассмотрим алгоритм реализации метода математического моделирования.

1. Строится кратчайшая сеть, связующая товарную базу и все пункты назначения без замкнутых контуров, начиная с пункта, который отстоит на минимальном расстоянии от товарной базы (в нашем случае это пункт М₅) (рисунок 6.5). Далее сеть строится таким образом, чтобы совокупный путь, соединяющий все пункты назначения и товарную базу (овощную базу К), был минимальный.

Рисунок 6.5 – Кратчайшая сеть, связующая овощную базу и пункты назначения

 

2. Затем по каждой ветви сети, начиная с пункта, наиболее удаленного от товарной базы К (считая по кратчайшей связующей сети – это пункт М₁₀), группируются пункты на маршруты с учетом количества ввозимого груза и грузоподъемности (вместимости) развозочного автотранспорта. При этом сумма грузов по группируемым пунктам маршрута должна быть равной или немного меньше грузоподъемности автомобиля, а общее число автомобилей – минимально необходимым (таблица 6.9).

 

Таблица 6.9 – Предварительные маршруты объезда пунктов назначения

 

№ маршрута	Пункты назначения	Потребность в продукции, тонн
	М10
М12
	Итого: 4
	М11
М9
М6
М4
	Итого: 4
	М4
М8
	Итого: 4
	М7
М3
М2
	Итого: 4
	М2
М1
М5
	Итого: 4

 

3. Определяется рациональный порядок объезда пунктов каждого маршрута (на примере маршрута № 2). Для этого строится таблица-матрица, в которой по диагонали размещаются пункты, включаемые в маршрут, и начальный пункт К, а в соответствующих клетках – кратчайшее расстояние между ними согласно рисунку 6.4 (таблица 6.10).

Таблица 6.10 – Таблица-матрица маршрута № 2

 

Номер строки	К
		М11
			М9
				М6
					М4
Сумма

 

Начальный маршрут строим для трех пунктов матрицы, имеющих наибольшие размеры сумм, показанных в строке (37; 35; 33), то есть пункты К, М₁₁, М₄. Для включения последующих пунктов выбираем из оставшихся пункт, имеющий наибольшую сумму – это пункт М₆ (сумма 29), и определяем, между какими пунктами его следует включить – К и М₁₁, М₁₁ и М₄, М₄ и К. Чтобы это решить, для каждой пары пунктов необходимо найти размер приращения маршрута по следующей формуле:

 

 

где С – расстояние, км;

i – индекс включаемого пункта;

k – индекс первого пункта из пары;

p – индекс второго пункта из пары.

 

При включении пункта М₆ между первой парой пунктов К и М₁₁ определяем размер приращения ∆ КМ₁₁ при условии, что i – М₆, k – К, p – М₁₁.

Получаем:

 

 

Таким же образом определяем приращения ∆ М₁₁М₄ = 0; ∆ М₄К = 2. Так как ∆ М₁₁М₄ = min, следовательно, пункт М₆ должен располагаться между пунктами М₁₁ и М₄ (К–М₁₁–М₆–М₄–К). Используя этот метод, определяем, между какими пунктами должны располагаться пункт М₉. После проведенных расчетов получаем следующий порядок объезда пунктов-потребителей предварительного маршрута № 2: К–М₉–М₁₁–М₆–М₄–К.

Важно подчеркнуть, что движение по полученному кольцевому маршруту можно осуществлять в двух направлениях: начиная обслуживание с пункта М₉ или с пункта М₄. Пути движения в обоих направлениях будут равны между собой (32 км), однако различными будут транспортные работы. Так, транспортная работа для направления движения с начальным пунктом М₉ будет равна 59 т-км (7км·4т + +3км·3т + 10км·2т + 2км·1т), тогда как для направления движения с начальным пунктом М₄ – соответственно 63 т-км (10·4 + 2·3 + 7·2 +3·1) (см. рисунок 6.4). Следовательно, более рациональным будет направление движения по маршруту с начальным пунктом М₉, так как при этом будет проделана меньшая транспортная работа.

Аналогичные расчеты проводятся для оставшихся маршрутов № 1, № 3, № 4 и № 5.

4. Составляется сводная маршрутная ведомость (таблица 6.11).

 

Таблица 6.11 – Сводная маршрутная ведомость

 

№ мар-шрута	Последовательность выполнения маршрута	Расшифровка	Протяженность пути движения на маршруте, км
	К→ М10→ М12→ К	К – овощная база М10 – магазин № 10 М12 – магазин № 12
	К→ М9→ М11→ М6→ М4→ К	К – овощная база М9 – магазин № 9 М11 – магазин № 11 М6 – магазин № 6 М4 – магазин № 4
	К→ М4→ М8→ К	К – овощная база М4 – магазин № 4 М8 – магазин № 8
	К→ М2→ М3→ М7→ К	К – овощная база М2 – магазин № 2 М3 – магазин № 3 М7 – магазин № 7
	К→ М5→ М2→ М1→ К	К – овощная база М5 – магазин № 5 М2 – магазин № 2 М1 – магазин № 1

Анализ таблицы 8.13 показывает, что совокупный пробег пяти автомобилей на пяти маршрутах в соответствии с проведенными оптимизационными расчетами согласно методу математического моделирования составляет 139 км.

 

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