Real-Time Route Optimization

LokadTV has invited our Head of Science, Cédric Hervet, to talk about Real-Time Route Optimization and discuss how real-time route optimization has changed the way delivery companies operate today. Joannes Vermorel, CEO and Founder at Lokad & Kieran Chandler, Business Development Manager at Lokad, received him.

Kieran Chandler : Hi ! With the recent advances in crowdsourced data, it is now possible to forecast the impact of traffic congestion more accurately than ever before. This week on Lokad TV, we are delighted to be joined by Cédric Hervet who is going to discuss with us how the increases in Quantum Computing and the ability to optimize routes in real-time has led the delivery companies changing the way they operate. So, Cédric, many thanks for joining us today. For starters, maybe you can start by telling us what you are doing at Kardinal, which is the company you co-founded ?

Cédric Hervet : Hello, thanks for welcoming me. So, Kardinal is a company that specializes in Route Optimization in real-time, with a great deal of context awareness in the way we proceed. Usually, tours are optimized by humans, manually, so they will plan and schedule things they have to do for their drivers or their technicians in a manual way. This is clearly suboptimal, but in another way, humans have a great capacity to handle emergencies, events, problems, and they are capable of envisioning the global scope of their priorities to somehow manage to make a decision. And algorithms are poorly equipped for that, especially Tour Optimization ones. 

On the contrary, there are softwares on the market that are already providing Route Optimization, but they do it in a very static way. It means they get data : stuff to do, people available, they will mix it somehow and provide an optimized solution for the route schedules. And this is problematic because the first event you will encounter will somehow destroy the quality of your tours. And once trucks are departed on the road, there are other issues, like you just said : traffic congestion, customers that are late or absent, that want to reschedule their appointment. All these kinds of event can somehow destroy the performance of what you’re doing. So, at Kardinal, we believe that the right way to optimize your tours, is really to never stop optimizing them. This way you get a greater capacity to really handle problems as they go. 

Another key aspect of what we are doing is that we have a strong focus on really not removing the human from the equation because in many ways, humans… they know stuff, they know their job, and they know stuff that cannot be found nor modeled in any database and this is really important not to remove them from the whole process because they have a strategic vision over their activity.

K : Yes, this idea of using a human brain and making the most of that particularly in those emergency sort of scenarios is a really interesting one. I think it is something you would probably agree with as well Joannes : making the best use of the human brain in terms of being an addition to an optimization ?

Joannes Vermorel : Yes absolutely, I mean that’s the idea of making the most of smart people that are very aware of the problem that the company is trying to address with its own supply chain using the best of what modern computing power has to offer. It’s pretty much, I would say at a very high level, also the strategy of Lokad. 

K : Ok great and today we’re talking a bit about real-time Route Optimization. Why is that of interest to you from a supply chain perspective ?

J : Obviously, at Lokad, when we think about supply chain optimization we don’t exactly think at the same time scale. I mean, if I compare a bit what Kardinal and Lokad, who are both Enterprise Software vendors, are doing, Kardinal is doing Route Optimization so decisions that can be rechallenged every minute or so. It is real-time, not exactly like microseconds, you’re not piloting real-time robots that are doing picking in a warehouse so it needs to be swift, but it’s not at the microseconds either. Lokad, on the contrary, is more like the decision that you want to take for tomorrow or up to, let’s say, one year ahead. So that’s the time range. So obviously, the fact that Lokad can optimize the supply chain, we are typically making assumptions on what can be made about delivery when we say we want to do inventory rebalancing between locations, it can be stalls or warehouses, obviously we heavily depend on the fact that there is tons of agility from tools that can be provided such as Route Optimization by Kardinal. 

And the way, at Lokad, we see it is that the more agility you have with your routes or the point you can rebalance stock between stores easier, it means that it lower the cost for that we see, to do those optimizations, thus we can do more of them.

K : Okay, let’s move on with our idea of agility then. I mean it was not so long ago that I would be printing out directions on Google Maps and I would not be very able to sort of make a change from my routes if there was traffic up ahead. Nowadays, we are much more sort of reliant on things like cell phones and GPS systems. So how Route Optimization developed over the last few years ?

