CVRP

[Erik De Kuyffer]

Hello,

I am solving the CVRP in a bit of a particular way, as such to get an optimal route between different product installations (for example curtains), where the demand is equal to the amount of minutes the installation takes and where the maximum capacity = 480 minutes (8 working hours). As such, I get the shortest route for every technician, while he/she stays within the limits of working hours (capacity constraint).

However, now I would like to add two more constraints, being:

1° Some of the installations need to be performed by two people, others by one. When defining an array in which at each node (0 at the depot, 2 technicians at job(node) 1 and 1 at job(node) 2:

 data['num_workers'] = [0, 2, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2] 

I would like to add this constraint to the routes, in such a way that two routes can contain the same node, since it has to be carried out by 2 workers and the demand is taken into account at this node for each route.

For example: Vehicle 0 -> 1 -> 2 > 5 > 6 -> 0 and Vehicle 2: 0 -> 3 -> 5 -> 8 -> 0

2° Secondly, I would like to not use the total vehicle_capacity as constraint - in my case, the number of working hours should not be more than 480min. I would like the sum of the demands + the sum of the travel distance for a vehicle be less than 480min. So the the sum of demands + the sum of the distances must be lower than the vecile capacity.

Could you please help me?

Thanks,

Erik

[Erik De Kuyffer]

Hi again,

The second issue has been solved by using a Time Dimension.

However the first point is still open.

Would someone be able to help me. I would be eternally grateful. :-) 

Regards,

Erik

Op zaterdag 1 april 2023 om 17:12:45 UTC+2 schreef Erik De Kuyffer:

[Priidik Vilumaa]

Hi,

now I haven't touched the VRP solver in some time, but maybe you could:

1. duplicate the nodes that need 2 workers

2. constrain the duplicate nodes to be serviced at the same time. Can't remember if possible using the VRP solver. Search the mailing list

3. constrain the duplicate nodes to be serviced by different vehicles. Something like `VehicleVar(node1a) != VehicleVar(node1b)`

If 2. is not possible, then use CP-SAT. You have to model the problem quite differently, but you have more options in terms of constraints imo.

Best,
Priidik

[Erik De Kuyffer]

Hello,

Thanks a lot for your reply!

What I did is duplicate the nodes as a first step, as you requested

Then I worked with pick-up and delivery nodes, to keep the duplicated nodes together. Pick-up is at 1a and delivery at 1b.

For the final step, I don't seem to manage to keep all the duplicated nodes in one vehicle.

I defined an array with nodes that need to be visited by the same vehicle:

data['groups'] = [1, 3, 8, 13] 

These are all the nodes that have been duplicated btw, while step 2 makes sure that 1a and 1b, 3a and 3b, ... together, I want the following piece of code to keep de duplicated nodes together, so that I get 1 vehicle visiting nodes 1a, 1b, 3a, 3b, 8a, 8b and 13a, 13b

# Define Grouping Requests.

for i in range(1, len(data['groups'])-1):

routing.solver().Add(

routing.VehicleVar(data['groups'][i]) == routing.VehicleVar(

data['groups'][i+1]))

Could you tell me what I do wrong?

Kind regards,

Erik

Op dinsdag 4 april 2023 om 03:54:36 UTC+2 schreef vil...@gmail.com:

[Priidik Vilumaa]

Hmm, now I'm confused. 

In the original post you mentioned that you want the service (like installing curtains) to be sometimes done by 2 people. 

My proposed solution was to: 

1) duplicate the node (if done by 2 people). Or make 3 duplicates if 3 workers are needed etc.

2) constrain the arrival time somehow to be the same for job1_worker1 and job1_worker2

3) add a redundant constraint that says worker1 != worker2 for job1 (i.e. VehicleVar)

But why would you want to have the SAME vehicle doing both the duplicate nodes? The key is, as per my understanding, to have 2 workers installing the curtains, not 1.

Also, I don't quite understand how the "groups" should work in your code. The constraint you added says that node1 and node3 and node8 and node13 must all be done by the same vehicle. I don't think this is your intention?

But as a disclaimer, I am not sure at all that step 2 can be modeled (well) with the VRP solver. Now I remember Laurent stating in some thread that "inter-route constraints are very hard for the VRP solver". So, if I'm understanding your problem right, then I'd advise to use CP-SAT instead. Using CP-SAT for VRP is quite involved but you can base off the github example `jobshop_distance.py` or whatever the exact name was. I found this old thread, maybe it'll help you.

Best,

Priidik

[Erik De Kuyffer]

Dear Priidik,

First of all many thanks for trying to solve this issue with me.

May be I haven't been clear enough.

Some of the jobs to be planned are executed by one worker. To solve this, I take one worker per vehicle and don't duplicate the nodes.

However, some other jobs require two workers, but in one vehicle. Therefore I duplicated the nodes. For example? i then get a node 1a with a demand of 45 + a node 1b with demand 0... Both need to be taken into account since two workers are needed, but the demand is for the two workers together.

This means that node 1a and 1b need to stay together for 1 vehicle, since both workers visiting this node need to be in one vehicle and at the same node at the same time. Thus, to get the two workers to visit one node, I duplicate the nodes, but both nodes need to be visitred at the same time by one vehicle (in which there are two workers). To make this work in the VRP solver, I used the pick-up and delivery constraint, so that 1a and 1b stay together. Hope this clarifies the problem.

In a third stage, I want the same vehicle with the two workers to visit all the duplicated nodes. This way I can keep the two workers in one vehicle for all the jobs that need two workers (all the duplicated nodes).

In the grouops variable, I put all the nodes that are duplicated and I want to use the piece of code to make sure that all duplicated nodes are bvisited by the same vehicle, with the two workers onboard.

Hope it is more clear?

Thanks!

Erik

Op zaterdag 8 april 2023 om 03:05:47 UTC+2 schreef vil...@gmail.com:

[blind.line]

I haven’t followed this thread in great detail but I will try to go back and reread. However, I did implement something similar for a client. The number of workers in a vehicle was set as a variable in the solver. Since the number of workers in the vehicle affects the service time (2 workers is twice as fast, etc) I recall making disjoint tuples of nodes. Only vehicles with two workers could visit the one with half the service time, etc. The constraint was that at no time could the sum of crew in vehicles exceed the supply of crew members. Plus some vehicles could load 3 or more crew, others could load just one. Interesting stuff. 

However, to Priidik’s point, eventually I had to bite the bullet and recode everything in cpsat. The client wanted to track working time for crew, pick ups and drop offs of crew and so on and I could not get any of that to work in the routing solver. 

James

On Apr 8, 2023, at 03:28, Erik De Kuyffer <ede...@gmail.com> wrote:

Dear Priidik,

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/2b0822bc-34dc-46c9-ad10-e69476368b70n%40googlegroups.com.