Originally posted by: schmeich

Hey guys,

i am currently working on a project in which i need to solve a kind of rich VRP using CPLEX. Unfortunately I never had to use this program during my studies which makes it somewhat hard for me to get into. I am already trying for a week and not making any progess. I dont know if this here is the right forum for problems/tasks like this but i didnt find any others. If there are such, please dont hesitate to link me forward.

 

I need to generate a VRP model with TW and some other contraints. I try to explain it with a practical example. A nursing service has a depot 0 and needs to service a certain numer of patients n. Each patient has only one timeframe in which he or she needs to be serviced. This sounds like the standard VRP for me until here.

As I understood the VRP each patient has a demand of a homogenous good. Yet in this case, the demand of each patient needs to include gender and skill level of the serving nurse. (Some old ladies dont want young men for example). Logically each nurse needs to have gender and skill level as attributes. As well as 8 hours of working time shall not be exceeded.

 

Objective shall be to minimize the cost in form of time and vehicles (nurses) needed.

 

I did already find a template for the VRPTW on github which seems for me to be useful and that only certain contrains need to be added.

 

https://github.com/afurculita/cplex-vrptw-implementation

 

I am not a pro in this topic and I do have great respect for ppl who are. I am kind of desperate trying to solve this issue. I assume it is very easy for Pros like you guys are around here and that you will help me.

 

Thanks so much in advance for your effort.

 

Best regards

 

schmeich

 

 

 

 

#CPLEXOptimizers
#DecisionOptimization

How are you trying to solve this? Are you using OPL (like in the template you quoted) or a programming API? Are you using docplex?

#CPLEXOptimizers
#DecisionOptimization

BTW, did you look through the various OPL examples that come with CPLEX? Also, did you check the tutorials in the online documentation?

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: schmeich

Yes i watched youtube videos fo the examples and so on. I am a little bit familiar with the programm for now. But my studies are business and not computer science and therefore  dont have any clue 

#CPLEXOptimizers
#DecisionOptimization

What I meant were the examples, tutorials and walkthroughs that are in the official CPLEX documentation. For example here and here.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: schmeich

Wow thanks for this fast answer.

Well as I said I am a total newbie and my university simply wants sth from me which i am not studying haha.

But yes i am supposed to use this OPL programm. i have no idea what the others are

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: schmeich

Thanks for the link. Indeed I tried out some of those but as I mentioned. Hasnt gotten me any further until now. Of course I am still trying to learn but also I thought it might be a great help here to understand better and find the solution

 

best regards

#CPLEXOptimizers
#DecisionOptimization

If I understood your problem description correctly then you only have to add a few constraints to the model you quoted. Consider for example the requirement that some customers require the nurse to have a particular gender. This can be modeled as follows:

First define the gender for each vehicle/nurse:

int Gender[Vehicles] = ...; // 1 = male, 2 = female

Next define the requirement for each customer:

int RequiredGender[Customers] = ...; // 1 = requires male, 2 = requires female, 0 = no requirement

With this you can state the a nurse can never stop by a customer unless the gender requirement is satisfied:

forall(i in Customers, k in Vehicles : RequiredGender[i] != 0 && RequiredGender[i] != Gender[k]) { // for all vehicle/customer combinations that do not satisfy the gender requirements
  forall(j in Customers) {
    x[k][i][j] == 0; // vehicle can never start from i
    x[k][j][i] == 0; // vehicle can never end in i
  }                   
}

It should be possible to handle the requirement for a certain age of nurses similarly.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: schmeich

Well thanks a lot for your help. I thought so too, that only a few constraints need to be added to the model and thats it.

 

I will try to explain the model again, how I understand it:

There is a nursing service which provides care for patients. All the nurses start from one Depot and every patient needs to be serviced within his/her time frame.

The demand of patients is not only one homogenous good (care). It differs into normal and special care. In addition to this the gender of the servicing nurse needs to be considered. (e.g. An old lady most likely doesnt want to be treated by a young man; there might be exceptions haha). Last but not least, the working time of a nurse must not exceed 8h.

 

This is the model for my understand should not be too hard to make. Where I do have difficulties in understanding is for example: 

-The VRP normally has a capacity constraint and the patients a certain demand of this homogenous good. In this case there is no such capacity in my understanding, because there is no such homogenous good. Only the patients need to be visited by a certain nurse with a certain skill. I thought maybe capacity in this case is the leftover working time or sth. like this. This is where I dont know any further.

- Also I need to simulate the data which is not too hard. Yet, I am uncertain if I do have X and Y coordinates if the distance between each nod is being treated as actual working time having in mind the 8h cant be exceeded

 

I hope I made myself a little bit more clear but I am also sure that I sound somewhat desperate haha

 

Thanks in advance again

 

Best regards

 

schmeich

#CPLEXOptimizers
#DecisionOptimization

I am not clear what you are missing right now. Isn't the skill requirement similar to the gender requirement and can be modeled in the same way? Probably a nurse has more than one skill, so instead of representing the skill by an integer you will have to use a set of integers. But that is the only difference I see right now.

For the 8h working time limit you indeed have to sum up the travel and the service time for each nurse. This is similar to the capacity constraints you mentioned. Assuming the service time for a customer i is given in ServiceTime[i] you will have a constraint like this

forall(k in Vehicles)
  sum(i in Customers) (ServiceTime[i] * (sum(j in Customers) x[k][i][j])) +
  sum(i in CustomersAndDepots, j in CustomersAndDepots) F * Distance[i][j] * x[k][i][j]
   <= 8 hours;

where 'F' is some factor that converts between distance in meters and travel time.

Maybe you can also check with the faculty staff for help? Since they know your problem they may be able to provide more specific help. They may even help you with OPL.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: schmeich

