How we solved the problem of optimizing cargo delivery using numerical methods using the example of the simulated annealing method

In this article we would like to share our experience in implementing an algorithm for solving a routing problem based on the simulated annealing method in Norbit CDS, a smart delivery management system.

After analyzing the materials, you can discover various proposed methods for solving VRP problems (Vehicle Routing Problem). Their main goal is to plan routes for vehicles in the optimal way. The main criteria, as always, remain the shortest route for the vehicle and the delivery of services to all specified points. In the Norbit CDS logistics workplace, the task is no different.

When creating our algorithm for optimizing the construction of delivery routes, we proceeded from the following input data: the number of vehicles, the number of applications for distribution, taking into account their dimensions and windows of the desired delivery time. The annealing method was chosen for implementation.

Illustration generated by AI using the ruDALL-E Kandinsky service

Simulated Annealing Method

The annealing method is one of the most effective methods for randomly searching for an optimal solution for various problems consisting of finding such a state at which the minimum solution of some function is achieved . The main concepts of the simulated annealing method are:

,Where – the set of all states, A – initial state;

– system temperature at -th step, respectively – temperature at the initial state ;

– temperature change function;

– a function that causes a new state;

– probability function of accepting a new state ;

– a state in which the best solution has been achieved.

The algorithm of the method is as follows.

The initial state is formed ,,.
-th iteration of the algorithm:

Implementation of the simulated annealing method in Norbit CDS

Designations

Having considered the basic concepts of the method, let's move on to implementing the simulated annealing method in the Norbit CDS system.

For a more comfortable discussion, let's introduce some concepts.

– a list of vehicles for forming routes, where – the number of vehicles to solve the problem.

– list of generated routes, .

– a list of delivery requests, where– the number of delivery requests that need to be distributed among routes. Each there are attributes such as weight, expected delivery time (calculated depending on other requests in the route), delivery window specified by the client.

$T_{finish}$ – temperature value at which the algorithm for finding the best solution ends.

$C_{max}$ – maximum number of deliveries in one route.

DeliveryInfoMatrix – matrix M×Mcontaining information about the distance of delivery request points from each other.

The project is used to form the matrix OSRM API, written in C++ with open source and allowing you to build the shortest paths between points on the map. For our needs, we used the Route Service, which provides a response in the form of a Route object, which contains the path distance in meters and time in seconds for this path.

It is worth noting that the times indicated are average, since the OSRM API does not contain traffic forecast data. Figure 1 shows a visual view of the matrix being formed. For each intersection, two values are indicated – the distance in meters and the required time in seconds to get from one delivery point to another.

*Figure 1. Example of a delivery matrix*

$KPI_{du}(x)$ – optimization criterion responsible for the magnitude of delays in the delivery of applications along all generated routes in the state .

$KPI_{dist}(x)$ – optimization criterion responsible for the total value of the footage of all routes in the state .

$x_{best}$ – the main solution for optimization, that is, the best solution.

$F(x)=KPI_{du}(x)+KPI_{dist}(x)$ – function for which you need to find the state at which it will take the smallest value.

$h(F(x')-F(x),t_k) = \frac{KPI_{dist}(x)^*t_k}{KPI_{dist}(x')^*t_0}$ – probability of accepting a new state .

Algorithm

The input parameters of the implemented algorithm are: list of vehicleslist of applicationsinitial temperaturefinal temperature $T_{finish}$ and the maximum number of applications in one route $C_{max}$ . Before running the algorithm, the matrix is calculated DeliveryInfoMatrix.

The next step is the formation of the initial state. Vehicles receive applications on a first-come, first-served basis. In the cycle, the route is filled with applications by detecting the closest application in the matrix DeliveryInfoMatrix to the last point added to the route. For each route, the starting point is the warehouse point .

When adding an application, it is checked whether it can be placed in the vehicle. The following points are taken into account: whether it passes by weight, whether the route exceeds the maximum number of applications $C_{max}$ , and it is also recorded that the application has not been added to other routes previously. As soon as the first route is filled, the next one begins to fill up.

When formingthere is a possibility that some of the applications did not fit into the vehicles and remained unloaded. Unloaded applications are sent to the list $D_{unload}$ .

For each route, a parameter is calculated BeginDateTime – time by which the driver will deliver the first request. Next, the approximate delivery time is calculated for all requests on the route. After this we can calculate the criteria $KPI_{dist}(x_0)$ And $KPI_{du}(x_0)$ and write down the initial state as a temporary solution and the best solution $x_{best}$ .

Now let's look at the algorithm for -th iteration. First, a new solution state is generated using the function .

In state x, one request is randomly selected and removed from each route. This sample is mixed with requests that were previously undistributed along the routes $D_{unload}$ . This way we get a list of requests that we will work with in the current iteration.

We are trying to distribute each of the requests according to routes. The application is placed in the first available route that meets the conditions – it is processed according to the weight and number of applications in the route. The application is placed on the route based on calculations from which point of existing applications will be the fastest to reach it. This continues until all applications are unloaded. According to this algorithm, the first suitable route is not completely filled with applications. Filling occurs gradually in each of them. An example of filling is shown in Figure 2.

*Figure 2. Algorithm for filling a route with requests*

