Разработка оптимальных маршрутов доставки груза - Моделирование транспортных процессов

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

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

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

примерный вид графа транспортной сети

Рис. 1 Примерный вид графа транспортной сети

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

На любом этапе определения кратчайших расстояний от заданной вершины все множество вершин разбивается на три группы:

    1). Вершины, до которых кратчайшие расстояния уже найдены. 2). Вершины смежные с вершинами первой группы. 3). Все остальные.

Решение задачи состоит из нескольких этапов:

    1). Выбирается вершина из первой группы с минимальным кратчайшим расстоянием от начального. 2). Определяются расстояния до нее от смежных с ней вершин. 3). Вершина с минимальным кратчайшим расстоянием переводится из группы 2 в группу 1. 4). По завершении определения всех кратчайших расстояний лишние связи из графа убираются.

Алгоритм метода:

1. В приложении "Microsoft Excel" необходимо внести исходные данные, отражающие расстояние (время движения, стоимость перевозок) между пунктами сети (рис. 2).

заполнение исходных данных графа транспортной сети

Рис. 2 Заполнение исходных данных графа транспортной сети

2. Определяем расстояние от вершины 1 до смежных с ней вершин и заполняем таблицу, представленную на рис. 3, а.

а) б)

Рис. 3 Заполнение расчетной таблицы графа транспортной сети

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

Похожие статьи




Разработка оптимальных маршрутов доставки груза - Моделирование транспортных процессов

Предыдущая | Следующая