Details

Title: Построение гибких маршрутов в динамической транспортной сети с учетом грузоподъемности транспортного средства: выпускная квалификационная работа бакалавра: направление 02.03.01 «Математика и компьютерные науки» ; образовательная программа 02.03.01_01 «Вычислительные, программные, информационные системы и компьютерные технологии»
Creators: Филиппова Елена Ивановна
Scientific adviser: Курочкин Леонид Михайлович
Other creators: Голубева Ирина Эрнестовна; Востров Алексей Владимирович
Organization: Санкт-Петербургский политехнический университет Петра Великого. Институт прикладной математики и механики
Imprint: Санкт-Петербург, 2020
Collection: Выпускные квалификационные работы; Общая коллекция
Subjects: динамическая транспортная задача; дорожная сеть; гибкий маршрут; грузоподъемность; кластеризация графа; dynamic vehicle routing problem; transport network; flexible route; carrying; graph clustering
Document type: Bachelor graduation qualification work
File type: PDF
Language: Russian
Speciality code (FGOS): 02.03.01
Speciality group (FGOS): 020000 - Компьютерные и информационные науки
Links: Отзыв руководителя; Отчет о проверке на объем и корректность внешних заимствований
DOI: 10.18720/SPBPU/3/2020/vr/vr20-3805
Rights: Доступ по паролю из сети Интернет (чтение, печать, копирование)

Allowed Actions:

Action 'Read' will be available if you login or access site from another network Action 'Download' will be available if you login or access site from another network

Group: Anonymous

Network: Internet

Annotation

Тема выпускной квалификационной работы: «Построение гибких маршрутов в динамической транспортной сети с учетом грузоподъемности транспортного средства». Предметом исследования является алгоритм построения маршрута в динамической транспортной сети, а целью – построение гибких маршрутов в динамической транспортной сети для 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.

Document access rights

Network User group Action
ILC SPbPU Local Network All Read Print Download
Internet Authorized users SPbPU Read Print Download
Internet Authorized users (not from SPbPU)
-> Internet Anonymous

Table of Contents

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

Usage statistics

stat Access count: 10
Last 30 days: 6
Detailed usage statistics