Автореферат (Эффективные алгоритмы планирования транспортировки продукции (на примере продуктов с особыми условиями перевозки)), страница 2

Разработанные алгоритмы и программное обеспечение использовались припроектировании подсистемы управления транспортировкой нефтепродуктовдля розничных сбытовых сетей нефтяных компаний.2. Полученные в диссертации результаты использованы в учебном процессе накафедре«Кибернетика»«КорпоративныеМИЭМНИУинформационныеВШЭв рамкахсистемы»,дисциплин«Проектированиеинформационно-управляющих систем».3. Полученные в диссертации результаты использованы в учебном процессе винституте ИБС НИТУ «МИСиС» на кафедре «Информационные бизнессистемы»врамкахдисциплины«Архитектурапредприятияипроектирование КИС».Апробация результатов. Основные положения и отдельные результатыбыли представлены на конференциях:61.

VIII Всероссийская научно-практическая конференция (с участием странСНГ)«СИСТЕМЫАВТОМАТИЗАЦИИвобразовании,наукеипроизводстве» – Новокузнецк, 2011 г.2. Научно-техническая конференция студентов, аспирантов и молодыхспециалистов МИЭМ – Москва, 2011 г.3. Научно-техническая конференция студентов, аспирантов и молодыхспециалистов МИЭМ, посвященная 50-летию МИЭМ – Москва, 2012 г.4.

Четвертая ежегодная научно-практическая конференция «Информационныебизнес-системы» – Москва, 2012 г.5. InternationalConferenceScientific-Practical«Innovativeinformationtechnologies» – Prague, 2012 г.6. Международная научно-практическая конференция «Инновации на основеинформационных и коммуникационных технологий» – Сочи, 2012 г.7. Научно-техническая конференция студентов, аспирантов и молодыхспециалистов МИЭМ НИУ ВШЭ – Москва, 2013 г.8.

2nd International Conference on Information Technology and QuantitativeManagement, ITQM – Moscow, 2014 г.Публикации. По теме диссертации опубликованы 11 научных работ, средикоторых 3 статьи в журналах из перечня ВАК.Структура и объем диссертации. Диссертация состоит из введения,четырех глав, заключения и списка литературы. Работа содержит 112 страниц,включает в себя 23 рисунка и 3 таблицы.

Список литературы состоит из 93наименований.СОДЕРЖАНИЕ РАБОТЫВо введении обоснована актуальность темы диссертационной работы,сформулированы цели работы, методика исследования, научная новизна,практическаяитеоретическаязначимость,7достоверностьполученныхрезультатов, основные защищаемые положения. Также представлены сведения овнедрении и апробации работы.В первой главе проведен анализ современного состояния проблемыразработки автоматизированных систем управления транспортировкой.В разделе 1.1 управление транспортировкой рассматривается как частьлогистической системы.

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

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

Опишем ее:имеется N нефтебаз, с которых M видов топлива развозятся по n АЗС;задан неотрицательный спросqij — i-ой АЗС на топливо типа j (i=1,...,n,j=1,...,M);для перевозки топлива используются бензовозы, состоящие из одной илинескольких емкостей, причем при наливе емкость бензовоза заполняется8полностью, а при сливе полностью освобождается, таким образом, частичныйналив или слив не допускаются;бензовоз выходит на линию из автопарка и возвращается в парк,количество автопарков равно K, в парке i имеется ki бензовозов (i=1,...,K);длины маршрутов от автопарков до нефтебаз, от нефтебаз до АЗС имеждувсемиАЗСзаданысоответствующимиматрицамиdij1 (i 1,..., K , j 1,..., N ), dij2 (i 1,..., N , j 1,..., n), dij3 (i, j 1,..., n) .Цель задачи транспортировки нефтепродуктов состоит в генерациимаршрутов бензовозов минимальной суммарной длины, удовлетворяющихпотребностям всех АЗС.Кроме того, в 1.3 показано, что данную задачу (со многими видамипродукции) можно свести к задаче развозки одного вида продукции, если ввести«фиктивных клиентов» и использовать ограничение, запрещающее частичныйслив из бензовоза.

