Combination of a routing an scheduling problem about jmetalpy HOT 7 CLOSED

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

Antonio

from jmetalpy.

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.

from jmetalpy.

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.

from jmetalpy.

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!

from jmetalpy.

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.

from jmetalpy.

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.

from jmetalpy.

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

from jmetalpy.