Задание №10

«ОПТИМИЗАЦИЯ СБОРНО – РАЗВОЗОЧНЫХ МАРШРУТОВ»

Данная задача формулируется следующим образом: необходимо сформировать сборный, развозочный или сборно – развозочный маршрут автомобиля для объезда нескольких пунктов, начиная с АТО (гаража) при минимизации общего пробега автомобиля. При этом известны расстояния между посещаемыми пунктами и АТО.

Задачу выбора оптимального маршрута для сборно – развозочного маршрута можно рассматривать как классическую задачу о коммивояжере.

Задачи о коммивояжере формулируются следующим образом. Имеется n пунктов, которые коммивояжер (автомобиль) должен посетить один раз. Известны расстояния между пунктами. Необходимо определить такой порядок посещения пунктов, чтобы суммарное расстояние, пройденное коммивояжером было минимальным.

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

Рассмотрим более простой метод, позволяющий получить решение, близкое к оптимальному.

Пусть автомобиль развозит продовольственные товары с базы А в магазины Б, В, Г, Д, Е. Расстояния между пунктами приведены в таблице.

Таблица

Таблица расстояний, км.

Пункты	А	Б	В	Г	Д	Е
А	-
Б		-
В			-
Г				-
Д					-
Е						-

Решение

1. Из пункта А (базы) находим ближайший пункт. Это будет пункт Д, расстояние до которого составляет 5 км. Тогда начало маршрута будет А→ Д.

2. К пункту Д ближе всего находится пункт Е, до которого 3 км. Тогда маршрут будет А → Д → Е.

3. К пункту Е ближайший пункт, в котором не останавливался автомобиль, будет пункт Г, на расстоянии также 3 км. Тогда маршрут будетА → Д → Е → Г с общим пробегом ℓ = 5+3+3=11 км.

4. Среди пунктов, которые не посетил автомобиль, ближайший будет пункт В. Он находится на расстоянии 2 км. Тогда маршрут автомобиля будетА → Д → Е → Г → В с общим пробегом ℓ = 5+3+3+2=13 км.

5. Расчеты повторяются до тех пор, пока автомобиль не посетит все запланированные пункты. Тогда в нашем примере кратчайший маршрут объезда автомобиля всех магазинов будет:

А → Д → Е → Г → В → Б → А

С общим пробегом:

ℓ = 5+3+3+2+3+11=27 км.

Постановка данной задачи может аппроксимировать следующей математической моделью:

Функция цели: необходимо минимизировать общий пробег автомобиля по объезду всех пунктов

()

При ограничениях:

1. Из каждого i-го пункта автомобиль направляется только в один j-й пункт:

()

2. В каждый j-й пункт автомобиль направляется в один из i-ых пунктов:

()

3. Переменная может принимать только 0 или 1.

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

Обозначения:

– искомая переменная, означающая что автомобиль из i-го пункта должен направиться в j-й пункт;

– расстояние между i-м и j-м пунктами, км.

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

Для этого методом простого перебора поочередно попарно всех пунктов маршрута. По минимальному суммарному расстоянию от этих пунктов до АТО выбираются начальный и конечный пункт маршрута.

Варианты исходных данных

№ вар	Пункты

№ вар	Пункты

Расстояния до АТО, км

Транспортная система региона

АТО

Практическое задание №11

ОПТИМИЗАЦИЯ НУЛЕВЫХ И ПОРОЖНИХ ПРОБЕГОВ ПРИ ИСПОЛЬЗОВАНИИ МАЯТНИКОВЫХ МАРШРУТОВ (Г-207)

---

Дата добавления: 2015-10-16