Методы определения кратчайших расстояний перевозок

Табличный метод:

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

На рис. 5 представлена модель участка транспортной сети, сформированная на основе карты экономического региона.

Задача о нахождении кратчайшего пути между пунктами (рис. 5) может быть в общем виде сформулирована на основе положений графов следующим образом. Дан граф

G = (x, y).

Каждому ребру графа приписано некоторое число (длина ребра) lij ≥ 0. Тогда любая цепь μ, составленная из нескольких ребер, характеризуется длиной l_μ. Требуется для двух произвольных вершин найти такой путь, чтобы его длина была наименьшей:

Рис. 5. Определение кратчайших расстояний по транспортной сети

методом потенциалов

Пусть задана транспортная сеть, состоящая из пунктовА₁, А_2…, А_i…,А_mи дорог, соединяющих эти пункты между собой. Длины участков дороги между каждой парой соседних пунктов А_i Аjизвестны и равны l_jj. Если два соседних пункта А_iиАjнепосредственноне соединены между собой участком дороги, то принимаем l_jj= ∞. Из начального пункта А₁ в

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

Переведём задачу на формальный язык. Обозначим каждый участок сети между двумя соседними пунктами А_i и Аj числом x_ij= 1, если он является звеном выбранного маршрута движения из А_i в А_m, и x_ij=0, если он не входит в этот маршрут. Тогда задача отыскания кратчайшего пути из А_i в А_m сводится к выбору чисел x_ij (i, j = 1, 2, …, m), при которых достигает минимума линейная форма

, (6.3)

при условии

i=2, 3, …, m-1; (6.4)

; (6.5)

; (6.6)

x _ij ≤ 1, i, j =1,2………….m(6.7)

Линейная форма (6.3) определяет длину маршрута между начальным и конечным пунктами. Условия (6.4) означают, что для любого 0≤ пункта маршрута А_i, исключая начальный и конечный, число дорог, входящих в этот пункт, равно числу дорог, выходящих из него. Поскольку l_ji>0 для всех I и j, условия (6.4) вместе с требованием минимизации линейной формы (6.3) означают, что из каждого пункта Аi (i=2, 3, …, m -1) выходит не более одной дороги. Условия (6.5) фиксируют тот факт, что количество дорог, выходящих из начального пункта маршрута, Аi превышает на единицу число дорог, входящих в этот пункт. Аналогично условия (6.6) указывает на то, что в последний пункт А_m входит на одну дорогу больше, чем выходит. Условия (6.5) и (6.6) вместе с условиями (6.4) и требованием минимизации линейной формы (6.3) означают, что в каждый пункт маршрута входит ровно одна дорога и из каждого пункта маршрута исходит ровно одна дорога. Наконец, условия (6.7) требуют, чтобы все x_ij были равны нулю или единице. В целом, соотношения (6.3-6.7) представляют собой определение кратчайшего пути на сети дорог между двумя заданными пунктами, т.е. аналитическую модель рассматриваемой задачи.

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

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

Общая вычислительная схема применительно к данной задаче следующая. В специальную таблицу (табл. 4) типа «шахматной»

Таблица 4

Базовая таблица. расчета расстояний между пунктами и индексов U и V

Пункт	Вспомо- гатель- ные	Пункт
А1	А2	…	Аj	…	Аm
Строка Столбец	υ1	υ2	…	υj	…	υm
А1	u1	l11	l12	…	l1j	…	l1m
А2	u2	l21	l22	…	l2j	…	l2m
…	…	…	…	…	…	…
Аi	ui	li1	li2	…	lij	…	lim
…	…	…	…	…	…	…	…
Аm	um	lm1	lm2	…	lmj	…	lmm

