Для решения задачи маршрутизации используем метод совмещенных матриц.
Представим исходные данные в виде таблицы
Таблица 10
|
ГО ГП |
Б1 (7) |
Б2 (6) |
Б3 (4) |
Б4 (3) |
Б5 (5) |
Итого по вывозу, ездок |
|
А1 (5) |
12 |
3 3 (5) |
6 4 (2) |
6 |
10 |
7 (7) |
|
А2 (8) |
6 2 |
8 |
12 |
5 |
3 4 (6) |
6 (6) |
|
А3 (2) |
6 2 (4) |
4 2 |
6 8 (10) |
1 6 (6) |
3 2 (0) |
20 (20) |
|
Итого по ввозу, ездок |
4 (4) |
5 (5) |
12 (12) |
6 (6) |
6 (6) |
33 (33) |
Холостые ездки обозначим числом в круглых скобках, груженые ездки занесем в матрицу в виде числа, выделенного жирным шрифтом.
Таким образом, получилась совмещенная матрица холостых и груженых ездок. С помощью этой матрицы будем формировать маршруты движения АТС.
На первом этапе выявляем маятниковые маршруты. Наличие в одной ячейке таблицы холостых и груженых ездок свидетельствует о необходимости использования маятникового маршрута. Количество ездок в маятниковом маршруте будет равно минимальному из значений количества груженых ездок и количества холостых ездок.
Маршрут 1: А1 - Б2 – А1 - 3 оборота
Маршрут 2: А1 – Б3 – А1 - 2 оборота
Маршрут 3: А2 – Б5 – А2 - 4 оборота
Маршрут 4: А3 – Б1 – А3 – 2 оборота
Маршрут 5: А3 – Б3 – А3 – 8 оборотов
Маршрут 6: А3 – Б4 – А3 - 6 оборотов
Объемы перевозок по маятниковым маршрутам вычитаем из загрузок соответствующих клеток и составляем новую матрицу для продолжения решения задачи (табл. 11).
На втором этапе составляем кольцевые маршруты. С этой целью строим замкнутые контуры. Вершины контура должны находиться в загруженных ячейках матрицы, при этом значения загрузок в вер- шинах контура должны чередоваться: сначала идет ячейка, содер- жащая груженые ездки, затем ячейка, содержащая холостые езд- ки, и т.д.
Каждый построенный контур соответствует кольцевому марш- руту. Количество ездок на маршруте соответствует наименьшему из числа холостых и груженых ездок по вершинам контура.
Например, построим контур А2Б1-А2Б5- А3Б5-А3Б1-А2Б1. В матрице сплошные линии расположены горизонтально и соответствуют перевозке груза. Пунктирные линии, расположенные вертикально, соответствуют подаче порожнего подвижного состава. Минимальная загрузка по этому контуру составляет две ездки. Строим кольцевой маршрут: