Пример готовой дипломной работы по предмету: Экономика
Содержание
Оглавление
Введение 4
1. Теоретическое обоснование 8
2. Постановка исследовательской проблемы 19
3. Данные и методология 27
4. Описание результатов 36
Заключение 53
Список литературы 58
Приложения 60
Выдержка из текста
Введение
С точки зрения экономической теории, понятие транспортной логистики рассматривается как планирование оптимальных маршрутов грузоперевозок с минимизацией затрат, что является особенно актуальным для торговых компаний, ежедневно доставляющих продукцию покупателям. В связи с растущей загруженностью автомобильных дорог, водители предприятий часто опаздывают в установленные временные интервалы доставки, что приводит к возвратам продукции, росту неудовлетворенности клиентов, и, в конечном счете, к потерям выручки и убыткам. Существует ряд моделей, применив которые, фирма может существенно сократить транспортные расходы и оптимизировать последовательность посещения контрагентов. Одна из них – классическая задача коммивояжера (КЗК), решением которой является кратчайший замкнутый маршрут водителя, проходящий через всех покупателей по одному разу. Задача была поставлена английскими математиками У. Гамильтоном и Т. Киркманом в середине ХIХ века. В течение последующих десятилетий ученые из разных стран изучали КЗК, разрабатывая новые математические постановки задачи и алгоритмы их решения. Так появились точные и приближенные методы достижения оптимальных маршрутов (Бронштейн, Заико, 2010).
К точным методам относятся алгоритм полного перебора и метод ветвей и границ, а к приближенным (позволяют найти маршрут близкий к точному решению задачи) – метод имитации отжига, алгоритм муравьиной колонии и др.
Несмотря на популярность классической задачи коммивояжера, она редко решается на практике, поскольку ее ограничения не учитывают, например, маршрутизацию нескольких машин в автопарке компании, пробки на дорогах и временные интервалы доставки покупателям. Желая приблизить теоретическую задачу к реальности, Данциг и Рамсер, предложили разновидность КЗК, включив в нее ограничение на количество автомобилей и назвав ее – задачей маршрутизации транспорта (ЗМТ) (Danzig,
Ramser, 1959).
Решение задачи представляет собой оптимальные маршруты для двух и более автомобилей, которые проходят через все точки на карте один раз, возвращаясь в исходную. Данную модель успешно применяют в таких отраслях науки как медицина, машиностроение и программирование
и т.д. Подчеркнем, что задача маршрутизации транспорта является обобщением классической задачи коммивояжера и решается похожими алгоритмами.
В настоящем исследовании рассматривается одна из областей применения задачи маршрутизации транспорта – логистика. В работе осуществляется поиск решения ЗМТ на примере пермской торговой фирмы ООО «Фабрика еды», занимающейся оптовой торговлей мясопродуктами. Компания имеет двух водителей, отвечающих за доставку продукции контрагентам. Летом 2015 года у предприятия возникли трудности с развозом продукции покупателям: в связи с увеличивающимся количеством заявок, водители часто опаздывали в желаемое время поставки, установленное покупателями, за что были оштрафованы возвратом продукции в полном размере. Общие непредвиденные транспортные расходы по вине двух водителей составляли от
2. до 35 тыс. в месяц, что послужило причиной поиска их минимизации. В исследовании предполагается, что решив задачу маршрутизации транспорта, торговая компания сократит свои логистические расходы. Отметим, что в работе рассматривается модифицированная ЗМТ, которая учитывает специфику бизнеса: в задачу добавляется ограничение на грузоподъемность транспортных средств, а также два условия, устанавливающие временные окна покупателей. Описываемая задача анализируется на реальных данных торговой компании (рассматривается день с
5. покупателем).
ЗМТ решается современными математическими алгоритмами: муравьиным методом и алгоритмом поиска с запретами. Применяемые методы являются эвристическими (приближенными) способами нахождения оптимального решения задачи.
На практике любой путь водителей будет оптимальным, если он удовлетворяет временным интервалам доставки. В исследовании рассматривается как детерминированная, так и стохастическая постановка ЗМТ, процесс пересчета маршрута водителей, а также проводится сценарный анализ пробок в г. Пермь c построением сетевых моделей планирования и управления логистикой. Результаты данной работы могут найти применение не только в исследуемой фирме, но и в различных предприятиях связанных с доставкой продукции и объездом контрагентов, например, в службе инкассации, пожарной и скорой помощи и т.д.
Целью выпускной квалификационной работы является постановка и решение задачи поиска оптимального плана доставки продукции торговой компании.
Задачами работы являются:
1) Анализ предметной области исследования;
2) Постановка задачи маршрутизации транспорта с временными интервалами доставки продукции и ограничением на грузоподъемность транспортных средств;
3) Анализ и сравнение алгоритмов решения различных модификаций задачи маршрутизации транспорта;
4) Разработка методологии сведения стохастической задачи маршрутизации транспорта к серии детерминированных задач;
5) Сбор данных, необходимых для математического моделирования;
6) Применение ряда методов в современных программных пакетах (Умные маршруты, Муравьиная логистика) на данных компании;
7) Формирование маршрутов развоза продукции водителями фирмы ООО «Фабрика еды» с учетом временных ограничений покупателей и грузоподъемности автомобилей;
8) Оценка и анализ полученных результатов.
Объект исследования – математические модели оптимизации логистики торговых предприятий. Предметом выпускной квалификационной работы является применение задачи маршрутизации транспорта с временными окнами и ограничением на грузоподъемность автомобилей на примере торговой фирмы ООО «Фабрика еды». В исследовании использовались следующие методы: анализ специальной и научной литературы, методы математического моделирования и оптимизации.
Выпускная квалификационная работа состоит из введения, четырех разделов, заключения и списка литературы. В первом разделе подробно рассматривается ряд существующих работ по исследуемой теме. Теоретическое обоснование структурно разделено на две части: первая часть посвящена классической задаче коммивояжера, а вторая – задаче маршрутизации транспорта с временными окнами и ограничением на грузоподъемность автомобилей (capacitated vehicle routing problem with time windows — CVRPTW).
Отметим, что последняя задача является обобщением первой, следовательно, необходимо провести как совместный, так и сепаратный анализ двух задач. Второй раздел, описывает предметную область (компанию), ограничения и предпосылки, возникающие в ходе моделирования. Рассматривается математическая постановка исследуемой задачи. В третьем разделе подробно описываются используемые данные и алгоритмы решения задачи. Также в третьей части проводится сравнительный анализ основных методов решения по ряду критериев. Большое внимание уделяется муравьиному методу и алгоритму «поиска с запретами». Последний раздел подразумевает обсуждение основных результатов исследования. В данной части работы в программных пакетах реализуются математические методы нахождения оптимальных маршрутов водителей торгового предприятия, строятся сетевые модели планирования и управления, проводится пересчет маршрутов в случае непредвиденных дорожных ситуаций, а также решается классическая задача об оптимальной загрузке автомобиля. Полученные результаты обобщаются в виде выводов, а также даются рекомендации по практическому применению моделей и внедрению их в компании.
Список использованной литературы
Список литературы
1. Бронштейн, Е.М., Заико, Т.А. (2010), «Детерминированные оптимизационные задачи транспортной логистики», Автоматика и телемеханика, № 10, с. 133-147.
2) Иглин, С.П. (2003), «Решение некоторых задач теории графов в MATLAB», Математика в приложениях, № 4, с. 28-33.
3) Костюк, Ю.Л. (2013), «Эффективная реализация алгоритма решения задачи коммивояжера методом ветвей и границ», Прикладная дискретная математика, Т. 20,
№ 2, с. 78-90.
4) Курейчик, В.М., Мартынов, А.В. (2014), «Об алгоритмах решения задачи коммивояжера с временными ограничениями», Информатика, вычислительная техника и инженерное образование, Т. 16, № 1, с. 1-13.
5) Лебедев, Б.K., Лебедев, О.Б. (2012), «Моделирование адаптивного поведения муравьиной колонии при поиске решений, интерпретируемых деревьями», Известия ЮФУ. Технические науки, Т. 132, № 7, с. 27-34.
6) Лопатин, А.С. (2005), «Метод отжига», Стохастическая оптимизация в информатике, Т.1. № 1, с. 133-139.
7) Макконнелл, Дж. (2004), Основы современных алгоритмов, М: Техносфера,
с. 233-255.
8. Пантелеев, А.В., Метлицкая, Д.В., Алешина, Е.А. (2013), Методы глобальной оптимизации. Метаэвристические стратегии и алгоритмы, Москва, с. 105-130.
9. Хайруллин, Р.З. (2014), «Математическое моделирование развоза грузов по разветвленной сети автодорог», Вестник МГСУ, № 7, с. 184-191.
10. Чеблоков, И.Б., Ченцов, А.Г. (2012), «Об одной задаче маршрутизации с внутренними работами», Вестник Удмуртского университета. Математика. Механика. Компьютерные науки, № 1, с. 96-119.
11) Applegate D., Cook J. (1993), “Solving large-scale matching problems”, Network Flows and Matching, pp. 557-576.
12) Azi, N., Gendreau, M. and Potvin, J.-Y. (2012), “A dynamic vehicle routing problem with multiple delivery routes”, Annals of Operations Research, pp. 1-10.
13) Baldacci, R., Mingozzi, A. and Roberti, R. (2012), “Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints”, European Journal of Operational Research, Vol. 218, No. 1, pp. 11-26.
14) Clarke, G., Wright, J.W. (1964), “Scheduling of vehicles from a central depot to a number of delivery points”, Operations Research, No. 12, 568-581.
15) Croes, G.A. (1958), “A method for solving traveling salesman problems”, Operations Research, No. 6, pp. 791– 812.
16) Dantzig, G. B., Ramser, J. H. (1959), “The truck dispatching problem”, Management Science, Vol. 6, No. 1, pp. 80-91.
17) Desrochers, M., Desrosiers, J. and Solomon, M. (1992), “A new optimization algorithm for the vehicle routing problem with time windows”, Operations Research, No. 40,
pp. 342-354.
18) Dorigo, M. (1999), “Ant algorithms for discrete optimization”, Artificial life, Vol. 5, No. 2, pp. 137-172.
19) Irnich, S. (2008), “Solution of real-world postman problems”, European Journal of Operational Research, Vol. 190, No. 1, pp. 52-67.
20) Kan, A.R., Lenstra, J.K. (1975), “Some simple applications of the travelling salesman problem”, Operations Research, No. 26, pp. 717-734.
21) Laporte, G. (1992), “The Vehicle Routing Problem: An Overview of Exact and Approximative Algorithms”, European Journal of Operational Research, Vol. 59, No. 3,
pp. 345-358.
22) Lin, S., Kernighan, B.W. (1973), “An effective Heuristic Algorithm for the TSP”. Operations Research, No. 21, pp. 498– 516.
23) Lorini, S., Potvin, J.-Y. and Zufferey, N. (2011), “Online vehicle routing and scheduling with dynamic travel times”, Computers & Operations Research, Vol. 38, No. 7,
pp. 1086– 1090.
24) Moon, I., Lee, J. and Seong, J. (2012), “Vehicle routing problem with time windows considering overtime and outsourcing vehicles”, Expert Systems with Applications, Vol. 39, No.18, pp. 13202– 13213.
25) Rodriguez, A., Ruiz, R. (2012), “A study on the effect of the asymmetry on real capacitated vehicle routing problems”, Computers & Operations Research, Vol. 39, No. 9,
pp. 2142– 2151.
26) Schneider, J.J., Bukur, T. and Krause, A. (2010), “Traveling salesman problem with clustering”, Journal of Statistical Physics, Vol. 141, No. 5, pp. 767-784.
27) Solomon, M. M. (1987), “Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints”, Operations Research, Vol. 35, No. 2, pp. 254– 265.
28) Toth, P. and Vigo D. (2002), The Vehicle routing problem, Society for Industrial and Applied Mathematics, p. 386
29) Wiener, J. M., Ehbauer, N. N. and Mallot, H. A. (2009), “Planning paths to multiple targets”, Psychological Research, No. 73, pp. 644– 658.
