Семенюта Евгения Викторовна

• Резюме
• Биография
• Реферат
• Библиотека
• Ссылки
• Отчет о поиске
• Индивидуальный раздел

Реферат по теме выпускной работы

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

Введение

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

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

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

Актуальность

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

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

По данным международных консалтинговых компаний, оказывающих услуги по оптимизации транспортно-логистических процессов, применение специализированного программного обеспечения помогает снизить транспортные издержки почти на 15% [1]. Интерес к системам планирования и мониторинга грузовых перевозок возрастает.

Цель и задачи

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

Основные задачи:

1. Разработать и реализовать алгоритм поиска первоначальных предполагаемых маршрутов.
2. Учесть ограничения на порядок обхода городов в составленных маршрутах.
3. Экспериментально проверить эффективность работы предложенных алгоритмов.
4. Реализовать мониторинг движения грузов.

Предполагаемая научная новизна

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

Практическая ценность результатов работы

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

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

Обзор исследований и разработок по теме

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

1. Система «TopLogistic» позволяет оптимизировать деятельность по доставке грузов в крупном городе или регионе, осуществлять планирование, учет и контроль процессов, связанных с отгрузкой и доставкой [3]. «TopLogistic» комплектуется модулем GPS-мониторинг для контроля в режиме реального времени транспорта и записи маршрутов перемещения в архив, что позволяет сравнивать плановый и фактический пробег автомобилей.
   
   Система обеспечивает:
   - автоматизацию работ по распределению заказов по автомобилям;
   - автоматизированный расчет маршрутов доставки заказов;
   - визуализацию адресов и маршрутов доставки на электронной карте;
   - формирование оптимального порядка объезда точек доставки с возможностью его изменения.
   
   Недостатками данного программного комплекса являются:
   - высокая стоимость;
   - необходимость адаптации к условиям новой страны, так как продукт является русским (в частности его комплектация новыми картами);
   - неизвестность, учтена ли здесь возможность дозагрузки транспортных средств по пути следования;
   - неизвестно, по скольким складам ведется учет грузов, и сколько их предусмотрено вообще;
   - неизвестно, сколько и какие пункты имеют собственный автопарк;
   - скорее всего, здесь подразумевается один единственный склад, загрузка на нем и разгрузка в заданных точках.


2. Программное решение ANTOR LogisticsMasterТМ предназначено для автоматизации работы диспетчеров и позволяет предприятиям, занимающимся доставкой товаров клиентам или транспортировкой грузов на торговые точки и склады, автоматизировать процессы управления перевозками и планирования маршрутов [4].
   
   Результаты работы системы
   1. Список рейсов.
   2. Заявки в рейсе.
   
   ANTOR MonitorMaster предназначен для мониторинга транспорта и мобильных объектов, определения отклонений от заданных маршрутов и графиков их передвижения [4]. В состав комплекса входит бортовое устройство и комплекс программных средств для обработки данных и подготовки отчетов.
   
   Недостатком данного программного комплекса является его ориентация на один склад, на котором производится загрузка, с последующей разгрузкой в точках доставки, следовательно, необходимость его корректирования для решения поставленных задач.


3. Решение «IT-Box: Грузоперевозки, Логистика, Склад» содержит автоматизацию специфических бизнес-функций управления грузопотоками, такими как планирование транспортно-логистической деятельности, оптимизация цепочек поставок, планирование и отслеживание маршрутов, учет, контроль и анализ грузопотоков, является комплексным решением для автоматизации всего жизненного цикла бизнес-процессов по учету, контролю и анализу грузопотоков [5].
   
   Система содержит следующие модули:
   - «Управление поставкой».
   - «Управление парком Транспортных Средств».
   - «Управление ВЭД и документооборотом».
   - «Расширенное управление складом».
   - «Постановка задач».
   - «Аналитическая отчетность».
   
   Недостатки решения:
   - выбор оптимального маршрута и транспорта за счет наглядной оценки возможных вариантов и анализа «что-если?», потому что для поставленных задач это неприемлемый вариант;
   - так как система ориентирована на международные поставки товара и содержит бизнес-функции управления грузопотоками, в ней содержится много лишней функциональности, такой как возможность организации мультимодальных перевозок, функция постановки задач сотрудникам, поддержание интеграции с таможенными системами, расширенное управление складом и т.д.


