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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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



СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ПОСТАНОВКА ЗАДАЧИ

1. ТЕРРИТОРИАЛЬНО РАСПРЕДЕЛЕННЫЕ МЕТОДЫ

1.1 Метод потенциалов

1.2 Метод составления расписания перевозок

1.3 Метод поиска кратчайшего пути в графе на основе алгоритма Флойда

2. ИНСТРУМЕНТАЛЬНАЯ СИСТЕМА МОДЕЛИРОВАНИЯ И ФОРМИРОВАНИЯ ОПТИМАЛЬНЫХ ВАРИАНТОВ ТРАНСПОРТНОГО ОБСЛУЖИВАНИЯ

2.1 МАТЕМАТИЧЕСКИЕ МОДЕЛИ МЕТОДОВ

2.1.1 Математическая модель метода потенциалов

2.1.2 Математическая модель метода составления расписания перевозок

2.1.3 Математическая модель метода поиска кратчайшего пути в графе на основе алгоритма Флойда

3. СТРУКТУРА ИНФОРМАЦИОННОГО ОБЕСПЕЧЕНИЯ

3.1 Информационное обеспечение транспортной логистики

4. СТРУКТУРА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ

4.1 Load and Route Optimization

4.2 Logistics Master

4.3 ANTOR LogisticsMaster

4.4 TopLogistic

5. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ

5.1 Пользовательский интерфейс

6. РЕЗУЛЬТАТЫ ПРАКТИЧЕСКОЙ АПРОБАЦИИ МОДЕЛЕЙ ОПТИМАЛЬНОГО ПЛАНИРОВАНИЯ ТРАНСПОРТНОГО ОБСЛУЖИВАНИЯ

ВЫВОДЫ

ЛИТЕРАТУРА

ВВЕДЕНИЕ

Большинство современных крупных народно-хозяйственных систем технического и экономического характера представляет собой территориально распределенные системы.

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

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

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



ПОСТАНОВКА ЗАДАЧИ

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

Цель данной работы состоит в выборе наиболее эффективного метода исследования территориально распределённой задачи транспортного обслуживания. Эффективность метода будет определяться по нескольким критериям таким, как минимальные затраты по времени доставки груза от одного пункта до другого.

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

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



1. ТЕРРИТОРИАЛЬНО РАСПРЕДЕЛЕННЫЕ МЕТОДЫ

В соответствии с темой работы рассматриваются территориально распределённые транспортные системы. Такие системы обладают характерной особенностью: целевые объекты взаимодействуют с функциональными объектами и необходимыми ресурсами на локальном уровне. Иными словами, потребление ресурсов некоторым целевым объектом может сказаться на обеспеченности тем же ресурсом лишь для целевых объектов, расположенных в некотором смысле близко от рассматриваемого объекта. Помимо этого, данный тип систем характеризуется удаленностью объектов и ограниченностью ресурсов.

Для исследования большинства территориально распределенных систем существует два основных типа методов исследования. Данные методы исследования относятся к традиционным методам теории исследования операций: это вероятностно-статистические методы и методы оптимизации.

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



Рис. 1.1. Вероятностно-статистические методы

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рис. 1.2. Методы оптимизации

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

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

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

Транспортная логистика - это перемещение требуемого количества товара в нужную точку, оптимальным маршрутом за требуемое время и с наименьшими издержками. Затраты на создание любого товара складываются из себестоимости изготовления и издержек на выполнение всех работ от момента закупки материалов до момента покупки товара конечным потребителем. Большую часть стоимости составляют наценки каждого звена в цепи производитель -- конечный покупатель. Движение материального потока от первичного источника сырья до конечного потребления также требует затрат, которые могут доходить до 50 % от общей суммы затрат на логистику.

Для дальнейших исследований были выбраны три метода (рис. 1.3):

1. Метод потенциалов

2. Метод составления расписания перевозок

3. Метод поиска кратчайшего пути в графе на основе алгоритма Флойда

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



Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рис. 1.3. Приоритетные методы для исследования

1.1 Метод потенциалов

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

Кроме того, к задачам транспортного типа сводятся многие другие задачи линейного программирования - задачи о назначениях, сетевые, календарного планирования.

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

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

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

Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Пример структурной схемы транспортной задачи и оптимизации её плана перевозок показаны на рис. 1.4а и рис. 1.4б соответственно.



Рис. 1.4а Пример структурной схемы транспортной задачи

Рис. 1.4б. Оптимизация плана перевозок схемы, показанной на рис. 1.4а, методом потенциалов