заносят расстояния l_ji от каждого пункта Аi ((i=1, 2, …, m) до всех соседних с ним пунктов Аi ((i=1, 2, …, m). После этого для каждого пункта Аi и Аj рассчитывают индексы u_i и υ_j следующим образом. Индекс u_i принимают равным нулю (u_i =0). Затем по порядку, начиная с первой строки таблицы, рассматривают клетки с заполненными l_ji. Если для некоторой заполненной клетки (I, j) индекс u_i уже известен, а υ_j - ещё нет, то определяют υ_j по формуле

υ_j= u_i+ l_ji. (6.8)

Если при определении очередного υ_j в i-м столбце имеется более одной клетки с записанными l_ji и известными u_i, то принимают

υ_j = min (u_i+ l_j). (6.9)

Найденные значения υ_j записывают в соответствующие клетки вспомогательной строки, а также в клетки вспомогательного столбца, исходя из правила: u₁= υ₁, u₂= υ₂, … u_m= υ_m. После определения всех индексов υ_j и u_i проверяют оптимальность данного решения, сравнивая все l_ji с их разностями (υ_j- u_i). Если для всех заполненных клеток соблюдается условие

l_ij ≥υ_j- υ_j, (6.10)

то решение оптимально и каждое найденное число υ_j дает кратчайшее расстояние от пункта А₁ до соответствующего пункта А_i, до соответствующего пункта Аj (i=1,2,…m). При

наличии хотя бы одной клетки с величиной l_ij <υ_j- u_i решение неоптимально и вычисления необходимо продолжить.

Предположим, что в клетке Аi _n Аj _n нарушено условие оптимальности (6.10), т.е.

li _njn< υ i _n- ui _n.

В этих условиях необходимо изменить решение следующим образом. Индекс υ _{j n} заменяют индексом υ` i _n, величину которого определяют по формуле

υ i _n= υ i _n+ li _njn.

На каждой итерации корректируют индексы υ_j у всех клеток с l_ij< υ_j- u_i, после чего решение снова проверяют на оптимальность. Вычисления повторяют до тех пор, пока в таблице не будет выполнено условие оптимальности (6.10).

При определении кратчайших расстояний от пункта А₂ до всех остальных принимают u₂=0, после чего находят все индексы и выполняют все описанные выше вычисления. При определении кратчайших расстояний от пункта А₃ до всех остальных принимают u₃=0 и т.д.

Методы планирования перевозок по сборно - развозочным маршрутам

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

При этих перевозках автомобили функционируют на развозочных, сборных, развозочно-сборных (далее развозочных) маршрутах в составе комплекса различных автотранспортных систем (РСТС). Используется классификация систем по комплексу признаков (выполняемая функция, конфигурация системы, мощность грузопотоков, количество пунктов погрузки-выгрузки и подвижного состава и другие). Все РСТС делятся на 9 видов.

1. Развозочная S_p – система, состоящая из пункта погрузки, множества пунктов разгрузки, транспортных связей между ними и одного автомобиля, осуществляющего доставку груза. Технологическая схема доставки груза представляет собой развозочный маршрут.

2. Сборная S_с – система, состоящая из множества пунктов погрузки, пункта разгрузки, транспортных связей между ними и одного автомобиля, осуществляющего доставку груза. Технологическая схема доставки груза представляет собой сборный маршрут.

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

4. Простая S_п – система, состоящая из множества S_p (S_с или S_pc), в которой осваиваются, по сравнению с предыдущими системами, большие грузопотоки.

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

5. Развозочная с центром погрузки S_рц – система, состоящая из совокупности S_p, в которой осваиваются, по сравнению с S_p, большие грузопотоки.

Пример функционирования S_рц - развоз газа в цистернах; развоз стеновых панелей с домостроительного комбината потребителям, раствора и другие.

6. Сборная с центром разгрузки S_сц – система, состоящая из совокупности S_с, в которой осваиваются, по сравнению со сборной системой, большие грузопотоки.

Пример функционирования S_сц – сбор и вывоз бытовых отходов на мусороперерабатывающий (сжигающий) завод, сбор и вывоз строительного мусора по системе «несменяемых» контейнеров.

7. Комбинированная первого вида S_к1 – система, состоящая из центрального пункта с несколькими фронтами погрузки (разгрузки и погрузо-разгрузки) и множества предыду

щих транспортных систем (кроме простой системы S_п), в которой по условиям перевозок работают несколько единиц или даже десятков автомобилей.

8. Комбинированная второго вида S_к2 – система, состоящая из центрального и множества периферийных пунктов погрузки и разгрузки, транспортных связей между ними и автомобилей, осуществляющих доставку груза.

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

9. Город-регион S_{r- p} – это система, состоящая из множества РСТС, приведенных выше, в которой по условиям перевозок работают несколько десятков и даже сотен автомобилей автотранспортного предприятия.

Для грузовых перевозок можно отметить следующие: метод перебора вариантов маршрута; метод сумм; метод «ветвей и границ»; Кларка-Райта и другие. Для пассажирских перевозок - метод Б.Л. Геронимуса и другие.

Необходимость учета при проектировании РСТС многочисленных требований и ограничений, часто противоречащих друг другу, особенностей функционирования реальных РСТС; выполнение значительного количества вычислительных процедур приводят к необходимости использования ЭВМ. Это обусловливает необходимость разработки обобщенного алгоритма проектирования РСТС, учитывающего особенности решения задачи проектирования для различных РСТС.

Метод перебора вариантов.

Число перестановок из w пунктов завоза (вывоза), включаемых в маршрут по w пунктам:

Pw = w!, (8.1)

где w! – факториал целого положительного числа w, который равен произведению: w! = 1·2·3…· w. При трех пунктах груза количество возможных маршрутов М = w! = 3! = 1·2·3 = 6, таким образом, возможны шесть маршрутов доставки груза из пункта А (см. табл. 5). Выбор маршрута осуществляется по критерию «минимум затрат», чему соответствует минимум пробега. При наличии двух и более маршрутов одинаковой протяженности цели системы соответствует минимум грузооборота на маршруте.

Таблица 5