Simple do-it-yourself logistics

I want to share with you the experience of creating a logistics system in one commercial enterprise.

One fine day, in the near 2012, the head set the task: to think about the problem of optimizing the cost of transport logistics of the organization.
The main activity of the enterprise is the wholesale sale and delivery of products, where transport costs occupy a significant share of costs.

The management considered that the time had come to bring order to the expenditure of funds for fuel, and there were also suspicions that the drivers were additionally engaged in more “left” delivery between flights. In small-medium enterprises, much is built on trust, as it is costly to keep individuals to control and is not always advisable. When costs grow, and efficiency drops, then you just need to do something.

To begin with, we tried to solve the problem with managerial methods: constant measurement of the fuel level, tachometer readings, delivery time measurement with personal cargo tracking. The effect was about nothing but negativity, suspicion, and unnecessary movements (measuring it, too, for someone to work). If during the single route it was still possible to define approximate frames, then during the flight from 25-35 trade objects everything changed very much, the spread was very large, both in time and in fuel.

Objective: to send loaded vehicles to trade enterprises reducing mileage, and therefore costs. If possible, avoid deviations from the route. The goal is to reduce costs with minimal investment in finance and time to implement, so to speak yesterday. During the discussions, agreed on several alternatives:

1. use one of the services for calculating routes and accounting for fuel;
2. put on the fleet tracking / tracking modules;
3. design something yourself;

We decided to try all three solutions and choose the best:

1. We did not find a good ready-made solution at that time. Either turnkey design, but expensive, or take it as it is and further by agreement. We tried several online services. In general, it is not bad, but basically the difficulty was to duplicate information from the accounting system, the number of actions to get the result (click here, go here, update the directory), everything is online (at that time it was critical). But the biggest drawback is the difficulty in drawing up routes with multiple points and choosing the best route. Usually, everything had to be selected manually, adjusting the values, which is a long and not always successful result.

After a couple of months of work, they refused such a decision.

2. As an experiment, GSM tracking modules were installed on a dozen vehicles.
The result is more successful. You always know where the car was. But the cost is more expensive than the first option. However, after identifying a couple of cases of deviations from the route (one driver of the Sabbath, the second visited the lady of the heart during working hours), the staff began to get rid of such devices. Although they have not previously enthusiastically accepted this innovation. Either the power terminal accidentally fell off, the device went out of order when the engine was repaired, the electronics in the sun “overheated”. So for three years we lost 9 devices. In general, the decision turned out to be positive, but from the drawbacks - it took a long time to look through the routes covered to identify suspicious activity, which is not very convenient. A plus in the tracking system was an item about track export, which allowed to accumulate certain statistics on routes.

Later we used another system from one of the major cellular operators for corporate communication and tracking the activity of sales agents, the result was similar: SIM cards broke, phones were lost, forgotten at home, the battery was exhausted, people would always find a way out.

3. In parallel with the first two approaches, it was decided to reinvent the wheel , to realize the possibility to build routes in their own accounting system.

For a start, we brought all the places of the visit and put their geo-coordinates in the database. We received the coordinates according to the GPS tracker when visiting, as well as visually using OSM maps, finding the right place with the mouse and copying the coordinates.

At the second stage, it was necessary to obtain vector maps of the region in a convenient format.
The choice fell on the same OSM, since the cards have an open format. We didn’t master the parsit dump of the planet, so we initially unloaded the data into XML in pieces, through export from the OSM itself, and then connected the territories. Later came across a GIS-LAB project. These worthy people for many years laid out a daily dump of territories, divided by region. But everyone wants to eat, the project has recently stalled, and the guys have moved , and are doing the same work for a reasonable price.

Having received the map in XML format, we extracted the layer responsible for the roads according to the specification . Since the volume of maps of several neighboring regions occupied a dozen gigabytes, the SAX parser was written in RUBY, it selected only the necessary tags and combined the neighboring regions in which the activity was carried out into a single structure.