1.2 Метод составления расписания перевозок

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

В наиболее общей формулировке задача составления расписаний состоит в следующем: с помощью некоторого множества ресурсов или обслуживающих устройств должна быть выполнена некоторая фиксированная система заданий. Цель заключается в том, чтобы при заданных свойствах заданий и ресурсов и наложенных на них ограничениях найти эффективный алгоритм упорядочивания заданий, оптимизирующий или стремящийся оптимизировать требуемую меру эффективности.

В качестве основных мер эффективности рассматривается общее количество перевезенного груза и общее время простоя при погрузочно-разгрузочных работах.

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

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

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



Рис. 1.5 Технологическая схема доставки

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

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

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

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

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

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

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

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

1.3 Метод поиска кратчайшего пути в графе на основе алгоритма Флойда

Теория графов относится к комбинаторным методам. Поиск кратчайшего пути в графе имеет применение для транспортной задачи.

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

Граф однозначно задан, если заданы множество его вершин, множество ребер и указаны все инцидентности (т.е. указано, какие вершины какими ребрами соединены). Наиболее наглядно граф задается рисунком; однако не все детали рисунка одинаково важны; в частности, несущественны геометрические свойства ребер (длина, кривизна и т.д.) и взаимное расположение вершин на плоскости.

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

Задача опирается на использование алгоритма Флойда.

Метод графов имеет широкое применение в определении оптимального пути. Также следует учесть, что задачи оптимизации расписания обслуживания и определения оптимального плана перевозок сводятся к задачам поиска кратчайшего пути в графе, которая реализуется на основе алгоритма Флойда.

Алгоритм Флойда -- алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного графа без циклов с отрицательными весами с использованием метода динамического программирования. Пример изображения данного алгоритма приведен на рис. 1.6.



Рис. 1.6. Пример реализации алгоритма Флойда для нахождения кратчайших расстояний между всеми вершинами взвешенного графа

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

Несмотря на сложность реализации задачи метод графов обладает возможностью применения на любом реальном объекте. Также данный метод отличается точностью расчета наиболее оптимального маршрута и других путей следования. Широко применяется в современных программных продуктах.

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



2. ИНСТРУМЕНТАЛЬНАЯ СИСТЕМА МОДЕЛИРОВАНИЯ И ФОРМИРОВАНИЯ ОПТИМАЛЬНЫХ ВАРИАНТОВ ТРАНСПОРТНОГО ОБСЛУЖИВАНИЯ

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

2.1 МАТЕМАТИЧЕСКИЕ МОДЕЛИ МЕТОДОВ

2.1.1 Математическая модель метода потенциалов

Транспортная задача ставится следующим образом: имеется m пунктов отправления А1, А2, ..., Аm, в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно а1, а2, ... , аm единиц. Имеется n пунктов назначения В1, В2, ..., Вn подавшие заявки соответственно наb1, b2, ..., bn единиц груза. Известны стоимости Сi,j перевозки единицы груза от каждого пункта отправления Аi до каждого пункта назначения Вj . Все числа Сi,j, образующие прямоугольную таблицу заданы. Требуется составить такой план перевозок (откуда, куда и сколько единиц поставить), чтобы все заявки были выполнены, а общая стоимость всех перевозок была минимальна.

Задача о перевозках, в которой сумма запасов ровна сумме заявок:

аi = bj (где i=1,...,m ; j=1,...,n) (2.1)

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

Баланс транспортной задачи может нарушаться в 2-ух направлениях

1. Сумма запасов в пунктах отправления превышает сумму поданных заявок

аi > bj (где i=1,...,m ; j=1,...,n);

2. Сумма поданных заявок превышает наличные запасы

аi < bj ( где i=1,...,m ; j=1,...,n );

Условимся первый случай называть “Транспортной задачей с избытком запасов“, а второй -- “Транспортной задачей с избытком заявок”.

Транспортная задача с избытком запасов.

В пунктах A1, A2, ... ,Am имеются запасы груза a1, a2, ... , am; пункты B1, B2, ... , Bnподали заявки b1, b2, ... , bn, причём

аi > bj (где i=1..m ; j=1..n)

Сверх имеющихся n пунктов назначения В1, B2, ... ,Bn, введём ещё один, фиктивный, пункт назначения Bn+1, которому припишем фиктивную заявку, равную избытку запасов над заявками

bn+1 = аi - bj (где i=1,...,m ; j=1,...,n),

