Автореферат (1137081)
Текст из файла
На правах рукописиСластников Сергей АлександровичЭффективные алгоритмы планирования транспортировкипродукции (на примере продуктов с особыми условиями перевозки)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.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
