Инструментальные средства управления территориально распределенными потоками заявок на транспортное обслуживание
Инструментальные
средства управления территориально распределенными потоками заявок на
транспортное обслуживание
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
ПОСТАНОВКА ЗАДАЧИ
. ТЕРРИТОРИАЛЬНО РАСПРЕДЕЛЕННЫЕ
МЕТОДЫ
1.1 Метод
потенциалов
.2 Метод
составления расписания перевозок
.3 Метод
поиска кратчайшего пути в графе на основе алгоритма Флойда
.
ИНСТРУМЕНТАЛЬНАЯ СИСТЕМА МОДЕЛИРОВАНИЯ И ФОРМИРОВАНИЯ ОПТИМАЛЬНЫХ ВАРИАНТОВ
ТРАНСПОРТНОГО ОБСЛУЖИВАНИЯ
.1
МАТЕМАТИЧЕСКИЕ МОДЕЛИ МЕТОДОВ
.1.1
Математическая модель метода потенциалов
.1.2
Математическая модель метода составления расписания перевозок
.1.3
Математическая модель метода поиска кратчайшего пути в графе на основе
алгоритма Флойда
. СТРУКТУРА
ИНФОРМАЦИОННОГО ОБЕСПЕЧЕНИЯ
.1
Информационное обеспечение транспортной логистики
. СТРУКТУРА
ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ
.1 Load and
Route Optimization
.2
Logistics Master
.3 ANTOR
LogisticsMaster
.4
TopLogistic
.
ПРОГРАММНАЯ РЕАЛИЗАЦИЯ
.1 Пользовательский
интерфейс
6. РЕЗУЛЬТАТЫ ПРАКТИЧЕСКОЙ АПРОБАЦИИ
МОДЕЛЕЙ ОПТИМАЛЬНОГО ПЛАНИРОВАНИЯ ТРАНСПОРТНОГО ОБСЛУЖИВАНИЯ
ВЫВОДЫ
ЛИТЕРАТУРА
ВВЕДЕНИЕ
Большинство современных крупных
народно-хозяйственных систем технического и экономического характера
представляет собой территориально распределенные системы.
К таким системам относятся, например, системы
связи, вычислительные системы коллективного пользования, некоторые системы
энергетики, транспортные системы, системы централизованного технического
обслуживания различных технических средств (вычислительной техники,
сельско-хозяйственной техники, транспортных средств и т.п.), системы
материально-технического снабжения.
Эти системы включают в свой состав целевые
объекты, задача которых заключается в выполнении основных "выходных"
функций, т.е. в создании основного выходного эффекта системы, функциональные
объекты, задача которых заключается в формировании организационно-управляющей
структуры и сервисном обеспечении основных целевых объектов системы, а также
различного рода ресурсов (материальных, информационных, энергетических и т.п.),
необходимых для обеспечения нормального функционирования объектов первых двух
типов.
Все объекты таких систем определенным образом
распределены по территории: целевые объекты размещаются, исходя из требований
функциональной необходимости выполнения системой своих основных задач, а
функциональные объекты и источники ресурсов размещаются по территории в
основном в соответствии с наилучшим обеспечением функционирования целевых
объектов.
ПОСТАНОВКА ЗАДАЧИ
На практике размещение целевых объектов является
заданным или же не подлежит выбору со стороны исследователей или
проектировщиков остальной части системы, являющейся "обеспечивающей".
На содержательном уровне задача ставится так: требуется оптимальным образом
спроектировать обеспечивающую часть территориально распределенной системы,
чтобы она с заданными показателями качества выполняла бы свои функции при
минимально возможном расходе ресурсов. (Возможно, естественно и обратная
постановка задачи: спроектировать обеспечивающую часть системы, чтобы она
функционировала с наилучшими показателями качества при существующих
ограничениях на ресурсы.) И прямая и обратная задачи являются задачами на
условную оптимизацию, возможность их конструктивного решения определяется видом
целевого функционала и структурой системы ограничений.
Цель данной работы состоит в выборе наиболее
эффективного метода исследования территориально распределённой задачи
транспортного обслуживания. Эффективность метода будет определяться по
нескольким критериям таким, как минимальные затраты по времени доставки груза
от одного пункта до другого.
Наиболее совершенный метод будет реализован
программным путем. Результатами станут выводы по проделанной работе, а также
возможности внедрения такого подхода к решению территориально распределенных
задач в реальной жизни.
Стоит отметить, что цель и результат
исследований не предполагает использование для решения задач на транспортное
обслуживание именно данного метода. Но, применение наиболее эффективного метода
в реальной задаче позволит находить решение за более короткие сроки и с
меньшими расходами.
. ТЕРРИТОРИАЛЬНО РАСПРЕДЕЛЕННЫЕ МЕТОДЫ
В соответствии с темой работы рассматриваются
территориально распределённые транспортные системы. Такие системы обладают
характерной особенностью: целевые объекты взаимодействуют с функциональными
объектами и необходимыми ресурсами на локальном уровне. Иными словами,
потребление ресурсов некоторым целевым объектом может сказаться на
обеспеченности тем же ресурсом лишь для целевых объектов, расположенных в
некотором смысле близко от рассматриваемого объекта. Помимо этого, данный тип
систем характеризуется удаленностью объектов и ограниченностью ресурсов.
Для исследования большинства территориально
распределенных систем существует два основных типа методов исследования. Данные
методы исследования относятся к традиционным методам теории исследования
операций: это вероятностно-статистические методы и методы оптимизации.
К вероятностно-статистическим методам (рис. 1.1)
относятся, прежде всего, комбинаторные методы, связанные с построением
многомерных производящих функций, и методы теории случайных потоков,
использующие приемы разрежения случайных потоков, а также методы теории
массового обслуживания, применительно к задачам обслуживания территориально
распределенных объектов.
Рис. 1.1. Вероятностно-статистические методы
К методам оптимизации (рис. 1.2) в первую
очередь относятся решения многокритериальных задач оптимизации, т.е. построение
множеств неулучшаемых решений (множеств Парето), а также разработка эффективных
вычислительных алгоритмов решения задач целочисленного линейного
программирования большой размерности.
Рис. 1.2. Методы оптимизации
Методы оптимизации подразумевают совокупность
методов для решения задач различных типов как на предприятии, так и связанные с
выбором оптимального маршрута. Многие методы оптимизации напрямую связаны с
таким понятием, как транспортная логистика. Так как в дальнейшем будут выбраны
методы, связанные с данным понятием, рассмотрим его подробнее.
Транспортная логистика и логистические методы
оптимизации транспортного обслуживания имеют широкий круг применения и
позволяют решать задачи поиска оптимального маршрута.
Значительная часть логистических операций на
пути движения материального потока осуществляется с помощью различных
транспортных средств.
Транспортная логистика - это перемещение
требуемого количества товара в нужную точку, оптимальным маршрутом за требуемое
время и с наименьшими издержками. Затраты на создание любого товара
складываются из себестоимости изготовления и издержек на выполнение всех работ
от момента закупки материалов до момента покупки товара конечным потребителем.
Большую часть стоимости составляют наценки каждого звена в цепи производитель -
конечный покупатель. Движение материального потока от первичного источника
сырья до конечного потребления также требует затрат, которые могут доходить до
50 % от общей суммы затрат на логистику.
Для дальнейших исследований были выбраны три
метода (рис. 1.3):
. Метод потенциалов
. Метод составления расписания перевозок
. Метод поиска кратчайшего пути в графе на
основе алгоритма Флойда
Все эти методы связаны с транспортным
обслуживанием и используются в решении задач территориально распределенных
систем.
Рис. 1.3. Приоритетные методы для исследования
1.1 Метод потенциалов
Транспортная задача линейного программирования
получила в настоящее время широкое распространение в теоретических обработках и
практическом применении на транспорте и в промышленности. Особо важное значение
она имеет в деле рационализации постановок важнейших видов промышленной и
сельскохозяйственной продукции, а также оптимального планирования грузопотоков
и работы различных видов транспорта.
Кроме того, к задачам транспортного типа
сводятся многие другие задачи линейного программирования - задачи о
назначениях, сетевые, календарного планирования.
Формальным признаком транспортной задачи
является то, что каждая переменная входит лишь в два ограничения, причем с
коэффициентами, равными единице. Если при этом критерий оптимальности (сумма
расходов, общий пробег) прямо пропорционален значениям переменных (транспортных
потоков), возникает линейная транспортная задача. В других случаях
рассматривается нелинейная транспортная задача, решаемая другими методами.
По существу метод потенциалов является
детализацией метода последовательного улучшения плана применительно к
транспортной задаче. Однако он был изложен вне связи с общими методами
линейного программирования. Несколько позднее аналогичный алгоритм был
разработан Данцигом, который исходил из общих идей линейного программирования.
В американской литературе метод потенциалов принято называть модифицированным
распределительным методом. Метод потенциалов позволяет, отправляясь от
некоторого опорного плана перевозок, построить решение транспортной задачи за
конечное число итераций (шагов).
Метод потенциалов предназначен для решения
транспортной задачи в матричной постановке. Потенциалы - это двойственные
переменные. Сам метод - прямой, на каждом шаге выбирается одно из двойственных
ограничений, которое не выполняется и исправляется таким образом, чтобы не
нарушить ограничения прямой задачи. Постепенно в двойственной задаче
ограничения будут выполнены, что будет означать оптимальность в прямой задаче.
Метод потенциалов является модификацией
симплекс-метода решения задачи линейного программирования применительно к
транспортной задаче. Пример структурной схемы транспортной задачи и оптимизации
её плана перевозок показаны на рис. 1.4а и рис. 1.4б соответственно.
Рис. 1.4а Пример структурной схемы транспортной
задачи
Рис. 1.4б. Оптимизация плана перевозок схемы,
показанной на рис. 1.4а, методом потенциалов
1.2 Метод составления
расписания перевозок
Рассмотрим методику оптимизации транспортного
процесса на основе модели составления расписаний. Данная методика используется
для оптимизации параметров различных типов перевозок с целью минимизации
затрат.
В наиболее общей формулировке задача составления
расписаний состоит в следующем: с помощью некоторого множества ресурсов или
обслуживающих устройств должна быть выполнена некоторая фиксированная система
заданий. Цель заключается в том, чтобы при заданных свойствах заданий и
ресурсов и наложенных на них ограничениях найти эффективный алгоритм
упорядочивания заданий, оптимизирующий или стремящийся оптимизировать требуемую
меру эффективности.
В качестве основных мер эффективности
рассматривается общее количество перевезенного груза и общее время простоя при
погрузочно-разгрузочных работах.
Для повышения эффективности и системной
устойчивости на рынке транспортных услуг при доставке грузов должна быть
обеспечена максимальная координация и интеграция всех звеньев транспортного
процесса, участвующих в формировании и управлении основными и вспомогательными
материальными и связанными с ними потоками. Элементами (звеньями) транспортного
процесса при перевозке грузов являются подача подвижного состава под погрузку,
погрузка, транспортирование и разгрузка.
Различные виды перевозок обладают специфическими
особенностями в технологии, организации и управлении, но они имеют общую
технологическую основу в виде конкретных технологических схем доставки (будь то
грузы или пассажиры). Рассмотрим схему, изображенную на рис. 1.1.
Рис. 1.5 Технологическая схема доставки
Простейшей организацией для перевозки грузов или
пассажиров является транспортное звено. Организационная структура транспортного
звена предполагает оптимизацию, как состава элементов, так и структуры звеньев
и взаимосвязей между ними.
Операционную систему доставки можно рассмотреть
в виде схемы, на входе которой имеем наличие определенного числа подвижного
состава, погрузчиков, разгрузчиков, времени погрузки, разгрузки, доставки
одного груза, а также распорядки дня для погрузчиков, разгрузчиков и водителей,
а на выходе - своевременную перевозку грузов (пассажиров) в пункт назначения.
Процессы трансформации представляют собой процессы преобразования - входа в
выход, т.е. с минимальными затратами перевозки грузов (пассажиров).
В целом перевозочный процесс можно рассматривать
как систему многофазового массового обслуживания дискретного типа с конечным
множеством состояний, в которой переход: из одного состояния в другое
происходит скачками в момент, когда осуществляется какое-то событие.
Параметры для оптимизации: общее время простоя,
время простоя при погрузке, время простоя при разгрузке, общее количество
перевезенного груза.
Пользователи транспортных услуг в настоящее
время отдают предпочтение таким показателям, как соблюдение временных графиков
доставки грузов и пассажиров, ответственность за удовлетворение оговоренных
потребностей, надежность доставки. Выполнение этих требований связано с
достаточно точной временной оценкой звеньев доставки грузов и пассажиров, т.е.
со знанием закономерностей изменения всех их элементов и установлением
конкретных величин. Выявление закономерностей и зависимостей звеньев и
элементов доставки является основой в системном построении всех возможных видов
организации перевозок грузов и пассажиров.
Сделаем вывод о том, что основная цель метода -
это сокращение времени погрузочно-разгрузочных работ и минимизация затрат на
транспортировку. Здесь играют важную роль исходные задачи, выбор транспорта и
ресурсы.
Метод, как и предыдущий, охватывает область
следования маршрута и его простоя. Однако теория расписаний имеет более
ограниченные возможности в условиях территориально распределенных систем и
сложность реализации реальной задачи.
Однако он позволяет оптимизировать задачи,
связанные с затратами не только на пути следования транспорта, но и задержки
при погрузке-разгрузке, прибытии и отправлении транспорта и другие наиболее
заметные с точки зрения времени простоя моменты.
1.3 Метод поиска
кратчайшего пути в графе на основе алгоритма Флойда
Теория графов относится к комбинаторным методам.
Поиск кратчайшего пути в графе имеет применение для транспортной задачи.
Анализ графов для поиска кратчайшего пути на
самом деле включает две близко связанные задачи. Сначала определяется
кратчайший путь от указанного начального узла графа до конечного, выражаемый
числом переходов. Вторая задача - определение длины кратчайшего пути, если
нужно учитывать некую весовую долю соединений графа.
Граф однозначно задан, если заданы множество его
вершин, множество ребер и указаны все инцидентности (т.е. указано, какие
вершины какими ребрами соединены). Наиболее наглядно граф задается рисунком;
однако не все детали рисунка одинаково важны; в частности, несущественны
геометрические свойства ребер (длина, кривизна и т.д.) и взаимное расположение
вершин на плоскости.
Маршрут, или путь- это последовательность ребер
в неориентированном графе, в котором конец каждого ребра совпадает с началом
следующего ребра. Число ребер маршрута называется его длиной.
Задача опирается на использование алгоритма
Флойда.
Метод графов имеет широкое применение в
определении оптимального пути. Также следует учесть, что задачи оптимизации
расписания обслуживания и определения оптимального плана перевозок сводятся к
задачам поиска кратчайшего пути в графе, которая реализуется на основе
алгоритма Флойда.
Алгоритм Флойда - алгоритм для
нахождения кратчайших расстояний между всеми вершинами взвешенного графа
<#"879990.files/image006.gif">
Рис. 1.6. Пример реализации
алгоритма Флойда для нахождения кратчайших расстояний между всеми вершинами
взвешенного графа
<#"879990.files/image007.gif">
Примечание: ТС - количество
транспортных схем перевозок грузов в системе; Аэ - количество подвижного
состава в эксплуатации; N - количество пунктов погрузки и разгрузки в
системе; J - средний интервал прибытия автомобилей в центральный
грузовой пункт системы; Яцп - ритм работы центрального пункта; t
- время ожидания грузовых операций подвижным составом; П, Р - условное
обозначения пункта погрузки и разгрузки: - движение с грузом, движение без
груза; Ws- выработка автомобиля; Qc - выработка системы
Все вышеназванные автотранспортные
системы доставки грузов объединены общим понятием: системы нижнего уровня
(уровня маршрута).
Общим признаком, объединяющим их в
одну группу, является то, что там непосредственно осуществляется доставка
груза, производится транспортная продукция, формируются затраты, негативно
влияющие на конечную стоимость продукции, именно здесь транспортный процесс
нуждается в адекватном управлении исполнением его операций. Еще одним
объединяющим фактором является то, что эти системы могут и зачастую
проектируются с помощью экономико-математических методов линейного
программирования.
К перечисленным аспектам следует
добавить то, что системы нижнего уровня являются в свою очередь начальными
элементами, из которых складываются автотранспортные системы более высокого
уровня.
Далее рассмотрим средние системы.
Как правило, в состав таких систем входят элементы, которые могут представлять
собой многофазные и многоканальные системы массового обслуживания. Поэтому
модели таких систем во многих работах разрабатывались на основе теории
вероятности, в частности, одного из ее разделов - теории массового
обслуживания.
Особенностями функционирования
средних систем являются следующие факторы: перевозка грузов осуществляется по
радиальному маршруту, ветви которого начинаются либо заканчиваются в одном
центральном грузовом пункте, при этом автомобили взаимодействуют друг с другом
через общие посты погрузки и разгрузки; необходимость последовательного выхода
на линию автомобилей для исключения образования первоначальной очереди
автомобилей; необходимость назначения очередной отправки автомобиля по одной из
ветвей радиального маршрута в рамках их работы по расписанию, таким образом,
чтобы обеспечить ритмичное поступление автомобилей в грузовые пункты системы.
Центральный и периферийные пункты
средних систем в силу сложившихся обстоятельств (планировки, механизации,
режима работы и др.) имеют свой ритм работы, который может отличаться от ритма
работы других участников транспортного процесса. В связи с этим появляются
отдельные элементы системы, определяющие пропускную способность и, соответственно,
ритм работы системы. Поэтому при описании ССДГ следует учитывать, что они могут
быть насыщенными или ненасыщенными. Насыщение системы может произойти по двум
условиям: по объему груза и по времени занятости постов погрузки-выгрузки.
Система называется насыщенной по
объему груза, если заявленное количество груза равно или превышает то
количество груза, которое способен переработать центральный пункт.
Система является насыщенной по
занятости постов погрузки-выгрузки, если интервал прибытия подвижного состава в
центральный пункт системы меньше ритма осуществления погрузочно-разгрузочных
работ. Например, используя автомобили малой грузоподъемности, можно полностью
обеспечить занятость по времени работы грузовых постов, однако количество
груза, которое они смогут перевезти, не будет соответствовать максимально
возможной величине. Так, при выполнении разгрузки на подъемниках
технологическое время разгрузки будет соответствовать времени подъема и
опускания, при этом механизму безразлично, какой грузоподъемности автомобиль
поднимать. Наоборот, используя подвижной состав наибольшей грузоподъемности,
можно добиться того, что занятость по времени грузовых постов будет не полной,
а суммарное количество груза, которое перевезут автомобили, будет
соответствовать пропускной способности пункта.
Формулировка задачи построения
модели функционирования ненасыщенной ССДГ производится следующим образом.
Имеется система доставки грузов с
одним центральным и множеством периферийных пунктов, соединенных между собой
транспортной сетью. На постах погрузки сосредоточен транспортно-однородный
груз. Ежедневно в систему поступают заявки на перевозку такого груза. В
зависимости от сложившейся или проектируемой организации перевозок конфигурация
ветвей системы соответствует радиальным транспортным схемам машинных отправок.
транспортный логистика
граф территориальный распределённый
Основная цель реализации модели
функционирования насыщенной ССДГ состоит в том, чтобы осуществить доставку
груза в заданный интервал времени рациональным количеством транспортных
средств.
Для достижения поставленной цели на
каждом этапе реализации расчетов по модели необходимо решение локальных задач,
определение очередности выполнения заданий (оборотов) по ветвям системы таким
образом, чтобы осуществить доставку груза рациональным количеством транспортных
средств с минимальными простоями участников транспортного процесса в ожидании
выполнения операций. Связь основной и локальной задачи объясняется тем, что
простои в ожидании прибытия автомобиля на посты погрузки - разгрузки снижают
пропускную способность системы.
Потери времени автомобилями в
ожидании обслуживания на посту приводят к сокращению времени их работы, что
снижает их возможности в освоении планового объема перевозок. Кроме того, при
пиковых объемах заявленного к перевозке груза система достигает насыщения по
пропускной способности, и привлечение дополнительного количества автомобилей не
приведет к увеличению выработки.
Сократить непроизводительные простои
как постов погрузки (разгрузки), так и автомобилей можно путем организации
отправок в такой последовательности, которая обеспечила бы их равномерный
возврат в центральный пункт системы и равномерное распределение отправок,
направляемых в адрес одного и того же периферийного пункта, по времени работы системы,
с учетом всех ограничений.
Например, при назначении отправки
автомобилю может отдаваться приоритет отправке с наибольшим количеством не
вывезенного груза или с наибольшей продолжительностью выполнения
(интегрированным показателем данных приоритетов является величина исполняемой
по каждой ветви транспортной работы). Таким же образом можно поступать с
отправками в адрес клиентов, время работы которых заканчивается раньше всех
остальных. Другими словами, при расчетах на модели должна быть предусмотрена
система приоритетов выбора отправок для рассмотрения возможности их включения в
общий план перевозок. При этом должны соблюдаться условия незанятости
обслуживающих постов грузовых пунктов системы, выполнение режима работы и
обеда, наличие в данный момент готового к погрузке автомобиля соответствующего
типа.
Поскольку фактическая
продолжительность и время окончания работы автомобилей, а также величина потерь
рабочего времени в ожидании погрузочно-разгрузочных операций могут быть
известны после расчетов на модели и построения расписания работы системы, то до
начала расчетов точно определить необходимую потребность в транспортных
средствах не представляется возможным. Ввиду того, что произвести расчеты и
построить расписание без определения потребного количества автомобилей нельзя,
то решение поставленной задачи будет связано с использованием итеративного
процесса, т. е. с повторным проведением расчетов на модели с измененными
входными параметрами.
Стоит отметить, что конкретной
математической модели и алгоритма для решения любой транспортной задачи данным
методом не существует. Это связано со сложностью реализации и ресурсоемкостью,
а также исходными данными, такими, как тип транспорта, маршруты следования и
другие.
Общая формулировка задачи
составления расписания состоит в выполнении некоторой фиксированной системы
заданий на перевозки с помощью ограниченного множества ресурсов, или
обслуживающих устройств.
Целью является поиск эффективного
алгоритма упорядочивания заданий, оптимизирующего требуемую меру эффективности
при заданных свойствах ресурсов и наложенных на них ограничениях. В качестве
основных мер эффективности изучаются длина расписания и среднее время
пребывания заданий в системе. Модели этих задач являются детерминированными,
т.е. вся информация, на основе которой принимаются решения об упорядочивании,
известны заранее.
Алгоритм составления расписания
делится на два этапа:
составление пробного расписания;
его оптимизация.
Рассмотрим алгоритм, применяемый в
городских условиях.
В условиях большого города
количество выполняемых пассажирским транспортом рейсов исчисляется тысячами, а
перевезенных пассажиров - сотнями тысяч единиц, поэтому для предотвращения сбоя
в работе пассажирского транспорта важно наладить оперативный контроль над его
движением. Во всех случаях, так как составить математическую модель практически
невозможно, для составления пробного расписания и его последующей оптимизации
применяется имитационное моделирование.
На первом этапе выполняется рутинная
работа, связанная с вычислением времени прибытия транспорта в конечные и
промежуточные пункты. Составитель расписания визуально по минутным сеткам
маршрутов и остановок оценивает качество расписания, изменяя настроечные
параметры (изменение времени движения между остановками и времени разворота на
конечных остановках). Ручной подбор этих параметров на основе опыта составителя
позволяет добиться визуальной равномерности движения транспорта.
На этапе оптимизации для каждого
варианта расписания вычисляется значение критерия оптимальности. Величина
критерия при изменении составителем расписания позволяет эксперту-составителю
оценивать качество варианта и переходить к более оптимальному.
Окончательным результатом работы
программы является расписание движения маршрутов, на основе которого
формируются выходные документы (расписания маршрутов, остановок, минутные
сетки, графики движения и т.п.).Для оценки оптимальности расписания, выделим
составляющие интегрального критерия ОПТ оптимальности движения:
, (2.5)
где 
- весовые коэффициенты компонентов
критериев оптимальности;
Мун- критерий
оптимальности с точки зрения муниципалитета;
ТР- критерий оптимальности с
точки зрения транспортного предприятия;
НАС- критерий
оптимальности с точки зрения населения.
Критерий оптимальности (ОПТ)
с точки зрения транспортного предприятия и конечного потребителя является
противоречивым. Так, минимизация времени ожидания прямым образом связана с
увеличением подвижного состава, а, следовательно, со снижением его загрузки и
суммы дохода с рейса. С другой стороны, чрезмерное стремление увеличить
доходность транспорта ведет к отказу населения от перевозок и к появлению
конкурирующих транспортных организаций. Следовательно, оценка показателей
эффективности должна проводиться с учетом:
достижения гарантированного
минимального экономического результата для транспортного предприятия и
административных органов в пределах удовлетворительной нормы прибыли;
достижения гарантированного
максимального результата для пассажиров в виде удовлетворения их требований с
вероятностью, не ниже некоторого порогового значения, за которым следует отказ
от использования определенного вида транспорта.
Рассмотрим муниципальный критерий
подробнее:
, (2.6)
где Жi- желание ехать i-го
пассажира: может быть равно 0 (если пассажир не хочет ехать) или 1 (пассажир
хочет ехать);
Сmj- стоимость
j-го проезда;
Пр- экономическая эффективность
муниципального транспортного предприятия; A(x)- весовой коэффициент составляющейxкритерия;
δ- дельта-функция.
Одной из компонент муниципального
критерия является желание пассажира ехать (потребность в перевозке), которое
зависит от качества обслуживания, включающего в себя время ожидания, время
перемещения, состояние и отношение к пассажирам кондуктора и водителя.
С другой стороны, на муниципальный
критерий влияет такой параметр как стоимость проезда, умноженная на количество
людей, оплативших проезд, так как муниципальный критерий определяет достижение
гарантированного минимального экономического результата для муниципального
предприятия.
Основное назначение транспортного
параметра - стремление максимизировать прибыль для предприятия:
, (2.7)
где Д(t)- интенсивность
поступления средств от осуществления перевозок;
З(t)-
интенсивность всех затрат на осуществление перевозок (расходные материалы и
топливо, оплата труда, амортизация, обязательные платежи, общепроизводственные
расходы и т.п.). Увеличить прибыль можно за счет увеличения интенсивности
поступления средств от осуществления перевозок, либо за счет уменьшения
интенсивности затрат на эти перевозки.
С точки зрения конечного
потребителя, выделение единого критерия эффективности движения вряд ли возможно
вследствие существенной разницы в потребительских задачах, решаемых с помощью
транспорта, и разнообразной мотивации в части принятия решения на перемещение и
выбора его способа. В качестве критериев оптимальности для отдельно взятого
пассажира могут выступать: время перемещения до заданной точки; время ожидания
транспорта; стоимость поездки (с учетом возможных пересадок); комплексный
критерий оптимальности, объединяющий с разными весовыми коэффициентами время
ожидания, стоимость поездки и время в пути:
где α, β,
γ-весовые
коэффициенты соответственно времени ожидания, стоимости, времени перемещения.
Данный критерий косвенно
определяет возможность отказа от использования транспорта со стороны населения.
Критерий для населения в целом
напрямую зависит от таких параметров как: стоимость проезда; время ожидания;
время перемещения.
В итоге, формулировка задачи
составления расписания транспорта звучит следующим образом: "Для заданного
набора маршрутов, обслуживающего персонала, а также заданного набора интервалов
времени, построить такое распределение выходов, при котором выбранный критерий
оптимальности является наилучшим".
Как сказано выше, качество
составления расписания может оцениваться муниципальным, транспортным,
пассажирским критериями и критерием населения, для определения которых
требуется оценить веса {α, β, γ}.
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) вершин;
. кратчайший путь из вершины i в вершину
j, в котором в качестве промежуточных допускается использование только первых
(m - 1) вершин.
Поскольку по предположению исходный граф не
может содержать контуров отрицательной длины, один из двух путей - путь,
совпадающий с представленным в пункте 3, или путь, являющийся объединением
путей из пунктов 1 и 2 - должен быть кратчайшим путем из вершины i в вершину j,
в котором в качестве промежуточных допускается использование только первых m
вершин. Таким образом,
,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.
. Алгоритм заканчивается получением
матрицы всех кратчайших путей DN, N - число вершин графа.
Напомним, для определения по известным элементам
матрицы Dm-1 элементов матрицы Dm в алгоритме Флойда применяется рекурсивное
соотношение:
,jm=min{ di,mm-1+ dm,jm-1; di,jm-1}
,jm - элемент матрицы Dm, di,jm-1- элементы
матрицы Dm-1, найденной на предыдущем шаге алгоритма.
Данный алгоритм один из самых эффективных для
реализации из тех методов, несмотря на сложность реализации. Помимо этого, он
имеет единую структуру. Он подходит для реализации любой территориально
распределенной системы, будь то телекоммуникационная система, транспортная
система и другие.
Он может использоваться в совокупности с таким
методом, как метод составления расписания перевозок. Данный метод, как уже
упоминалось, необходим для составления расписания маршрутов, времени простоя
транспорта и т. д.
Эти методы охватывают весь спектр задач на
транспортное обслуживание.
Перед тем, как осуществлять программную
реализацию рассмотрим имеющиеся на данный момент программные продукты для
оптимизации маршрута следования транспорта, а затем выберем тот, который будет
отвечать поставленной задаче.
3. СТРУКТУРА ИНФОРМАЦИОННОГО ОБЕСПЕЧЕНИЯ
До того, как начать работать с программой
моделирования и формирования оптимальных планов транспортного обслуживания,
необходимо провести серьезную работу по сбору и подготовке исходных данных.
Прежде всего, это данные, характеризующие транспортную сеть предприятия: данные
о взаимном удалении узлов, о среднем времени прохождения отрезков дорог между
соседними узлами, пункт дислокации ТС. Затем создать задание на оптимизацию:
определить продолжительность периода времени, на котором будет построено
расписание, определить множество объектов-исполнителей, заявок и обозначить
взаимосвязи между ними.
Наиболее распространенная
трактовка реляционной модели данных, по-видимому, принадлежит Дейту, который
воспроизводит ее (с различными уточнениями) практически во всех своих книгах.
Согласно Дейту реляционная модель состоит из трех частей, описывающих разные
аспекты реляционного подхода: структурной части, манипуляционной части и
целостной части. Пример использования реляционной модели данных приведена на
рис. 3.1.
Рис. 3.1 Пример использования
реляционной модели данных
В структурной части модели
фиксируется, что единственной структурой данных, используемой в реляционных БД,
является нормализованное n-арное отношение. По сути дела, в предыдущих двух
разделах этой лекции мы рассматривали именно понятия и свойства структурной
составляющей реляционной модели.
В манипуляционной части модели
утверждаются два фундаментальных механизма манипулирования реляционными БД -
реляционная алгебра и реляционное исчисление. Первый механизм базируется в
основном на классической теории множеств (с некоторыми уточнениями), а второй -
на классическом логическом аппарате исчисления предикатов первого порядка.
Заметим, что основной функцией манипуляционной части реляционной модели
является обеспечение меры реляционности любого конкретного языка реляционных
БД: язык называется реляционным, если он обладает не меньшей выразительностью и
мощностью, чем реляционная алгебра или реляционное исчисление.
Наконец, в целостной части
реляционной модели данных фиксируются два базовых требования целостности,
которые должны поддерживаться в любой реляционной СУБД. Первое требование
называется требованием целостности сущностей. Объекту или сущности реального
мира в реляционных БД соответствуют кортежи отношений. Конкретно требование
состоит в том, что любой кортеж любого отношения отличим от любого другого кортежа
этого отношения, т.е. другими словами, любое отношение должно обладать
первичным ключом. Как мы видели в предыдущем разделе, это требование
автоматически удовлетворяется, если в системе не нарушаются базовые свойства
отношений.
Второе требование называется
требованием целостности по ссылками и является несколько более сложным.
Очевидно, что при соблюдении нормализованности отношений сложные сущности
реального мира представляются в реляционной БД в виде нескольких кортежей
нескольких отношений.
Однако реляционный подход не подразумевает
структуризации данных, что делает очень неудобной работу с разнородной
информацией. Кроме того, хранение ограничений в реляционной базе данных в том
виде, в каком они фигурируют в системе, оказалось невозможным.
Следующим способом организации входных данных,
который был рассмотрен - это иерархический способ. В этом случае данные
представляются в виде дерева. Иерархический способ организации данных оказался
более удобным для работы, поэтому он был принят в качестве базового (рис. 3.1),
так как между объектами существуют связи, каждый объект может включать в себя
несколько объектов более низкого уровня. Такие объекты находятся в отношении
предка (объект более близкий к корню) к потомку (объект более низкого уровня),
при этом возможна ситуация, когда объект-предок не имеет потомков или имеет их
несколько, тогда как у объекта-потомка обязательно только один предок. Объекты,
имеющие общего предка, называются близнецами (в программировании применительно
к структуре данных дерево устоялось название братья).
Входные данные для работы системы разделяются на
два информационных блока (рис. 4.1):
) Блок данных задания на составление расписания.
) Блок данных транспортной сети.
Программа моделирования и оптимизации
обслуживания запросов транспортной системой предназначена для
автоматизированного построения расписания с учетом географической удаленности
филиалов.
Рис. 3.2 Входные данные для работы системы
Теперь перейдем к рассмотрению имеющихся на данный
момент приложений и разработке программного обеспечения для реализации задачи
оптимизации транспортного обслуживания с применением выбранных ранее методов
составления расписания перевозок и метода поиска кратчайшего пути в графе с
применением алгоритма Флойда.
3.1 Информационное
обеспечение транспортной логистики
Так как дальнейшее приложение будет основано на
понятии транспортной логистики, рассмотрим данную тему подробнее.
Практика показывает, что логистический подход к
транспортным процессам за последнее десятилетие коренным образом изменился, что
управление грузоперевозками стало одной из высокоприбыльных и развитых сфер
экономики и бизнеса. Это стало возможным благодаря новым хозяйственным
отношениям, которые возникли между владельцами грузов, перевозчиками и
транспортно-экспедиторскими компаниями на основе новейших информационных
технологий.
Время и качество становятся самыми критическими
факторами в системе транспортной логистики. «Все транспортные операции должны
подчиняться важнейшему требованию логистики - доставке «точно в срок» с
обеспечением сохранности груза. Поэтому возникают вопросы взаимодействия между
перевозчиком, логистическим оператором и потребителем транспортных услуг на
базе информационных ресурсов интегрированной логистики.
Информационное обеспечение в
транспортной логистике играет одну из ключевых ролей. Поэтому менеджеры и
специалисты должны уметь вырабатывать управленческие решения по его внедрению и
развитию и применять их в масштабе предприятия или транспортно-логистической
сети.
Основным побудительным мотивом
применения логистических информационных систем (ЛИС) на транспорте является
повышение производительности интегрированных транспортных систем, получение
качественной информации на всех иерархических уровнях, существенное снижение
совокупных затрат. Центральная идея звучит так: «Удачные фирмы имеют хорошие
формальные и неформальные информационные системы, неудачные - тратят огромные
суммы денег на компьютерные системы, но не знают, как правильно их использовать
и выбирать информацию, которую эти системы должны содержать».
Управление данными в ЛИС
обеспечивает все виды операций, необходимых для исполнения заказов по
транспортировке грузов, контроля за операциями и оценки их эффективности. В
результате ИОТЛ формируется два информационных потока:
) планирование и координация
производственной, транспортной деятельности и размещение запасов;
) оперативная деятельность,
связанная с управлением транспортированием и грузопереработкой.
В ЛИС весь ход подготовки и
принятия решений является процессом переработки информационного потока.
Различают три варианта взаимодействия транспортных и информационных потоков:
информация опережает, сопровождает, поясняет транспортно-материальный поток.
Опережение материального потока
информационным ставит своей целью устранение узких мест в логистическом
процессе. Опережающий информационный поток во встречном направлении содержит
сведения о заказе, в прямом направлении - предварительное сообщение о
предстоящем прибытии груза.
Сопровождение, когда одновременно
с транспортным потоком идет информация о количественных и качественных
параметрах, позволяет быстро и правильно идентифицировать грузы и направить их
по назначению.
Отставание информационного
потока от транспортного обычно допускается только для пояснения и оценки
последнего. Вслед за транспортным потоком во встречном направлении может
проходить информация о результатах приемки груза по количеству и качеству,
претензиях и взаиморасчетах.
Цель ИОТЛ заключается в том,
чтобы получить возможность эффективного управления, контроля и комплексного
планирования движения транспортно-материального потока. Все более насущной
становится проблема непрерывного учета результатов функционирования системы,
что способствует оперативному внесению изменений как в построение, так и
реализацию хода интегрированного процесса «поставка - транспортировка».
Информационный процесс с
помощью информационных технологий реализуется со следующими основными
функциями:
транспортировка потоков
информации внутри ЛИС;
накопление информации и
хранение данных в базе знаний;
фильтрация потока -
избирательная переработка одних и «фильтр» других информационных данных и
сопровождающих документов;
объединение и разделение
информационных потоков в структуре ЛИС и сетях коммуникаций;
различные элементарно-информационные
преобразования (копирование, тиражирование информации, обработка и
систематизация данных, поиск и выдача информации, создание информационных
моделей) и управление информационным потоком;
В этой связи ИОТЛ должно
соответствовать следующим основным требованиям:
системность обслуживания с
учетом характера деятельности потребителей, решаемых ими задач при управлении
транспортно-логистическими процессами, качественном удовлетворении
информационных потребностей;
надежность обслуживания, что
предполагает обеспечение информацией логистических менеджеров и участников
транспортно-логистических цепочек в нужные сроки и в наиболее удобном для них
виде;
полнота информационного
обслуживания выполняемых процессов (операций) и доведение необходимой
информации до конкретного потребителя;
дифференцированность, состоящая
в том, что каждый потребитель индивидуально обеспечивается информацией, которая
способствует решению поставленных задач.
Информационные ресурсы интегрированной логистики
представлены на рис. 3.2 в виде своеобразного «дерева», состоящего из 12
базовых элементов и отражающего логику изучаемого материала.
Рис. 3.3 Информационные ресурсы
транспортной логистики
В транспортной логистике
информация является одним из ключевых факторов конкурентоспособности.
Конкурентоспособность ТЛП обеспечивает такая ЛИС, которая способна обеспечить
информационную поддержку:
базовых логистических операций;
управленческого контроля;
анализа оперативных и
стратегических решений.
ЛИС для эффективного
обслуживания ТЛП должна иметь такие качества, как:
доступность - простота и
легкость доступа к логистической информации;
точность - информация должна точно
отражать текущие операции,
динамичность - изменение
процессов при выполнении заказов, консолидации грузов при грузопереработке в
транспортных терминалах;
своевременность - информация
измеряется промежутком времени между моментом, когда происходит событие, и
моментом, когда оно находит отражение в ЛИС;
возможность сосредоточить
внимание на наиболее трудных и не поддающихся автоматизации процессов и
решений;
гибкость - структура
информационной системы должна предусматривать ее совершенствование и настройку
на нужды клиентов;
эффективность оформления
отчетных данных - экраны ПК и отчеты должны содержать нужную информацию в
удобной форме.
4.СТРУКТУРА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ
Что же касается структуры программного
обеспечения, ниже представлена схема программы, которая иллюстрирует процесс
функционирования программного обеспечения.
На вход поступают исходные данные, то есть
транспортная сеть предприятия и задание на обслуживание.
Рис. 4.1 Входные данные
Данная схема применима для большинства программных
продуктов.
Далее рассмотрим примеры программных продуктов
для решения задач, связанных с транспортной логистикой.
4.1 Load and Route
Optimization
Компания “Консид Решения” для решения задач
оптимизации загрузки транспорта и формирования оптимальных маршрутов доставки
грузов предлагает своим Заказчикам программный продукт Load and Route
Optimization от компании Accellos (Канада). Load and Route Optimization
позволит логистическим операторам, дистрибьюторам, розничным сетям,
производителям и компаниям перевозчикам минимизировать транспортные затраты и
увеличить оптимальность использования ресурсов. Это решение комбинирует
оптимизацию загрузки груза в транспорт, планирование отгрузок и поддержку
маршрутизации с учетом наименьшей стоимости. Load and Route Optimization может
использоваться как отдельное программное решение, которое может быть
интегрировано с любой WMS, TMS, ERP или диспетчерской системами. Данное решение
предназначено для формирования отгрузок и маршрутов доставки заказов со склада
распределительного/ дистрибутивного центра или логистического оператора по
клиентам: магазинам, конечным потребителям, региональным складам. 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™ предназначена для
автоматизации работы диспетчеров и позволяет предприятиям, осуществляющим
доставку товаров клиентам или транспортировку грузов на торговые точки и
склады, автоматизировать процессы управления доставкой и планирования
маршрутов, оптимально загружать весь парк транспортных средств, обеспечивать
своевременную доставку продукции клиентам, эффективно контролировать работу
водителей и экспедиторов.
А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. Список заявок на доставку товара на один
день. Заявки на доставку на каждый день импортируются из информационной системы
заказчика.
. Список автомашин, готовых к выполнению
маршрутов доставки. Каждый автомобиль имеет ряд характеристик, которые
учитываются при расчетах:
грузоподъемность;
максимально допустимый объем груза;
статус автомобиля (собственный или
арендованный);
ограничения по максимальному количеству
обслуживаемых за день заявок;
максимально допустимая продолжительность рейса;
. Адрес склада.
. Компьютерная карта региона с описанием
транспортной сети (входит в состав АNTOR LogisticsMaster™).
4.4 TopLogistic
СистемаTopLogistic
<#"879990.files/image017.gif">
Рис. 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 Добавления начальной и конечной точки
маршрута
Операция производится аналогично принципу
установки связей между точками. После чего оптимальный (с точки зрения времени)
маршрут автоматически установится и будет отмечен красным цветом. Данную
операцию можно будет произвести повторно каждый раз, получая маршрут после
указания конечной точки.
Каждый раз при прокладывании маршрута в левой
части окна будет выводиться отчёт, содержащий информацию о начальной и конечной
точке, о пройдённых узлах и времени, затраченном на путь. Строки, выводимые в
данный отчёт можно копировать и использовать в дальнейшем. Копирование
осуществляется выделением соответствующей строки и стандартной комбинацией
клавиш Ctrl+C. Пример отчёта, выводимого в левой части окна приведен на
рис.5.9.
Рис. 5.9 Добавление начальной и конечной точки
маршрута
Необходимо отметить, что время, затраченное на
преодоление маршрута, представлено в условных единицах. Однако, этого
достаточно для оценки качества работы алгоритма и определения затраченного
времени.
После завершения работы с программой
генерируется отчёт. Для удобства пользователя формат отчетов совместим с
программой Word офисного пакета Microsoft Office. Пример генерации отчетов
представлен на рис. 6.1.
На основании данных примеров можно сделать
выводы о том, что количество узлов на этапе маршрута можно выбирать любое и
количество ребер также не имеет определенного значения.
Тем самым можно решать транспортные задачи для
достаточно больших по отдаленности пунктов отправки-прибытия.
Наконец, результаты работы программы будут рассмотрены
в следующем разделе с готовыми решениями.
. РЕЗУЛЬТАТЫ ПРАКТИЧЕСКОЙ АПРОБАЦИИ МОДЕЛЕЙ
ОПТИМАЛЬНОГО ПЛАНИРОВАНИЯ ТРАНСПОРТНОГО ОБСЛУЖИВАНИЯ
Для оценки эффективности системы оптимального
планирования транспортного обслуживания проводилось сравнение результатов
планирования спроектированной системы с результатами системы разработанной на
основе стандартного переборного алгоритма: алгоритма с возвратом. Сравнение
осуществлялось по критерию времени на перевозку при осуществлении обслуживания
и времени работы алгоритмов. Исходные данные при исследовании оставались одними
и теми же для каждой из систем, при этом в последовательно добавлялись
дополнительные удаленные объекты транспортной сети, и соответствующим образом
изменялось задание на составление расписания.
Рис. 6.1 Генерация отчетов
По рисунку 6.1 или окну в программе можно
увидеть результат работы программы и работу алгоритма.
Выберем произвольные пункты на карте и найдем
оптимальный маршрут.
Отмечаем узлы в следующих точках на карте:
. Тихорецкая - Динская
. Тихорецкая - Тбилисская
. Тихорецкая - Новопокровская
Выполняем необходимые процедуры, как было
описаны в предыдущем разделе. Теперь мы имеем граф с несколькими вариантами
маршрута, рис. 6.2.
Рис. 6.2 Проверка работы программы
В окне слева после работы алгоритма выводится
результат с наиболее оптимальным маршрутом, рис. 6.3.
Рис. 6.3 Результат
. Выполняем те же процедуры, но уже выбрав новые
точки, рис. 6.4.
Следующие узлы были отмечены на карте:
. Дядьковская - Тбилисская
. Дядьковская - Брюховецкая
. Дядьковская - Новопокровская
По завершении исследований определили, что
алгоритм работает эффективно и дает верные результаты. Скорость вычисления
оптимального маршрута небольшая по сравнению с высокой точностью получения
результата.
Как показали результаты, алгоритм достаточно
прост и не менее эффективен по сравнению с другими. Также его несложно
реализовать программным путем с минимальным набором интерфейса и наглядности
работы программы и получения результатов.
Для сравнения результаты планирования
спроектированной системы были сравнены с результатами системы разработанной на
основе стандартного переборного алгоритма: алгоритма с возвратом. Сравнение
осуществлялось по критерию временных затрат на перевозку.
Исходные данные при исследовании оставались
одними и теми же для каждой из систем, при этом последовательно добавлялись
дополнительные удаленные объекты транспортной сети, и соответствующим образом
изменялись маршруты.
На диаграмме видно, что разработанная система с
выбранным методом и алгоритмом исследования эффективнее традиционного алгоритма
с возвратом. Значит, она позволяет решать задачи с более высоким качеством и
точностью в плане временных затрат.
По результатам исследовательской работы сделаем
выводы о проделанной работе.
ВЫВОДЫ
В результате исследования алгоритмов и методов
решения территориально распределённых задач на транспортное обслуживание
рассмотрены их преимущества по отношению друг к друг и области применения.
Таким образом, решение задачи транспортного обслуживания получено с помощью
алгоритма Флойда для поиска кратчайшего пути на графе. Данный алгоритм
позволяет реализовать нахождение оптимального маршрута следования исполнителя
от заданной точки до места назначения.
Использовавшийся алгоритм один из самых
эффективных для реализации поставленных задач, несмотря на сложность
реализации. Кроме того, он имеет единую структуру. Он подходит для реализации
самых различных территориальных распределенных систем, в том числе занимающих
большие географические пространства.
Методика решения может сочетаться с таким
методом, как метод составления расписания перевозок. Так же разработанная
система подойдёт для составления расписания маршрутов, времени простоя
транспорта и т. д.
Выбранный алгоритм сыграл неотъемлемую часть в
коде разработанной программы. Сама программа содержит удобный для понимания
интерфейс и минимальный набор необходимого функционала. Это возможности добавления
и удаления узлов и ребер построенных графов. Также интерфейс содержит окно с
картой области, на которой расположены пункты отправки-прибытия и все,
включенные в данной области маршруты и населенные пункты. Тем самым можно на
любом участке карты строить граф и определять программным путем кратчайшее
расстояние.
Программа позволяет производить расчеты на
достаточно больших участках карты без значительной потери времени в рамках
расчетов. Также имеется возможность увидеть результаты решений в левом окне
программы с описанием выбранных маршрутов и временем затрат в условных
единицах.
Также можно сказать, что полученные данные можно
без труда скопировать в любой текстовый файл для дальнейших нужд.
Кроме того, произведены сравнения скорости
работы спроектированной системы, с результатами системы разработанной на основе
стандартного переборного алгоритма: алгоритма с возвратом. По результатам
исследований построена диаграмма. На диаграмме отражены преимущества
разработанной системы перед стандартным алгоритмом с возвратом.
ЛИТЕРАТУРА
1. http://ru.wikipedia.org/wiki.
. http://www.dissercat.com/content/modeli-optimalnogo-planirovaniya-transportnogo-obsluzhivaniya-v-menedzhmente-territorialno-r.
. Кравец О.Я., Кулишенко В.С.
научная статья на тему: “Инструментальные средства управления территориально
распределенными потоками заявок на транспортное обслуживание” Электронный
научный журнал "Исследовано в России"- 15 с.
. Чепасов В.И., Осипов О.В. научная
статья на тему: “Методика оптимизации транспортного процесса на основе модели
составления расписаний” ВЕСТНИК ОГУ №6(88)/июнь 2008 - 7 с.
. Попов А.В., Обрезанова Е.Р.,
Синебрюхова Е.Р. научная статья на тему: “Вероятностное моделирование
логистической системы грузоперевозок” - 8 с.
. http://www.ibs.ru/