Development of an optimal route algorithm based on separable criteria: distance and time

Аннотация

This paper considers the problem of finding the shortest paths between all vertices of a weighted undirected sparse graph. A “graph disassembly and reassembly” algorithm is proposed, which uses the solution of a problem on a low-dimensional graph to obtain a solution for the original graph. A comparison of the proposed algorithm with one of the fast classical algorithms on open access data is provided. The complexity of the original problem is notably reduced by the proposed algorithm such that it can be scaled to large networks. In addition to the sub-gradient Lagrangian multiplier updating strategy integrated with projection, a novel one based on the deep-cut ellipsoid method is proposed as well. 1 INTRODUCTION to the optimal one in a given range, so that the user can choose the most suitable one when making the Known for solving the problem are: the city's final choice. road network, the place of departure and the There are a number of implemented destination. It is necessary to select the optimal programs that allow you to search for the shortest route and all the routes close to it from the point of route along the road network on an electronic map departure to the destination, which take into account [1-5]. The considered systems use various criteria the real situation on the roads: possible traffic for the optimality of the path - from the criterion of congestion and options for bypassing it, delays in the shortest distance to complex criteria for front of traffic lights at intersections, different estimating time, taking into account information speeds of traffic on certain sections of the city’s road about traffic jams. The mentioned works mainly network. Time, distance traveled, etc. can serve as a consider algorithms for searching only the optimal criterion for choosing a route. In reality, the shortest path. Only in [6] an algorithm for searching K routes route in terms of distance is not always optimal in for deviation from the optimal one is described terms of time, fuel consumption, etc. It is very based on the optimal route passing through K difficult to reduce these criteria to one. Often the vertices of the graph. criterion for the optimality of a path is quite difficult to formalize. On the other hand, any mathematical Algorithm for solving. The algorithm for model does not take into account many external solving the problem consists of two stages. factors that influence the result, since the situation Determining the shortest travel route in time is on the road may change. Therefore, not only the reduced to solving the well-known problem of the optimal path is considered, but also all routes close shortest path on a directed graph. To solve it, a well- known algorithm is used, based on placing marks on nondeterministic polynomial label correcting the vertices of the graph [10]. To determine the set algorithm (discrete travel time distribution) for the of all routes close to the optimal, an algorithm is a priori path problem [16]. The adaptive path variant used. based on the method of sequential analysis of for a continuous link travel time distribution was options and the use of the rule for rejecting examined by Hall, who proposed a non-polynomial unpromising options before obtaining a final DP-based algorithm [17]. In addition, Miller-Hooks decision. proposed a label setting algorithm for the discrete version of the problem [18]. As a result of the As is known in Dijkstra's algorithm, to find absence of the Markovian property, finding LET the shortest path, temporary or permanent marks are paths on STV networks is computationally difficult assigned to the vertices of the graph. Labels define even with the assumption of independence [18]. for a vertex the upper bound on the length of the Reliability-based stochastic routing has been path from the vertex to the current one. The values studied primarily in the context of finding a priori of the temporary markings of the vertices gradually optimal paths. Frank in his seminal paper, proposed decrease. The marking value determines the an algorithm to compute the continuous probability possible length of the path from the initial to this distribution of the minimum travel time [19]. vertex. At each step of the algorithm, only one of However, shortest paths are identified through the marks with the minimum value at the level under paired comparisons within an already enumerated consideration is selected as a constant [11]. This path set. Nie and Wu introduced a concept of means that the label value is the length of the “locally reliable” paths and proposed a label shortest path from a vertex to the current vertex. correcting algorithm to compute the set of locally reliable paths (nondominated with respect to reliability at varying thresholds) for static 2 REVIEW OF LITERATURE THE independent link travel time distributions [20]. In contrast, the problem of computing an optimal Classical shortest path problem involves reliability strategy (polic