After all routes are completed, we obtain the following solution state and update the list of currently unallocated applications $D_{unload}$ . For calculate the criteria $KPI_{dist}(x')$ And $KPI_{du}(x')$ .

The next step is to decide whether it is suitable as . First of all, we check the criteria $KPI_{dist}(x')$ then already $KPI_{du}(x')$ to determine whether the current state is better than ours And $x_{best}$ decision states. If $KPI_{du}(x')<KPI_{du}(x)$ or $(KPI_{du}(x')=KPI_{du}(x)$ And $KPI_{dist}(x')<KPI_{dist}(x))$ That . If $KPI_{du}(x')<KPI_{du}(x_{best})$ or $(KPI_{du}(x')=KPI_{du}(x_{best})$ And $KPI_{dist}(x')<KPI_{dist}(x_{best}))$ That $x'→x_{best}$ . There is also a possibility that the state of the solution which is worse according to the criteria $KPI_{du}(x')$ And $KPI_{dist}(x')$ how $KPI_{du}(x)$ And $KPI_{dist}(x)$ may still become the next decision state to continue searching for the best option.

Function used to make transition decisions . The value is determined randomly [0,1)” alt=”α∈ [0,1)” src=”https://habrastorage.org/getpro/habr/upload_files/e16/3c2/8ac/e163c28acbbd643f21fc9f2583078b99.svg” width=”77″ height=”22″/>. Если , то в случае, если таких состояний решений на -тых итерациях было подряд меньше 50 раз, то так и быть . В случае, если давно не находилось состояния решения лучше (а именно 50 итераций подряд), то $x_{best}→x$ . Тем самым, мы повышаем шансы получить более выгодное состояние решения при следующей итерации, так как меняем , от которого ищутся видоизменённые варианты новых состояний решений.

После определения состояния решения по алгоритму метода отжига требуется перерасчет температуры . Для пересчета температуры используется формула как в Больцмановском отжиге:

$T_k=\frac{t_0}{ln(1+k)},k>0.$

Так итерации будут выполняться до того момента, пока $T_k>t_{finish}$ . В конце получаем лучшее состояние решения $x_{best}$ .

Чтобы повысить шансы по поиску самого оптимального состояния решения, данный алгоритм выполняется в двух параллельных потоках. После прогона из двух состояний решений выбирался вариант с лучшими показателями критериев $KPI_{du}$ и $KPI_{dist}$ .

После метод отжига применяется еще раз, но относительно маршрутов , составленных в лучшем состоянии решения $x_{best}$ . В ходе самого маршрута , permutations of delivery order points will be applied route and, accordingly, the best solution for visiting points will be assigned to the route . At this step we obtain our final solution state for the task $x_{best}$ .

Results of the method

Let's consider the results of the algorithm. Let us submit the following data to the input: 18 applications, located as follows in Figures 3, 4 vehicles, $t_0=120, t_{finish}=10.$

*Figure 3. Location of incoming requests*

The algorithm completed the task in 4 minutes 15 seconds, and 2 routes were generated. Figures 4 and 5 show the generated routes. Despite the fact that a larger number of vehicles was specified at the input, the required number is checked based on the volume and weight of delivery requests. Since according to our algorithm the maximum number of delivery requests in a vehicle is 11, the vehicles are calculated based on the formula $\frac{N}{11}$ Where – the number of possible cars. Next, if there are still available vehicles, a calculation is made based on the weight of applications in order to add an additional vehicle. This approach helps to avoid half-empty routes.

Route No. 1 includes requests that are located at almost the same address and where the algorithm works correctly, arranging visits to these points one after another (Figure 6). However, there are also a couple of requests that were not included in any generated route.

*Figure 6. Sequence of visiting route points*

Let's consider the routes formed in Figure 7. You can notice that point number 1 (Figure 7a) and point number 2 (Figure 7b) are in the same delivery area. Therefore, it would be logical to send not two vehicles, but one, to the distant delivery area. This situation arises due to the fact that the written algorithm for distributing requests along routes does not take into account the global state of all routes, but considers and improves only the already formed one, introducing a minimal random change into it with each iteration.

Also, the filling of the route strongly depends on the initial state, which consists of completely filled routes and part of the routes with a couple of requests that do not fit into the others. In total, we get the following picture: Figure 8 shows a display of routes created by the algorithm, sorted by occupancy. Red means fully loaded, and green means the vehicle is barely loaded. This draws our attention to the fact that the distribution of applications along the routes is uneven. In some places there are a lot of deliveries, in others there are almost none.

cid:image003.png@01DA5853.6EC70EC0 — *Figure 8. Sorting routes by occupancy*

This problem also affects the wide spread of requests across the map, as can be seen in two examples of route formation. The algorithm does not have the ability to consider applications by area of their location. But the initial state and subsequent changes in the form of rearrangement of one request from a route to another do not lead to the desired result.

Conclusion

Thus, based on the simulated annealing method, one of the automatic route planning algorithms was formed, which is part of the Norbit CDS software solution developed by NORBIT. In the course of analyzing its work, we can conclude that the algorithm needs to be refined in the future for a better distribution of applications. It is also worth noting that the Norbit CDS system supports multiple algorithms and even customer algorithms. In particular, there are combinatorial and genetic algorithms, which provide not only better convergence, but also execution time, but are less horizontally parallel.