Стоимость перевозок из всех пунктов отправления в фиктивный пункт назначения bn+1 будем считать равным нулю. Введением фиктивного пункта назначения Bn+1 с его заявкойbn+1 мы сравняли баланс транспортной задачи и теперь его можно решать, как обычную транспортную задачу с правильным балансом.

Далее рассмотрим транспортную задачу с характерным избытком заявок. Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления Am+1 с запасом am+1 равным недостающему запасу и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равным нулю.

Решение транспортной задачи начинается с нахождения опорного плана. Для этого существуют различные способы. Например, способ “северо-западного угла”, метод минимального элемента и метод Фогеля. Клетки таблицы, в которых стоят ненулевые перевозки, являются базисными. Их число должно равняться m + n - 1. Необходимо отметить также, что встречаются такие ситуации, когда количество базисных клеток меньше чем m + n - 1. В этом случае распределительная задача называется вырожденной. И следует в одной из свободных клеток поставить количество перевозок равное нулю.

Циклом в транспортной задаче мы будем называть несколько занятых клеток, соединённых замкнутой ломаной линией, которая в каждой клетке совершает поворот на 90.

Существует несколько вариантов цикла:

1) 2) 3)

Рис. 2.1. Варианты цикла

Нетрудно убедиться, что каждый цикл имеет чётное число вершин и значит, чётное число звеньев (стрелок). Условимся отмечать знаком “+” те вершины цикла, в которых перевозки необходимо увеличить, а знаком « - « те вершины, в которых перевозки необходимо уменьшить. Цикл с отмеченными вершинами будем называть “означенным”. Перенести какое-то количество единиц груза по означенному циклу -- это значит увеличить перевозки, стоящие в положительных вершинах цикла, на это количество единиц, а перевозки, стоящие в отрицательных вершинах уменьшить на то же количество. Очевидно, при переносе любого числа единиц по циклу равновесие между запасами и заявками не меняется: по-прежнему сумма перевозок в каждой строке равна запасам этой строки, а сумма перевозок в каждом столбце -- заявке этого столбца. Таким образом, при любом циклическом переносе, оставляющем перевозки неотрицательными допустимый план остаётся допустимым. Стоимость же плана при этом может меняться: увеличиваться или уменьшатся. Назовём ценой цикла увеличение стоимости перевозок при перемещении одной единицы груза по означенному циклу. Очевидно цена цикла ровна алгебраической сумме стоимостей, стоящих в вершинах цикла, причём стоящие в положительных вершинах берутся со знаком “+”, а в отрицательных со знаком “-“. Обозначим цену цикла через . При перемещении одной единицы груза по циклу стоимость перевозок увеличивается на величину. При перемещении по немуk единиц груза стоимость перевозок увеличиться на k. Очевидно, для улучшения плана имеет смысл перемещать перевозки только по тем циклам, цена которых отрицательна. Каждый раз, когда нам удаётся совершить такое перемещение, стоимость плана уменьшается на соответствующую величину k. Так как перевозки не могут быть отрицательными, мы будем пользоваться только такими циклами, отрицательные вершины которых лежат в базисных клетках таблицы, где стоят положительные перевозки. Если циклов с отрицательной ценой в таблице больше не осталось, это означает, что дальнейшее улучшение плана невозможно, то есть оптимальный план достигнут.

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

Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены.

Пусть имеется транспортная задача с балансовыми условиями

xi,j = ai (i=1..m ; j=1..n);

xi,j =bj (j=1..n ; 1..m),

причём ai = bj.

Стоимость перевозки единицы груза из Ai в Bj равна Ci,j; таблица стоимостей задана. Требуется найти план перевозок (xi,j), который удовлетворял бы балансовым условиям и при этом стоимость всех перевозок бала минимальна.

Идея метода потенциалов для решения транспортной задачи сводиться к следующему. Представим себе, что каждый из пунктов отправления Ai вносит за перевозку единицы груза (всё ровно куда) какую-то сумму i; в свою очередь каждый из пунктов назначения j также вносит за перевозку груза (куда угодно) сумму j. Эти платежи передаются некоторому третьему лицу (“перевозчику“). Обозначим i+ j=ci,j ( i=1..m ;j=1..n) и будем называть величину ci,j “псевдостоимостью” перевозки единицы груза из Aiв Bj. Заметим, что платежи i и j не обязательно должны быть положительными; не исключено, что “перевозчик” сам платит тому или другому пункту какую-то премию за перевозку. Также надо отметить, что суммарная псевдостоимость любого допустимого плана перевозок при заданных платежах (i и j) одна и та же и от плана к плану не меняется.

