topic Re: Combination of VRP and Scheduling problem based on Home Healthcare Problem in Mathematical Optimization, Discrete-Event Simulation, and OR

Combination of VRP and Scheduling problem based on Home Healthcare Problem

norachanisara — Sun, 15 Sep 2024 11:23:36 GMT

Hi community,

I am modelling an OR problem based on home healthcare scheduling problem, which is combining VRP with schedule problem.

For context, I am just trying with small hypothetical data.

Staff Availability:

Each staff member can work up to 40 hours per week.

Customer Requirements:

Customer 1: Needs 3 visits/days per week, each visit/day takes 2 hours.
Customer 2: Needs 2 visits/days per week, each visit takes 1.5 hours.
Customer 3: Needs 1 visit/day per week, each visit takes 2 hours.

Distance between customers

Distance Matrix:

From/To 1 2 3 4 5

1	0	10	20	15	25
2	10	0	15	20	30
3	20	15	0	30	20
4	15	20	30	0	25
5	25	30	20	25	0

I want to make this an open VRP where the staff can start at any customer and end at any customer. So I will add a dummy customer with distance to and from other customers = 0 and all other data visits_per_week visit_duration is 0.

The aim is to minimise total travel distance while all customers are visited. I am aiming to get output something like sets of route for each staff and total distance travelled.

The code is generating lots of syntax errors around sets and read data.

data distance;
   input from to distance;
   datalines;

0 1 0
0 2 0
0 3 0
0 4 0
0 5 0
1 2 10
1 3 20
1 4 15
1 5 25
2 3 15
2 4 20
2 5 30
3 4 30
3 5 20
4 5 25
;
run;

data customer;
   input customer_id visits_per_week visit_duration;
   datalines;
0 0 0 
1 3 2
2 2 1.5
3 1 2
;
run;

data staff;
   input staff_id available_hours;
   datalines;
1 40
2 40
3 40
;
run;

proc optmodel;
   /* Define sets */
   set <num> C; /* Customers */
   set <num> S; /* Staff members */
   set <num> D; /* Days of the week */
   set <num> LOCATIONS; /* Including customers and the dummy customer (depot) */

   /* Define parameters */
   num distance {LOCATIONS, LOCATIONS}; /* Distance between locations */
   num visits_per_week {LOCATIONS}; /* Number of visits per week for each customer, including dummy */
   num visit_duration {LOCATIONS}; /* Duration of each visit for each customer, including dummy */
   num available_hours {S}; /* Available working hours per week for each staff */
   
   /* Define variables */
   var x {S, LOCATIONS, LOCATIONS} binary; /* 1 if staff s travels from location i to location j */
   var y {S, C, D} binary; /* 1 if staff s visits customer c on day d */
   var total_travel_time {S} >= 0; /* Total travel time for each staff member */
   var u {LOCATIONS} >= 0; /* Auxiliary variables for subtour elimination */

   /* Read data */
   read data distance into [from, to] distance;
   read data customer into [customer_id] visits_per_week visit_duration;
   read data staff into [staff_id] available_hours;

   /* Add dummy customer */
   /* Assuming the dummy customer is indexed as 0 */
   LOCATIONS = C + {0}; /* Add dummy customer to the locations */
   distance[0, i] = 0; /* Distance from dummy to other locations is 0 */
   distance[i, 0] = 0; /* Distance from other locations to dummy is 0 */
   visits_per_week[0] = 0; /* Dummy customer has 0 visits per week */
   visit_duration[0] = 0; /* Dummy customer has 0 visit duration */

   /* Define sets from parameters */
   C = (setof {i in visits_per_week: i ne 0} i); /* Exclude dummy customer */
   S = (setof {i in available_hours} i);
   D = (setof {1, 2, 3, 4, 5}); /* Assuming a fixed number of days */

   /* Objective: Minimize total travel time */
   minimize TravelTime: sum {s in S, i in LOCATIONS, j in LOCATIONS} distance[i, j] * x[s, i, j];

   /* Constraints */
   /* Staff working hours constraint */
   con staff_hours {s in S}:
      sum {d in D, c in C} visit_duration[c] * y[s, c, d] <= available_hours[s];

   /* Customer visit requirements */
   con customer_visits {c in C}:
      sum {s in S, d in D} y[s, c, d] = visits_per_week[c];

   /* Flow constraints */
   impvar FlowOut {i in LOCATIONS} = sum {j in LOCATIONS: i ne j} x[s, i, j];
   impvar FlowIn {j in LOCATIONS} = sum {i in LOCATIONS: i ne j} x[s, i, j];

   con Arrival_con {i in LOCATIONS}:
      FlowIn[i] = 1;

   con Departure_con {j in LOCATIONS}:
      FlowOut[j] = 1;

   /* Subtour elimination constraints */
   con Subtour_elimination_con {i in LOCATIONS, j in LOCATIONS: i ne j}:
      u[i] - u[j] + n * x[s, i, j] <= n - 1;

   con u_restrict1_con {i in LOCATIONS: i ne 0}: /* Assume '0' is the dummy customer */
      u[i] >= 1;

   con u_restrict2_con {i in LOCATIONS: i ne 0}:
      u[i] <= n - 1;

   /* Ensure total travel time for each staff member */
   con travel_distance {s in S}:
      total_travel_distance[s] = sum {i in LOCATIONS, j in LOCATIONS} distance[i, j] * x[s, i, j];

   /* Solve the problem */
   solve;

   /* Display results */
   print x y total_travel_distance;
