ADDITIONAL CONSTRAINTS IN THE VEHICLE ROUTING PROBLEM

ABSTRACT

The paper considers the vehicle routing problem (VRP) in the presence of additional restrictions, such as carrying capacity and kind of transport, time windows, a ban on traffic in urban areas, etc. We describe accounting method such restrictions when solving VRP using a genetic algorithm with a preliminary clustering of delivery points into geographic areas. The presented algorithm is implemented in the automation system of transport logistics Zig-Zag, examples of solving specific practical problems are shown.

АННОТАЦИЯ

В работе рассматривается задача маршрутизации транспортных средств (VRP) при наличие дополнительных ограничений, таких как грузоподъемность и вид  транспорта, временные окна, запрет на движение в районах городской застройки и т. д. Описан способ учета таких ограничений при решении VRP с помощью генетического алгоритма с предварительной кластеризацией пунктов доставки на географические районы. Представленный алгоритм реализован в системе автоматизации транспортной логистики «Zig-Zag», показаны примеры решения конкретных практических задач.

Keywords: vehicle routing problem, time windows, vehicle capacity, genetic algorithm, k-means, speed factor heat map,  cargo frame of road network.

Ключевые слова: маршрутизация транспортных средств, временные окна, грузоподъемность транспорта, генетический алгоритм, k-means, тепловая карта коэффициента скорости,  грузовой каркас

Introduction. There are many different models of transport logistics: the traveling salesman problem, the Monge–Kantorovich transportation problem, the vehicle routing problem, etc. Currently, there are quite effective methods for solving some of them in the simplest formulation. Some, like TSP or VRP, belong to the class of NP-hard problems, and even with a small number of points can not be solved by a complete search in a reasonable time. Therefore, approximate methods and heuristics are used to solve them [1], and one of the best algorithms for solving the metric traveling salesman problem is Concorde [2, 3]. However, the more complex the real problem and the closer the used model is to it, the more there are additional constraints that need to be considered. Such restrictions are associated with the availability of a certain fleet of vehicles, their carrying capacity, the schedule of customers and the desired delivery time, restrictions of movement of trucks in residential areas, multi-depot.

Large companies often have to solve routing problems in which there are tens to hundreds of vehicles and couriers and thousands of delivery points. This paper presents the algorithm that is used in automation system of transport logistics Zig-Zag, which allows you to successfully solve the problem of routing vehicles with a different set of restrictions in a reasonable time, while minimizing the total length of routes, their duration or total cash costs for the delivery of cargo.

VRP solution algorithm. Additional restrictions determine the specific type of routing problem [4] and significantly complicate its solution.  When the constraints are violated, penalty is added to the objective function, as a result of this, in general, the objective function becomes complex and multi-extreme. This fact makes it impossible to directly apply gradient methods to minimize it. The most suitable method for solving such problems is a genetic algorithm [4–6] with the appropriate implementation of genetic mutation and selection operators [7, 8], which allows to take into account the limitations and ensure searching for a global conditional minimum. The only significant disadvantage of genetic algorithms is with an increase in the dimension of the problem leads to a multiple increase in its computational complexity. A common solution to this problem is to apply the well-known "divide and conquer" principle to reduce the original problem to several independent subtasks of smaller dimension. To this end, the Zig-Zag system uses the k-means method to pre-cluster delivery points. Because the k-means method does not guarantee that the resulting clusters will be balanced against the number of delivery points, the total area, or traversal time, cluster balancing is further evaluated during the clustering process, and if the clusters are not sufficiently uniform, they are adjusted by redistributing boundary points. As a result, geographic areas are formed that determine the delivery points for each individual courier. After that, using a genetic algorithm, independent optimization problems obtained for each courier separately are solved in parallel.

To solve vehicle routing problems, it is necessary to take into account that the traffic speed on a given road section depends on factors affecting the roads congestion: time of day, day of the week, weather conditions, etc. For this, the routing algorithm uses heat maps of the speed factor, allowing us to adjust the regulated speed values on each route section. The speed factor is the coefficient of proportionality between the maximum permitted speed on a selected section of road and the actual speed of traffic flow in each specific time interval. For example, in Moscow, in some sections of the Third Transport Ring, the maximum permitted speed is 60 km/h, while the real traffic speed on the same sections of the road in the evening can be less than 20-30 km/h. Thus, the speed factor for this section in the evening will be equal to the ratio of the real speed to the maximum, i.e. 0.3-0.5.

