Combination of a routing an scheduling problem

[boiro9]

I want to solve a problem that it is a combination of a routing and a scheduling problem with NSGA2. I want to manage the routing part of the solution using the operators compatible with PermutationSolution, but I need to get the scheduling part of the solution with a custom-made algorithm. The idea is that, once I know a route, I need to find a schedule associated to it. Thus, my solution structure only includes the routing part of the solution, and inside the evaluate method (of the specific problem class I have created) I call my custom-made algorithm to obtain a schedule.

The issue that I am facing is that, since I am solving a multiobjective problem, for a given route I can obtain several schedules associated to it and several of them could also be non dominated solution. The "problem" is that the evaluation method only allows to return one solution, so I am not able to propagate all of the several solutions I can compute given a route.

I do not know what is the best way to manage this. One idea could be to modify the evaluation method to allow returning several solutions, but I do not know if this could derive in bugs in other steps of the algorithm. Other option could be to define a custom solution structure including also the schedule part, but this implies that a I can not employ the PermutationSolution operators directly.

I appreciate any ideas regarding the best way of managing this.

[ajnebro]

Hi @boiro9
A question about your message: given a solution, what are the objectives to optimize?

Antonio

[boiro9]

Hi @ajnebro

Given a solution we consider two objectives:

• One takes into account the welafre of users in terms of: the affinity between services-caregivers and a penalization of violating soft time windows.
• The other objective considers the schedule cost in terms of: the overtime of caregivers and their total worked time.

So once a route is fixed (the services that must be attended by a caregiver), it is necessary to find the schedule to be able to evaluate each objective. Further, depending on how you want to prioritize each objective, given a route, we can find several schedules.

Our idea is to only manage the routing part of the solution with the operators already included in jmetal, but not the schedule part since it is very difficult to find feasible schedules (we do not consider time steps, the schedule is treated as a continuous variable). To this aim, we have already developed an heuristic that, given a route, it is able to find several routes. This is the reason I want to, given a route, in the evalutaion phase provides several solutions (accodring to different schedules) to generate a wide diversity of solutions during the iterations of the NSGA2 algorithm.

[ajnebro]

If you keep the first objective fixed and get a number of schedules, you will get only a non-dominated solution with that objective and best schedule.

For example, if we assume that the value of the first objective is 1.0 and the different schedules are in the list [2.0, 3.0, 4.0], the resulting solution should be [1.0, 2.0] as the others ([1.0, 3.0], [1.0, 4.0] ) would be dominated by the first one.

[boiro9]

Sorry @ajnebro , I have not explained correctly the problem.

Suppose that I have a route with 3 points (A,B and C). I apply one of the PermutationSolution operators and I get the route= B->C->A. For this route, now I must compute the associatedd schedule, this is the initial time at which each task must be carried out. We have developed a taylor-made heuristic to compute the schedule once the route is fixed, and several strategies can be used. For example:

• Using strategy 1 we get: t_{B}=9:00, t_{C}=12:00, t_{A}=16:00. This gives the following objective values: sol1 = [f1=1,f2=2].
• Using strategy 2 we get: t_{B}=10:00, t_{C}=11:00, t_{A}=13:00. This gives the following objective values: sol1 = [f1=2,f2=1].

So as you can see in this toy example, we can generate non dominated solutions: [1,2] and [2,1]. This is the reason why I need to provide several solutions once I have a route, not only one.

Taking a deep look into the code, I think that one possibility could be to overload the function evaluate of NSGA to return the list of evaluations I need, instead of using the population_generator that call the evaluate method defined inside the specific problem class and only allows to return one solution. Do you think that this could work?

Thank you very much for your time!

[ajnebro]

I undestand now the problem. The point is that you are not merely evaluating a solution, which is the mission of the evaluate() method, but generating a list of new solutions. Of course, you are free to modify the code to adapt it to your needs. What you would get would be a variant of NSGA-II which, in the evaluation step, from a population of N solutions the result are M solutions (with M >N). From it, the replacement step would apply the ranking and crowding methods to keep the best N solutions for the next generation.

[ajnebro]

Perhaps you could keep the functionaly of the evaluate() method as is (from a solution, it returns the same solution but evaluated) by considering two alternatives:

• Return a random solution from the non-dominated list.
• If the number of non-dominated solutions is high (let us say, higher than 5), you could compute the crowding distance density estimator to return the solution in the least crowded region.

This way, you don't have to modify the behaviour of NSGA-II algoritm.

[boiro9]

Thank you very much for your suggestions. I will try them and let you know.