Грузовые перевозки: Сборник методических указаний к практическим занятиям, страница 13

В клетках столбцов А, В₁, В₂, …, В_n указаны расстояния (стоимости, время) проезда между любыми двумя пунктами.

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

Так выигрыш, т.е. величина сокращения длины пробега (стоимости, времени) автотранспортного средства при объединении маршрутов А - В_i - А  и  A - B_j - A определяется "функцией выгоды" по формуле

где  - расстояния от начального  пункта  А  до пункта  B_i и от А до B_j соответственно;

L_ij - расстояние между пунктами B_i и B_j.

Выигрыши от объединения каждой пары маятниковых маршрутов

Таблица 2

Кроме того, к матрице выигрышей присоединяется отдельный столбец (допустимые значения 0; 1 или 2) индикаторов J пунктов В_i Индикатор J_i строки В_i показывает, каким является пункт: внутренним (J=0), первым или последним (J=1) в развозочном или включен еще в маятниковый маршрут вида A – В_i – A     (J=2). Постепенно  производится  объединение  маятниковых  маршрутов в кольцевые (от большего выигрыша к меньшему).  Затем в  соответствующих строках меняются элементы первого и второго столбцов: в первых клетках указывается начальная загрузка автомобиля на объединенном  маршруте  и новые номера индикаторов. Максимальный выигрыш отыскивается в строках, которые соответствуют пунктам с индикаторами J=1 и J=2.

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

Порядок выполнения работы

13.  Изучить теоретическую часть работы.

14.  Пользуясь рассмотренным выше алгоритмом и программой, найти оптимальные маршруты перевозок клиентам предприятиями, расположенными на территории района, дорожная сеть которого показана в виде графа на рис. 1.

Студент в соответствии со своим номером в журнале должен выбрать вариант исходных данных из таблицы 1.

Таблица 1