Файл: Воркут А.И. Автомобильные перевозки партионных грузов учеб. пособие.pdf

На рисунке видно, между какими точками маршрута А — В —

— С — А должен быть включен пункт/). На практике необя­

пары пунктов находим величину приращения длины мар­

В нашем примере должны сопоставляться такие выражения:

Это суммы расстояний от точки D к двум соседним точкам на исходном маршруте за вычетом длины звена, которое из-за этого включения из маршрута выпадает. Приведен­ ные выражения показывают, на сколько увеличилась бы протяженность маршрута, включающего на один пункт больше, по сравнению с исходным. Поэтому пункт D вклю­ чаем в маршрут между теми двумя пунктами, для которых это увеличение является наименьшим. Если в нашем при­ мере наименьшим будет А/вс,-то новым маршрутом будет

А — В — D — С — А.

Далее необходимо включить в маршрут точку с пятой наибольшей суммой расстояний. Для этого вычисляем уже четыре выражения Alkp аналогично предыдущим.

104

Процесс продолжается до тех пор, пока в маршрут не будут включены все точки.

Проиллюстрируем метод составления маршрута на кон­ кретном примере. Составим маршрут завоза грузов из пунк­

4—А, не гарантирующий оптимальный результат, поэтому возможно улучшение.

Дополним матрицу суммой цифр столбцов.

В соответствии со значениями суммы цифр в столбцах

3 — А — 1—3.

Далее в исходный кольцевой маршрут включим пункт 2, для чего необходимо вычислить все варианты прироста

105

длины маршрута при включении точки 2 между пунктами

3 и А, А и 1, 1 и 3:

Д4—А = 4 —2+ 4 —А — 4—А = 1.3 |

Д/л—i = /л—2 + 4 —i— /л—i = 3,5 I A/i—з = min. A/i—з = l\—2 + 4—3 — А—з = 0,0 j

Наименьший прирост длины маршрута соответствует включению точки 2 между точкой 1 и 3 — 0 км.

Если в процессе решения получается несколько вариан­ тов включения с одинаковым приростом длины маршрута, выбирают любой из них. В рассматриваемом примере при­ рост A/i-з равен нулю. Это значит, что включаемый пункт находится в точке, через которую проходит исходный

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

Таким образом, пункт 2 целесообразно включить между пунктами Л и 1, что приводит к маршруту 3— А —4—1 —

— 2—3.

Так как грузоотправитель находится в точке А, то реко­ мендуется развозочяый маршрут

Л — 4 — 1— 2 — 3 — Л

или

Л — 3 — 2 — 1 — 4 — Л.

Этот же маршрут был нами выбранило кратчайшей связы­ вающей сети.

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

Недостатком метода является его трудоемкость при большом числе пунктов завоза, так как он требует опреде­ ления расстояния между всеми пунктами завоза и, кроме того, надо рассматривать большое число вариантов при

106

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

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

§ 4. МЕТОД ДАЦЕЯ

Метод. Дацея можно применять для составления развозочных маршрутов и в том случае, когда матрица расстояний несимметрична.

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

Достоинством метода является то, что нет необходимости заполнять все расстояния в матрице, поэтому не надо опре­ делять расстояния между отдаленными пунктами. Это зна­ чительно облегчает работу.

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

Расстояния между пунктами приведены в матрице

(табл. 18).

Отмечать элементы будем сверху вниз, а в каждом ряду слева направо.

Зачеркиваем оба значения 7,2, оба значения 6,2 и зна­ чение 5,5 (элемент 3—1).

107

После вычеркивания элемента 3—1 в третьем столбце останется только один элемент — это 3—2. Включаем зве­ но 3—2 в развозочный маршрут. В матрице его обводим кружком.

Так как из каждого столбца и ряда матрицы выбирают только один элемент, то необходимо после выбора каждого элемента вычеркнуть ряд и столбец, в котором этот элемент находится, и в дальнейшем не принимать во внимание вхо­ дящие в них элементы. Вычеркиваем второй ряд и третий столбец. Одновременно с выбором элемента i — / (в данном

случае 3—2 ) необходимо вычеркнуть элемент, противоле­ жащий по диагонали — / — i (2 —3), чтобы предотвратить краткий двучленный цикл (в нашем примере 3—2 —3).

Для различия зачеркиваем в противоположном направ­ лении.

108

Перепишем для наглядности матрицу (табл. 19). На прак­ тике при хорошем знании метода вся задача решается непрерывно в одной матрице.

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

Перечеркиваем третий ряд и первый столбец. Необхо­ димо воспрепятствовать возникновению кратких циклов. Для этого зачеркиваем противолежащий элемент (здесь он уже вычеркнут на предыдущем этапе). Кроме того, вычер­ киваем элемент 2 —1 , так как он вместе с уже выбранными элементами 3— 2 и 1—3 составил бы краткий цикл 3—2 —

—1—3.

Так как в матрице нет столбцов и строк с одним свобод­

ным элементом, зачеркиваем элемент 2—А, имеющий наи­ большее значение — 5,5. После этого во втором ряду и пя­ той строке остается по одному свободному элементу. Обве­ дем кружком элемент в пятой строке со значением 2 ,8 .

Вычеркиваем пятый ряд, четвертый столбец и противо­ положный элемент (табл. 2 0 ).

Другие элементы матрицы не вычеркиваем, так как н» один из оставшихся элементов (А — 1, 2—4) не образует краткого цикла.

Остаются два элемента (Л — 1 и 2—4), которые могут быть включены в маршрут. Включим вначале в маршрут элемент с меньшим значением 2—4.

109