Планирование развозочных маршрутов методом Кларка-Райта

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

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

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

Для решения задач маршрутизации перевозок мелкопартийных грузов существует 2 группы методов:

получение точных результатов

получение приблизительных результатов.

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

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

"Выигрыш" от объединения пунктов i и j маршрутов определяется по формуле , где li,o-кратчайшее расстояние от пункта i до ГО, lo,j - кратчайшее расстояние от ГО до j пункта, li,j - кратчайшее расстояние от пункта i до пункта j.

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

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

В данном случае отыскивается максимальный "выигрыш" в столбце i и в строке j таблицы оценок, в зависимости от которого производят подключение очередного пункта в строящийся фрагмент маршрута.

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

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

Пример заполнения таблицы "выигрышей":

f 1-2=4+12-10=6,f 1-6=4+16-12=8,f 1-3=4+9-7=6,f 1-7=4+12-8=8,f 1-4=4+8-4=8,f 1-8=4+9-11=2,f 1-5=4+4-8=0,f 1-9=4+7-5=6,f 1-10=4+5-7=2.

Таблица № 9.

Таблица "выигрышей"