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

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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

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.LoadandRouteOptimization

4.2. Logistics Master

4.3. ANTOR LogisticsMaster

4.4. TopLogistic

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

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

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

ВЫВОДЫ

ЛИТЕРАТУРА

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 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. Предположим, что нам известны:

кратчайший путь из вершины i в вершину m, в котором в качестве промежуточных допускается использование только первых (m - 1) вершин;
кратчайший путь из вершины m в вершину j, в котором в качестве промежуточных допускается использование только первых (m - 1) вершин;
кратчайший путь из вершины 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 до N целыми числами, определить матрицу D0, каждый элемент di,j которой есть длина кратчайшей дуги между вершинами i и j. Если такой дуги нет, положить значение элемента равным . Кроме того, положить значения диагонального элемента dii, которое равно 0.
Для целого m, последовательно принимающего значения 1...N определить по элементам матрицы Dm-1 элементы Dm.
Алгоритм заканчивается получением матрицы всех кратчайших путей 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-арное отношение. По сути дела, в предыдущих двух разделах этой лекции мы рассматривали именно понятия и свойства структурной составляющей реляционной модели.

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

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

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

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

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

Входные данные для работы системы разделяются на два информационных блока (рис. 4.1):

1) Блок данных задания на составление расписания.

2) Блок данных транспортной сети.

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

Рис. 3.2. Входные данные для работы системы

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

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

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

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

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

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

Основным побудительным мотивом применения логистических информационных систем (ЛИС) на транспорте является повышение производительности интегрированных транспортных систем, получение качественной информации на всех иерархических уровнях, существенное снижение совокупных затрат. Центральная идея звучит так: «Удачные фирмы имеют хорошие формальные и неформальные информационные системы, неудачные – тратят огромные суммы денег на компьютерные системы, но не знают, как правильно их использовать и выбирать информацию, которую эти системы должны содержать».

Управление данными в ЛИС обеспечивает все виды операций, необходимых для исполнения заказов по транспортировке грузов, контроля за операциями и оценки их эффективности. В результате ИОТЛ формируется два информационных потока:

1) планирование и координация производственной, транспортной деятельности и размещение запасов;

2) оперативная деятельность, связанная с управлением транспортированием и грузопереработкой.

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

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

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

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

Цель ИОТЛ заключается в том, чтобы получить возможность эффективного управления, контроля и комплексного планирования движения транспортно-материального потока. Все более насущной становится проблема непрерывного учета результатов функционирования системы, что способствует оперативному внесению изменений как в построение, так и реализацию хода интегрированного процесса «поставка – транспортировка».

Информационный процесс с помощью информационных технологий реализуется со следующими основными функциями:

-транспортировка потоков информации внутри ЛИС;

-накопление информации и хранение данных в базе знаний;

-фильтрация потока – избирательная переработка одних и «фильтр» других информационных данных и сопровождающих документов;

-объединение и разделение информационных потоков в структуре ЛИС и сетях коммуникаций;

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

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

В этой связи ИОТЛ должно соответствовать следующим основным требованиям:

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

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

-полнота информационного обслуживания выполняемых процессов (операций) и доведение необходимой информации до конкретного потребителя;

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

Информационные ресурсы интегрированной логистики представлены на рис. 3.2 в виде своеобразного «дерева», состоящего из 12 базовых элементов и отражающего логику изучаемого материала.

Рис. 3.3. Информационные ресурсы транспортной логистики

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

-базовых логистических операций;

-управленческого контроля;

-анализа оперативных и стратегических решений.

ЛИС для эффективного обслуживания ТЛП должна иметь такие качества, как:

-доступность – простота и легкость доступа к логистической информации;

-точность – информация должна точно отражать текущие операции,

-динамичность – изменение процессов при выполнении заказов, консолидации грузов при грузопереработке в транспортных терминалах;

-своевременность - информация измеряется промежутком времени между моментом, когда происходит событие, и моментом, когда оно находит отражение в ЛИС;

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

-гибкость – структура информационной системы должна предусматривать ее совершенствование и настройку на нужды клиентов;

-эффективность оформления отчетных данных – экраны ПК и отчеты должны содержать нужную информацию в удобной форме.

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

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

На вход поступают исходные данные, то есть транспортная сеть предприятия и задание на обслуживание.

Рис. 4.1. Входные данные

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

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

4.1. LoadandRouteOptimization