quit;

I am following the logic of this example code I have.

data food_data;
	INFILE DATALINES DLM=' ';
	length Name $ 14 Type $ 14 Colour $ 14  ;
	input Name  Type Colour  Price     ;
	datalines;
Apple  Fruit Red 0.65
Orange Fruit Orange 0.70 
Mandarin Fruit  Orange 0.75
Cheese  Dairy Yellow 0.65 
Milk Dairy White 7
Yogurt Dairy White 0.75 
;
run;

data time_data;
	INFILE DATALINES DLM=' ';
	length  TimeName $14 ;
	input Time TimeName    Budget;
		datalines;
	1 Breakfast 5
	2 MorningTea 5
	3 Lunch 4
	4 AfternoonTea 4
	5 Dinner 3
	;
	run;

proc optmodel;
	 

    /* Populating sets from a dataset */
	set <num> TIME ; 
	set <str> FOOD ;
	set <str> DAIRY ;
	set <str> FRUIT ;
	set <str> COLOUR;
	str foodType {FOOD};
	num foodPrice {FOOD};
	str foodColour {FOOD};
	num budget {TIME};
	str TimeName {TIME};
	
	read data food_data into 
			FOOD=[Name] 
			foodType=Type 
			foodPrice=price
			foodColour = Colour;

	/* Create sets from variables */
	COLOUR = (setof{i in FOOD} foodColour [i]);
	DAIRY =(setof{i in FOOD: foodType[i]='Dairy'} i);
	FRUIT =(setof{i in FOOD: foodType[i]='Fruit'} i);
	
	read data time_data into 
			TIME = [time]
			TimeName
			budget;

Any expert could you kindly help? Thank you very much in advance.

Re: Combination of VRP and Scheduling problem based on Home Healthcare Problem

RobPratt — Mon, 16 Sep 2024 16:53:53 GMT

Note for example that you cannot have

c in C

because c and C are treated the same. So I renamed C, S, and D.

You must also populate sets before you can use them.

The subtour elimination constraints should exclude the depot as j.

The following code avoids the syntax errors:

proc optmodel;
   /* Define sets */
*   set <num> C; /* Customers */
*   set <num> S; /* Staff members */
*   set <num> D; /* Days of the week */
   set <num> CUSTOMERS; /* Customers */
   set <num> STAFF; /* Staff members */
   set <num> DAYS; /* Days of the week */
   set <num> LOCATIONS; /* Including customers and the dummy customer (depot) */

   /* Define parameters */
*   num distance {LOCATIONS, LOCATIONS}; /* Distance between locations */
   num distance {LOCATIONS, LOCATIONS} init 0; /* Distance between locations */
   num visits_per_week {LOCATIONS}; /* Number of visits per week for each customer, including dummy */
   num visit_duration {LOCATIONS}; /* Duration of each visit for each customer, including dummy */
   num available_hours {STAFF}; /* Available working hours per week for each staff */
   
   /* Define variables */
   var x {STAFF, LOCATIONS, LOCATIONS} binary; /* 1 if staff s travels from location i to location j */
   var y {STAFF, CUSTOMERS, DAYS} binary; /* 1 if staff s visits customer c on day d */
   var total_travel_time {STAFF} >= 0; /* Total travel time for each staff member */
   var u {LOCATIONS} >= 0; /* Auxiliary variables for subtour elimination */

   /* Read data */
/*   read data customer into [customer_id] visits_per_week visit_duration;*/
   read data customer into LOCATIONS=[customer_id] visits_per_week visit_duration;
/*   read data distance into [from, to] distance;*/
   read data distance into [from to] distance;
/*   read data staff into [staff_id] available_hours;*/
   read data staff into STAFF=[staff_id] available_hours;

   /* Add dummy customer */
   /* Assuming the dummy customer is indexed as 0 */