C : Well, Route Optimization, there are two problems that you are mentioning here. There’s the problem from going from one point to another and finding the right road and this is especially for that use case that stuff like Google Maps are built and there are the more general problem of having N stops to visit and you want to also know in what order you will visit all these stops, knowing many things about the traffic and everything. So we are really focused on the second problem, which is much more difficult because if you have just maybe 20 stops to visit, the number of combination is so high that it would take you, even with a very powerful computer, thousands of years to compute all the possible combinations. So obviously you need algorithms that are much smarter than just enumerating everything and that is where the maths comes in. But beyond that, this capacity from mathematics to model that problem and trying to provide algorithms to solve it efficiently, it has been developed for many years now. I think it started in the 60’s, but the actual implementation of such algorithms is very relying on data, on the availability of the data. Traffic data especially, because you can build very optimized routes, if the data you gave the algorithm is wrong or inaccurate, you will just provide infeasible routes. So, you would be happy with great KPIs, like 10 to 20% drivers less, fewer kilometers traveled and everything, but if it is infeasible in practice, it does not really make sense. So what we are doing at Kardinal is really focusing on providing routes that are feasible. It means that when we are giving them to a driver, he will say “Okay, I probably would not have done it this way but it’s obviously smart, and I think I can manage to do it in my day, without finishing 2 hours later”, which is actually their daily life today. They are always working extra hours, so yes, what we are focusing on right now is taking all these theoretical mathematics, beautiful theorems, beautiful maths really, beautiful algorithms to make things realistic, feasible in practice. This is really how we see our work at Kardinal.

K : Yes, and Joannes, from what you have observed, who are the key companies and the key players that have really driven this growth and driven this expertise in route optimization.

J : Well I see that first there has been like intense development for online solutions for pretty much everything. For example, I think historically probably the one company that literally did something near magical in this area was Google. You know, search engines before Google, was literally something people did not realize at the time, that companies like Yahoo were actually updating their index something like one per quarter. So literally, you were getting results, search results that were always out of date. So if you had a page that only appeared yesterday, it would never show up on the results and Google was very innovative on many fronts, but one of them was to really have things that were completely online so you want to have like, the best results for your query but the reality is that with new pages being added to the index, like all the time, and actually they didn’t quite manage to have it all the time. I think at the beginning they were only doing like weekly refreshes but it was like already like 20 times faster nearly than most of the competition. But you see, that was a transition toward a problem where you fundamentally wanted to have like, an always up to date results under changing conditions and I don’t think that Kardinal or Lokad are actually using Google algorithm for search engine but it was more like, I would say, a source of inspiration of the sort of stuff that you can do at scale with the proof that it can actually work. And it is very interesting, so for me that was it and many other players started to do similar things on many different types of problems and I think there was a new wave of people who are like “how can you have the online version of a problem that is much smarter and also something that is probably very different from what Kardinal is doing right now compared to what people were doing in the 50s is all those constraints, all those nonlinearities where you want to have something that is very an optimization that can deal with a lot of stuffs that are mathematically hard to represent. You know, nonlinear constraints, the fact that maybe your driver cannot drive more than X hours because there is like an employment regulation that says this and this and this…

K : Ok, and let’s talk a bit about the data. I mean, what’s the data that’s actually of interest to Kardinal and where do you get the data from as well ?

C : well, there are two main sources of data. The first source is obviously our client that is providing us with the orders we have to optimize. He is giving us the most accurate description possible of his activity and that can be, just like you said, legal constraints for working hours of their drivers, drivers’ availability, where do they start, where do they end their service, what kind of vehicle they are driving, what kind of capacity, is he assermented to transport dangerous goods, is it possible for him to conduct specific technical intervention that requires a specific skill set. All this kind of data is somehow defining constraints over their activity, so we need to understand this. There are also data coming from the client describing the orders themselves, so that could be packages to deliver, that can also be some interventions like for example repairing IT equipment so all these are interventions. So this is really describing the activity and on our side, we are relying on technological partners like Here Technology, which is our partner for, you know, getting the distance data. We need to understand how long it takes to go from one stop to another and we need to understand how the traffic will change over time. We also need, once trucks are on the road, to get the actual real-time traffic to adapt our tours so Here, for us, is a data provider, and we are handling this data with our algorithms to really provide updated solutions. So those are the two main sources of information for us.