The project itself is written as an external DLL to the accounting system written in Pascal. The fleet of devices on which the system was supposed to work was, to put it mildly, obsolete, so there was a limitation of 1 GB of RAM (Yes, there are still companies that use such equipment, it has been working for 10 years, it will work as long). Initially, there was a desire to break the map into pieces and load it into RAM as needed (as on navigators), but this was extremely slow. As a result, managed to build up to a reasonable fifty MB.

In OSM, road maps are represented as vector sections of the roadway with additional attributes. In our solution, we used adjacency lists . Where the vertex is a point on the map, and the edges are the paths to the neighboring point. For optimization, we assume that there can be a maximum of four paths from one vertex (intersection). If there are more than 4 paths, then we need to split the edge into two additional ones, so we always have a fixed number of edges = 4 for each point of the map. This approach allows alignment of data in memory, although it is somewhat redundant.

It is worth noting that the Earth is not a ball (unexpectedly), but a geoid , but for mapping purposes it is simplified to a spheroid or ellipsoid .

For our purposes, I found a formula for calculating the distances between two points on the surface of an ellipsoid, which I could not understand the whole deep meaning, but this does not prevent us from using it.


After creating the road base, a visual layer was needed to display the surrounding space. Here the maperitive project helped , it allowed parsing the OSM map of the regions into tiled areas in approximation layers, just like 10 ^ 100 or Yandex does. There was an attempt to work with maps of giants online, drawing a vector map on top of the browser layer, but due to licensing restrictions, they decided to refuse. As a result, a virtual disk was created and a dump of tiles for a couple of dozen gigabytes was uploaded there, but everything is at hand and does not slow down. True, you have to refresh about once every six months, usually this coincides with the overload of maps.



To combine a tile image and a vector map you need to know that tiles, Google, OpenStreetMap, Bing, Yahoo are represented in the Mercator projection (more precisely, WEB MERCATOR , which is a projection on the sphere), where each deeper layer is twice as detailed as the previous one.



Yandex.Maps use the ellipsoid Mercator projection.

It does not matter if you can recalculate the geo-coordinates on the projection plane and back.

We chose level 17 as the maximum. Closer does not make sense due to the increased storage of the number of tiles (each level is 4 times more than the previous one), as well as their low information content.

2 ^ 17 * 256 = 33554432 (256 is the size of the edge of the tile in pixels).


Now that we have the basic tools, we can proceed directly to the task of creating the optimal route. We connect trade objects with the nearest edge in the graph of roads, and then we start the search for the shortest path. For this, we use a variant of the Dijkstra algorithm for its rarefied variation, successively for each entry point. At the output, we obtain the adjacency matrix , the size (N + 1) * (N + 1) with infinity on the main diagonal (ring prohibition), where N is the number of visiting points without taking into account the exit point.

The resulting matrix stores the minimum distance on the roads between all shopping facilities, which is the classic task of a traveling salesman . Since the algorithmic complexity of such a task exceeds the limit, we used the branch and bound method for solving. For n <15, exhaustive search, otherwise a rough estimate of depth was included. The option is certainly not perfect, but quite working.

As a result, we received a route close to the optimal distance with an estimate in km. If necessary, the operator can manually change the route in favor of the priority of individual points.

The solution works in the organization for about 7 years, quite successfully, although not without flaws, both in accuracy and in convenience. The results are quite consistent with the data of GPS-tracking cars. In my estimation, the introduction of logistics allowed saving 10-12% of the allocated funds for fuel. The program was designed, launched and accompanied by just one person - your humble servant.

My conservative leadership is not eager to "shine", so for the attention I offer a fictional example of the route.



Without visualization, the calculation goes many times faster, and within one settlement, almost instantly.

After so many years, sometimes itching to climb into the code and rewrite it with a new experience on a new, more modern platform, but so far there is no economic feasibility.

That's all that I wanted to tell you, I hope it was interesting.
I apologize if I was somewhere not accurate.