Таким образом, поставленная задача развозки нефтепродуктовот нефтебаз до АЗС (размерности n) сводится к задаче маршрутизации транспорта(размерности M n ).В 1.4 приводится обзор различных вариантов задачи маршрутизации,которые приближают ее к практическим задачам оперативного планирования натранспорте. Модель задачи маршрутизации транспорта с ограничениямигрузоподъемности является наиболее подходящей в рамках рассматриваемыхзадач транспортировки и их ограничений. Она выглядит следующим образом.Задан граф G=(V, A, D), где V{v0 ,..., vn } — множество вершин ( v0 —склад, остальные вершины — клиенты); A — набор дуг, соединяющихсоответствующиевершиныграфа;D {dij , i, j 0,1,..., n}—множествонеотрицательных чисел, которые чаще всего имеют смысл длины пути, времениили стоимости перевозки по дуге между вершинами vi и v j (далее для краткостибудем называть их просто i и j), их можно рассматривать как обобщение всехвидов затрат на перевозку продукции из i в j.

Для клиента в вершине i (клиента i)задан неотрицательный спрос ci на некую продукцию или товар. На складе9имеется m транспортных средств, грузоподъёмность каждого из которыхограниченавеличинойCk( k 1,..., m ).Длязадачизаданыследующиеограничения:каждый клиент должен быть посещён ровно один раз;местом начала и окончания всех маршрутов транспортных средств являетсясклад.Целью задачи является построение маршрутов минимальной суммарнойстоимости,удовлетворяющихспросвсехклиентовиненарушающихограничений, описанных выше.В разделе 1.5 обобщены результаты, полученные в первой главе.

Один изглавных выводов состоит в целесообразности разработки алгоритмического ипрограммного обеспечения, позволяющего оптимизировать решение задачимаршрутизации транспорта. Результатом такой разработки должна стать системапланирования транспортировки, обладающая следующими характеристиками:нахождение оптимальных или субоптимальных решений для задачиразвозки продукции (в том числе с особыми условиями транспортировки);возможность ее применения независимо от способа организациилогистической цепочки доставки продукции;инвариантность относительно используемых других информационныхсистем.Во второй главе представлен обзор и анализ методов решения задачимаршрутизации транспорта (ЗМТ).В разделе 2.1 приведена классификация существующих методов решения.Их можно разбить на:точные методы;классические эвристические методы;метаэвристические методы.Подробное описание методов в каждой группе приводится в разделах 2.3 – 2.5.10В разделе 2.2 описаны четыре различные математические постановкизадачи маршрутизации транспорта, которые позволяют взглянуть на нее с разныхсторон и необходимы для описания некоторых подходов к решению задачи.Наиболее полной и строгой математической моделью является трехиндекснаяпостановка, которую можно сформулировать следующим образом:mnndij X ijkFmin(1)k 1,..., m ,(2)k 1 i 0 j 0при ограниченияхnnX ijkcii 1Ckj 0nX 0k j 1k 1,..., m ,(3)X ik0 1k 1,..., m ,(4)j 1ni 1mnX ijki 1,..., n ,1(5)k 1 j 0nnX ihki 0X hjkh 1,..., n,k 1,..., m ,(6)j 0X ijk {0,1}X iikесли Sk00i, j 0,..., n,k 1,..., m ,k 1,..., m ,i 0,..., n,(7)(8){(i, j ) : X ijk 1} , тоk 1,..., mj0(i, j ) Skjl1( j p , j p 1 ) Sk ( p 0,..., l ) :0, (i, j ) ( jr , jr 1 ), r l .(9)Величина X ijk принимает значение 1, если транспортное средство k следуетот клиента i к клиенту j, и 0 в противном случае.

S k — множество пар вершин,определяющих маршрут машины k. Целевая функция (1) минимизируетстоимость всех маршрутов всех транспортных средств. Неравенство (2)гарантирует,чтовыполняютсяограничения11грузоподъемностикаждоготранспортного средства. Ограничения (3) и (4) определяют, что каждоетранспортное средство не может покинуть склад и вернуться на склад более 1раза. Равенство (5) показывает, что каждый клиент обслуживается только однимтранспортным средством и только один раз.