Федеральное государственное образовательное учреждение высшего профессионального образования «Финансовый университет при Правительстве Российской Федерации»
Кафедра
«Информационные технологии»
Реферат
по дисциплине «Научно-исследовательский семинар»
Тема: «Многокритериальная оптимизация транспортных перевозок»
Выполнил: ________________ Кушнир А.Ю.
Подпись
Группа ПИ 1–1м
Проверил: _________________
Подпись
Москва 2014
Содержание
Проблематика 3
Методы решения 6
Многокритериальная оптимизация 6
Нейросетевое прогнозирование 7
Перспективы 11
Выводы 12
Проблематика
Проблема поиска методов оптимизации перевозок грузов в транспортной сети актуальна по целому ряду причин.
Во-первых, с развитием мелкого и среднего предпринимательства в торговой сфере возникает все большая потребность в мелкопартионных перевозок грузов широкой номенклатуры большому числу потребителей.
Во-вторых, наличие большого количества автоперевозчиков значительно обострило конкуренцию на рынке автотранспортных услуг, что вынуждает владельцев автотранспорта искать новые конкурентные преимущества. При этом меры предпринимаемые перевозчиками ради улучшения своего конкурентного положения часто оказываются малоэффективными или же негативными, заводящими автотранспортное предприятие в тупик. Например, применение низкорентабельных тарифов, когда транспортные услуги продаются по тарифам, не превышающим себестоимости перевозок. Становится очевидной необходимость поиска новых конкурентных преимуществ. Конкурентные преимущества в сфере автомобильных перевозок сегодня - это повышение качества и снижение финансовых потерь от неэффективно организованных перевозок, предоставление большого спектра услуг, улучшение обслуживания клиентуры, своевременное реагирование на изменение транспортных услуг.
В-третьих, повышению эффективности доставки грузов в настоящее время уделяется недостаточное внимание несмотря на то, что доля транспортных затрат, учитываемых при формировании цен на конечную продукцию, доходит до 50%.
В-четвертых мелкопартионные перевозки большей частью приходятся на транспортные системы крупных и средних городов, которые накладывают ряд серьезных технических ограничений, усложняющих процесс организации перевозок мелкопартионных грузов: ограничения по скорости и направлению движения, ограничения по времени и др. Организация мелкопартионных перевозок в транспортных системах городов связана с анализом больших массивов данных (число поставщиков, число перевозчиков, число грузополучателей, количество и грузоподъемность автомобилей, объем спроса по каждому грузополучателю). Кроме того, в транспортных системах городов велика роль случайных факторов внешней среды, которые очень сложно учитывать заранее при планировании (моделировании) грузоперевозок, например, - аварии, автомобильные пробки и т.п.
В-пятых, перевозки товаров широкой номенклатуры, предназначенные для удовлетворения потребностей большого числа потребителей, отличающихся разным уровнем спроса и его постоянными колебаниями организовать значительно сложнее, чем перевозки массовых грузов в условиях сформировавшихся стабильных и мощных грузопотоков между отправителями и получателями. При доставке такой многономенклатурной продукции появляется необходимость в применении более широкого использования развозочных и сборочных маршрутов средствами автомобильного транспорта. При этом планирование развозочных маршрутов сопряжено с необходимостью учета большого количества технологических ограничений и обработки исходной информации значительного объема. В результате, доставка мелкопартионных грузов становится значительно более дорогостоящей, чем доставка массовых грузов.
Решение задачи оптимизации мелкопартионных грузов в транспортной сети городов осложняется рядом объективных факторов:
- большие объемы информации, возникающие в процессе выполнения перевозок, требующие срочной обработки;
- высокая временная частота поставок;
- большое количество временных и технологических ограничений;
- частые колебания спроса;
- большое число грузополучателей и грузоотправителей;
- сильное влияние неучтенных факторов внешней среды.
Одной из основных проблем при решении данных задач является их большая размерность, вызванная тем, что маршруты необходимо прокладывать между десятками и даже сотнями грузополучателей ежедневно. Второй не менее важной проблемой является необходимость выполнения жестких требований клиентов по времени доставки груза, например, при перевозке молочных продуктов все грузополучатели могут требовать доставки товара до 10 часов утра, что может затруднить объединение в один маршрут нескольких клиентов.
Следствием чего является необходимость привлечения к перевозкам дополнительного подвижного состава при его неполной загрузке и, соответственно, увеличение транспортных затрат. Третьей проблемой является существенная неравномерность поставок по дням недели и месяцам года, вызванная колебаниями спроса.
Анализ отечественной и переводной зарубежной литературы по этому вопросу показывает, что среди множества разнообразных подходов к решению проблемы оптимизации мелкопартионных перевозок грузов в транспортной сети городов, пока еще не существует такого, который бы отражал все аспекты оптимизации. Кроме того, мало уделяется внимания определению сравнительной эффективности предлагаемых методик.
Необходимо обратить внимание на средний уровень запасов и величину резервных запасов, как процент от среднего уровня.
Методы Решения
Многокритериальная оптимизация
В теории многокритериальной оптимизации решаются задачи принятия решений одновременно по нескольким критериям. В отличие от задач оптимизации с одним критерием в многокритериальной оптимизации имеется неопределенность целей. Действительно, существование решения, максимизирующего несколько целевых функций, является редким исключением, поэтому с математической точки зрения задачи многокритериальной оптимизации являются неопределенными и решением может быть только компромиссное решение. В методе многокритериальной оптимизации Парето по уступкам критерии нумеруются в порядке убывания важности.
1-й шаг. Решается однокритериальная задача по 1-му критерию:
 .