Компания “Консид Решения” для решения задач оптимизации загрузки транспорта и формирования оптимальных маршрутов доставки грузов предлагает своим Заказчикам програмный продукт Load and Route Optimization от компании Accellos (Канада). Load and Route Optimization позволит логистическим операторам, дистрибьюторам, розничным сетям, производителям и компаниям перевозчикам минимизировать транспортные затраты и увеличить оптимальность использования ресурсов. Это решение комбинирует оптимизацию загрузки груза в транспорт, планирование отгрузок и поддержку маршрутизации с учетом наименьшей стоимости. Load and Route Optimization может использоваться как отдельное программное решение, которое может быть интегрировано с любой WMS, TMS, ERP или диспетчерской системами. Данное решение предназначено для формирования отгрузок и маршрутов доставки заказов со склада распределительного/ дистрибутивного центра или логистического оператора по клиентам: магазинам, конечным потребителям, региональным складам. Пример пользовательского интерфейса и работы программы приведен на рис. 4.2.

Рис. 4.2. Пример работы и пользовательского интерфейса программы LoadandRouteOptimization

Load and Route Optimization позволит:

-Уменьшить транспортные расходы. Автоматизация управления загрузкой транспорта и маршрутизацией позволит сократить транспортные расходы на 10-20%.

-Сэкономить время. Уменьшить затрачиваемое время на распределение заказов, формирование отгрузок и разработку маршрутов.

-Управлять временными окнами доступности ворот (доков). Вести список занятости ворот (доков) и крайними сроками ожидания траспорта в каждый промежуток времени.

-Увеличить эффективность использования траспорта. Минимизировать простои, пробег транспорта по маршруту и расход топлива.

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

-Улучшить доступ к информации. Возможность доступа к решению из любого Веб-браузера через Internet.

4.2. LogisticsMaster

Система«Logistics» Master компании ANTORпредназначена для автоматизации планирования маршрутов доставки продукции. Не слишком дорогая и в меру гибкая. Торговая маркаTopPlanизвестна своими качественными, но дорогими решениями по автоматизации транспортной и логистической сферы, справочниками и картами. Вот несколько их программных продуктов: TopLogistic — для управления транспортной логистикой и перевозками, оптимизации маршрутов; TopPlan Monitoring — мониторинг транспорта.

При использовании самостоятельных решений многие компании сталкиваются с проблемой синхронизации данных в 1С. Транспортные программы включают в себя не только независимые продукты, но и отдельные модули для более крупных систем, таких как 1С. Можно назвать следующие: «1С: Диспетчер» и «1С: Управление автотранспортом», которые предлагают решение типичных задач и автоматизируют транспортное направление.

4.3. ANTORLogisticsMaster

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

Рис. 4.3. Пример работы АNTOR LogisticsMaster™

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

Рассчитанные с помощью ANTOR LogisticsMaster™ маршруты оптимизируются по двум основным параметрам:

-Должен быть обеспечен минимальный пробег (общий и для каждой машины в отдельности).

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

Благодаря подобному подходу пользователи получают:

-Сокращение на 20-30% фактического пробега и количества используемых транспортных средств (как собственных, так и арендуемых).

-Сокращение на 15-25% затрат на закупку топлива (наибольшая эффективность достигается при использовании системы планирования маршрутов ANTOR LogisticsMaster™ совместно с системой спутникового GPS/ГЛОНАСС мониторинга ANTOR MonitorMaster).

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

-Повышение на 10-15% загрузки каждого рейса (коэффициента использования транспортных средств).

Области применения

Система АNTOR LogisticsMaster™ служит для автоматизации управления доставкой и предназначена для:

-производственных компаний, осуществляющих доставку своей продукции клиентам и партнерам;

-оптовых торговых компаний, доставляющих товары своим клиентам (прямая дистрибуция);

-транспортных и логистических компаний, оказывающих услуги перевозки грузов;

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

-муниципальных органов власти (управление работой муниципального транспорта и специальной техники);

-строительных организаций (планирование работы строительной техники).

Преимущества системы АNTOR Logistics Master™

Внедрение АNTOR Logistics Master™ позволяет не только сократить время планирования доставки грузов, но и улучшить ее качество:

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

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

-Система автоматизации планирования доставки повышает лояльность клиентов, т.к. доставка осуществляется вовремя.

-Повышается эффективность контроля выполнения плана и расхода топлива на основе объективных расчетов.

Исходные данные

1. Список заявок на доставку товара на один день. Заявки на доставку на каждый день импортируются из информационной системы заказчика.

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