4. Конфигурация БИТ: НОВА Управление транспортной логистикой ред. 3.0 является идеологическим потомком конфигурации НОВА: Управление доставкой, созданным с использованием новейших технологий и на новой платформе 1С:Предприятие 8 [6].
   
   Возможности системы управления транспортной логистикой:
   - Управление адресами доставки
   - Управление заказами на доставку
   - Управление графиками доступности транспорта и работы водителей
   - Автоматическое и ручное планирование маршрутов доставки
   - Сопровождение рейсов в пути
   - Учет затрат и доходов по рейсу
   - Анализ грузоперевозок
   - Возможность интеграции с системами GPS мониторинга транспорта
   
   Система GPS мониторинга транспорта - это программно-аппаратный комплекс. Для определения местоположения автомобиля система GPS-мониторинга использует систему спутниковой навигации GPS (NAVSTAR), технологию GPRS в сетях GSM для передачи отчетов на сервер [6].
   
   Недостатками такой системы являются:
   - немалая стоимость;
   - система предназначена для функционирования в пределах одного города, поэтому несложна, а значит, не способна решать задачи указанного масштаба.

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

1. Метод ветвей и границ. Метод является вариацией полного перебора с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений.
   
   Общая идея метода может быть описана на примере поиска минимума и максимума функции f(x) на множестве допустимых значений x. Функция f и x могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ) [7].
   
   Правило отсева устраняет просмотр некоторых частей дерева, но на самом деле оно может допускать глубокое проникновение внутрь дерева до того, как ветви обрываются, поэтому метод ветвей и границ не эффективен по времени выполнения.


2. Эвристические методы вставок. Наилучшее решение для конкретных исходных данных может быть найдено путем последовательного применения различных эвристических методов, используя для сравнительной оценки качества приближения длину полученного маршрута [8]. Рассмотрим 4 наиболее популярных эвристических алгоритма:
   1) метод ближайшего соседа (Nearest Neighbor) [9];
   2) метод ближайшего города (Nearest Town) [9];
   3) метод самого дешевого включения (Most Cheap Inclusion) [9];
   4) метод минимального остовного дерева (Minimum Spanning Tree) [9].
   
   В методе ближайшего соседа пункты плана последовательно включаются в маршрут, причем, каждый очередной включаемый пункт должен быть ближайшим к последнему выбранному пункту среди всех остальных, еще не включенных в состав маршрута.
   
   Метод ближайшего города на каждом шаге алгоритма строит допустимый маршрут по текущему подмножеству пунктов уже включенных в маршрут, добавляя к нему новый пункт из числа еще не включенных в маршрут, для которого найдется ближайший сосед из числа пунктов уже принадлежащих маршруту.
   
   Метод самого дешевого включения на каждом шаге алгоритма проводит допустимый маршрут по текущему подмножеству пунктов, уже включенных в маршрут, добавляя к нему новый пункт, включение которого между некоторыми смежными пунктами приводит к минимальному увеличению стоимости (длины) маршрута.
   
   Однако любой эвристический метод базируется на формально не обоснованных соображениях, поэтому невозможно доказать, что эвристический алгоритм для любых исходных данных находит решения близкие к оптимальному.


3. Генетический алгоритм. Это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию [10]. Является разновидностью эволюционных вычислений.
   
   Генетический алгоритм (ГА) представляет собой метод оптимизации, основанный на концепциях естественного отбора и генетики. В этом подходе переменные, характеризующие решение, представлены в виде ген в хромосоме. ГА оперирует конечным множеством решений (популяцией) — генерирует новые решения как различные комбинации частей решений популяции, используя такие операторы, как отбор, рекомбинация (кроссинговер) и мутация. Новые решения позиционируются в популяции в соответствии с их положением на поверхности исследуемой функции [11].


4. Табу-поиск. Основоположником мета-эвристического алгоритма табу поиска является Ф. Гловер, который предложил принципиально новую схему локального поиска [12].
   
   Табу поиск является мета-эвристическим алгоритмом, который ведет местный поиск, чтобы уберечь его от попадания в ловушку преждевременных местных оптимумов, запрещая те перемещения, которые возвращают поиск к предыдущим решениям и приводят к циклической работе [13].
   
   Основным механизмом, позволяющим алгоритму избегать локальный оптимум, является табу список, который обновляется в конце каждой итерации. Выбор лучшего решения в окрестности происходит таким образом, что он не принимает ни одного из запрещённых атрибутов.
   
   Алгоритм табу поиска является довольно перспективным, однако введение штрафов на нарушение всех видов ограничений в целевую функцию не дает гарантий нахождения допустимых решений.


