The team that works on the Vehicle Routing Problem (VRP) Solver has started a blog series to dive deeper into topics and help explain how best to model with the VRP solver. We have a list of topics we think are important but the most important ones are what you would like to discuss. Please respond in this thread and let us know what topics you would like us to dive further into on the VRP solver.
Hello VRP Blog folks, I have a series of address point that need to be visited for a utility billing application. This would be easy with the VRP but there are more than 1000 points per district. Is there a method where I could split the large number of orders to <1000 and create individual routes as necessary to complete the overall route for that district? The key will be to find the last stop on the first group of 1000 and send the route to the fist stop on the second group of 1000, and so on. Are there any ideas out there about how to string 1000-order routes together using NA? Can Backhaul do this sort of thing?
That sounds like an interesting use case. Are you intending one vehicle to drive to all locations within a district in a single day? And so want a single really long route. If so you might be able to just the route solver with it reordering the stops to find the optimal sequence.
One thing I would definitely recommend no matter if you are looking to solve this with route or VRP is to consolidate the stops on a side of edge to a single point. I'm guessing being a use case for utilities that you are planning on visiting multiple buildings on a single block. This creates a very dense problem that we are not optimized to solve. We have had some users have success by consolidating them though. So if you take all of the orders/stops that are on one side of the street and consolidate them to a single point that accounts for the quantity and service time to visit all of them and give them a right side of street curb approach. Do this separately for each side of the street if you need to drive down both sides or you could consolidate the whole street into one location if you can drive down the street once and visit all stops. This will typically reduces the problem size drastically and also provides better results from our solvers.
For stringing the routes together... You could solve the problem first with all of the orders in the problem and the single route starting at your depot and having the ending depot left as null. This will end the route at the last stop. Next you could create a problem removing the 1000 stops that were visited in the first solve and have the starting depot as the last stop of the previous solve again leaving the route without an ending depot. Continuing on in this iterative solve way until all have been routed.
Hope this helps. Let me know if you have more questions or need something clarified.
Hi Heather, great idea on stringing the routes together! Yes, each route is driven by one truck per zone, per day. The truck receives utility information from ERTs of different wattages at each home or business. The stronger the ERT wattage, the further the truck can be from the target to pick up the signal. This is convenient for the driver but it makes for some really large zones, with many targets. I did try reducing the number of targets down by way of consolidation but found it to be a time intensive process and any savings I attempted seemed to cause missed streets. I will try your iterative process, very promising. I can let you know how it goes. Thank you!
I'm modeling a network to provide the truck dispatcher, pickup and delivery of goods. I've noticed that the VRP Courier/Rideshare model can be applied to solve the problem. Do you have any documentation or examples about solving a problem using the Courier/Rideshare model?
Thanks for sharing your use case. Looks interesting. To accomplish the Courier/Rideshare model you would use order pairs. Here is our basic VRP documentation. If you search for "Order Pairs class" you will move to the part of the doc that is about the Order Pairs to get some more information on them. It is pretty far down the page.
There is also a tutorial for setting up a problem with Order Pairs. This will walk you through the steps and provide a bit more discussion on different settings you can adjust. Exercise 8: Finding best routes to service paired orders.
Hope this helps and reach out if you have some more questions.
Hi Heather, thank you. I've created and loaded an Order Pairs table and I was able to solve the Route but I'm looking for a way to solve the Route without an Order Pairs table: In this case I need to route the shortest path between each pickup and drop points automatically. Do you have any suggestion, please?
Hello Heather, I was able to find a solution: First, I created a Closest Facility and It returned me an Origin-Destiny table between the pickup and drop points. Next I imported the result into the VRP Orders Pairs.
Now I have the shortest path for the truck dispatcher, pickup and drop points.
Thank you for the help,
Can VRP be used for dynamic routing problems that provide on demand service? for example, Uber type ride hail service?
I have a set of demand profile that is historical taxi trips of one day. The data has pick up and drop off locations as well as hailed date time. I want to answer questions like how many vehicles needed to fulfill all the trips, total miles driven, etc.. In VRP, I use historical trip data as OrderInputs and OrderPairs, I also inputted a fleet as RoutesInput. But the outputs show that the vehicle will go to next pickup location after completing previous trip and wait for the next request to come in. So it is treating the demand as pre-scheduled and it is kind of perfectly predicting where and when the next request will be.
In one of your blogs, you said VRP can be used for courier/ride share - "A courier company picks up packages and delivers on demand for their customers. Sometimes there is a time window for deliveries". Can you point me to some specifications/examples on how to model on demand in VRP?
Thank you very much in advance!
For on demand type work flows, I would recommend getting an initial solve of the problem from what you know at the start of the time frame. Then as new orders come in (depending on the frequency of this you might wait until a set number have come in or a set interval of time has passed) you resolve the problem. The depot locations can be changed to the vehicles current location, the orders already completed can be removed from the problem, and if orders need to stay on a specific route because say the product for it is already on the vehicle then you can change the assignment rule for the order to preserve route. The next solve will then try to optimize with the new state of the problem.
Hope this helps,