ИСХОДНЫЕ ДАННЫЕ
Из пункта А (база)доставляется груз в 11 других пунктов, перечисленных в исходных данных, изкоторых в свою очередь необходимо в пункт А доставить груз, например возвратнуютару (рисунок 1). Количество единиц груза доставляемого из пункта А в каждый изних, дан в исходных данных.
Вместимость одногоавтомобиля составляет не более 250 ед. груза. Необходимо организовать перевозкимежду пунктами наименьшим пробегом автомобиля.
Таблица 1 – ИсходныеданныеПункт Ввоз Вывоз Б 10 30 В 30 20 Г 50 55 Д 20 80 Е 15 40 Ж 70 30 З 45 70 И 20 25 К 100 40 Л 50 20 М 30 30 ИТОГ 440 440
/> /> /> /> /> /> /> /> />
Рисунок 1 – Схемаразмещения пунктов и расстояния между ними
РЕШЕНИЕ:
Решение находится путемпоследовательного расчета по нескольким этапам.
1 этап – нахождениекратчайшей связывающей сети.
Пусть все пункты,указанные на рисунке 1, называются вершинами сети, а линия, соединяющая двесоседние вершины, — звеном; незамкнутая сеть, связывающая две и более вершины сминимальной суммарной длиной всех соединяющих их звеньев; кратчайшейсвязывающей сетью.
Она определяетсяследующим образом:
1) на сети находим меньшее звено В-Г=2км;
2) рассмотрим все звенья, связанные содной из своих вершин с выбранным звеном, т. Е. звенья В-А=9; В-Б=3; В-Д=4;Г-Б=2; Г-Д=4; Г-Е=4;
3) из них выбираем звенья с наименьшимрасстоянием Г-Б=2;
4) рассмотрим звенья, связанные свершинами полученной линии В-Г-Б, и из них выберем наименьшее (при этом нельзявыбирать звено, соединяющее две ранее включенные в сеть вершины), такое звено –В-Б;
5) другими звеньями связанными своимивершинами с уже выбранной сетью являются звенья В-А, В-Д, Г-Д, Г-Е, Б-Е(последние 4 имеют = наименьшие расстояния);
6) примем наименьшее Б-Е и получим сетьВ-Г-Б-Е. На рисунке 2 представлена кратчайшая связывающая сеть;
/> /> /> /> /> /> /> /> /> /> /> /> /> /> />
100 /> /> /> /> /> />
30 /> /> /> />
Рисунок 2 – Кратчайшаясвязывающая сеть
7) условиями задачиустановлено, что вместимость автомобиля – 250 ед. груза; исходя из этого пункты,указанные на рисунке 2 можно сгруппировать, так как это сделано в таблице 2;
Таблица 2 – ГруппировкамаршрутовПункты Маршрут №1 Пункты Маршрут №2 Количество груза, ед. Количество груза, ед. Ввоз Вывоз Ввоз Вывоз Б 10 30 Д 20 80 В 30 20 И 20 25 Г 50 55 К 100 40 Ж 70 30 Л 50 20 Е 15 40 М 30 30 З 45 70 ИТОГО 220 195 ИТОГО 220 245
2 этап — набор пунктов в маршруты
Покаждой ветви сети, начиная с той, которая имеет наибольшее число звеньев,группируют пункты в маршруты с учетом количества ввозимого и вывозимого груза ивместимости подвижного состава. Если все пункты данной ветви не могут бытьвключены в один маршрут, то ближайшие к другой ветви пункты группируются вместес пунктами этой ветви.
В нашемслучае условиями задачи установлено, что максимальная вместимость автомобилясоставляет 250 ед. груза. Исходя из этого пункты, указанные на рисунке 2, можносгруппировать так, как это сделано в таблице 2.
3 этап –определение очередности объезда пунктов маршрута
На этомэтапе все пункты маршрута, начиная с А, связываются тонкой замкнутой линией,которая соответствует кратчайшему пути объезда этих пунктов.
Длямаршрута №1
/>
Рисунок 3 – Маршрут №1
/>Для маршрута №2/> /> /> /> /> /> /> /> /> /> /> />
20 /> /> /> /> /> /> /> /> /> />
30 /> /> />
Рисунок 4 – Маршрут№2
Известнонесколько методов расчета кратчайшего пути объезда заданных пунктов. Какправило, все они являются приближенными. Одним из наиболее простых является такназываемый метод сумм, с помощью которого строится таблица, называемаясимметричной матицей. На главной диагонали в ней располагаются пункты,включаемые в маршрут.
Длямаршрута №1 симметричная матрица представлена в таблице 3.
Таблица3 – Симметричная матрица для маршрута №1А 6 7 11 9 9 6 6 Ж 5 9 9 11 8 7 5 Е 4 4 6 13 11 9 4 Б 2 3 17 9 9 4 2 Г 2 15 9 11 6 3 2 В 15 6 8 13 17 15 15 З 48 48 39 46 41 46 74
Цифрыпоказывают расстояние между этими пунктами. Дополнительно в этой матрицеимеется итоговая строка — строка сумм. В ней проставляется сумма расстояний покаждому столбцу.
Затемстроим начальный маршрут из 3 пунктов имеющих максимальную сумму, в нашемслучае – АЖЗА. В него включаем следующий пункт с максимальной суммой – Б. Чтобыопределить, между какими пунктами его ставить необходимо поочередно включать егомежду каждой соседней парой.
При этомнаходим величину прироста пробега автомобиля на маршруте при его включении.
/>
/>
/>
Изполученных значений выбираем минимальную и между соответствующими ей пунктамивставляем данный. В нашем случае это — />= 14 км, поэтому получаем маршрут – АБЖЗА.
/>км.
Вновьнаходим в таблице 3 пункт не принимавшийся в расчете, в нашем случае это – В.Все дальнейшие расчеты производим аналогично.
/> - min
/>
/>
/>
/>км.
Затем вполученную последовательность вставляем пункт Г
/>
/> - min
/>
/>
/>
/>км.
Затем вполученную последовательность вставляем пункт Е
/>
/>
/>
/> - min
/>
/>
/>км.
Можноутверждать, что полученная последовательность объезда пунктов маршрута даетнаименьший или весьма близкий к наименьшему путь движения, так как при движенииавтомобиля по ранее выбранному маршруту общее расстояние равно 48 км, а скорректированный – 36 км, что дает уменьшение расстояния на 12 км.
Помаршруту № 2 проводим аналогичные расчеты.
Составляемсимметричную матрицу для маршрута №2, которая представлена в таблице 4.
Таблица4 – Симметричная матрица для маршрута №2А 5 9 8 11 6 5 Д 14 13 16 11 9 14 Л 2 7 3 8 13 2 К 5 2 11 16 7 5 М 6 6 11 3 2 6 И 39 59 35 30 45 28
Строим начальныймаршрут из 3 пунктов имеющих максимальную сумму, в нашем случае – АДМА. В неговключаем следующий пункт с максимальной суммой – Л. Чтобы определить, междукакими пунктами его ставить необходимо поочередно включать его между каждойсоседней парой.
При этомнаходим величину прироста пробега автомобиля на маршруте при его включении.
/>
/> — min
/>
Изполученных значений выбираем пункт с минимальным значением и междусоответствующими ей пунктами вставляем данный. В нашем случае это — />= 5 км, поэтому получаем маршрут – АДЛМА.
/>км.
Вновьнаходим в таблице 4 пункт не принимавшийся в расчете, в нашем случае это – К.Все дальнейшие расчеты производим аналогично.
/>
/>
/> — min
/>
/>км.
Затем вполученную последовательность вставляем пункт И
/>
/> - min
/>
/>
/>
/>км.
Можноутверждать, что полученная последовательность объезда пунктов маршрута даетнаименьший или весьма близкий к наименьшему путь движения, так как при движенииавтомобиля по ранее выбранному маршруту общее расстояние равно 39 км, а скорректированный – 37 км, что дает уменьшение расстояния на 2 км.
На рисунках5 и 6 представлены скорректированные схемы движения автомобилей по маршрутам №1 и 2 (выделены пунктирной линией).
Длямаршрута №1
/>
Рисунок 5 – Маршрут №1
/>Для маршрута №2/> /> /> /> /> /> /> /> /> /> />
30 /> /> />
Рисунок 6 – Маршрут№2
автомобиль пробег маршрут
Если бы указанныемаршруты являлись только развозочными или только сборными, то на этом всерасчеты заканчивались.
В нашемслучае же по маршруту одновременно осуществляется развоз и сбор груза, поэтому необходимопровести дополнительный четвертый этап расчетов.
4 этап –определение возможности одновременного развоза и сбора груза на маршруте
Так каквместимость подвижного состава ограничена, необходимо проверить возможность егоиспользования для одновременного развоза и сбора груза на маршруте в тойпоследовательности объезда пунктов, которая получена на предыдущем этаперасчетов. Покажем это на примере расчета скорректированных маршрутов № 1 и 2.
Маршрут№ 1 по полученному решению должен иметь следующую последовательность объездапунктов: АВГБЕЖЗА. Проверяем, какое при этом количество груза будет находитьсяв автомобиле на протяжении всего маршрута. Сделаем это в таблице 5, где даныпункты маршрута в полученной последовательности и расчет наличия груза вавтомобиле после погрузки и выгрузки в каждом пункте. Из этой таблицы видно,что на протяжении всего маршрута автомобиль не будет перегружен, так какмаксимальная загрузка автомобиля — 250 ед. груза.
Таблица5 – Определение количества груза в автомобиле при движении его по маршруту №1Пункты Количество груза, ед. Пункты Количество груза, ед. Прибытие Отправление Всего в автомобиле Прибытие Отправление Всего в автомобиле А - 70 70 Б 10 30 85 В 30 20 60 Е 15 40 110 Г 50 55 65 Ж 70 30 70 З 45 70 95
Втаблице 6 сделаем то же самое для маршрута № 2: АДИЛКМА.
Таблица6 – Определение количества груза в автомобиле при движении его по маршруту №2Пункты Количество груза, ед. Пункты Количество груза, ед. Прибытие Отправление Всего в автомобиле Прибытие Отправление Всего в автомобиле А - 185 185 Л 50 20 220 Д 20 80 245 К 100 40 160 И 20 25 250 М 30 30 160
ВЫВОД:
принятые маршрутыобеспечат наименьшее расстояние перевозки, а также автомобиль в процесседвижения по этим маршрутам не будет перегружен, что и требовалось доказать.
СПИСОК ИСПОЛЬЗОВАННЫХИСТОЧНИКОВ
1 Витязев, М. В.Экономико-математические методы в управлении перевозками [Текст]: курс лекций/ М. В. Витязев. – Архангельск, 2007.
2 Геронимус, Б. Л.Экономико-математические методы в планировании на автомобильном транспорте[Текст]: учебник для вузов / Б. Л. Геронимус. – М.: Транспорт, 1977.
3 Кожин, А. П. Математические методыв планировании и управлении грузовыми автомобильными перевозками [Текст]:учебник / А. П. Кожин. – М.: Высшая школа, 1979. – с. 94-102.