title: ÐÐ¾ÑÑÑÐ¾ÐµÐ½Ð¸Ðµ Ð³Ð¸Ð±ÐºÐ¸Ñ Ð¼Ð°ÑÑÑÑÑÐ¾Ð² Ð² Ð´Ð¸Ð½Ð°Ð¼Ð¸ÑÐµÑÐºÐ¾Ð¹ ÑÑÐ°Ð½ÑÐ¿Ð¾ÑÑÐ½Ð¾Ð¹ ÑÐµÑÐ¸ Ñ ÑÑÐµÑÐ¾Ð¼ Ð³ÑÑÐ·Ð¾Ð¿Ð¾Ð´ÑÐµÐ¼Ð½Ð¾ÑÑÐ¸ ÑÑÐ°Ð½ÑÐ¿Ð¾ÑÑÐ½Ð¾Ð³Ð¾ ÑÑÐµÐ´ÑÑÐ²Ð°
title: Ð²ÑÐ¿ÑÑÐºÐ½Ð°Ñ ÐºÐ²Ð°Ð»Ð¸ÑÐ¸ÐºÐ°ÑÐ¸Ð¾Ð½Ð½Ð°Ñ ÑÐ°Ð±Ð¾ÑÐ° Ð±Ð°ÐºÐ°Ð»Ð°Ð²ÑÐ°
titleType: Subtitle
title: Building flexible routes in a dynamic transport network, taking into account the carrying capacity of the vehicle
Creators: name: Ð¤Ð¸Ð»Ð¸Ð¿Ð¿Ð¾Ð²Ð°, ÐÐ»ÐµÐ½Ð°
Publisher: name: Ð¡Ð°Ð½ÐºÑ-ÐÐµÑÐµÑÐ±ÑÑÐ³ÑÐºÐ¸Ð¹ Ð¿Ð¾Ð»Ð¸ÑÐµÑÐ½Ð¸ÑÐµÑÐºÐ¸Ð¹ ÑÐ½Ð¸Ð²ÐµÑÑÐ¸ÑÐµÑ ÐÐµÑÑÐ° ÐÐµÐ»Ð¸ÐºÐ¾Ð³Ð¾
Year: 2020
Subjects: Ð´Ð¸Ð½Ð°Ð¼Ð¸ÑÐµÑÐºÐ°Ñ ÑÑÐ°Ð½ÑÐ¿Ð¾ÑÑÐ½Ð°Ñ Ð·Ð°Ð´Ð°ÑÐ°
Ð´Ð¾ÑÐ¾Ð¶Ð½Ð°Ñ ÑÐµÑÑ
Ð³Ð¸Ð±ÐºÐ¸Ð¹ Ð¼Ð°ÑÑÑÑÑ
Ð³ÑÑÐ·Ð¾Ð¿Ð¾Ð´ÑÐµÐ¼Ð½Ð¾ÑÑÑ
ÐºÐ»Ð°ÑÑÐµÑÐ¸Ð·Ð°ÑÐ¸Ñ Ð³ÑÐ°ÑÐ°
dynamic vehicle routing problem
transport network
flexible route
carrying
graph clustering

