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

На правах рукописиСластников Сергей АлександровичЭффективные алгоритмы планирования транспортировкипродукции (на примере продуктов с особыми условиями перевозки)05.13.01 – «Системный анализ, управление и обработка информации»(управление)АВТОРЕФЕРАТдиссертации на соискание ученой степеникандидата технических наукМосква2014Работа выполнена на кафедре «Кибернетика»Московского институтаэлектроники и математики Национального исследовательского университета«Высшая школа экономики».Научный руководитель:Белов Александр Владимирович,кандидат технических наук, доцент,декан факультета Прикладной математикии кибернетики МИЭМ НИУ ВШЭОфициальные оппоненты:Лупян Евгений Аркадьевич,доктор технических наук,заместитель директора ФГБУН «Институткосмических исследований» РАНФролов Евгений Борисович,доктор технических наук, профессор,кафедра «Информационные технологии ивычислительные системы» МГТУ «Станкин»Ведущая организация:ФГБУН «Вычислительный центр им.Дородницына» Российской академии наукА.А.Защита состоится 9 марта 2015 года в 11:00 часов на заседании диссертационногосовета Д002.086.02 Федерального государственного бюджетного учреждениянауки Институт системного анализа Российской академии наук (ИСА РАН) поадресу: 117312, Москва, проспект 60-летия Октября, 9.С диссертацией можно ознакомиться в библиотеке ИСА РАН.Электронные версии диссертации и автореферата размещены на официальномсайте ИСА РАН http://www.isa.ru.Электронная версия автореферата отправлена для размещения на официальномсайте ВАК Министерства образования и науки РФ по адресуreferat_vak@mon.gov.ru __ декабря 2014 года.Отзывы и замечания по автореферату в двух экземплярах, заверенные печатью,просьба высылать по адресу 117312, Москва, проспект 60-летия Октября, 9, ИСАРАН, диссертационный совет.Автореферат разослан ___ __________ 201_ года.Ученый секретарьдиссертационного совета Д002.086.02д.т.н., профессорПропой А.И.ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫАктуальностьработы.Задачаэффективногопланированиятранспортировки продукции всегда привлекала повышенное внимание какэкономистов и специалистов по логистике, так и математиков.

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

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

Она является обобщением известнойзадачи коммивояжёра и, следовательно, принадлежит к классу NP-полных задач.Сначала активно развивались точные методы решения, идеи которых былизаимствованы из методов решения задачи коммивояжера. Среди них можновыделить методы ветвей и границ (Augerat P., 1995; Rinaldi G., 1989; МеламедИ.И., Сигал И.Х., 1997), динамического программирования (Christofides N.,Mingozzi A., Toth P., 1981) и целочисленного линейного программирования(Desrochers M., Laporte G., Nobert Y., 1985; Desrosiers J., Solomon M., 1992).Однако, начиная уже с 60-х годов, основные усилия были брошены на разработкуприближенных алгоритмов – эвристик.

Их можно разбить на 3 большие группы:конструктивные алгоритмы (Clarke G., Wright J., 1964; Solomon M., 1987),двухфазные (Gillett B., Miller L., 1974; Fisher M., Jaikumar R., 1981) и улучшающиеалгоритмы (Kinderwater G., Savelsbergh M., 1997). Метаэвристические алгоритмыначали активно разрабатываться после 1990-х годов. Большинство известныхметаэвристик были предложены на основе идей, возникших при наблюдениипроцессов живой и неживой природы (Glover F., 1989; Dueck G., 1993; GendreauM., Hertz A., Laporte G., 1994; Dorigo M., Gambardella L.M., 1997; Курейчик В.М.,2002; Bräysy O., Gendreau M., 2008; Nguyen Q.C., Ong Y.S., Lim M.H., 2009).Целью данной работы является разработка эффективных алгоритмовпланирования доставки продукции, в том числе обладающей специфическими4правилами перевозки.

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

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

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

Практическая значимостьработы подтверждается пригодностью применения разработанной системыпланирования доставки, в частности, в области транспортировки нефтепродуктов.Достоверностьполученныхрезультатовподтвержденавходевычислительных экспериментов на выборке модельных задач маршрутизациитранспорта с ограничениями грузоподъемности.Основные защищаемые положения:1. Модификация метаэвристического алгоритма муравьиных колоний длярешениязадачимаршрутизациитранспортасограничениямигрузоподъемности и подтверждение его эффективности.2. Зависимости управляющих параметров алгоритма от числа клиентов задачи.3. Двухфазный алгоритм, основанный на предложенной модификации.4. Реализация предложенных алгоритмов в виде программной библиотеки.5. Архитектура системы планирования доставки продукции.Внедрение результатов работы1.