2-й шаг. Назначается разумная с инженерной точки зрения уступка  , составляется и решается новая задача оптимизации по 2-му критерию:
 .
3-й шаг. Назначается уступка для 2-го критерия  , составляется и решается задача оптимизации по 3-му критерию:
 .
Процесс назначения уступок по каждому критерию и решения однокритериальных задач продолжается, пока не дойдем до последнего  – го шага.
-й шаг. Назначается уступка для  – го критерия  , составляется и решается задача оптимизации по последнему – му критерию:
 .
Основной недостаток методов, использующих ограничения на критерии, состоит в субъективности выбора контрольных показателей и в субъективности выбора уступок.
Нейросетевое прогнозирование
В процессе обучения нейронная сеть способна выявлять сложные зависимости между входными данными и выходными, а также выполнять обобщение. Это значит, что в случае успешного обучения сеть сможет вернуть верный результат на основании данных, которые отсутствовали в обучающей выборке, а также неполных, частично искаженных данных. Для решения многокритериальной транспортной задачи это значит, что при достаточно больших объемах данных, использование нейросети позволит выявить связи между критериями.
Далее приведена картинка нейросети, сделанная в Deductor studio в которой отображены критерии доставки по виду транспорта.
Этапы решения задачи
Сбор данных для обучения;
Подготовка и нормализация данных;
Выбор топологии сети;
Экспериментальный подбор характеристик сети;
Экспериментальный подбор параметров обучения;
Собственно обучение;
Проверка адекватности обучения;
Корректировка параметров, окончательное обучение;
Вербализация сети с целью дальнейшего использования.
Следует рассмотреть подробнее некоторые из этих этапов.
Сбор данных для обучения
Выбор данных для обучения сети и их обработка является самым сложным этапом решения задачи. Набор данных для обучения должен удовлетворять нескольким критериям:
Репрезентативность — данные должны иллюстрировать истинное положение вещей в предметной области;
Непротиворечивость — противоречивые данные в обучающей выборке приведут к плохому качеству обучения сети.
Исходные данные преобразуются к виду, в котором их можно подать на входы сети. Каждая запись в файле данных называется обучающей парой или обучающим вектором. Обучающий вектор содержит по одному значению на каждый вход сети и, в зависимости от типа обучения (с учителем или без), по одному значению для каждого выхода сети. Обучение сети на «сыром» наборе, как правило, не даёт качественных результатов. Существует ряд способов улучшить «восприятие» сети.
Нормировка выполняется, когда на различные входы подаются данные разной размерности. Например, на первый вход сети подаются величины со значениями от нуля до единицы, а на второй — от ста до тысячи. При отсутствии нормировки значения на втором входе будут всегда оказывать существенно большее влияние на выход сети, чем значения на первом входе. При нормировке размерности всех входных и выходных данных сводятся воедино;
Квантование выполняется над непрерывными величинами, для которых выделяется конечный набор дискретных значений. Например, квантование используют для задания частот звуковых сигналов при распознавании речи;
Фильтрация выполняется для «зашумленных» данных.
Кроме того, большую роль играет само представление как входных, так и выходных данных. Предположим, сеть обучается распознаванию букв на изображениях и имеет один числовой выход — номер буквы в алфавите. В этом случае сеть получит ложное представление о том, что буквы с номерами 1 и 2 более похожи, чем буквы с номерами 1 и 3, что, в общем, неверно. Для того, чтобы избежать такой ситуации, используют топологию сети с большим числом выходов, когда каждый выход имеет свой смысл. Чем больше выходов в сети, тем большее расстояние между классами и тем сложнее их спутать.
Выбор топологии сети
Выбирать тип сети следует, исходя из постановки задачи и имеющихся данных для обучения. Для обучения с учителем требуется наличие для каждого элемента выборки «экспертной» оценки. Иногда получение такой оценки для большого массива данных просто невозможно. В этих случаях естественным выбором является сеть, обучающаяся без учителя (например, самоорганизующаяся карта Кохонена или нейронная сеть Хопфилда). При решении других задач (таких, как прогнозирование временных рядов) экспертная оценка уже содержится в исходных данных и может быть выделена при их обработке. В этом случае можно использовать многослойный перцептрон или сеть Ворда.
Экспериментальный подбор характеристик сети
После выбора общей структуры нужно экспериментально подобрать параметры сети. Для сетей, подобных перцептрону, это будет число слоев, число блоков в скрытых слоях (для сетей Ворда), наличие или отсутствие обходных соединений, передаточные функции нейронов. При выборе количества слоев и нейронов в них следует исходить из того, что способности сети к обобщению тем выше, чем больше суммарное число связей между нейронами. С другой стороны, число связей ограничено сверху количеством записей в обучающих данных.
Экспериментальный подбор параметров обучения]
После выбора конкретной топологии необходимо выбрать параметры обучения нейронной сети. Этот этап особенно важен для сетей, обучающихся с учителем. От правильного выбора параметров зависит не только то, насколько быстро ответы сети будут сходиться к правильным ответам. Например, выбор низкой скорости обучения увеличит время схождения, однако иногда позволяет избежать паралича сети. Увеличение момента обучения может привести как к увеличению, так и к уменьшению времени сходимости, в зависимости от формы поверхности ошибки. Исходя из такого противоречивого влияния параметров, можно сделать вывод, что их значения нужно выбирать экспериментально, руководствуясь при этом критерием завершения обучения (например, минимизация ошибки или ограничение по времени обучения).
Собственно обучение сети
В процессе обучения сеть в определенном порядке просматривает обучающую выборку. Порядок просмотра может быть последовательным, случайным и т. д. Некоторые сети, обучающиеся без учителя (например, сети Хопфилда), просматривают выборку только один раз. Другие (например, сети Кохонена), а также сети, обучающиеся с учителем, просматривают выборку множество раз, при этом один полный проход по выборке называется эпохой обучения. При обучении с учителем набор исходных данных делят на две части — собственно обучающую выборку и тестовые данные; принцип разделения может быть произвольным. Обучающие данные подаются сети для обучения, а проверочные используются для расчета ошибки сети (проверочные данные никогда для обучения сети не применяются). Таким образом, если на проверочных данных ошибка уменьшается, то сеть действительно выполняет обобщение. Если ошибка на обучающих данных продолжает уменьшаться, а ошибка на тестовых данных увеличивается, значит, сеть перестала выполнять обобщение и просто «запоминает» обучающие данные. Это явление называется переобучением сети или оверфиттингом. В таких случаях обучение обычно прекращают. В процессе обучения могут проявиться другие проблемы, такие как паралич или попадание сети в локальный минимум поверхности ошибок. Невозможно заранее предсказать проявление той или иной проблемы, равно как и дать однозначные рекомендации к их разрешению.
Все выше сказанное относится только к итерационным алгоритмам поиска нейросетевых решений. Для них действительно нельзя ничего гарантировать и нельзя полностью автоматизировать обучение нейронных сетей. Однако, наряду с итерационными алгоритмами обучения, существуют не итерационные алгоритмы, обладающие очень высокой устойчивостью и позволяющие полностью автоматизировать процесс обучения.
Проверка адекватности обучения
Даже в случае успешного, на первый взгляд, обучения сеть не всегда обучается именно тому, чего от неё хотел создатель. Известен случай, когда сеть обучалась распознаванию изображений танков по фотографиям, однако позднее выяснилось, что все танки были сфотографированы на одном и том же фоне. В результате сеть «научилась» распознавать этот тип ландшафта, вместо того, чтобы «научиться» распознавать танки. Таким образом, сеть «понимает» не то, что от неё требовалось, а то, что проще всего обобщить.
Тестирование качества обучения нейросети необходимо проводить на примерах, которые не участвовали в её обучении. При этом число тестовых примеров должно быть тем больше, чем выше качество обучения. Если ошибки нейронной сети имеют вероятность близкую к одной миллиардной, то и для подтверждения этой вероятности нужен миллиард тестовых примеров. Получается, что тестирование хорошо обученных нейронных сетей становится очень трудной задачей.
Перспективы
Современный общемировой тренд изменил свое направление и указывает на преимущественное оказание транспортных услуг крупными компаниями, которые в состоянии оказать более полный и качественный набор услуг по сравнению с мелкими и средними перевозчиками. В свою очередь крупная компания, насчитывающая десятки и сотни машин не может обойтись без автоматизации управления ими.
Технический прогресс сделал возможным доведение информационной системы до отдельно взятого транспортного средства. Последние оснащаются производителями электронными системами диагностики и управления. Многие параметры (расход топлива, средняя скорость движения, остановки и время начала движения, маршрут) фиксируются в памяти бортового компьютера или контроллера. Данные о работе отдельных систем могут передаваться при помощи GSM/GPRS связи в он-лайн режиме в диспетчерский центр, что значительно повышает оперативность принимаемых решений. При достижении более полной интеграции между системой автопарка и различного рода технических средств, находящихся в распоряжении водителя, таких как смартфоны и планшетные компьютеры, обмен информации между бортом транспортного средства и логистом автокомпании может происходить на постоянной основе.
Уже сейчас достигается более плотное взаимодействия системы управления автопарками со службами технического обслуживания и ремонта. В случае возникновения той или иной неисправности ее код будет оперативно передан механикам. Последние в свою очередь могут оперативно связаться с водителем по смартфону и передать рекомендации по ее устранению. Более того, еще во время нахождения транспортного средства в пути можно спланировать необходимый объем работ по техническому обслуживанию и поставить требуемое количество нужных запасных частей.
Вместе с тем для более полного и качественного использования автоматизированных систем в нашей стране существует весьма весомое препятствие. Различные государственные органы, которые в тех или иных случаях запрашивают документацию транспортных предприятий, признают за показаниями автоматизированных систем второстепенное значение, выдвигая на первый план традиционную документацию на бумажных носителях: путевые листы, накладные, журналы учета.
Выводы.
Чтобы идти в ногу со временем и не дать обойти себя конкурентам необходимо оптимизировать процессы на производстве
Решение многокритериальной задачи оптимизации транспортных перевозок, пусть с достаточным количеством ограничений, имеет важное прикладное значение для дальнейшего развития экономики.
|