5. Муравьиный алгоритм. Один из эффективных полиномиальных алгоритмов для нахождения приближённых решений задачи коммивояжёра, а также аналогичных задач поиска маршрутов на графах [14]. Суть подхода заключается в анализе и использовании модели поведения муравьёв, ищущих пути от колонии к источнику питания, и представляет собой метаэвристическую оптимизацию. Изначально предложен доктором философских наук Марко Дориго в 1992 году, является первым алгоритмом, направленым на поиск оптимального пути в графе [14].
   
   Моделирование поведения муравьёв связано с распределением феромона на тропе - ребре графа в задаче коммивояжёра. При этом вероятность включения ребра в маршрут отдельного муравья пропорциональна количеству феромона на этом ребре, а количество откладываемого феромона пропорционально длине маршрута [15]. Чем короче маршрут, тем больше феромона будет отложено на его рёбрах, следовательно, большее количество муравьёв будет включать его в синтез собственных маршрутов. Моделирование такого подхода, использующего только положительную обратную связь, приводит к преждевременной сходимости - большинство муравьёв двигается по локально оптимальному маршруту. Избежать этого можно, моделируя отрицательную обратную связь в виде испарения феромона. При этом, если феромон испаряется быстро, то это приводит к потере памяти колонии и забыванию хороших решений, с другой стороны, большое время испарения может привести к получению устойчивого локального оптимального решения [15].

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

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

В каждом областном центре Украины существует склад, который использует некоторое количество транспортных средств поставки с идентичной грузоподъемностью Q. На N складах есть груз весом,. На каждом i-м складе,, имеется Z заказов весом,. Требуется составить маршруты доставки грузов с одних складов на другие в течение 48 часов, причем выгрузка и дозагрузка могут осуществляться на складах по пути следования транспортного средства.

Дан полный взвешенный граф из вершин N. Вершинам графа сопоставим склады, на которых имеется груз, ребрам - пути, ведущие от склада к складу, и припишем им стоимость пути. Решение для задачи маршрутизации транспорта может быть представлено в виде перевозок всего имеющегося на всех складах груза K маршрутами {R1...Rk}, К --> min. Задача оптимизации грузовых перевозок может быть сформулирована как минимизация общей стоимости всех маршрутов с учетом выполнения ограничений: где - вес ребра, ведущего из вершины i в вершину j, – подмаршрут от склада i к складу j, - соответствующий маршрут, где, К – количество маршрутов, Е – вес уже имеющегося груза в автомобиле.

Ограничение (2) определяет, что транспортное средство не может быть загружено больше, чем позволяет его грузоподъемность. – вес р-го груза на i-м складе, , N – количество складов, , Z – количество грузов на складе. Ограничение (3) – это ограничение по времени; прибытие машины на склад не должно быть позднее установленного срока. – это время прибытия соответствующей k-й машины на i-й склад, – крайний срок времени обслуживания i-го склада.

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

Решение задачи

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

Можно попробовать связать с метаэвристикой локальную оптимизацию. Это интересное сочетание, так как локальный оптимизатор часто страдает от проблемы «инициализации», кроме того, локальная процедура поиска тратит много времени, улучшая низкое начальное качественное решение [16]. Поэтому интересно найти хорошие метаэвристические локальные оптимальные сцепления, где сцепление хорошо, если метаэвристика генерирует начальные решения, которые можно отнести к очень хорошим локальным оптимумам локальным оптимизатором. Необходимо решить задачу последовательного упорядочения (SOP) с помощью муравьиного алгоритма в сочетании с модифицированной версией 3-х оптимальной процедуры поиска.

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

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

Каждый муравей многократно начинает движение с узла 0 и добавляет новые узлы, пока все узлы не были посещены, и узел n достигнут. Находясь в узле і, муравей выбирает вероятностно следующий узел j из набора F (i) из выполнимых узлов. F (i) сдержит все узлы j, которые еще должны быть посещены, и все, что должны предшествовать j, согласно ограничениям предшествования, были уже вставлены в последовательность.

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

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

След феромона также испаряется в течение построения решения. В этом случае, однако, он удален из посещенных ребер. Другими словами, каждый муравей, перемещаясь из города i в город j, применяет правило испарения феромона, которое заставляет количество следа феромона на ребре (і,j) уменьшаться [15]. Правило: где - первоначальное значение следов. Считается, что хорошее значение для этого параметра
Объяснение использования формулы (7) - то, что муравьи съедают след феромона, в то время как они строят решения так, чтобы определенное множество в произведенных решениях было точно.

Далее для того, чтобы учесть ограничения на порядок обхода городов (узлов графа) будет применен лексикографический поиск. Который будет заключаться в следующем. Берем найденную ранее последовательность узлов и получаем новую посредством обмена узлов в ней так, как это было предложено Дориго и Гамбарделла в [16]. Проходим все узлы и инвертируем те из них, которые стоят не в нужном порядке. Для этого генерируем 2 пути (левый и правый), которые первоначально составлены из одного единственного узла и расширяются добавлением одного нового узла на каждом шаге. Эта особенность позволяет легко проверить выполнимость решения, потому что условия предшествования должны быть проверены только для нового добавленного узла. Будем различать прямой и обратный поиск. Процедура поиска начинается, устанавливая узел h=0, и затем перемещает h через последовательность, пока узел n-2 не достигнут. Каждый раз, когда узел h отобран, процедура выполняет прямой и обратный лексикографический поиск того же самого h.