*   LOCATIONS = C + {0}; /* Add dummy customer to the locations */
   CUSTOMERS = LOCATIONS;
   LOCATIONS = CUSTOMERS union {0}; /* Add dummy customer to the locations */
*   distance[0, i] = 0; /* Distance from dummy to other locations is 0 */
*   distance[i, 0] = 0; /* Distance from other locations to dummy is 0 */
   for {i in LOCATIONS} do;
      distance[0, i] = 0; /* Distance from dummy to other locations is 0 */
      distance[i, 0] = 0; /* Distance from other locations to dummy is 0 */
   end;
   visits_per_week[0] = 0; /* Dummy customer has 0 visits per week */
   visit_duration[0] = 0; /* Dummy customer has 0 visit duration */

   /* Define sets from parameters */
*   C = (setof {i in visits_per_week: i ne 0} i); /* Exclude dummy customer */
*   S = (setof {i in available_hours} i);
*   D = (setof {1, 2, 3, 4, 5}); /* Assuming a fixed number of days */
   DAYS = 1..5; /* Assuming a fixed number of days */

   /* Objective: Minimize total travel time */
/*   minimize TravelTime: sum {s in S, i in LOCATIONS, j in LOCATIONS} distance[i, j] * x[s, i, j];*/
   minimize TravelTime = sum {s in STAFF, i in LOCATIONS, j in LOCATIONS} distance[i, j] * x[s, i, j];

   /* Constraints */
   /* Staff working hours constraint */
   con staff_hours {s in STAFF}:
      sum {d in DAYS, c in CUSTOMERS} visit_duration[c] * y[s, c, d] <= available_hours[s];

   /* Customer visit requirements */
   con customer_visits {c in CUSTOMERS}:
      sum {s in STAFF, d in DAYS} y[s, c, d] = visits_per_week[c];

   /* Flow constraints */
/*   impvar FlowOut {i in LOCATIONS} = sum {j in LOCATIONS: i ne j} x[s, i, j];*/
/*   impvar FlowIn {j in LOCATIONS} = sum {i in LOCATIONS: i ne j} x[s, i, j];*/
   impvar FlowOut {s in STAFF, i in LOCATIONS} = sum {j in LOCATIONS: i ne j} x[s, i, j];
   impvar FlowIn {s in STAFF, j in LOCATIONS} = sum {i in LOCATIONS: i ne j} x[s, i, j];

*   con Arrival_con {i in LOCATIONS}:
      FlowIn[i] = 1;
   con Arrival_con {i in LOCATIONS}:
      sum {s in STAFF} FlowIn[s,i] = 1;

*   con Departure_con {j in LOCATIONS}:
      FlowOut[j] = 1;
   con Departure_con {j in LOCATIONS}:
      sum {s in STAFF} FlowOut[s,j] = 1;

   /* Subtour elimination constraints */
   num n = card(LOCATIONS);
/*   con Subtour_elimination_con {i in LOCATIONS, j in LOCATIONS: i ne j}:*/
   con Subtour_elimination_con {s in STAFF, i in LOCATIONS, j in LOCATIONS: i ne j and j ne 0}:
      u[i] - u[j] + n * x[s, i, j] <= n - 1;

   con u_restrict1_con {i in LOCATIONS: i ne 0}: /* Assume '0' is the dummy customer */
      u[i] >= 1;

   con u_restrict2_con {i in LOCATIONS: i ne 0}:
      u[i] <= n - 1;

   /* Ensure total travel time for each staff member */
   con travel_distance {s in STAFF}:
/*      total_travel_distance[s] = sum {i in LOCATIONS, j in LOCATIONS} distance[i, j] * x[s, i, j];*/
      total_travel_time[s] = sum {i in LOCATIONS, j in LOCATIONS} distance[i, j] * x[s, i, j];

   /* Solve the problem */
   solve;

   /* Display results */
/*   print x y total_travel_distance;*/
   print x y total_travel_time;
quit;

The resulting optimal solution has objective value 0. You still need other constraints, such as flow balance for each s and i. But hopefully the above code helps you proceed further.

Re: Combination of VRP and Scheduling problem based on Home Healthcare Problem

Kalistha — Thu, 19 Sep 2024 03:20:35 GMT

Can you pls explain if the situation is as follows;

there are two types of staff models
1. One paid for the hours worked and how they reach the site do not matter
2. One is paid for the hours worked (more efficient than model 1) and the travelling time from the previous working location where a VRP should be applied.
the final solution should be a mix of both models
there is no data on the total number of staff available
Our objective is to maximise the profit

How would the code change??