K : Yeah and you talked about this kind of online solutions, the rising growth of it. From a technical perspective, what sort of challenges do that introduced, being able to work in real time ?

J : Obviously, real-time introduced massive complications. First there is no such thing as real-time, the speed of light is finite. You would say “oh it’s incredibly fast !”, yes but when you think about it, it’s not that fast. The problem is that once you have distributed computer systems and you need to go back and forth from multiple data centers and you do thousands of kilometers every single time, you would say “it’s just milliseconds”. But if you need to do thousands of round trips, then you start to realize that it takes seconds to get results. So actually, achieving real-time systems when you operate globally, it takes a lot of skills. Plus there is so many things that can prevent you having a good real time system. You would think “oh my system on average is super fast”, but think of your computer, how many times do you try to do something with your computer and for like, 2 minutes, it’s kind of stuck because maybe there is like a Windows Update going on or whatever. So the reality is that our computers are on average very fast yes, but if you start thinking about the worst case, the worst case is that they can actually be pretty slow. And again once you have like an enterprise system you want to think that typically the speed of your system is going to be whatever is the slowest that you have. Which by the way if you have like many machines, the slowest can be very very slow because if you have like many machines, one of them, for some bizarre reasons, an update of some kind or whatever, it’s going to be visible. So real-time is in itself a set of challenges which are very complicated. Another part of complication is that suddenly you introduce dependency to partners. Which means that how can you as an enterprise software vendor, make your service very available and reliable, even if your partners are not. Again, the problem is that the more dependency you have, the more potential problems for downtimes. If your service is only as good as your dependencies, your third party technology providers, that means that every time you move down the chain you get something with lower availability, lower uptime, and lower everything. So that is also quite a challenge.

K : ok, and we’re now sort of entering an era where actually end users can have control of that data and, so for example with Waze, you can now say it there’s a police moving speed camera somewhere. And do you think that’s a positive impact, the fact that we can now control these pieces of data ?

C : It’s obviously something very important, to have that capacity. Especially in contexts that I was decribing before. At Kardinal we are paying very much attention at keeping humans on board the system. Because once they lose control over it, and everything is automated, they can’t really check that the algorithm is doing something relevant to them. And especially, they lose so much understanding on what is happening that they can’t realy provide their expertise. They always have an expertise.

There is this short story of when we started to do what we’re doing. We were you know trying to challenge the tours of drivers and we were proposing our own optimized tours. They always had an example of something that the algorithm could not see. And a funny example is that, based on a very beautifully optimized route which was obviously the perfect way of visiting all those stops, and when the driver saw this, he was not focusing on the general aspect of the tour, which was kind of better than what he would have done anyway but he was really focusing on some specific stops. He was telling us : “okay, so you’re telling me I will deliver this person here, it will be 4:45pm, and here there is a school and I know that every parents will be parking in that street and I won’t be able to park myself to just make that delivery !”.

So okay, this is obviously mathematically optimal but I know that  this delivery at this specific time, just a 15 minutes interval, but it’s impossible to deliver someone in this interval. And this is really something, for those working in data, the cost of knowing that in advance to avoid that specific stop during these 15 minutes by anticipating that fact is very costly for us. And I mean, it’s pointless because we have someone in the truck knowing that already. So the key interaction we are trying to implement with them is : okay, you know stuff that we will never know, and we will never really try to know it because it comes out at a too great cost for us. So just give us that input, and you can challenge the algorithme even when you are on the road ! And what we are trying to do is that, many events can happen : it can be problems from the clients, from the data, anything, but we also consider that the user’s input is an event for us as well. And if you think that something is really better, you can choose to do otherwise than what we just suggested. What we will do is : okay, you take that decision, and this is the impact. We just reoptimize things, this is the impact, and then you can make an informed decision and you are really the master of your tour because you probably know stuff that we don’t know. So, to really answer your question, it’s really important that data and control over the data, because data itself, if you cannot understand it and you don’t have something that tells you what this data actually means,  it’s pointless to anyone. But once you are capable of giving insights on what the data means, on what the decisions you are providing, humans are not removed, they are augmented somehow. They take better decisions because they have information of the impact of our computations, and with the other things you have in mind, you can make the best decision possible. This is really what we are trying to achieve : the right combination between the two.

