Google Maps and Google OR, Tools for Route Optimization - Emad Ehsan - GDG Sacramento

hello everyone i am i am a google developer expert for pakistan and this talk is about using google or tools and maps for a route optimization so just recently i had the experience of working with a startup in lahore that does a fresh fresh goods delivery to shopkeepers and lahore is a really obvious and old city and if you would look at closely at the photo of the map you can see most of the streets are closed and it so it's really difficult to navigate in such a congested and most of the times undocumented area but since google maps has covered everything so most of the streets are on google maps and they were facing the challenge of uh optimizing the route for the delivering the goods daily to the shop owners and there were a lot of options to select from so usually the top silicon valley startups that work in root optimization and delivery domain like only and rockefect are usually not considered as a viable option because they are really expensive compared to uh for the startups were working in developing countries and like in pakistan india and also probably most countries in africa so we ended up for the time being for the time we ended up relying on and on a really cheap solution that would use google apps behind the scene for optimizing the load and group that each vehicle has to carry and follow to deliver the goods and that inspired me to look into what actually happens behind the scenes on boot optimization and before that i did not have any experience in optimization so and also since the start of it there have been a lot of volunteer projects uh trying to be helpful with all the code 19 situation and as bill gates also mentioned that we'll probably have the next scene next year but we can start the efforts uh regarding logistic efforts probably regarding vaccine delivery to dangerous and on even probably more areas right now those efforts in order to scale those efforts we have to start thinking about the logistics problems right now so there was also an inspiration about probably building some open source rule with a couple of friends that could do root optimization not only for like in urban areas but it would also probably some really remote areas where you have access to fuel so usually vehicles [Music] behind all the logistics of doing group optimization so i stumbled on traveling salesman problem and it is a classic algorithm study in operations research or integer programming so these are the domains of mathematics and computer science that deals with that deal with optimization algorithm so traveling salesman it turns out is a classic and comparatively basic algorithm and it the major uh the most popular variation of traveling skills tries to find the shortest or to visit all the cities or all the locations in a closed path and there are also variations where you visit so the main data that is the input data required for solving traveling solves the salesman problem is of the distance matrix it's a 2d array of containing the distance between all the cities and for example the the table in these slides shows the distance for a few chinese cities that i calculated um for a cycling rule actually but hey you here on the left if the cities are listed on the left uh if you traverse to the table and was derived you get the distance from the city on the left to the city on top for example xi'an is 1724 kilometers away from and in order to calculate this distance google offers uh different metrics that are part of google maps platform and you can use these apis to calculate the distance between the cities or even the locations within the cities using google direction api so hey you simply you can actually recall you provide your key and you give it the origin of the city also for the original locations to the cities for which we want to calculate the distance metrics so uh in this slide the listen the origin series would be the cities listed on the left and the destination cities would be the cities listed on the top they are the same cities but we want to get from every city to every other city and this is the major input that we need for solving distance sorry travelling and problem was and also for root optimization so we could take every possible day and that the google search is about traveling salesman problem left directly to google or tools and understandably they have done a great job with so you can optimization improve just from the stock sheets you can model that problem really easily with the help of google who are rules and they film in python sleeplessness you you can model your problem in python java and c so values of course the software uh that optimizes that finds the optimum or feasible solution for us and the variables so for example uh for the follow on the right the variable would be the in the the values required to describe the shape so they could be the coordinates in the system and the variable and the objective our objective would be for example find the point that is an equal distance from all the edges all the vertices of this here and the constraint would be probably you could [Music] using our tools apis or who would be able to find a review there are approaches uh traveling salesman problem and other optimization algorithms so defining decision variables right the right way is um question because they are used by the uh by the solver to find the optimal solution and for the traveling salesman problem with a decision variable could be a 2d array containing ones and zeros and let's say that julia and his so the solution of our family salesman problem would be from and the constraints are the rules uh that must be respected [Music] uh for example for previously all the city is supposed to be visited and a city must be visited only once so the the second constraint is used in the most common variant of traveling but there are some other variants that are lenient on this route where you want to find the minimum path no matter if you have to repeat the city and the objective is of course the goal of your program so obviously it is to minimize the distance that you have to travel and in uh traveling salesman problem the distance is distance is usually traveled by this one legal or one unit uh i wrote cyclists here because actually i took this slide from the work i was doing on optimizing loop for cyclists that brings us to weaker routing problem and the most basic uh weakened volume used with delivering goods from the people uh go down to the customers the customer locations and you have multiple vehicles in this case and the people have uh go out from the right and they have to come back to the regular if you reduce the number of vehicles in legal routing problem then it becomes the simple case of travelling salesman problem where it is only one visiting all the moves in um while traveling the minimum distance so uh for this problem uh i took this diagram from google or website where they describe the uh routing problem and so let's say we have the uh that is zero kilometers from itself so but [Music] [Music] [Music] problem [Music] and hey you can you simply you just need to install what's all the libraries are already installed for you and we do the necessary imports the the most important is the pirate cp which is the series for solving the legal mounting problem and in the traveling salesman problem that we discussed there are a lot of ways to model model that problem using all tools where you describe your decision variables you describe your constraints and you also describe your objective but in the case of weaker or important google provides is the distance metric the major input so it specifies that the table in the shape of a 2d array and contains the distance from all the series to the results and other cities and we also specify in our variables the number of uh vehicles so in this case they are four and the index of it is zero so uh the first the first row contains the distance of from all other nodes and uh the rest are the sensors of the nodes that these classifiers [Music] so we define a friends print solution function where we take the data manager solution these variables uh so the manager is a variable that is the format that is used by the the software here we are specifying the uh information about how to print the solution uh the actual code that does the root optimization is here so here we are getting the data model that we just saw about the distance plus the information about number of vehicles and the depot so we created our routing manager and we provided the data and you can see here we have built-in methods just for solving vr uh figure out and if it is registered uh transition callback to the task of this folder is to it and we use that to extract the distance for the for the nodes in between which the distance was uh requested so this function will be called multiple times by the solver while trying to find an optimal solution for the problem and it the solver would provide the indexes between which it is using that distance it will try to solve to find an optimal solution for uh root optimization here we register that object and in the documentation uh about how you specify the the transit callback so the distance callback that provides the distance between cities that is mutually registered as and the dimension right here we are adding the distance dimension so dimensions in this root optimization solver are the variables that accumulate over time so you can think of them as so let's say when you are considering the distance so and a vehicle has to visit five nodes or cities or locations so once it visits uh it goes from city a to b and then from b to c between b and c so uh distance another dimension in the case of optimization algorithms would be the time [Music] so these are the these are the variables that are completed and we are looking to optimize uh find the minimum possible values for these dimensions so we could do root optimization effectively and here we set that dimension and so first solution heuristic is being set here so the first optimal solution that is [Music] print function that prints them in this section so uh i'll share the links to this google code all of the code is actually taken from the qualcomm's foreign that was written by the solver so looking at it gives us a pretty good idea that probably it found it was able to find a solution where nodes that are near each other they would be assigned to similar people but that is not always the case sometimes the solutions are not as perfect so you have to keep running the program uh furthermore so you don't you don't rely on first solution here is the second variation of weaker routing problem is usually the capacity constraint in which we also look at the demand so the demand of that is to be delivered to each node so for basically for this uh diagram and for this example let's say uh the load that we have to carry to each customer is in kg so we are only dealing with so probably even if the load has a different size it can fit into a vehicle or not uh for this variation we are not interested in that uh we are more interested in let's look at how we would do [Music] so because we are looking to optimize the distance but we are also looking for a way to optimize the the capacity that is to be carried to each customer so this demands variable this is an array a list that contains uh let's say engages from the metric tons how much foods are to be delivered to [Music] the vehicle capacity so the task assigned to each vehicle uh the the load assignment must be less than or equal to its capacity and for this we have four vehicles [Music] here we define the solution predictor but we are more interested in looking at how we define the capacitance capacitance so uh the distance called the is similar to the previous variation but we also have a demand call where we give the index of each node on each customer and it returns the load here we again set the first solution heuristics to find the first uh solution meaning finding the best and i am not a lot educated on guiding local search i am pretty new to optimization algorithms but yeah [Music] so one thing that we might want to look here is that here we are giving it zero so uh even if a vehicle is assigned so in the testing i think it was regarding the even if a vehicle is not assigned anything and any task that is okay so you do not have to so using the solution printers the the output provided by the routing looks like this so i'm not uh i'm showing you the previous output but once i hear this you can run and check the data live make changes to it so here we start from zero this is vehicle zero so we start we go to [Music] and so the solution would look for this problem uh like this so here are will be mounted to the solution that our demand constraint should also be effectively and here you can see the boot does not look as perfect as it looks in the previous case but it pushes the customers [Music] we so so same like previously we have our distance matrix and here we also define the pickup delivery so this specifies the you can think of each row uh in the story matrix as a pickup plus pre-order and the values specified from which node we have to pick and uh which node we have to deliver that and this variation is a really simple variation that just involves pickup and and here we also satisfy the number of people are going to be blue sorry for and in order to specify this problem uh once we register this callback so here we define the pickup and delivery order to the solver so we take the nodes the complete apis for this variation and we give it the index is there any question [Music] so we give it the index of the pickup location to the delivery location and here we are letting it know that for a vehicle that a single vehicle has to carry this pickup and delivery order so we are adding the constraint that is [Music] [Music] must be less than the combinative distance covered in the delivery point of view so this ensures that uh any every route con any house does not uh suggested by the software does not continue where we and also here we are defining the first solution characteristic and for this variant the is the output given by the program let's see it visually here so the same vehicle is responsible for delivering if it picks up from from a location it delivers it to the location for that order so let's focus on node 1 6 and 7 e you can see we have to take something from node 1 and deliver it to 6 and 0 4 7 and 8. [Music] it takes up the load and then it visits node six drops the load pick up from location one and then it visits drops the second node so it is not it is an efficient rule so from a really basic solver that usually uh for example i was working with the solver that was not able to do it it would uh pick from one location drop that order first then it would go to the pickup location for the other order and the third and uh sorry the fourth and last variation that we will be looking is the time window constraint and it is very similar to [Music] [Music] period so let's look at the code for it so unlike the previous problem here we had a distance metric for a bigger loading problem with time window we have a time matrix and the vehicle has to depart from between 7 and 12. specifying the time interval as time you can probably think of them as pause of the day so between 7 00 am till 12 pm we have to visit this node with the load and again we uh specify four vehicles and the depot is node zero so solution printer let's move to the code for time window vip so before we specify we used to specify time for distance callback if it would return the distance uh between two nodes here we specify the time callback it returns the approximate distance and we are registering in this transit and here we are allowing 20 units of waiting time and maximum so this in the case of if you specify uh it makes them allow the waiting time to be zero uh for the case of distance uh it would allow the vehicle to even if a vehicle is not assigned any tasks that will be okay uh but for the uh the second uh actually the third argument is [Music] in this case this time cannot be exceeded the task should be complete in these units of time and set that dimension and here we go for each location but we exclude the people location uh that's because the those vehicles have to return back to people after completing their tasks and so and uh next please specify the instantiate so air variable minimized by finalizer we have the time dimension so this is time dimensions must be minimized for each speaker but we are also specifying both the start and the end so because we have that range [Music] [Music] and so effectively reaching those nodes uh the link you will just do that in the slide and i'll probably get [Music] i'm going to replace it in chat yeah so you can see that there are a couple of questions in the chat if you want to take a look at those and answer them now [Music] optimization uh let me show you the very simple variation from the my previous talk that i did just on the nodes and uh so but we visit them using only one vehicle and uh so the simplest form of figure routing problem is simplified to even more here and maybe and we are not returning to the starting location um i do not have the visualization for multiple vehicles on the map but probably this will give you an idea i calculated this route using the maps metrics api and maps for a cyclist group that is planning to travel on the road next year so they'll be traveling from [Music] used in this so uh probably this gives an idea about because in real life the the parts are not in straight line they are passing through multiple locations streets highways and a lot of other locations yeah that would be [Music] if uh uh while designing our optimization service we cannot only rely on our tools we also have to build some other services on that so for example all the root optimization services like monthly routing and probably token they all use state-of-the-art mobile apps to try to travel those management software uh for further reading i would highly recommend protective practical python uh on linkedin and on twitter that's it from my side all right thanks a lot for your talk um i do have one question for you one one follow-up question so you use a distance matrix api to get all of the distances between the locations um does that distance matrix api take traffic into account can you specify your time frame when this has to happen or not yes so they do specify the time and the current current traffic so google has this awesome service called routing it's part of the google maps platform and here you you can use this service to take real-time information about the route that you want to take so the traffic current traffic uh situation and also the distances so it's available under the roofs under google cloud okay perfect and um so the matrix distance api it's it's on the web right i can i can create some code that's gonna call it get a response from it the optimization tools are all offline uh it is there an online api for those tools meaning could i build a solution where i just make calls to different google apis and build a solution based on on that or would i have to mix some remote calls to to the google apis and some offline stuff with python like you did here so uh uh if i understood your question correctly uh you mean that do we have to call the message api uh for every problem or can all the calculations can i do everything online or everything offline i guess yeah so for the second question doing everything i think that google does not provide the complete solution themselves [Music] so so you all the services that are built you usually rely on the mix of business metrics and these routine service part of google cloud okay perfect do we have any other questions from the audience looks like we are all good so thanks for not iman for your talk that was very interesting and i didn't know that there was all of these optimization apis now um i played with the routing a little bit years ago and back then it was just a distance matrix api there was pretty much nothing else so knowing that now they have all of these different things that take into account uh um constraints so all of the different examples you shot that was pretty interesting to to learn about so thanks a lot for your time thanks for giving us this talk and we are going to to publish it on youtube very soon so thanks again thank you for having me and take a pleasure preparing it and presenting it thank you thanks a lot and thanks everyone for attending tonight

Channel: GDG Sacramento

Views: 2,396

Keywords:

Id: PzDjViiDMLY

Length: 52min 3sec (3123 seconds)

Published: Thu Nov 12 2020