Процедура прямого лексикографического 3-opt поиска начинается установкой значения i, которое определяет самый правый узел левого пути (path_left), и выполняется цикл на значение j, которое определяет самый правый узел правого пути (path_right)(Рис. 1а и 1б): path_right=(i+1,...j) итерационно расширяется новым ребром {j,j+1}[16].

Когда все возможные узлы добавлены в правый путь, левый путь расширяется новым ребром {i,i+1} (Рис. 1в). И поиск снова начинается в правом пути. Левый и правый пути при инициализации состоят только из элементов i=h+1 и j=i+1 (Рис. 1г).
В случае обратного поиска (Рис. 2) левый путь идентифицируется (j+1, ..., i) и правый (i+1, ..., h). После установки h, i=h-1 и j=i-1 (Рис. 2а), и расширяем левый путь перемещением j до начала последовательности, присваивая j значения i-2, i-3, ..., 0 (Рис. 2б). Затем правый путь итерационно расширяется в обратном порядке новым ребром {i,i+1}, и цикл в левом пути повторяется.

Полный лексикографический поиск посещает все возможные узлы последовательности, но он должен быть остановлен, как только находит невыполнимый обмен. Левый путь должен быть определен как (h+1, ..., i), тогда правый путь будет j=i+1. В этой ситуации возможно проверить обменную выполнимость, проверяя, есть ли отношение предшествования между узлом j и узлами в правом пути. Перед расширением правого пути новым ребром {j,j+1} мы проверяем, выполнимы ли все еще результирующие пути, проверкой отношения предшествования между новым узлом j+1 и узлами в левом пути. В случае, если проверка не выполняется, поиск останавливается.

Заключение

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

Литература

1. Современные системы планирования и управления транспортом. [Электронный ресурс]: Режим доступа: URL: http://www.odamis.ru/doc/pub/analit/20080519_2123
2. GPS GPRS Cлежение. Определение местоположение через спутник. [Электронный ресурс]: Режим доступа: URL: http://gribok.kiev.ua
3. Транспортная логистика :: Оптимизация грузоперевозок. [Электронный ресурс]: Режим доступа: URL: http://www.toplogistic.ru/transport_logistics.html
4. SystemGroup Логистика. [Электронный ресурс]: Режим доступа: URL: http://systemgroup.com.ua/solutions/logistics
5. Решение для транспортно-логистических компаний. [Электронный ресурс]: Режим доступа: URL: http://www.itboxcons.ru/content/view/22/39/
6. Транспортная логистика. [Электронный ресурс]: Режим доступа: URL: http://www.nova-it.ru/
7. Метод ветвей и границ. [Электронный ресурс]: Режим доступа: URL: http://ru.wikipedia.org/wiki
8. Рейнгольд Э. Комбинаторные алгоритмы. Теория и практика. - М.: Мир, 1980. — 476 c.
9. Пушкарёва Г.В. Исследование и применение бионических методов и моделей для автоматизированного проектирования маршрутов обхода геометрических объектов Компьютерная графика и представление GraphiCon 2005: науч.-техн. конф., 20-24 июня 2005г. : - 2005. - Режим доступа: URL: http://www.graphicon.ru/2005/proceedings/papers/Pushkaryova.pdf
10. Генетический алгоритм. [Электронный ресурс]: Режим доступа: URL: http://ru.wikipedia.org/wiki
11. Обобщённая задача коммивояжёра для определения рациональных маршрутов поставки. [Электронный ресурс]: Режим доступа: URL: http://econference.ru
12. Glover F. Tabu Search Journal of the Operational Research Society. - 1999. – Vol.50, № 1. – pp. 106–107. - Режим доступа: URL: http://glossary.computing.society.informs.org/notes/spanningtree.pdf
13. Сухарев А.Г. Курс методов оптимизации: Учебное пособие. - [2-е изд]. – М.: ФИЗМАТЛИТ, 2005. – 368 с.
14. Муравьиный алгоритм. [Электронный ресурс]: Режим доступа: URL: http://ru.wikipedia.org/wiki
15. Штовба С.Д. Муравьиные алгоритмы// Exponenta Pro. Математика в приложениях. - 2003. – № 4. – С. 70-75
16. Gambardella L.M., Dorigo M. HAS-SOP Hybrid Ant System for the Sequential Ordering Problem Technical Report IDSIA 11-97. - Режим доступа: URL: http://citeseerx.ist.psu.edu/viewdoc

Замечание. При написании данного автореферата магистерская работа еще не завершена. Дата окончательного завершения работы: декабрь 2011 г. Полный текст работы и материалы по теме могут быть получены у автора или его научного руководителя после указанной даты.

Резюме | Биография | Библиотека | Ссылки | Отчет о поиске | Индивидуальный раздел