Need Help : Constraint on Max Travel Time in CVRP-TW

[abhijitdarekar]

Hi,

I've searched through available resources, but couldn't find what I needed. I'm working on a CVRPTW model for picking up patients and dropping them at a hospital. The hospital is considered as the depot, and vehicles travel through nodes within their time windows. Each vehicle can handle the same number of demands per day.

I need help with adding a constraint for Max Travel Time between nodes. This maximum allowable travel time varies for each vehicle from a regular node (patient) to the depot.

Where,
Max Travel Time (for Current Node) = min ( 1.3 * Time took from Current node till depot , Time to travel fromCurrent node to Next Node and then Depot)

Consider, there are three Nodes(X,Y,Z) and Depot D.
Required Output Route =
Case 1. D -> X -> Y -> D
Case 2. D -> Z -> D #ignoring this out as this does not have second node to visit.

In Case 1.
x = timeCumul( X->D) & y = timeCumul( X-> Y -> Depot)
i.e. the Cumul of y is less then 1.3 * x. ( within 30% of existing time vehicle covered another node and then came to depot.

#685 - I found this issue dated 6 years back andit was given for pickup and Delivery where pickup and drop nodes are specified to model beforehand but in case of CVRP there are no nodes specified as pickup and drop.

If possible provide code snippet as I'm new to the or-tools.

Platform Info: Ortools Version : 9.9.3963 in python 3.8

[Mizux]

1. First I would add a node for the drop e.g. for node X i want a node DX (which location is same than D)
2. Then I would use the Pickup & Delivery
3. since you have two nodes, now you can model your constraint:
   time_dim.CumulVar(DX) - time_dim.CumulVar(X) < 1.3 * "direct_travel_from_X_to_Dx"

[abhijitdarekar]

Hi @Mizux , Thanks for replying.

As , I have mentioned earlier the discussion, I don't know if this can be a pickup-delivery problem as I wend through multiple implementations/discussions this is a CVRPTW problem, where each node(pickup) has specific delivery nodes within given time frame.

This main goal is to collect patients, according to there scheduled time window(s) leave them to Hospital(depot). There can be different arrival time at Hospital(Scheduled Surgery Time like 8AM, 9:30 AM etc.), and number of patients at any scheduled time can change.(say 10 patients at 8AM, 5 at 9:30 PM).

Given the Capacity of Vehicle and Demands at Nodes, Vehicle once visits the nodes(picks up a patient) ,should be back to hospital with maximum of 1.3 times of drive time for first node till depot and 1 times for second node to depot.

As you mentioned above,

• Then I would use the Pickup & Delivery.

Does Duplicating Depot/Hospital Node for as drop node for every regular is useful is useful in this situation ?

If Duplicating nodes doesn't work, How can be regular nodes be consider as drop nodes?

• Since you have two nodes, now you can model your constraint:
  time_dim.CumulVar(DX) - time_dim.CumulVar(X) < 1.3 * "direct_travel_from_X_to_Dx"

The capacity of Vehicle is 3 , Does this constraint is valid for 3 intermediate nodes?

Any Suggestions ?

AD

[Mizux]

depot does not exist from the solver point of view, solver need a unique node index for each vehicle start and end. So if you don't have a duplicating Depot/Hospital how can you find the correct vehicle end index to use since you don't know which vehicle will pickup the patient ?

the constraint force the delta time aka duration between patient pickup and patient delivery (at hospital) wherever if there is 0 or 10 000 nodes in between, so if you have this constraint for any pair then you guaranty that all patient will have less than 1.3 * direct route travel time from pickup to hospital.

For the capacity constraint simply add a capacity dimension in addition to the time_dimension.
merging a cvrptw samples with a p&d should be straightforward don't hesitate to join our discord if you are facing some implem issue and/or share a gist with your attempt

[abhijitdarekar]

Hi Mizux,

Here is the Gist of m attempt, I have attempted i believe it not correct way.
https://gist.github.com/abhijitdarekar/12285409869485450aba0fc6f8144a5e.

I have Understood the Above Points and I have duplicated the nodes for each corresponding regular nodes for p&d.
Kindly Tell me if I need to change/add anything.

Thanks,
AD

[Mizux]

My Gist based on your but using main branch (so pywrapcp has been replaced by pywraprouting etc..)
https://gist.github.com/Mizux/36a87040af87eb9c5324d49224f709ac

I also updated the print function to have more data display...

However, one error spotted: distance callback

    def distance_callback(from_index, to_index):
         from_node = manager.IndexToNode(from_index)
-        to_node = manager.IndexToNode(to_node)
+        to_node = manager.IndexToNode(to_index)
         if from_node in range(data["duplicate_nodes"], data["num_Locations"]):
             from_node = 0
         if to_node in range(data["duplicate_nodes"], data["num_Locations"]):

Also you can use the AddDisjunction([pickup, delivery], penalty, 2) instead of two disjunctions.

[jmarca]

My two cents, having done exactly this in the past, is this approach works fine up to a point. I started to have trouble when the patients hit the thousands per day scale.  Then I had to start partitioning the problem. (Then eventually the startup who hired me pivoted so the project ended.)JamesOn Jul 3, 2024, at 01:46, Mizux ***@***.***> wrote: depot does not exist from the solver point of view, solver need a unique node index for each vehicle start and end. So if you don't have a duplicating Depot/Hospital how can you find the correct vehicle end index to use since you don't know which vehicle will pickup the patient ? the constraint force the delta time aka duration between patient pickup and patient delivery (at hospital) wherever if there is 0 or 10 000 nodes in between, so if you have this constraint for any pair then you guaranty that all patient will have less than 1.3 * direct route travel time from pickup to hospital. For the capacity constraint simply add a capacity dimension in addition to the time_dimension. merging a cvrptw samples with a p&d should be straightforward don't hesitate to join our discord if you are facing some implem issue and/or share a gist with your attempt —Reply to this email directly, view it on GitHub, or unsubscribe.You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[abhijitdarekar]

Hi James,

Thanks for Suggestion, I will keep this in mind.

Just as you mentioned, you have implemented this, Can you let me know how to tackle this problem in case of either CVRPTW or P&D.

Thanks,
AD