Матрица выигрышей после составления маршрутов

Ввоз, ед.

Вывоз, ед.

При­знак

Марш­рут

гпп

ПО

*

*

*

*

*

*

 

Заносим эти данные в табл. 8.16. Значение признака для пунк­тов 5 и 7 становится равным 1. Пункт 8 является внутренним пунктом маршрута, и значение признака для него равно 0. Соот­ветствующие этому пункту строка и столбец исключаются из рас­смотрения.

Так как максимальная грузовместимость автомобиля составля­ет 240 единиц и больше нет пунктов с объемом ввозимого груза, менее чем 30 единиц, то можно исключить из рассмотрения лю­бые варианты объединения маршрута 0—7—8—5—0 с другими марш­рутами.

Из оставшихся для рассмотрения вариантов максимальный эффект, равный 8, может быть получен при объединении маятниковых маршрутов 0—2 —0 и 0—3 — 0. Суммарное количество ввози­мого груза при этом составит 140 единиц, а вывозимого груза -80 единиц. Организуем маршрут 3 и для его выполнения выбираем автомобиль грузовместимостью 160 единиц.

Возможный последний вариант объединения маршрутов 0-2 — 3 — О и О—1 — 0 может дать эффект, равный 6. Но суммарное количество ввозимого груза при таком объединении составит 250 единиц. Так как автомобиля соответствующей грузовместимости нет, от этого варианта придется отказаться.

Таким образом, остается последний маятниковый маршрут > 0—1—0 — маршрут 4. На этом построение маршрутов методом Кларка—Райта закончено.

Получены следующие результаты. Для выполнения развозочно-сборочных маршрутов согласно заданию необходимо:

два автомобиля грузовместимостью 240 единиц для выполне­ния маршрутов 1:0—6 — 4—9 — 0 (загрузка автомобиля при ввозе 230 единиц, а при вывозе 85 единиц) — и 2: 0 — 7 — 8 — 5 — 0 (за­грузка при ввозе 210 единиц, при вывозе 50 единиц);

два автомобиля грузовместимостью 160 единиц для выполне­ния маршрутов 3: 0—2 — 3 — 0 (загрузка при ввозе 140 единиц, при вывозе 80 единиц) — и 4: 0— 1 —0 (загрузка при ввозе 110 еди­ниц, при вывозе 25 единиц).

Пробег по объединенным маршрутам составляет 54 км (марш­рут 1), 31 км (маршрут 2), 16 км (маршрут 3), 20 км (маршрут 4).

Таким образом, суммарный пробег по объединенным кольце­вым маршрутам равен 121 км; суммарный пробег по маятнико­вым маршрутам равен 228 км. Пробег автомобилей сократился на 107км.

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

Решение задачи оптимального объезда точек в маршрутах. Ме­тод Кларка—Райта не гарантирует оптимальный порядок объезда пунктов внутри маршрута. Поэтому после получения кольцевых маршрутов необходимо для каждого маршрута решить задачу оп­тимального объезда пунктов в маршруте (эта задача еще называ­ется задачей коммивояжера) с целью сокращения общего пробега на маршруте.

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

Рассмотрим пример. Найдем оптимальный вариант объезда то­чек в маршруте 1, который проходит через пункты 0—6—4—9—0. Матрица кратчайших расстояний между пунктами этого маршру­та приведена в табл. 8.17. В итоговой строке каждой таблицы про­ставим сумму расстояний по каждому столбцу.

Затем выбираем три пункта маршрута, имеющих наибольшие суммы в итоговой строке. В данном случае это пункты 0, 6 и 9, которые образуют кольцевой маршрут 0—6 — 9 — 0.

В маршрут необходимо вставить пункт со следующей макси­мальной суммой в итоговой строке. В данном примере это пункт 4, он является последним пунктом, входящим в маршрут.

Пункт 4 может быть вставлен в маршрут между следующими парами пунктов (0 и 6), (6 и 9) или (9 и 0). Чтобы определить, между какими пунктами его следует вставить, необходимо найти минимально возможное увеличение длины маршрута ∆ lij обусловленное -

 

Таблица 8.17

Исходные данные для построения оптимальной последовательности объезда пунктов на маршруте

 

Пункты
Итого

включением пункта 4 в маршрут 0—6—9 — 0. Величину ∆ lij находят по формуле

(8.2)

где i и j — пункты, между которыми предполагается вставить новый пункт в маршрут; k — вставляемый в маршрут пункт; lik, lkj, lij — расстояние между соответствующими пунктами. Определим по формуле (8.2) увеличение длины маршрута 0 — 6 — 9 — 0 при включении в него пункта 4:

Минимальное увеличение длины маршрута и определяет место вставки нового пункта в маршрут. В данном примере минимальное увеличение длины маршрута, равное 0, получается при вставке пункта 4 в маршрут между пунктами 6 и 9. Таким образом, марш рут примет следующий вид: 0 — 6 — 4—9—0.

Если бы были еще пункты, не включенные в маршрут, надо было бы продолжить описанные действия. В данном примере пунктов, не включенных в маршрут, больше нет.

Получили маршрут 0 — 6—4—9—0. Последовательность объезда точек маршрута в данном случае совпала с последовательностью объезда точек, полученной в результате планирования мелкопартионных перевозок методом Кларка—Райта.