This text arose due to the random coffee fun in Yandex - the system makes an appointment for two random employees if they indicated that they want to participate in such meetings. My interlocutors found the story about what I was doing interesting, and now I got my hands on offering it to a wider audience.Before Habr, I gave a guest lecture at the Faculty of Computer Science of HSE and Yandex - I told the students of the FCS exactly the same thing, which I will tell you about now (at the end of the post there is a video) Namely, how traveling with drivers delivering orders from online stores convinced our team to make a new service about logistics. I hope I can manage to convey to you my feelings from this area: I traveled to Gazelles and Largus, listened to complaints from employees about the picky âaunt from Noginskâ and witnessed how an order of three scooters for three children turned into a drama . And in the end, let's talk about technology.Part 1. How it all began
A few years ago, walking around the office thinking about whether itâs time for me to change something in my life, I almost accidentally ran into a corridor with a colleague whom I respected greatly on one of my past projects. It turned out that he switched to an internal startup, and they are just looking for an analyst. So I ended up in a division called B2BGeo. This small group at that time was supposed to do some kind of thing for companies based on Yandex geo-services - only no one knew which ones. Historically, geoservice employees have made desktop Yandex.Maps, Maps, Navigator and Metro mobile applications. Also, this unit includes an impressive infrastructure: development of a routing engine, a map service, recognition of road signs, extraction of data from satellite images, and much more. Both web maps and Yandex.Navigator are applications,intended for the mass user. Of the services for companies, we had only a set of mapping APIs: a JS map widget for sites, MapKit for applications, and a REST route building API.So the B2BGeo team, before starting to sell products for companies, had to come up with these products. We spent some time on market research and prototyping. The prototypes were interesting, for example, a map of the quality of a cellular signal inside buildings. Then the cellular operators did not use the huge amounts of data that they have, measured quality mainly on the streets and in a rather primitive way. Another example of a prototype is a universal customizable router with machine learning. By the way, hereinafter referred to as a router and router is not network equipment, but a route-building program.Some prototypes did not take off, others would not be interested in a sufficient number of companies. Something larger was needed. In the future, it will turn the world around and open new horizons, and for a start it will bring significant benefits through geotechnologies. We had a strategic session: we left the office and brainstormed for two days. Based on the results of the session, we identified an industry where there are sufficient prospects for us. Our choice fell on logistics.In Russia, a lot of commercial vehicles, many transport and courier companies carry something somewhere. And all of them, most likely, make their routes either manually or with the help of programs that probably do not work very well, because they do not take traffic jams into account. And behind us there was a whole Yandex with a lot of hardware, only a small number of companies (only a rare example - Google) had sample data, and good programmers. Competencies in this area are rare and valuable: Uber at some point bought out a whole cartographic team.Encouraged by this prospect, we agreed with one of the delivery aggregators (a company that delivers orders from various online stores) so that they would let us look at their work from the inside out, "immerse themselves in the industry." The members of our small team traveled with couriers delivering orders, and sat next to the logistician who plans the routes.Part 2. Immersion in the industry
8 am, one of the industrial zones behind the Third Ring Road, where the warehouse and office of the aggregator are located. A small room, reminiscent of the post office: the corner is fenced with a desk, inside - logistic computers, telephones, printers. Greasy chairs and computer chairs with cracked dermantine. A box with cheap Chinese phones, a paper with a number is glued on each - they are handed out to drivers. There are simple sofas-banquets along the walls, a stand with printouts at the exit: transportation rules, some kind of internal instructions, a table of fines - for example, 200-300 rubles will be taken from the driver for an undelivered order. The aggregator also has a normal office, where the director, managers and bookkeeping are sitting at beautiful tables, but the key events for us are happening in this small room.
Drivers smoke outside, but itâs cool there, most are inside, so itâs crowded and stuffy in the room. Mat-remat in three floors, many gloomy in the morning, someone wants to get his bundle of invoices and leave to load, someone has a hitch, he is unhappy. The situation is tense, there are two logisticians, and they are in the soap. We are told that this is a normal day, just in the morning, when leaving for routes, there is always a park. At night, when the planning went on, there was also a drowning, somewhere in an hour the tension will decrease, and the logistician will be able to rest.Several drivers are told that Yandex will go with you. They are surprised and not particularly happy - it is not clear why they are so happy and whether they have set us to follow them. We, office workers, IT workers with backpacks, are in stark contrast to this gloomy men.I got the Gazelle, it has a driver and a forwarder, I sit down third with a backpack in my arms and try not to take up too much space. Orders are already loaded into the body, we start.
Later I learned that usually precedes the departure of cars on the route.Suppose today is Wednesday, you order a refrigerator on a small site that you found on Yandex.Market, this store has the best price and reasonable reviews. Delivery is possible only on Friday, it suits you. The site is really just a showcase; for very small sites, the manager who confirmed the order can generally be the only employee. Your refrigerator is located somewhere in a warehouse near Podolsk along with other refrigerators of the same company (a small store does not have its own warehouse - in fact, the sale is from the manufacturerâs warehouse). The manager reserves this refrigerator and sends the order to the delivery aggregator. During Wednesday, the aggregator collects orders and on Thursday sends a large truck to Podolsk for your and other refrigerators ordered in other stores.All this comes to the warehouse rented by the aggregator in the Moscow industrial zone.On Thursday evening, when all the goods to be delivered on Friday are collected at the warehouse, logisticians sit down for work. By 4-5 in the morning they should distribute orders by machine, warehouse workers will put the goods in heaps, each machine has its own heap - you need to leave them a margin of time for this work. A bunch will be loaded into the car, and it will go to please customers.
To distribute orders by machine, the logistician uses a specially purchased program. It integrates with 1C: Enterprise, data on machines (allowable weight and volume of cargo, cost of a day of work) and on goods (weight, volume, address and delivery interval, customer contacts, comments) are loaded into it. Some of the cars belong to the aggregator, this one had heels (Lada Largus) and Gazelles (Gazelle / Ford Transit / Hyundai Porter). There were also hired couriers on personal vehicles, usually on station wagons (we saw Ford Focus, Mitsubishi Pajero and even some old Lexus).The program was written by good programmers, it knows how to distribute loads on cars and build the optimal (by time or mileage) route to avoid orders, given a bunch of parameters. But the logistician does not use this functionality in any way. But he actively uses the visualization of orders on the map. The program allows you to draw polygons-areas on the map and display statistics of cargo and routes inside these areas. Logisticians divided all of Moscow and Moscow Region up to the Big Concrete (highway A108) into zones of approximately the following type:
In the center, there are some small areas, and then radial sectors begin that run along major highways and encompass the region.In each such zone, certain drivers work, who are usually familiar with it, know the roads, the features of the traffic, know where the traffic cops are, what restrictions and signs are for trucks. The logistician, in turn, knows how many orders the crew can carry. He gives more experienced under 30 orders, and for those who have started working recently, 20-25 orders. He looks at how many orders are in a certain area, and if there are too many, he throws them to the next one. Or adds from a neighboring: let's say, the logistician is friends with some drivers and gives them âlightâ orders, which are likely to be on the way. And the unloved driver can annoy. For example, to toss an order for a client, about whom it is known in advance that he is picky, will require delivery strictly at the indicated time, will print all the goods, will examine them for a long time. Besides,the logistician can simply give the driver fewer orders: for each order the driver receives 200 rubles, he is interested in having more.The ability to plan routes in the program is completely ignored. This possibility does not make sense in such a system: if the logistician tells the driver how he needs to go round the orders, the driver will answer him: âYou are sitting in the office there, and Iâm in this area like the back of my handâ. So the logistician only assigns orders for the car, the task for the driver is formulated as a pile in the warehouse and a pile of printed invoices.So, back to the Gazelle. Our region is the Enthusiasts highway and further towards Noginsk, there will be about 15 orders to the Moscow Ring Road, I will go there. The driver leaves for the Third Transport Ring, at which time the forwarder takes a pack of invoices and transfers them in the correct order. The correct order is this:- First, we will drive along the Enthusiasts highway towards the Moscow Ring Road and take all orders that are on the right. We donât always take it on the left, there may be traffic jams when crossing the highway, itâs better to take them in the evening. Then weâll leave for the region, weâll take it there. In the evening we will go back and carry the rest.- But, for example, the first order in the pile - with the wish âafter 14 hoursâ? Leave it for the evening?- It is possible for the evening, but itâs better to try to agree to give it now.The negotiation process was immediately demonstrated. At 9:30, the forwarder called the phone order after 14 hours:- Hello, delivery, we are already in your area, can you accept the order? .. We will go to the region after your area, and we wonât return here before evening. Maybe weâll return after nine, or maybe weâll stay completely in the region, this is an unpredictable business, we may have to postpone the delivery the next day ... Well, then weâll arrive in 15 minutes.It was then that I realized where the couriers come from, who say: "Hello, Iâm already with you!" - and completely ignore my comments and delivery interval!Colleagues who drove in other cars told me that someone had a driver or forwarder honestly called the client an hour before delivery. Mine were not very sociable, they called for about fifteen minutes, pronounced the comments of customers aloud. Simple wishes (âdo not call the intercom, the child is sleepingâ) were taken into account, but everything that influenced the route was usually ignored. Shifting invoices, the forwarder fished out an order that had to be taken to a village a few kilometers from Noginsk.- Oh, this aunt again. Remember, she had an order, then a return on marriage? Now a new order.- Yeah, raise the washing machine again. Another interesting one is: âplease deliver from 12 to 16â. How does she imagine it?- Yes, in general, they do not understand what they are writing.I think so: if you order a washing machine in Noginsk, then sit there and wait calmly until it is brought. Either agree somehow with the neighbors, or take leave of work. We cannot go to her this Noginsk every day.I got off near the Moscow Ring Road, and the driver took the Gazelle further along the Gorky Highway. In fact, they are not bad guys, and despite the buzz against customers (it amounted to at least two-thirds of all conversations), they most likely would have managed to deliver the washer to 16. Simply if they hadnât, they would not even bother.My second trip took place in a smaller car: the cargo Largus drove around the North-Western Administrative District. The cargo was small, no refrigerators, so the driver was alone. Uncle got sociable, we talked a lot about him. He said that in general he is a master of sports in wrestling, works as a coach, but now everything is deaf, so he moonlights as a courier. The money is small, but the increase is pleasant: about 2 thousand are obtained per day. Itâs easy to deliver orders, it works when it wants. Of course, there are nuances: you come across unpleasant customers, you have to eat stored sandwiches in the car, you are in a hurry, you donât even go to the toilet, you have to ask customers. But on the whole, he is quite prosperous, for him it is more likely entertainment.It's funny: colleagues, especially girls, delivery service employees also told stories that âThe courier is not the main job, but purely for the soulâ, âIn general, I usually go in a behheâ, etc.I remember that in the area of ââRublevka or Krylatsky such a conversation:- Once in the City he brought an order, there they have apartments in a skyscraper, the corridors are all in marble, I go into the apartment - carpets, paintings in golden frames, some fur coats hang, which just isn't there. An order for 5800, so he asked for a change of 200 rubles, count up ?!- So, maybe he has fur coats and paintings precisely because he saves even 200 rubles.After my words, the driver thought hard. And an hour later we arrived in Schukino and I âunderstood everythingâ about this business.In the next overhead pen, a note was made that not everything was in order with the order: out of three purchased children's scooters with a total value of 20 thousand rubles, only two were in the car. The driver called the logistician. It turned out that the woman made an order for three scooters on Monday, but yesterday, Wednesday, the third scooter was mistakenly put in the wrong car. And it was a private car, for some reason he didnât return to the warehouse in the evening, as the âregularâ drivers do, and the scooter still rides with it. We could try to intercept him, but today he goes about his business, it is impossible to cross. Next time he will work tomorrow (Friday), but this is not accurate. It is guaranteed to reunite all three scooters and take them all at once will only be possible on Saturday.Armed with this information, the driver called the client. There was a very displeased woman. She said: on Saturday at 10 am they have a family holiday, where they wanted to give scooters to her three children. Therefore, she needs them strictly in the amount of three pieces, she does not agree to a partial redemption and does not understand how it is possible at all - she placed the order on Monday, and now we, the scooter store, are substituting her for that. Delivery on Saturday at an indefinite time does not categorically suit her. Tomorrow she is at home before dinner, if you cannot today or tomorrow morning, she cancels the order and curses the store to the third knee (and you can understand it).Part 3. Local minimum
The store buys an order delivery service from a courier company. For undelivered scooters, he will fine a courier company for 500 rubles. The company will fine its storekeeper and driver who did not bring the scooter back on time by 200-300 rubles. An upset woman will give her 20 thousand to a more agile store, and one star on Yandex.Market will slap this. The store can provide the best service, but the "last mile" is carried out by gloomy men at Gazelles and Largus. If they behave badly with customers, the store will not be able to influence this.At the same time, the store usually looks for the lowest cost delivery - in the sense that if you pay drivers even less, they will go to work as taxi drivers or somewhere else. Drivers optimize their daily earnings - you need to carry more orders and not be fined. If we compose a global cost function that describes the system as a whole, then this state of the function will certainly correspond to its local minimum, the âpotential wellâ.
There are clearly large, systemic problems in this pit. Firstly, the most difficult work was handed over to the most unskilled employee: the driver controls the machine and plans the route and communicates with the client. He also carries money. He has additional skills and specializations - for example, the ability to deliver 30 orders per day in a certain area. It turns out that the company must train inexperienced drivers, and experienced ones not to lose, because they (unfortunately for the company) are difficult to replace.Secondly, the delivery process is completely unpredictable. The client does not know what time they will come to him. The customer is usually offered wide delivery windows - four, six hours or more. This creates great inconvenience for him: it is not always possible to sit in one place for six hours. And even drivers cannot always get into these windows. The opportunity to make narrower windows convenient for customers (two hours, or better an hour) is possible only for large companies that were able to push harder and jump out of a potential hole into a more optimal state. We are talking about companies with their own delivery and couriers. âOwnâ couriers would be useful to all companies: this way you can control the quality of their work and even do some kind of upsale (when the courier offers a person something to buy to order).But keeping a staff of couriers is very expensive - only the largest companies like WildBerries or Lamoda can afford it.Thirdly, logisticians are constantly cheating. Tricks such as overloading cars and breaking drivers' shifts are considered commonplace (instead of 8 hours, they work 10-12). âIt's okay - if it does not fit in the volume, then he will put the excess in the cabâ - even this happens. For this, fines are imposed, especially for overloading trucks: to the fine itself (from one hundred thousand rubles per company) will be added compensation for damage to the roadbed. It is considered to be a multiplication of the overload coefficient by a distance and can easily reach hundreds of thousands of rubles. Fleet owners would love to drive without breaking. But suppose the logistician has a choice:- âShove the extra pallet, a little exceededâ- âAdd the extra car, increase costs, but without breakingâ- âSit for another half an hour and make a plan properlyâOften he chooses the first.Such a depressing picture inspired us with great optimism. We conducted several interviews with companies in other branches of logistics, such as the delivery of large goods, the delivery of documents. All our hypotheses that the world is not perfect in this place have been confirmed. So, before us a large window of opportunity opened. We eagerly set to work.Part 4. MVRP and traffic jams
Below are the technical details of our product, so let's start with the definition. MVRP is a multiple vehicle routing problem, that is, a task in which you need to optimally go around several locations, having a fleet of several cars. We use terminology in which a similar task for a single machine is called SVRP (single VRP). It differs from the classic traveling salesman problem (TSP, traveling salesman problem) by the presence of delivery windows. There seems to be no common terminology: in the Wikipedia article , the tasks we solve are called the complex abbreviation VRPPDTW (VRP with pickup-and-delivery mode and delivery windows).Programs that solve such problems are traditionally called âsolversâ. For versatility, you need to put a bunch of options and restrictions in the solver:Examples of additional optionsâ , .
â (, ), .
â ( , ).
â . , : , .
â .
â .
â (, -), : . , * .
â «» , . , , - .
â : , .
There are several types of algorithms that can be used in solvers. For example, there is a large group of universal open source and paid constraint solvers (Google OR-Tools, OptaPlanner, Choco-solver). Within each of them, a functional is built that is optimized taking into account the required restrictions. Such solvers are usually able to solve a whole bunch of tasks: VRP-tasks, scheduling, optimal allocation of resources in the cloud.There are also many commercial solutions tailored specifically for MVRP tasks and ready for integration with enterprise management systems. VeeRoute, Maxoptra, Antor are known in Russia.Solver Yandex.Routing uses a combination of annealing simulation algorithmand genetic algorithm. We do not know what competitors are using, but most likely something similar. According to our measurements, in VRP-tasks constraint-solvers very much lose to commercial solvers.
Solution of the TSP-problem of the roundabout of states in AmericaIâll immediately make a reservation: the topic of solving the MVRP-problem is so great that in the article we will not discuss it in detail, but rather we will write a separate article.The main input for a solver is a matrix of distances between points involved in planning (order points plus one or more depots). In fact, this is not one matrix, but two: by mileage and travel time. It is through these matrices that optimization is done. As already mentioned, Yandex, unlike the developers of other commercial solutions, has traffic information. That is, for us, the matrix is âânot constant, but changes in time, and we take this into account in the solver. As far as we know, no one does this in the world: even knowing everything about traffic jams, it is difficult to build a set of distance matrices with reasonable discretization (sufficient to ensure that the resulting routes are good). The fact is that the number of matrix cells grows quadratically from the number of orders.Suppose we are solving a VRP task for delivering 10,000 orders using a fleet of 500 cars. Then we get two huge matrices that change in time. Downloading them on the network alone will take a lot of time, but their contents must first be calculated. If this is not done efficiently enough, we will need to wait a couple of hours until the matrices are built and downloaded, and only then can the solver be launched. The Dijkstra algorithm helps us here: the calculation of large distance matrices can be realized in almost linear (from the matrix size) time. But our team will also talk about this in a separate article in the coming weeks.So, we built a smart solver, parallelized it to a bunch of cars, made a router with ultrafast distance matrices that take into account traffic jams, and also figured out how to put these matrices into the solver. As a result, they got the opportunity in 15 minutes to solve the problem of driving around 3,000 locations. Result on the map:
Part 5. Results and difficulties of implementation
You can compare our routes and those built by logisticians who plan trips manually or (sometimes) in semi-automatic mode using competitor programs. In a typical case, our solution allows you to beat logisticians by an average of 20% with a small route in optimality. At the same time, the time to get the finished route is much lower - 15 minutes instead of a few hours. In a wonderful future, the logistician should turn from a nervous exhausted person scattering orders by cars in the middle of the night, into a respectable member of society. He will use our automatic planning and occasionally correct single edge cases with his hands.The implementation went most smoothly when customers bought our solution at the time of opening their delivery service. But most of our customers are not new. They already have an implemented solution for logistics, and the larger the client, the stronger it has overgrown with all sorts of features of the processes of this particular company, and just crutches. Their development and support is carried out by their own or hired IT-service. It is believed that large companies (even if the advantages of our product are obvious to them) can implement Routing only together with a major update of the IT infrastructure. And this usually happens every few years. In May 2018, our newborn service was announced at the YaC 2018 conference in partnership with IKEA. Six months later, the implementation began, we began to exchange data,and a year later at the industry conference on logistics, the project manager at IKEA spoke about the results.The results were positive, but a little unexpected for us. For example, informing customers increased their satisfaction and significantly reduced the number of calls to the call center (before, without knowing anything about the fate of the sofa, people were nervous and started calling).Or another example - with oil industry workers., . , . , « » â . , , , «» ( , YouTube , ). , ( , ), , . : â , , , . . .
That is, it turned out that our initial installation is not entirely correct. We thought that we would sell an effective detour of points, but it turned out that companies need different products that affect different indicators, and not only and not so much on efficiency. Fortunately, we supply several more with the core technology product.Smaller companies are better at overcoming integration difficulties, but may face human factors. It is very difficult to convince the driver to follow the planned route and keep the phone with the tracking application turned on. This is somewhat reminiscent of stories about peasants of the 19th century breaking mechanized mowers and plows. Everything, of course, is not so sad, but there is resistance to progress.Conclusion
In a short time, we managed to build a product that, we hope, will turn all the logistics in the country (or at least affect it strongly). Our current customers and Yandex believe in us. The latter is also important: yes, the internal startup is calmer than the startup outside the company, but we also need to show the result.We started with an emphasis on large companies, in our future plans - to lower the threshold for entering the service. You can play around with solving SVRP problems directly on Yandex.Maps: when you add a fourth point to the route, the âOptimizeâ button appears, which calls our solver.
Video of the same story for students of FCN in HSE:All the best routes!