description: Ð¢ÐµÐ¼Ð° Ð²ÑÐ¿ÑÑÐºÐ½Ð¾Ð¹ ÐºÐ²Ð°Ð»Ð¸ÑÐ¸ÐºÐ°ÑÐ¸Ð¾Ð½Ð½Ð¾Ð¹ ÑÐ°Ð±Ð¾ÑÑ: Â«ÐÐ¾ÑÑÑÐ¾ÐµÐ½Ð¸Ðµ Ð³Ð¸Ð±ÐºÐ¸Ñ Ð¼Ð°ÑÑÑÑÑÐ¾Ð² Ð² Ð´Ð¸Ð½Ð°Ð¼Ð¸ÑÐµÑÐºÐ¾Ð¹ ÑÑÐ°Ð½ÑÐ¿Ð¾ÑÑÐ½Ð¾Ð¹ ÑÐµÑÐ¸ Ñ ÑÑÐµÑÐ¾Ð¼ Ð³ÑÑÐ·Ð¾Ð¿Ð¾Ð´ÑÐµÐ¼Ð½Ð¾ÑÑÐ¸ ÑÑÐ°Ð½ÑÐ¿Ð¾ÑÑÐ½Ð¾Ð³Ð¾ ÑÑÐµÐ´ÑÑÐ²Ð°Â». ÐÑÐµÐ´Ð¼ÐµÑÐ¾Ð¼ Ð¸ÑÑÐ»ÐµÐ´Ð¾Ð²Ð°Ð½Ð¸Ñ ÑÐ²Ð»ÑÐµÑÑÑ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼ Ð¿Ð¾ÑÑÑÐ¾ÐµÐ½Ð¸Ñ Ð¼Ð°ÑÑÑÑÑÐ° Ð² Ð´Ð¸Ð½Ð°Ð¼Ð¸ÑÐµÑÐºÐ¾Ð¹ ÑÑÐ°Ð½ÑÐ¿Ð¾ÑÑÐ½Ð¾Ð¹ ÑÐµÑÐ¸, Ð° ÑÐµÐ»ÑÑ â Ð¿Ð¾ÑÑÑÐ¾ÐµÐ½Ð¸Ðµ Ð³Ð¸Ð±ÐºÐ¸Ñ Ð¼Ð°ÑÑÑÑÑÐ¾Ð² Ð² Ð´Ð¸Ð½Ð°Ð¼Ð¸ÑÐµÑÐºÐ¾Ð¹ ÑÑÐ°Ð½ÑÐ¿Ð¾ÑÑÐ½Ð¾Ð¹ ÑÐµÑÐ¸ Ð´Ð»Ñ n ÑÑÐ°Ð½ÑÐ¿Ð¾ÑÑÐ½ÑÑ ÑÑÐµÐ´ÑÑÐ² Ñ Ð¾Ð³ÑÐ°Ð½Ð¸ÑÐµÐ½Ð½Ð¾Ð¹ Ð³ÑÑÐ·Ð¾Ð¿Ð¾Ð´ÑÐµÐ¼Ð½Ð¾ÑÑÑÑ ÑÐ°Ðº, ÑÑÐ¾Ð±Ñ Ð¿Ð¾ÐºÑÑÑÑ Ð¼Ð°ÐºÑÐ¸Ð¼Ð°Ð»ÑÐ½Ð¾Ðµ ÐºÐ¾Ð»Ð¸ÑÐµÑÑÐ²Ð¾ Ð·Ð°ÑÐ²Ð¾Ðº Ð·Ð° Ð·Ð°Ð´Ð°Ð½Ð½Ð¾Ðµ Ð²ÑÐµÐ¼Ñ Ð¿ÑÐ¸ ÑÑÐ»Ð¾Ð²Ð¸Ð¸, ÑÑÐ¾ Ð·Ð°ÑÐ²ÐºÐ¸ Ð¿Ð¾ÑÐ²Ð»ÑÑÑÑÑ ÑÐ»ÑÑÐ°Ð¹Ð½Ð¾ Ð¿ÑÐ¸ Ð¿ÑÐ¾ÑÐ¾Ð¶Ð´ÐµÐ½Ð¸Ð¸ Ð¼Ð°ÑÑÑÑÑÐ°. Ð ÑÐ°Ð±Ð¾ÑÐµ Ð¸ÑÐ¿Ð¾Ð»ÑÐ·Ð¾Ð²Ð°Ð»Ð¸ÑÑ Ð¼ÐµÑÐ¾Ð´Ñ Ð¼Ð°ÑÐµÐ¼Ð°ÑÐ¸ÑÐµÑÐºÐ¾Ð³Ð¾ Ð¼Ð¾Ð´ÐµÐ»Ð¸ÑÐ¾Ð²Ð°Ð½Ð¸Ñ, Ð¼Ð°ÑÐµÐ¼Ð°ÑÐ¸ÑÐµÑÐºÐ¾Ð¹ ÑÑÐ°ÑÐ¸ÑÑÐ¸ÐºÐ¸, ÑÐ»ÐµÐ¼ÐµÐ½ÑÑ ÑÐµÐ¾ÑÐ¸Ð¸ Ð³ÑÐ°ÑÐ¾Ð² Ð¸ Ð¾Ð±ÑÐµÐºÑÐ½Ð¾-Ð¾ÑÐ¸ÐµÐ½ÑÐ¸ÑÐ¾Ð²Ð°Ð½Ð½Ð¾Ð³Ð¾ Ð¿ÑÐ¾Ð³ÑÐ°Ð¼Ð¼Ð¸ÑÐ¾Ð²Ð°Ð½Ð¸Ñ. ÐÑÐ» ÑÐ°Ð·ÑÐ°Ð±Ð¾ÑÐ°Ð½ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼ ÑÐµÑÐµÐ½Ð¸Ñ Ð·Ð°Ð´Ð°ÑÐ¸ Ð½Ð° ÑÐ·ÑÐºÐµ JAVA Ð½Ð° Ð±Ð°Ð·Ðµ Ð´Ð²ÑÑÑÐ°Ð·Ð½Ð¾Ð³Ð¾ (ÐºÐ»Ð°ÑÑÐµÑÐ½Ð¾Ð³Ð¾) Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð°. ÐÐ»Ñ ÐºÐ»Ð°ÑÑÐµÑÐ¸Ð·Ð°ÑÐ¸Ð¸ Ð¸ÑÐ¿Ð¾Ð»ÑÐ·Ð¾Ð²Ð°Ð»Ð°ÑÑ Ð¼Ð¾Ð´Ð¸ÑÐ¸ÐºÐ°ÑÐ¸Ñ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð° ÑÐ±Ð°Ð»Ð°Ð½ÑÐ¸ÑÐ¾Ð²Ð°Ð½Ð½Ð¾Ð³Ð¾ Ð´Ð¸ÑÐ¾ÑÐ¾Ð¼Ð¸ÑÐµÑÐºÐ¾Ð³Ð¾ Ð´ÐµÐ»ÐµÐ½Ð¸Ñ Ð²ÐµÑÑÐ¸Ð½, Ð¿Ð¾ÑÑÑÐ¾ÐµÐ½Ð¸Ðµ Ð¼Ð°ÑÑÑÑÑÐ¾Ð² Ð¿ÑÐ¾Ð¸Ð·Ð²Ð¾Ð´Ð¸Ð»Ð¾ÑÑ Ñ Ð¿ÑÐ¸Ð¼ÐµÐ½ÐµÐ½Ð¸ÐµÐ¼ ÑÐ²ÑÐ¸ÑÑÐ¸ÐºÐ¸ Ð±Ð»Ð¸Ð¶Ð°Ð¹ÑÐµÐ³Ð¾ ÑÐ¾ÑÐµÐ´Ð°, Ð° Ð¿Ð¾Ð¸ÑÐº Ð¼Ð°ÑÑÑÑÑÐ° Ð¼ÐµÐ¶Ð´Ñ Ð´Ð²ÑÐ¼Ñ Ð²ÐµÑÑÐ¸Ð½Ð°Ð¼Ð¸ Ð¾ÑÑÑÐµÑÑÐ²Ð»ÑÐ»ÑÑ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ð¾Ð¼ Astar. Ð ÐµÑÐµÐ½Ð¸Ðµ Ð¿Ð¾ÑÑÐ°Ð²Ð»ÐµÐ½Ð½Ð¾Ð¹ Ð·Ð°Ð´Ð°ÑÐ¸ Ð¿Ð¾Ð·Ð²Ð¾Ð»ÑÐµÑ Ð¾Ð¿ÑÐ¸Ð¼Ð¸Ð·Ð¸ÑÐ¾Ð²Ð°ÑÑ ÑÐ¾ÑÑÐ°Ð²Ð»ÐµÐ½Ð¸Ðµ Ð¼Ð°ÑÑÑÑÑÐ¾Ð² ÑÐ°Ð·Ð²Ð¾Ð·ÐºÐ¸ Ð¿Ð°ÑÑÐ°Ð¶Ð¸ÑÐ¾Ð² Ð¸Ð· Ð¾ÑÐ³Ð°Ð½Ð¸Ð·Ð°ÑÐ¸Ð¸, Ð´Ð¾ÑÑÐ°Ð²ÐºÐ¸ ÑÐ¾Ð²Ð°ÑÐ¾Ð² ÑÐ¾ ÑÐºÐ»Ð°Ð´Ð° Ð¿Ð¾ ÑÐ¾ÑÐ³Ð¾Ð²ÑÐ¼ ÑÐ¾ÑÐºÐ°Ð¼Ð¸ Ð¸Ð»Ð¸ Ð¾Ð±ÑÐ»ÑÐ¶Ð¸Ð²Ð°Ð½Ð¸Ðµ ÑÐ»ÐµÐºÑÑÐ¸ÑÐµÑÐºÐ¸Ñ ÑÐ°Ð¼Ð¾ÐºÐ°ÑÐ¾Ð². Ð­ÐºÑÐ¿ÐµÑÐ¸Ð¼ÐµÐ½ÑÑ Ð¿ÑÐ¾Ð²Ð¾Ð´Ð¸Ð»Ð¸ÑÑ Ð½Ð° Ð´Ð¾ÑÐ¾Ð¶Ð½Ð¾Ð¹ ÑÐµÑÐ¸ Ð³Ð¾ÑÐ¾Ð´Ð° Ð¡Ð°Ð½ÐºÑ-ÐÐµÑÐµÑÐ±ÑÑÐ³.
description: 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.