A heat map can be obtained both by the expert method and as a result of statistical processing of the accumulated data. The Zig-Zag system uses both approaches.

Taking into account the dependence of urban traffic on the time of day, 4 time zones were allocated: "night hours" (from 19:00 to 08:00), "morning rush hour" (from 08:00 to 10:00), "daytime hours" (from 10:00 to 17:00), and "evening rush hour" (from 17:00 to 19:00). The heat map for each time zone is a matrix, the elements of which determine the speed factors on specific transport network roads sections.

The algorithm for calculating heat maps and recalculating the transport speed depending on its type and time of day is as follows.

Split the day on Nt discrete time intervals

,

and the urban transport network G on the Nz geographic zones

.

Let be many possible types of vehicles and be the sets of delivery points for each vehicle.

Suppose you know the distance matrix between each pair of vertices of the road graph obtained for an ideal situation on the roads with no traffic jams  and the corresponding time matrix is . Then the matrix of the speed of the transport flow under ideal conditions can be obtained as:

.

To take into account the possibility of traffic congestion and their impact on the solution to the routing problem a global coefficient  set by the expert method was introduced.

To determine the speed, depending on the type of transport, we introduce coefficients  where foot, car, hgv denote foot, road, truck transport, respectively. We will also introduce the speed factors  obtained by the expert method for transitions between different geographic zones.

Then the desired real speed matrices will be calculated according to the following formula

.

An interpolation algorithm is used for smoothly speed changing during the transition between time intervals, Heat maps of speed factors are matrices of  values defined for each time interval and for each section of the roads of the transport network.

In the Zig-Zag system, heat maps are continuously learning on accumulated statistics and open data from other systems, for example, Yandex.

Additional constraints. The main types of constraints in vehicle routing problems, which can be taken into account in the automation system of transport logistics Zig-Zag is as below.

Vehicle capacity. If the total cargo weight in the selected region exceeds the carrying capacity of the vehicle, the driver is forced to return to the depot for a new consignment of cargo during the delivery process. In this case, the distance or time of movement from the last point to the depot and back is additionally added to the objective function, depending on its type. Such a penalty makes unnecessary returns to the depot not profitable.

Vehicles start from the depot and, finally, return to the depot. This condition can be taken into account as follows. Each individual of the genetic algorithm is a traversal sequence of the route points, in which the starting and ending points are depots, and further, when applying the operators of crossover and mutation, the starting and ending points do not change. When calculating a fitness-function, the need to return to the depot is included by adding the appropriate time or distance to it, depending on the using optimization criterion.

Type of vehicle or pedestrian (bicycle) couriers. Quite often there are tasks when the weight of the delivered cargo is not large, the delivery points are within walking distance, and the use of vehicles is inefficient. In such cases, it is necessary to be able to select a foot courier to serve the relevant geographical area. An example of solving the problem with 3 couriers, one of which is on foot (bicycle), and 44 delivery points in the conditions of the road network of Nizhny Novgorod, is presented in Fig. 1.

Figure. 1. The result of solving the routing problem with a foot courier.

A foot courier has the ability to move almost arbitrarily, and not only on roads, so his route is not marked on the map, only the traversal order is shown. The routing sheets corresponding to each courier are presented in tables 1 to 3.

Table 1.

Courier №1 route sheet (car)

Table 2

Courier №2 route sheet (car)

Table 3.

Courier №2 route sheet (on foot)

Due to the fact that courier No. 3 is a foot courier (bicycle) and has the ability to move almost arbitrarily, the assessment of the duration and length of its route is an overestimated (table 3). However, it is logical that in accordance with the received solution, its route is the shortest. When comparing all three route sheets, it is clear that, despite the different delivery methods, they all have approximately the same shift duration of no more than 4-5 hours.

Time windows. The constraint related with the delivery point working hours or the preferences of the client is also often.  In this case, they talk about VRP with time windows, and the penalty added to the objective function is the courier waiting duration after the arrival of the time when delivery becomes possible. Otherwise, the solution is no different from the solution of the classic VRP.

