Round Trips - VRP ArcGIS Online

[IhabElAttar]

We are using the vrp solver to optimize a fleet at real time where the startDepotName of routes is used to model the current driver position. We would like to know the best way to model round trips. In the map below we have 8 stops with two “round trips”. The relative sequence of each four stops must be preserved. In this scenario order pairs cannot be used for stops D-8057896 and P-8057898 since the first order is a delivery. Similarly, D-8057983 and P8058569 cannot be an order pair. Assuming we have one driver to visit the four locations to fulfil the eight stops, the only way I can think of is to split this into two routes. Each route represents one of the two round trips. Each stop will have to be assigned to a route and have a relative sequence. Please confirm that this is the right approach. The real problem with using routes to model round trips is when we have more than one driver available in the area. Using routes means that we will have to assign the routes to stops upfront to the drivers instead of putting the onus on the vrp solver to do the assignment based on the capacities of the drivers and their location with respect to stops. Is there any other way to address this situation without pre assigning stops to routes?

The business mandates that the pickups at 17250 Yonge  and 17360 Yonge Street are fulfilled before the drop offs and pickups at hill gate and alexander road .I do not see a setting in the api to preserve "actual sequence" on defined routes.

Please see the map below for your reference. I also attached a word document with the problem description for your reference

First Round Trip:

P-8057896 -17250 Yonge – Pickup

D-8057896 -789 Hill Gate - Drop Off

P-8057898 -789 Hill Gate – Pickup

D-8057898 17250 Yonge Street - Drop Off

Second Round Trip:

P-8057983 -17360 Yonge Street – Pickup

D-8057983 -31 Alexander Road - Drop Off

P-8058569 - 31 Alexander Road – Pickup

D-8058569 17360 Yonge Street – Drop Off

[IhabElAttar]

Following up with my question above, I created the request using two routes and one driver (driver one on the map above). Both the request and the outstops are attached.

Looking at the response,it seems that the solver honored the relative sequence but solved one route at a time. The solver did four trips  instead of  Three. We expected the solver to do the two pickups at 17250 Yonge and 17360 Yonge Street before travelling back east then west again to drop off.  Does the solver have to fulfill the stops of one route first before taking care of the second ? Cant it just address both routes at the same time ? Also this approach ,using routes and sequences, may not work for multiple driver scenarios

Please see the results below ordered by arrival utc

stop	route	seq	arriveutc	address
P-8057896	13	2	1612198926729	17250 yonge
D-8057896	13	3	1612198996382	Hill gate
P-8057898	13	4	1612217257686	Hill gate
D-8057898	13	5	1612217434684	17250 yonge
P-8057983	14	2	1612235257686	17360 Yonge
D-8057983	14	3	1612235434684	alexander
P-8058569	14	4	1612253623859	alexander
D-8058569	14	5	1612253973531	17360 yonge

[HeatherMoe]

I'm trying to understand your problem a little more. It seems like you are wanting one driver to pick up someone/something at location 1, drive to location 2 and then back to location 1 with that same person or item. Is this correct?

Is there a certain amount of time at location 2 that the person or item needs to stay there? and if so can the driver go to a different location to pick up a different order during that time or does the full round trip need to happen before the driver can do anything else?

If the driver is allowed to do something else while waiting for picking back up from location 2 is it possible to then have two orders on the vehicle at once or would a full pickup and drop off need to be done during that time?

When expanding the problem to multiple routes, is it a hard requirement that the return trip is done by the same vehicle/driver or could that be done by a different route in the area?

[IhabElAttar]

Hi Heather,
Thank you for looking into this. This is very much appreciated. Answers to your questions are below.

1. I'm trying to understand your problem a little more. It seems like you are wanting one driver to pick up someone/something at location 1, drive to location 2 and then back to location 1 with that same person or item. Is this correct?

That is correct. An example would be the driver picking up a certified cheque and location 1, needing it take it to location 2 to pay for the item they are picking up and then returning to location 1. The route cannot be done in reverse because location 2 will not release the item until the cheque has been received.

2. Is there a certain amount of time at location 2 that the person or item needs to stay there? and if so can the driver go to a different location to pick up a different order during that time or does the full round trip need to happen before the driver can do anything else?

The certain time the driver would have to be on site at location 2 is included in our request for service time (5 min). The driver cannot leave and come back before picking up the return. However, the driver could make additional stops in between – on their way from location 1 to location 2 or on their way back from location 2 to location 1. As long as trying to maintain the time constraints.

3. If the driver is allowed to do something else while waiting for picking back up from location 2 is it possible to then have two orders on the vehicle at once or would a full pickup and drop off need to be done during that time?

In this business case – the driver needs to deliver the cheque, then pick up the return in that order.

4. When expanding the problem to multiple routes, is it a hard requirement that the return trip is done by the same vehicle/driver or could that be done by a different route in the area?

Yes – the driver that does the delivery must also be the driver doing the return. If it was ok to have different drivers doing the orders, we wouldn’t need to actually link the orders in any way.

Please let me know if you have any other questions.

[HeatherMoe]

This sounds like an interesting use case and not something I've heard before. I don't think this is something fully supported by the VRP solver but something to try would be using two sets of order pairs, one going from location 1 to location 2 and one going from location 2 back to location 1. If on the routes you also add a small ArriveDepartDelay it will encourage the solver to stop at orders at the same location consecutively and by the same route. The ArriveDepartDelay will add time to the route for each stop the vehicle makes. If multiple orders are at the same exact location and visited consecutively the time is only added once because the vehicle only arrives and departs once for all of those coincident orders. This should encourage the drop off of the first order pair and the pick up of the second order pair to happen consecutively. It is certainly not a guarantee but maybe it will get most of the round trips correct and only a few would need adjusting by hand.