До сих пор мы никак не связывали платежи (i и j) и псевдостоимости ci,j с истинными стоимостями перевозок ci,j. Теперь мы установим между ними связь. Предположим, что план (xi,j) невырожденный (число базисных клеток в таблице перевозок ровно (m + n -1). Для всех этих клеток xi,j>0. Определим платежи (i и j) так, чтобы во всех базисных клетках псевдостоимости были равны стоимостям:

ci,j =i + j = сi,j, при xi,j>0.

Что касается свободных клеток (где xi,j= 0), то в них соотношение между псевдостоимостями и стоимостями может быть какое угодно.

Оказывается, соотношение между псевдостоимостями и стоимостями в свободных клетках показывает, является ли план оптимальным или же он может быть улучшен. Существует специальная теорема: Если для всех базисных клеток плана (xi,j> 0)

i +j=ci,j= сi,j,

а для всех свободных клеток (xi,j=0)

i +j=ci,j сi,j,

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

ci,j= сi,j (для всех базисных клеток) (2.2)

ci,j сi,j(для всех свободных клеток ) (2.3)

называется потенциальным планом, а соответствующие ему платежи (iи j) -- потенциалами пунктов Ai и Bj (i=1,...,m ; j=1,...,n). Пользуясь этой терминологией вышеупомянутую теорему можно сформулировать так: всякий потенциальный план является оптимальным. Итак, для решения транспортной задачи нам нужно одно -- построить потенциальный план. Оказывается, его можно построить методом последовательных приближений, задаваясь сначала какой-то произвольной системой платежей, удовлетворяющей условию (2.1). При этом в каждой базисной клетке получиться сумма платежей, равная стоимости перевозок в данной клетке; затем, улучшая план следует одновременно менять систему платежей. Так, что они приближаются к потенциалам. При улучшении плана нам помогает следующее свойство платежей и псевдостоимостей: какова бы ни была система платежей (i и j), удовлетворяющая условию (2.1), для каждой свободной клетки цена цикла пересчёта равна разности между стоимостью и псевдостоимостью в данной клетке: i,j= сi,j - сi,j.

Таким образом, при пользовании методом потенциалов для решения транспортной задачи отпадает наиболее трудоёмкий элемент распределительного метода: поиски циклов с отрицательной ценой.

Процедура построения потенциального (оптимального) плана состоит в следующем: в качестве первого приближения к оптимальному плану берётся любой допустимый план (например, построенный методом Фогеля). В этом плане m + n - 1 базисных клеток, где m -- число строк, n -- число столбцов транспортной таблицы. Для этого плана можно определить платежи (i и j), так, чтобы в каждой базисной клетке выполнялось условие:

i+j= сi,j (2.4)

Уравнений (2.4) всего m + n - 1, а число неизвестных равно m + n. Следовательно, одну из этих неизвестных можно задать произвольно (например, равной нулю). После этого изm + n - 1 уравнений (2.4) можно найти остальные платежи i, j, а по ним вычислить псевдостоимости: сi,j=i+ для каждой свободной клетки.

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



2.1.2 Математическая модель метода составления расписания перевозок

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

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

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



Таблица 2.1. Классификация автотранспортных систем доставки грузов

Примечание: ТС - количество транспортных схем перевозок грузов в системе; Аэ - количество подвижного состава в эксплуатации; N - количество пунктов погрузки и разгрузки в системе; J - средний интервал прибытия автомобилей в центральный грузовой пункт системы; Яцп - ритм работы центрального пункта; t - время ожидания грузовых операций подвижным составом; П, Р - условное обозначения пункта погрузки и разгрузки: - движение с грузом, движение без груза; Ws- выработка автомобиля; Qc - выработка системы

Все вышеназванные автотранспортные системы доставки грузов объединены общим понятием: системы нижнего уровня (уровня маршрута).

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

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

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

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

Центральный и периферийные пункты средних систем в силу сложившихся обстоятельств (планировки, механизации, режима работы и др.) имеют свой ритм работы, который может отличаться от ритма работы других участников транспортного процесса. В связи с этим появляются отдельные элементы системы, определяющие пропускную способность и, соответственно, ритм работы системы. Поэтому при описании ССДГ следует учитывать, что они могут быть насыщенными или ненасыщенными. Насыщение системы может произойти по двум условиям: по объему груза и по времени занятости постов погрузки-выгрузки.

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

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

Формулировка задачи построения модели функционирования ненасыщенной ССДГ производится следующим образом.

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

транспортный логистика граф территориальный распределённый

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

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

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

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

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

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

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

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

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

Алгоритм составления расписания делится на два этапа:

-составление пробного расписания;

-его оптимизация.

Рассмотрим алгоритм, применяемый в городских условиях.

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

На первом этапе выполняется рутинная работа, связанная с вычислением времени прибытия транспорта в конечные и промежуточные пункты. Составитель расписания визуально по минутным сеткам маршрутов и остановок оценивает качество расписания, изменяя настроечные параметры (изменение времени движения между остановками и времени разворота на конечных остановках). Ручной подбор этих параметров на основе опыта составителя позволяет добиться визуальной равномерности движения транспорта.

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

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

, (2.5)

где - весовые коэффициенты компонентов критериев оптимальности;

Мун- критерий оптимальности с точки зрения муниципалитета;

ТР- критерий оптимальности с точки зрения транспортного предприятия;

НАС- критерий оптимальности с точки зрения населения.

Критерий оптимальности (ОПТ) с точки зрения транспортного предприятия и конечного потребителя является противоречивым. Так, минимизация времени ожидания прямым образом связана с увеличением подвижного состава, а, следовательно, со снижением его загрузки и суммы дохода с рейса. С другой стороны, чрезмерное стремление увеличить доходность транспорта ведет к отказу населения от перевозок и к появлению конкурирующих транспортных организаций. Следовательно, оценка показателей эффективности должна проводиться с учетом:

-достижения гарантированного минимального экономического результата для транспортного предприятия и административных органов в пределах удовлетворительной нормы прибыли;

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

Рассмотрим муниципальный критерий подробнее:

, (2.6)

где Жi- желание ехать i-го пассажира: может быть равно 0 (если пассажир не хочет ехать) или 1 (пассажир хочет ехать);

Сmj- стоимость j-го проезда;

Пр- экономическая эффективность муниципального транспортного предприятия; A(x)- весовой коэффициент составляющейxкритерия;

д- дельта-функция.

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

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

Основное назначение транспортного параметра - стремление максимизировать прибыль для предприятия:

, (2.7)

где Д(t)- интенсивность поступления средств от осуществления перевозок;

З(t)- интенсивность всех затрат на осуществление перевозок (расходные материалы и топливо, оплата труда, амортизация, обязательные платежи, общепроизводственные расходы и т.п.). Увеличить прибыль можно за счет увеличения интенсивности поступления средств от осуществления перевозок, либо за счет уменьшения интенсивности затрат на эти перевозки.

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

, (2.8)

где б, в, г-весовые коэффициенты соответственно времени ожидания, стоимости, времени перемещения.

Данный критерий косвенно определяет возможность отказа от использования транспорта со стороны населения.

Критерий для населения в целом напрямую зависит от таких параметров как: стоимость проезда; время ожидания; время перемещения.

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

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

2.1.3 Математическая модель метода поиска кратчайшего пути в графе на основе алгоритма Флойда

Алгоритм Флойда является одним из методов поиска кратчайших путей в графе.

Прежде чем представлять алгоритм, необходимо ввести некоторые обозначения. Перенумеруем вершины исходного графа целыми числами от 1 до N (рис. 2.2).

Рис. 2.2 Неориентированный граф с шестью вершинами и девятью ребрами

Обозначим через di,jm длину кратчайшего пути из вершины i в вершину j, который в качестве промежуточных может содержать только первые m вершин графа. Напомним, что промежуточной вершиной пути является любая принадлежащая ему вершина, не совпадающая с его начальной или конечной вершинами.

Если между вершинами i и j не существует ни одного пути указанного типа, то условно будем считать, что di,jm=?. Из данного определения величин di,jm следует, что величина di,j0 представляет длину кратчайшего пути из вершины i в вершину j, не имеющего промежуточных вершин, т. е. длину кратчайшей дуги, соединяющей i с j (если такие дуги присутствуют в графе). для любой вершины i положим di,im=0. Отметим далее, что величина di,jm представляет длину кратчайшего пути между вершинами i и j.

Обозначим через Dm матрицу размера NxN, элемент (i, j) которой совпадает с di,jm. Если в исходном графе нам известна длина каждой дуги, то мы можем сформировать матрицу D0. Наша цель состоит в определении матрицы DN, представляющей кратчайшие пути между всеми вершинами рассматриваемого графа.

В алгоритме Флойда в качестве исходной выступает матрица D0. Вначале из этой матрицы вычисляется матрица D1. Затем по матрице D1 вычисляется матрица в D2 и т. д. Процесс повторяется до тех пор, пока по матрице DN-1 не будет вычислена матрица DN.

Рассмотрим основную идею, лежащую в основе алгоритма Флойда. Суть алгоритма Флойда заключается в проверке того, не окажется ли путь из вершины i в вершину j короче, если он будет проходить через некоторую промежуточную вершину m. Предположим, что нам известны:

1. кратчайший путь из вершины i в вершину m, в котором в качестве промежуточных допускается использование только первых (m - 1) вершин;

2. кратчайший путь из вершины m в вершину j, в котором в качестве промежуточных допускается использование только первых (m - 1) вершин;

3. кратчайший путь из вершины i в вершину j, в котором в качестве промежуточных допускается использование только первых (m - 1) вершин.

Поскольку по предположению исходный граф не может содержать контуров отрицательной длины, один из двух путей -- путь, совпадающий с представленным в пункте 3, или путь, являющийся объединением путей из пунктов 1 и 2 -- должен быть кратчайшим путем из вершины i в вершину j, в котором в качестве промежуточных допускается использование только первых m вершин. Таким образом,

di,jm=min{ di,mm-1+ dm,jm-1; di,jm-1}

Из соотношения видно, что для вычисления элементов матрицы Dm необходимо располагать лишь элементами матрицы Dm-1. Более того, соответствующие вычисления могут быть проведены без обращения к исходному графу.

Алгоритм:

1. Перенумеровать вершины графа от 1 до N целыми числами, определить матрицу D0, каждый элемент di,j которой есть длина кратчайшей дуги между вершинами i и j. Если такой дуги нет, положить значение элемента равным ?. Кроме того, положить значения диагонального элемента dii, которое равно 0.

2. Для целого m, последовательно принимающего значения 1...N определить по элементам матрицы Dm-1 элементы Dm.

3. Алгоритм заканчивается получением матрицы всех кратчайших путей DN, N - число вершин графа.

Напомним, для определения по известным элементам матрицы Dm-1 элементов матрицы Dm в алгоритме Флойда применяется рекурсивное соотношение:

di,jm=min{ di,mm-1+ dm,jm-1; di,jm-1}

di,jm - элемент матрицы Dm, di,jm-1- элементы матрицы Dm-1, найденной на предыдущем шаге алгоритма.

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

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

Эти методы охватывают весь спектр задач на транспортное обслуживание.

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

3. СТРУКТУРА ИНФОРМАЦИОННОГО ОБЕСПЕЧЕНИЯ

До того, как начать работать с программой моделирования и формирования оптимальных планов транспортного обслуживания, необходимо провести серьезную работу по сбору и подготовке исходных данных. Прежде всего, это данные, характеризующие транспортную сеть предприятия: данные о взаимном удалении узлов, о среднем времени прохождения отрезков дорог между соседними узлами, пункт дислокации ТС. Затем создать задание на оптимизацию: определить продолжительность периода времени, на котором будет построено расписание, определить множество объектов-исполнителей, заявок и обозначить взаимосвязи между ними.

Наиболее распространенная трактовка реляционной модели данных, по-видимому, принадлежит Дейту, который воспроизводит ее (с различными уточнениями) практически во всех своих книгах. Согласно Дейту реляционная модель состоит из трех частей, описывающих разные аспекты реляционного подхода: структурной части, манипуляционной части и целостной части. Пример использования реляционной модели данных приведена на рис. 3.1.



Рис. 3.1 Пример использования реляционной модели данных

В структурной части модели фиксируется, что единственной структурой данных, используемой в реляционных БД, является нормализованное n-арное отношение. По сути дела, в предыдущих двух разделах этой лекции мы рассматривали именно понятия и свойства структурной составляющей реляционной модели.

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

Наконец, в целостной части реляционной модели данных фиксируются два базовых требования целостности, которые должны поддерживаться в любой реляционной СУБД. Первое требование называется требованием целостности сущностей. Объекту или сущности реального мира в реляционных БД соответствуют кортежи отношений. Конкретно требование состоит в том, что любой кортеж любого отношения отличим от любого другого кортежа этого отношения, т.е. другими словами, любое отношение должно обладать первичным ключом. Как мы видели в предыдущем разделе, это требование автоматически удовлетворяется, если в системе не нарушаются базовые свойства отношений.