Расчет оптимального замкнутого маршрута

Определим оценку для множества G14:

ξ(G14)=ξ(G13)+=252+0=252.

Матрица С(4) имеет размерность 2´2 и допускает включение в маршрут только двух пар городов (4,2) и (6,5), что соответствует шагам 5 – 6. В результате получаем цикл l(t)={(1,3), (5,1), (2,4), (3,6), (4,5), (6,2)}, отвечающий подмножеству G16. Длина цикла l(t) равна оценке подмножества G16: l(t)=ξ(G16)=252.

На основании данных о расстояниях между городами был разработан оптимальный маршрут коммивояжера. В разработке использовался метод ветвей и границ. На рисунке 2.2 приведена условная схема движения коммивояжера. Исходя из расчетов определено минимальное расстояние, равное 252 км, которое потребуется коммивояжеру, чтобы совершить полный рейс. В результате минимизации пройденного расстояния экономятся оборотные средства, и повышается скорость доставки клиентов в места назначения, что повышает уровень конкурентоспособности данного вида транспорта.

Рисунок 2.2 – Схема оптимального замкнутого маршрута коммивояжера

Популярные материалы:

Расчет средних технико-эксплуатационных показателей
Определяем эксплуатационное количество автомобилей Аэ =ΣАэ, авт. Аэ =4,81+4,14+4,31+4,18+4,29=21,73 авт. Определяем среднее время в наряде Тн ср = Тн ср =15,78 ч Определяем среднесуточный пробег Lcc = Lcc =184,44 ≈ 184 ...

Характеристика предприятия и объекта проектирования
Тип авто предприятия: таксопарк, АТП занимается перевозкой населения по городу. Таблица 1.1 – Характеристика предприятия и объекта проектирования Тип, модификация автомобиля Наименование исходных данных и обозначений единицы изме ...

Безопасность в чрезвычайных ситуациях. Дезактивация объекта, загрязненного радиоактивными веществами
В результате запроектной аварии на РОО с выбросом радиоактивных веществ произошло радиоактивное загрязнение объекта, рассматриваемого в дипломном проекте, а именно подвижного состава. Исходные данные для расчета радиационной разведки: Н ...