-грузоподъемность;

-максимально допустимый объем груза;

-статус автомобиля (собственный или арендованный);

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

-максимально допустимая продолжительность рейса;

-тип разгрузки автомобиля (боковой или задний борт).

3. Адрес склада.

4. Компьютерная карта региона с описанием транспортной сети (входит в состав АNTOR LogisticsMaster™).

4.4. TopLogistic

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

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

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

Рис. 4.3. Пример работы TopLogistic

TopLogistic комплектуется модулем GPS/ГЛОНАСС –мониторинг для контроля в режиме реального времени транспорта и записи маршрутов перемещения в архив. Это позволяет сравнивать плановый и фактический пробег автомобилей.

Система обеспечивает:

-автоматизацию работ по распределению заказов по автомобилям;

-автоматизированный расчет маршрутов доставки заказов;

-визуализацию адресов и маршрутов доставки на электронной карте;

-формирование оптимального порядка объезда точек доставки с возможностью его изменения.

Система использует для расчётов:

-базу данных автотранспорта с характеристиками каждого а/м;

-базу данных точек доставки с адресами, привязанными к карте;

-базу данных заказов клиентов с количественными характеристиками.

Система рассчитывает:

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

-потребность в автомобилях для обеспечения развозки.

Система учитывает:

-рабочее время каждого автомобиля;

-ограничения по количеству точек доставки для автомобилей;

-продолжительность разгрузки заказа в точке доставки;

-возможность подъезда автомобилей определенного типа к точке доставки;

-зональный принцип формирования заказов.

Система комплектуется:

-модулем работы с картой;

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

-модулем GPS/ГЛОНАСС мониторинга с возможностью on-line контроля местонахождения а/м и получения план/факта маршрутов доставки;

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

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

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

Отчеты и документы:

-маршрутные листы и маршруты движения для каждого автомобиля;

-сводные документы и отчеты по клиентам, заказам;

-отчеты по результатам маршрутизации;

-отчеты по заданному пользователем шаблону.

Интеграция с внешними системами:

-экспорт и импорт данных через независимые от конкретной системы файлы;

-бухгалтерия, склад, финансы и др.;

-управленческие системы (ERP, CRM, SCM и т.д.).

Помимо готовых программных продуктов решение задач может быть осуществлено с помощью такого программного продукта, как Microsoft Office Excel.

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

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

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

На основании выбранной математической модели разработан программный продукт “Программа моделирования и оптимизации обслуживания запросов транспортной системой”.

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

Программа обеспечивает пользователю следующие возможности:

- выбор количества узлов в сети, и их координат;

- выбор среднего времени перемещения между узлами;

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

- вывод информации об объектах;

- отображение вспомогательной информации;

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

- генерацию отчета о передвижении объектов-исполнителей, и исполнении заявок;

- генерацию отчета о передвижении транспортных средств.

Программный продукт разработан в среде визуального программирования QT.

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

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

- главное меню (состоит из пунктов, описанных в табл. 5.1);

- область для графического отображения объектов транспортной сети;

- область для текстового отображения;

Таблица 5.1 Функциональность главного меню

Добавить узел	Добавляет узел транспортной сети
Добавить ребро	Создаёт связь между существующими узлами
Добавить Старт/Финиш	Указывает программе начальную и конечную точку пути

Рис. 5.1. Структурная схема программной реализации.

Интерфейс программы представлен на рис. 5.2. Здесь представлены основные элементы, описанные выше.

Рис. 5.2. Интерфейс программы моделирования и оптимизации обслуживания запросов транспортной системой

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

Рис. 5.3.Добавление узлов в транспортную сеть

В результате на карте получится набор транспортных узлов как показано на рис. 5.4. Для перехода к дальнейшим действиям необходимо отключить режим расстановки транспортных узлов путём нажатия правой кнопки мыши. После того как все требуемые пункты расставлены можно перейти к редактированию имён транспортных узлов. Данная операция осуществляется с помощью щелчка левой кнопкой мыши по текущему текстовому полю, обозначающему название узла. По умолчанию название «CityN», где N – это номер узла.

Рис. 5.4.Расстановка узлов транспортной сети

При редактировании названия транспортного узла, текстовое поле будет обведено пунктирной линией, как показано на рис. 5.5.

Рис. 5.5. Редактирование название транспортного узла

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

Рис. 5.6. Добавление связей в транспортную сеть