Freight frame of the road network. In many cities, in order to reduce noise and air pollution, reduce the number of accidents and improve traffic in residential areas, the movement of trucks in residential areas is limited, which must be taken into account when planning routes. In particular, a freight frame (Fig. 2) has been introduced in Moscow, consisting of roads on which free movement of freight transport is allowed. Along with it there is a residential area, the movement of trucks in which is limited, and the passage of trucks with a permissible maximum weight of more than 2.5 tons is allowed only for servicing enterprises or residents within the area, but for this it is necessary to have the appropriate permits.

Figure 2. The current freight frame of Moscow roads

The road network of the city is additionally marked in order for the algorithm to take into account the possibility of specific vehicles movement on selected roads. When calculating the objective function in the process of operation of the genetic algorithm, it is assumed that the condition of impossibility of movement in a certain section is mathematically equivalent to the infinite transition time between the two corresponding vertices of the road graph. Thus, impossible routes correspond to an infinitely large fitness-function value, as a result of which they will be automatically excluded when searching for a global minimum.

An example of a task in which part of the cargo is delivered by truck is shown in Fig. 3. In this task there are 3 vehicles, one of which is cargo, and 45 delivery points.

Figure 3. The result of solving the routing problem with the constraints on the trucks movement on Moscow roads

The comparison Fig. 2 and Fig. 3 shows that the truck movement takes place on the marked roads of the freight frame in Moscow. See also in Fig. 3 clearly shows that the pre-clustering of delivery points made it possible to divide the entire initial set of points into approximately identical non-overlapping geographical areas, thereby significantly simplifying and accelerating the task of constructing optimal routes.

Conclusion. The approach presented in the paper showed that a genetic algorithm can not only effectively solve multi-extreme optimization problems, but also allows you to naturally include additional constraints in VRP, without requiring their strict mathematical formalization. Due to the complexity of the city's transport system, the peculiarities of the operation of delivery points and the possibility of force majeure (accidents, a sudden change in weather conditions), the error in assessing routes according to such an algorithm may be inconsistent. However, even taking this into account, the average error in determining the speed of the traffic flow does not exceed 10%, and in 80% of cases the time deviations from the planned routes are less than 5 minutes. This algorithm is implemented in the automation system of transport logistics Zig-Zag and allows you to simultaneously solve problems for several customers at once with hundreds of vehicles and foot couriers, as well as thousands of delivery points in a reasonable time. So the average time to solve the routing problem for 20 vehicles and 1000 delivery points is less than 5 minutes. A full description of the Zig-Zag system and its functionality is presented in [9].

References:

1. Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.
2. Applegate, D.L., Bixby, R.B., Chav´atal, V., and Cook, W.J. The Traveling Salesman Problem: A Computational Study. Princeton University Press, 2006.
3. Pouya Baniasadi, Vladimir Ejov, Michael Haythorpe, and Serguei Rossomakhine. A new benchmark set for Traveling salesman problem and Hamiltonian cycle problem. 2018.
4. Barkaoui M., Gendreau M. An adaptive evolutionary approach for real-time vehicle routing and dispatching. Computers & Operations Research, 2013, vol. 40, no. 7, pp. 1766-1776. DOI: 10.1016/j.cor.2013. 01.022.
5. Xu H., Duan F.Y., Pu P. Solving dynamic vehicle routing problem using enhanced genetic algorithm with penalty factors. Int. J. of Performability Eng., 2018, vol. 14, no. 4, pp. 611-620. DOI: 10.23940/ijpe.18.04. p3.611620.
6. Sabar N.R., Bhaskar A., Chung E., Turky A., Song A. A self-adaptive evolutionary algorithm for dynamic vehicle routing problems with traffic congestion. Swarm and Evolutionary Computation, 2019, vol. 44, pp. 1018-1027. DOI: 10.1016/j.swevo.2018.10.015.
7. Abdoun Otman, Jaafar Abouchabaka, Chakir Tajani. Analyzing the Performance of Mutation Operators to Solve the Travelling Salesman Problem. Int. J. Emerg. Sci.. 2. 2012.
8. Batishchev D. I., Neymark Ye. A., Starostin N. V. Primeneniye geneticheskikh algoritmov k resheniyu zadach diskretnoy optimizatsii [Application of genetic algorithms to solving discrete optimization problems]. Nizhny Novgorod, 2007, 88 p. (in Russ.).
9. Zig-Zag is a service for optimizing transport logistics. URL: https://zig-zag.org/.