topic Re: Topic Suggestions for Fleet Routing with the VRP Solver in ArcGIS Network Analyst Questions

Topic Suggestions for Fleet Routing with the VRP Solver

HeatherMoe — Mon, 17 Sep 2018 17:14:58 GMT

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.

Re: Topic Suggestions for Fleet Routing with the VRP Solver

BrettGovernanti1 — Fri, 08 Feb 2019 20:45:16 GMT

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?

Thank you,

Brett

routing‌ #vrp

Re: Topic Suggestions for Fleet Routing with the VRP Solver

HeatherMoe — Mon, 11 Feb 2019 17:27:10 GMT

Hi Brett,

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.

Thanks,

Heather Moe

Re: Topic Suggestions for Fleet Routing with the VRP Solver

BrettGovernanti1 — Mon, 11 Feb 2019 23:37:29 GMT

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!

Brett

Re: Topic Suggestions for Fleet Routing with the VRP Solver

Rafaelde_Oliveira_Casagrande — Tue, 12 Mar 2019 15:01:40 GMT

Hello Team,

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?

Thank you,

Rafael Casagrande

Re: Topic Suggestions for Fleet Routing with the VRP Solver

HeatherMoe — Tue, 12 Mar 2019 20:00:43 GMT

Hi Rafael,

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.

Heather

Re: Topic Suggestions for Fleet Routing with the VRP Solver

Rafaelde_Oliveira_Casagrande — Wed, 13 Mar 2019 21:07:06 GMT

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?

Thank you,

Rafael Casagrande

Re: Topic Suggestions for Fleet Routing with the VRP Solver

Rafaelde_Oliveira_Casagrande — Thu, 14 Mar 2019 17:39:38 GMT

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,

Rafael Casagrande

Re: Topic Suggestions for Fleet Routing with the VRP Solver

RongJing — Fri, 09 Aug 2019 20:00:33 GMT

Hi Heather:

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!

Rong

Re: Topic Suggestions for Fleet Routing with the VRP Solver

HeatherMoe — Fri, 23 Aug 2019 13:33:49 GMT

Hi Rong,

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,

Heather

Re: Topic Suggestions for Fleet Routing with the VRP Solver

BushtelAdmin — Sun, 09 Feb 2020 09:14:48 GMT

G'day All

Bus routing would be of interest or do people use other software for this task? I see a few posts from circa 2010 with references to ArcLogistics (https://www.esri.com/library/whitepapers/pdfs/k12-school-bus-routing.pdf ). Also took a while to find the High Density Routing tips. Surprised not more questions or maybe it's easier to do than I think

This would be multi layered:

- Selection of bus stop locations (pretty much fixed though would be interesting to see)

- Route school buses

- Route public transport buses (I guess same method, just different input)

- Route trip to school using public transport bus and school bus (throw in a train or ferry for bonus points)

- Optimize bus numbers across depots

- Driver schedules

- Costing figures to run buses under different scenarios

I've just started exploring VRP and still on a steep learning curve. Likely have missed some points above.

Some areas we have to route are relatively small, with few roads, so the route is 'obvious'

One thing that hasn't jumped out at me yet in my initial testing has been how to handle the scattering of students that live near each other and go to different schools. I have assigned all students from one school to one (or two) route. Depot to students to school to depot. All students in that area go to the local school. Thinking as I type this, I guess I'll just make student routes with interchanges vs having a bus dedicated to a school. I'm sure the bus people here will have ideas ... they are doing the routing already!

Thanks

Re: Topic Suggestions for Fleet Routing with the VRP Solver

HeatherMoe — Wed, 26 Feb 2020 18:39:31 GMT

Hello,

Thank you very much for your interest. We are planning a demo on school bus routing and will work to include as many of your topic points as we can.

Thanks,

Heather

Re: Topic Suggestions for Fleet Routing with the VRP Solver

BushtelAdmin — Mon, 27 Apr 2020 01:50:27 GMT

G'day Heather

Apologies for the delay ... now have some 'spare' time.

Another aspect of the routing we have yet to resolve (and haven't broached just yet) is when to have a student change buses (the scattered students point from above)

At the moment we have order pairs for all students (well subset to start with) from home to school and then throw at the VRP solver.

For various reasons, there are some students far from their school and it appears to be an inefficient use of the buses.

I suspect mainly a learning curve thing; ie setting up routes vs what routes a student should take to get to school.

I assume either changing buses along a route or at a dedicated interchange is not a VRP issue?

If we manually decide what interchange a student should be paired to, we would still need to manage the time windows that a different bus would leave the interchange at a time the arriving student could catch.

And one more aspect we have yet to tackle (and have seen something the touches on it) is spreading the load across routes. This is probably a low priority for us as currently more interested in the optimal cost routes.

Regards