В результате получится набор транспортных узлов и связей, как показано на рис. 5.7.

Рис. 5.7. Транспортная сеть

Следует отметить, что при щелчке по области, не занимаемой транспортным узлом, установка пары сбросится и необходимо будет повторить операцию сначала. По завершении создания транспортной сети можно указать пункт нахождения ТС и пункт назначения. Для этого выбирается пункт меню «Добавить Старт/Финиш» как показано на рис. 5.8.

Рис. 5.8. Добавления начальной и конечной точки маршрута

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

Рис. 5.8. Добавления начальной и конечной точки маршрута

Каждый раз при прокладывании маршрута в левой части окна будет выводиться отчёт, содержащий информацию о начальной и конечной точке, о пройдённых узлах и времени, затраченном на путь. Строки, выводимые в данный отчёт можно копировать и использовать в дальнейшем. Копирование осуществляется выделением соответствующей строки и стандартной комбинацией клавиш Ctrl+C. Пример отчёта, выводимого в левой части окна приведен на рис.5.9.

Рис. 5.9. Добавление начальной и конечной точки маршрута

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

После завершения работы с программой генерируется отчёт. Для удобства пользователя формат отчетов совместим с программой Word офисного пакета Microsoft Office. Пример генерации отчетов представлен на рис. 6.1.

Далее приведены примеры программы для решения задач на различных маршрутах рис. 5.10 – 5.12.

Рис. 5.10. Пример реализации программы. Исходный н/п «Павловская»

Рис. 5.11. Пример реализации программы. Исходный н/п «Брюховецкая»

Рис. 5.12. Пример реализации программы. Исходный н/п «Калниболотская»

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

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

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

6. РЕЗУЛЬТАТЫ ПРАКТИЧЕСКОЙ АПРОБАЦИИ

МОДЕЛЕЙ ОПТИМАЛЬНОГО ПЛАНИРОВАНИЯ

ТРАНСПОРТНОГО ОБСЛУЖИВАНИЯ

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

Рис. 6.1. Генерация отчетов

По рисунку 6.1 или окну в программе можно увидеть результат работы программы и работу алгоритма.

Выберем произвольные пункты на карте и найдем оптимальный маршрут.

Отмечаем узлы в следующих точках на карте:

1. Тихорецкая - Динская

2. Тихорецкая - Тбилисская

3. Тихорецкая – Новопокровская

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

Рис. 6.2. Проверка работы программы

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

Рис. 6.3. Результат

2. Выполняем те же процедуры, но уже выбрав новые точки, рис. 6.4.

Следующие узлы были отмечены на карте:

1. Дядьковская - Тбилисская

2. Дядьковская - Брюховецкая

3. Дядьковская – Новопокровская

Рис. 6.4. Проверка работы программы

Получим результат, как на скриншоте ниже, рис. 6.5.

Рис. 6.5. Результат

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

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

Для сравнения результаты планирования спроектированной системы были сравнены с результатами системы разработанной на основе стандартного переборного алгоритма: алгоритма с возвратом. Сравнение осуществлялось по критерию временных затрат на перевозку.

Исходные данные при исследовании оставались одними и теми же для каждой из систем, при этом последовательно добавлялись дополнительные удаленные объекты транспортной сети, и соответствующим образом изменялись маршруты. Результаты сравнения приведены на рис.6.6.

Рис. 6.6. Проверка работы программы

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

По результатам исследовательской работы сделаем выводы о проделанной работе.

ВЫВОДЫ

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

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

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

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

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

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

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

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

ЛИТЕРАТУРА

1. http://ru.wikipedia.org/wiki.

2. http://www.dissercat.com/content/modeli-optimalnogo-planirovaniya-transportnogo-obsluzhivaniya-v-menedzhmente-territorialno-r.

3. Кравец О.Я., Кулишенко В.С. научная статья на тему: “Инструментальные средства управления территориально распределенными потоками заявок на транспортное обслуживание” Электронный научный журнал "Исследовано в России"- 15 с.

4. Чепасов В.И., Осипов О.В. научная статья на тему: “Методика оптимизации транспортного процесса на основе модели составления расписаний” ВЕСТНИК ОГУ №6(88)/июнь 2008 - 7 с.

5. Попов А.В., Обрезанова Е.Р., Синебрюхова Е.Р. научная статья на тему: “Вероятностное моделирование логистической системы грузоперевозок” – 8 с.

6. http://www.ibs.ru/.