Задача организации пассажирских перевозок частной компанией в условиях пандемии

Скрипцов Дмитрий Алексеевич
Бесплатно
В избранное
Работа доступна по лицензии Creative Commons:«Attribution» 4.0

Целью работы является решение задачи транспортировки сотрудников от места жительства до территории компании за оптимальное время. Поставленная задача разделена на две подзадачи: кластеризация точек, характеризующихся географическими координатами, и задача коммивояжера. Для решения поставленных задач использован геокодер HERE Technologies, проведен обзор некоторых метод кластеризации точек и реализован наиболее подходящий. Изучены статьи и пособия, посвященные задачам комбинаторики, в частности задаче коммивояжера и метода ее решения. Проведен сравнительный анализ некоторых методов поиска решения задачи коммивояжера и его приближения, реализован лучший из представленных.

Введение ……………………………………………………………………………………….. 3
Постановка задачи ………………………………………………………………………….. 4
Обзор литературы …………………………………………………………………………… 5
§1: Задача кластеризации……………………………………………………………… 7
1.1 Получение и обработка геокоординат ……………………………………. 9
1.2 Обзор некоторых алгоритмов кластеризации ……………………….. 11
1.3 Алгоритм FOREL и его программная реализация …………………. 14
§2. Задача коммивояжера ……………………………………………………………. 17
2.1 Методы решения задачи коммивояжера ………………………………. 19
2.2 Сравнительный анализ алгоритмов ……………………………………… 20
2.3 BV-метод …………………………………………………………………………… 25
2.4. Реализация BV-метода ………………………………………………………. 26
Заключение…………………………………………………………………………………. 27
Список литературы ………………………………………………………………………. 28
Приложение 1 ………………………………………………………………………………. 30
Приложение 2 ………………………………………………………………………………. 32
Приложение 3 ………………………………………………………………………………. 35

В декабре 2019 года в Китае была зарегистрирована первая вспышка
коронавируса, а 11 марта того же года Всемирная организация здравоохранения
объявила ее пандемией. Человечество борется с вирусом уже на протяжении
двух лет, и нельзя не отметить, как сильно он повлиял на нашу жизнь.
Чтобы помешать распространению вируса и обезопасить свой бизнес и
своих сотрудников, многие компании стали массово переходить на удалённую
работу, однако далеко не у всех есть такая возможность. Производственные
предприятия и заводы не могут работать в удаленном режиме, но если в данной
ситуации не предпринять необходимые меры, здоровье сотрудников будет
подвержено опасности, а значит и работа самого предприятия попадает под
удар.
Одним из решений данной проблемы является организация пассажирских
перевозок для сотрудников компании. Это позволит в некоторой мере
изолировать предприятие, ограничивая пересечение сотрудников со
случайными людьми в общественном транспорте и на улицах города в час пик.
Постановка задачи
Необходимо как можно быстрее доставить всех сотрудников на
территорию предприятия с помощью имеющегося транспортного средства. В
силу того, что на предприятии может работать большое количество людей, и
некоторые из них могут жить рядом друг с другом, рациональным будет
решение собирать таких соседей в одной точке для оптимизации процесса.
Однако, как было сказано ранее, пандемия накладывает ограничения на
безопасное передвижение людей по городу. Поэтому описанные точки сбора
должны располагаться не дальше некоторого расстояния R от сотрудника,
«привязанного» к этой точке.
Решение поставленной задачи должно быть реализовано в виде
программы, способной кластеризовать адреса сотрудников и проложить через
все кластеры оптимальный маршрут, начало и конец которого – территория
предприятия.
Поставленную задачу разделим на две подзадачи: кластеризация адресов
и поиск оптимального маршрута.
В задачу кластеризации входит получение координат по адресам, анализ
алгоритмов кластеризации и выбор наиболее подходящего из них.
Задача маршрутизации в данном случае, по сути, представляет собой
задачу коммивояжера. Необходимо провести сравнительный анализ методов
решения задачи и реализовать один из них.

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

Заказать новую

Лучшие эксперты сервиса ждут твоего задания