Hi Daniel,

thanks again for your big help right here. 

I attached an Excelfile with the simulated data i made for the patients. Included are the X and Y coordinates, time frames and necessities of gender and skill.

At this point now I am wondering if i need to simulate data for the vehicles/nurses. I would say no since my intention is to get the optimal solution of how many vehicles/nurses with the mentioned attributes i will need. Is this correct?

In a next step I would then need to adapt that a nurse can only stop at a patient when the skill requirement is satisfied.

 

What do you think?

 

Thanks a lot again.

 

Best regards.

 

schmeich

 

#CPLEXOptimizers
#DecisionOptimization

You will have to create data for the nurses since the model you picked assumes that you have a pool of nurses from which you can pick. The model attempts to satisfy requirements at minimal cost with a given pool of vehicles/nurses.

If you don't have a concrete pool of nurses then one thing that may work is to create one nurse for each customer. This ensures the model always has a feasible solution and optimizing should select the best set of nurses.

Unless you are optimizing over a give pool of nurses you probably want to extend your model by a boolean variable for each nurse that specifies whether you "hire" this nurse at all. Typically a fixed cost will be associated with this variable. This is the most flexible model. With it you can for example

• minimize the number of nurses: set the fixed cost for each nurse to 1 and ignore the cost for travel/service
• minimize the service cost with a fixed pool of nurses: set the fixed cost for each nurse to 0.
• minimize total cost by summing up the costs for hiring and service.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: schmeich

I might have gotten a little further but still having problems modelling

 

I was thinking that my problem is VRPTW with a heterogenous fleet. In literature also knows as the Split Delivery VRPTW.

I was thinking that the capacity constraint stated in the model mentioned above can be eliminated since the capacity is unlimited, except for the working time.

Therefore there should only be 2 additional constraints stating the Gender of the fleet and the Skill level? Is this correct?

I am a little confused about the capacity. Does this need to be modeled with the working time?

 

Thanks a lot in advance.

 

Best regards.

 

schmeich

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: schmeich

Hey Daniel,

thanks again man. I appreaciate your help. This is the fact which I was missing in my previous statement.

So the model above assumes a pool of nurses and optimizes cost with this exact number of nurses? I was thinking about this, how many nurses I am giving the model itself. I thought that the model wiill give me the optimal solution in form of optimal time which also includes the optimal number of nurses needed to achieve optimal time. Isnt this correct?

Therefore for example, if i give a pool of lets say 7 nurses will the model use all nurses or would it also only use 5 if the solution was better?

This is the point where I am lost again.

The thing with the extra boolean variable you mentioned sounds like the perfect solution. But I am pretty sure that I wont be able to model this since I am already struggeling very hard.

 

Thanks in advance again

 

Best regards

 

schmeich

#CPLEXOptimizers
#DecisionOptimization

You got this correct: If you work with a fixed pool of nurses then the solver will only schedule tours for nurses that result in minimal cost. So usually if it is cheaper to use 5 nurses than 6 or 7, you will only see 5 "active" nurses in the solution, even though your pool as 7 nurses.

Note however that your model has a constraint that requires each nurse/vehicle to leave depot 0 and arrive at depot n+1. So in a solution you will see travel even for nurses that don't visit any customer. If you put depots 0 and n+1 at the same coordinates then the cost for this sort of travel should be 0.

I suggest you first try to get things working without that additional boolean variable. Once you have this working you can take it further.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: schmeich

Okay. I got something to work but still have tons of questions about it.

i tried to include the gender specifications with the code you made above. Same i tried for the skill specifications.

I did indeed inderstand how they are defined, for the vehicles and the customers itself. What I dont really get is this code portion:

 

forall(i in Customers, k in Vehicles : RequiredGender[i] != 0 && RequiredGender[i] != Gender[k]) { // for all vehicle/customer combinations that do not satisfy the gender requirements
  forall(j in Customers) {
    x[k][i][j] == 0; // vehicle can never start from i
    x[k][j][i] == 0; // vehicle can never end in i
  }                   
}

I uderstand what it does but donet quite understand the code yet. Maybe you can help.

 

In a next step I am trying to include the time windows but i am not sure how to set the time in the model. Like Service time is set to 30, which i assume is 30 minutes. But I have no idea how to integrate a time window of maybe 06:00am - 12-´pm with those integers

And finally the 8 hours working time. Same problem here how to calculate the time in the model.

 

Last but not least i found interesting that if i add for example a nurse the and keep the number of patients with all their attributes the solution gets bigger which it shouldnt?

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: schmeich

I figured like you mentioned above that the model uses 2 depots. I only want one. I to just delete the second depot like this but it brings me no solution. If i just do the coordinates the same like oyu said it works

 

range   CustomersAndDepots   = 0..(CustomersNumber+1);  --> range   CustomersAndDepots   = 0..(CustomersNumber);

 

I MADE LIKE THIS

 

For me this looks right but something is still wrong. 

 

Another question came up to me when fooling around with the programm:

In the attached file I changed the second depots coordinates to the depot 0 and figures the following:

With this data:

v = 2;
CustomersNumber = 5;
Gender = [1,2];
Skill = [1,2];

No Solution is given which i dont understand because we have a skilled male and an unskilled female The requirements of the patiens are fine with this

 

 

Only a skilled male is required and the rest dont care for either gender or dont need skilled people. (I figured that requirement for unskilled is silly and theerefore simply put 0 for no care)

 

If i just add one nurse it works. This doestn make snese to me since there is no capacity contraint anymore and i didnt add the 8hr working day yet.

 

Okay so far for now from me.

 

thanks a lot

#CPLEXOptimizers
#DecisionOptimization