K : Yeah, and another sort of example I came across when I was conducting research for this was, in the US there was all the wildfires and when people were putting in their routes to try an escape these wildfires, obviously the roads where there were fires, Waze was showing them as clear and they were actually directing them through that way. So having a way of sort of adjusting that and avoid that area…

C : Definitely, because you know stuff, that are out of the context that the algorithm actually handles. So you need to really take that into account when you’re doing what we’re doing.

K : And Joannes, would you say, from a data perspective that we’re a bit too reliant on some of the large companies, the Amazons, the Googles, the Microsofts, they very much kind of dominate nowadays… Would you say we’re a little bit too reliant in some of those big companies ?

J : I would say probably yes but also the fact that technology is really fast moving so if you look at map data, there is not many providers worldwide. There is even the question is whether map data should be a common good, and by the way there are some people who are trying to do that with open maps and whatnot. But the reality is that when you have technology that is super fast moving, it’s hard for many companies to compete. Usually, when people say “winner takes all”, what they forget in technology is that frequently, things rotate swiftly, so yes, but it’s not the same winner at the same time. So, right now, for maps indeed, there is not that many players in the market. It’s very concentrated, but I see also plenty of changes where data that was considered, as you know, very hard to access, is now getting closer to be more like a common good with open maps and whatnot. It will take a long time, but what I suspect is that, with time, those things will become really like commodities. The problem will have moved to something else entirely. So yes, you will still have like private companies that dominates, but they will not be necessarily as strong as they used to be. So the bottom line is that right now, and Kardinal you’re probably on the front line for this, but for map data, there are probably like four or five players and that qualifies but indeed it’s still a fairly concentrated market here.

K : Okay and in sort of wrapping things up today, as sort of a final point : I think you are involved in research and development, you’ve really benefited from some of the advances in kind of AI in recent times. And what’s the real things from a research and development that excite you over the next couple years.

C : Well, first there are what we’re doing at Kardinal that excites me a lot. We have PhD students working on these aspects of, you know, solving the online version of you optimization, and they are really expanding the scope of operations research as a mathematical field, to new extents to really handle our problems in the proper way. But we’ve also seen other things happening in the AI community as a whole. There is stuff on reinforcement learning which is really a different approach of what we are doing with Operations Research. It’s somehow teaching algorithms what the best decision is, without telling it explicitly what the right decision is, which is very different philosophically from what we are doing at Kardinal where we are telling the algorithm what is global scope of possible solutions to a problem and telling it what is better solution than another so we can really focus on finding that solution inside a closed envelope of possible solutions. Reinforcement learning provides another way of doing it and probably very suited for real-time decision making. I think the limitation today of this approach is that it cannot really handle the variety of constraints we handle with our techniques, but who knows, we’ve been very much surprised with reinforcement learning could do in Go or even video games now. The can beat very strong players so this is really something we are following. And, it’s really prospective, but we’ve seen recently Google announcing QUantum Supremacy, that means having quantum computers solving problems in short times that are unavailable for normal computer that have to enumerate all the solutions. And we know that there are quantum algorithms that are suited for solving the Traveling Salesman Problem for example, which is one of our core problems, and they can solve in seconds optimally problems that would take thousands of years for a computer that will just enumerate. So this is also something we need to follow. Obviously this is very long term, and with our algorithms we are, by being smart in their conception, already matching the speed of quantum algorithms but quantum computing, somehow, yields at its core, a kind of democratization of making all these problems that are hard by nature, easy to solve. And this is quite something interesting for us because obviously, if our problems become easy to solve tomorrow, we will have to be on the front of handling this technology to help our clients perform much better than today.

K : Okay, brilliant. Well thanks for your time today anyway, it’s really interesting.

C : Thank you very much.

K : So, that’s it for this week. Thank you for staying to the end, and we will see you again next time. Bye for now !