Детальная информация

Название: Построение гибких маршрутов в динамической транспортной сети с учетом грузоподъемности транспортного средства: выпускная квалификационная работа бакалавра: направление 02.03.01 «Математика и компьютерные науки» ; образовательная программа 02.03.01_01 «Вычислительные, программные, информационные системы и компьютерные технологии»
Авторы: Филиппова Елена Ивановна
Научный руководитель: Курочкин Леонид Михайлович
Другие авторы: Голубева Ирина Эрнестовна; Востров Алексей Владимирович
Организация: Санкт-Петербургский политехнический университет Петра Великого. Институт прикладной математики и механики
Выходные сведения: Санкт-Петербург, 2020
Коллекция: Выпускные квалификационные работы; Общая коллекция
Тематика: динамическая транспортная задача; дорожная сеть; гибкий маршрут; грузоподъемность; кластеризация графа; dynamic vehicle routing problem; transport network; flexible route; carrying; graph clustering
Тип документа: Выпускная квалификационная работа бакалавра
Тип файла: PDF
Язык: Русский
Код специальности ФГОС: 02.03.01
Группа специальностей ФГОС: 020000 - Компьютерные и информационные науки
Ссылки: Отзыв руководителя; Отчет о проверке на объем и корректность внешних заимствований
DOI: 10.18720/SPBPU/3/2020/vr/vr20-3805
Права доступа: Доступ по паролю из сети Интернет (чтение, печать, копирование)

Разрешенные действия:

Действие 'Прочитать' будет доступно, если вы выполните вход в систему или будете работать с сайтом на компьютере в другой сети Действие 'Загрузить' будет доступно, если вы выполните вход в систему или будете работать с сайтом на компьютере в другой сети

Группа: Анонимные пользователи

Сеть: Интернет

Аннотация

Тема выпускной квалификационной работы: «Построение гибких маршрутов в динамической транспортной сети с учетом грузоподъемности транспортного средства». Предметом исследования является алгоритм построения маршрута в динамической транспортной сети, а целью – построение гибких маршрутов в динамической транспортной сети для n транспортных средств с ограниченной грузоподъемностью так, чтобы покрыть максимальное количество заявок за заданное время при условии, что заявки появляются случайно при прохождении маршрута. В работе использовались методы математического моделирования, математической статистики, элементы теории графов и объектно-ориентированного программирования. Был разработан алгоритм решения задачи на языке JAVA на базе двухфазного (кластерного) алгоритма. Для кластеризации использовалась модификация алгоритма сбалансированного дихотомического деления вершин, построение маршрутов производилось с применением эвристики ближайшего соседа, а поиск маршрута между двумя вершинами осуществлялся алгоритмом Astar. Решение поставленной задачи позволяет оптимизировать составление маршрутов развозки пассажиров из организации, доставки товаров со склада по торговым точками или обслуживание электрических самокатов. Эксперименты проводились на дорожной сети города Санкт-Петербург.

The subject of the graduate qualification work is «Building flexible routes in a dynamic transport network, taking into account the carrying capacity of the vehicle». The subject of the research is an algorithm for building a route in a dynamic transport network, and the goal is to build flexible routes in a dynamic transport network for n vehicles with limited load capacity so as to cover the maximum number of requests for a given time, provided that requests appear randomly when passing the route. We used methods of mathematical modeling, mathematical statistics, elements of graph theory and object-oriented programming. An algorithm for solving the problem in JAVA was developed based on a two-phase (cluster) algorithm. For clustering, a modification of the balanced dichotomous vertex division algorithm was used, routes were constructed using the nearest neighbor heuristic, and a route search between two vertices was performed using the Astar algorithm. The solution to this problem allows you to optimize the preparation of routes for transporting passengers from the organization, delivering goods from a warehouse to retail outlets, or servicing electric scooters. The experiments were carried out on the road network of the city of Saint Petersburg.

Права на использование объекта хранения

Место доступа Группа пользователей Действие
Локальная сеть ИБК СПбПУ Все Прочитать Печать Загрузить
Интернет Авторизованные пользователи СПбПУ Прочитать Печать Загрузить
Интернет Авторизованные пользователи (не СПбПУ)
-> Интернет Анонимные пользователи

Оглавление

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

Статистика использования

stat Количество обращений: 4
За последние 30 дней: 0
Подробная статистика