от 5 000 ₽

Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям

    Нажимая на кнопку, я соглашаюсь на обработку персональных данных и с правилами пользования Платформой

    Хочешь уникальную работу?

    Больше 3 000 экспертов уже готовы начать работу над твоим проектом!

    Антон П. преподаватель, доцент
    4.8 (1033 отзыва)
    Занимаюсь написанием студенческих работ (дипломные работы, маг. диссертации). Участник международных конференций (экономика/менеджмент/юриспруденция). Постоянно публик... Читать все
    Занимаюсь написанием студенческих работ (дипломные работы, маг. диссертации). Участник международных конференций (экономика/менеджмент/юриспруденция). Постоянно публикуюсь, имею высокий индекс цитирования. Спикер.
    #Кандидатские #Магистерские
    1386 Выполненных работ
    Олег Н. Томский политехнический университет 2000, Инженерно-эконо...
    4.7 (96 отзывов)
    Здравствуйте! Опыт написания работ более 12 лет. За это время были успешно защищены более 2 500 написанных мною магистерских диссертаций, дипломов, курсовых работ. Явл... Читать все
    Здравствуйте! Опыт написания работ более 12 лет. За это время были успешно защищены более 2 500 написанных мною магистерских диссертаций, дипломов, курсовых работ. Являюсь действующим преподавателем одного из ВУЗов.
    #Кандидатские #Магистерские
    177 Выполненных работ
    Юлия К. ЮУрГУ (НИУ), г. Челябинск 2017, Институт естественных и т...
    5 (49 отзывов)
    Образование: ЮУрГУ (НИУ), Лингвистический центр, 2016 г. - диплом переводчика с английского языка (дополнительное образование); ЮУрГУ (НИУ), г. Челябинск, 2017 г. - ин... Читать все
    Образование: ЮУрГУ (НИУ), Лингвистический центр, 2016 г. - диплом переводчика с английского языка (дополнительное образование); ЮУрГУ (НИУ), г. Челябинск, 2017 г. - институт естественных и точных наук, защита диплома бакалавра по направлению элементоорганической химии; СПХФУ (СПХФА), 2020 г. - кафедра химической технологии, регулирование обращения лекарственных средств на фармацевтическом рынке, защита магистерской диссертации. При выполнении заказов на связи, отвечаю на все вопросы. Индивидуальный подход к каждому. Напишите - и мы договоримся!
    #Кандидатские #Магистерские
    55 Выполненных работ
    Татьяна Б.
    4.6 (92 отзыва)
    Добрый день, работаю в сфере написания студенческих работ более 7 лет. Всегда довожу своих студентов до защиты с хорошими и отличными баллами (дипломы, магистерские ди... Читать все
    Добрый день, работаю в сфере написания студенческих работ более 7 лет. Всегда довожу своих студентов до защиты с хорошими и отличными баллами (дипломы, магистерские диссертации, курсовые работы средний балл - 4,5). Всегда на связи!
    #Кандидатские #Магистерские
    138 Выполненных работ
    Евгения Р.
    5 (188 отзывов)
    Мой опыт в написании работ - 9 лет. Я специализируюсь на написании курсовых работ, ВКР и магистерских диссертаций, также пишу научные статьи, провожу исследования и со... Читать все
    Мой опыт в написании работ - 9 лет. Я специализируюсь на написании курсовых работ, ВКР и магистерских диссертаций, также пишу научные статьи, провожу исследования и создаю красивые презентации. Сопровождаю работы до сдачи, на связи 24/7 ?
    #Кандидатские #Магистерские
    359 Выполненных работ
    Анна К. ТГПУ им.ЛН.Толстого 2010, ФИСиГН, выпускник
    4.6 (30 отзывов)
    Я научный сотрудник федерального музея. Подрабатываю написанием студенческих работ уже 7 лет. 3 года назад начала писать диссертации. Работала на фирмы, а так же помог... Читать все
    Я научный сотрудник федерального музея. Подрабатываю написанием студенческих работ уже 7 лет. 3 года назад начала писать диссертации. Работала на фирмы, а так же помогала студентам, вышедшим на меня по рекомендации.
    #Кандидатские #Магистерские
    37 Выполненных работ
    Мария М. УГНТУ 2017, ТФ, преподаватель
    5 (14 отзывов)
    Имею 3 высших образования в сфере Экологии и техносферной безопасности (бакалавриат, магистратура, аспирантура), работаю на кафедре экологии одного из опорных ВУЗов РФ... Читать все
    Имею 3 высших образования в сфере Экологии и техносферной безопасности (бакалавриат, магистратура, аспирантура), работаю на кафедре экологии одного из опорных ВУЗов РФ. Большой опыт в написании курсовых, дипломов, диссертаций.
    #Кандидатские #Магистерские
    27 Выполненных работ
    Дмитрий М. БГАТУ 2001, электрификации, выпускник
    4.8 (17 отзывов)
    Помогаю с выполнением курсовых проектов и контрольных работ по электроснабжению, электроосвещению, электрическим машинам, электротехнике. Занимался наукой, писал стать... Читать все
    Помогаю с выполнением курсовых проектов и контрольных работ по электроснабжению, электроосвещению, электрическим машинам, электротехнике. Занимался наукой, писал статьи, патенты, кандидатскую диссертацию, преподавал. Занимаюсь этим с 2003.
    #Кандидатские #Магистерские
    19 Выполненных работ
    Анастасия Б.
    5 (145 отзывов)
    Опыт в написании студенческих работ (дипломные работы, магистерские диссертации, повышение уникальности текста, курсовые работы, научные статьи и т.д.) по экономическо... Читать все
    Опыт в написании студенческих работ (дипломные работы, магистерские диссертации, повышение уникальности текста, курсовые работы, научные статьи и т.д.) по экономическому и гуманитарному направлениях свыше 8 лет на различных площадках.
    #Кандидатские #Магистерские
    224 Выполненных работы

    Другие учебные работы по предмету

    Кооперативные игры на гиперграфах
    📅 2019год
    🏢 Санкт-Петербургский государственный университет