Solving Scheduling Problem (VRP) Using Genetic Algorithm in Pymoo

[ZaRiyam]

Hi Julian,

I'm using Pymoo for the first time to solve a vehicle routing problem (VRP) of maintenance scheduling. I initially formulated my problem using Mixed Integer Programming (MIP) but I found it impractical for solving this problem using an exact methods. That's why I'm using Pymoo right now. Till now, I was able to formulate a mini problem but I need a help on the conceptual part of the problem.

My model includes binary decision variables with max 4 indices & some continuous variables. Currently, I'm using the same definition of the variables in MIP but I do have feeling that there is a better way for defining the variables in Pymoo. For example (Xijkt) it is binary decision variable equal to 1 if a team k will move from location i to location j in day t. So, I'm using reshape function to reshape Pymoo variable (X) into 4 indices (Xijkt). So, in principle, do I need to use the same concept of MIP in formulating my problem in Pymoo ? if not, could you please give me some other options?

Here is the things I need to get from the solution:

• The daily route of each team between locations
• Starting time of the activity
• If there is a long-time activity, it will be split between multiple consecutive days. That's why I'll need to have a track on the team daily working hours.

[blankjul]

Hi ZaRiyam,

Yes, MILP and genetic algorithms might approach optimization problems very differently.

For mixed variables problems, I recommend having a look at customization.
I have written an example for subset selection: https://pymoo.org/customization/subset.html
Basically, you define your own operators (sampling, crossover, mutation) that operate on the genotype.

The information about your problem is not sufficient to give a direct answer to your question. But I recommend first thinking about the genotype representation and the operators.

Keep in mind that the GA approach is different. For instance, for the TSP problem where you intend actually trying to find a permutation (let us say of length n), MILP will define boolean n^2 variables and use constraints to ensure it maps to a feasible permutation.
In GA, however, you would directly use the permutation as a genotype and define the operators on it.

[ZaRiyam]

Hello Julian,

Thanks for your response. I used premutation for the solution representation as you recommended and it works fine but I need to improve the solution quality now. I actually used premutation for all the decision variables although they are not all related to premutation. It's like a assumed some dummy customers for premutation but they actually have other meaning than premutation. They have meaning for either days or depot. So, in my problem, I need to know which day will I visit the customer (multi-period problem) and from which depot (multi depot problem) or in other words customer is related to which route. This is a very challenging problem till now I found no one coded a genetic algorithm having similar characteristics of multi period multi depot vehicle routing problem. Anyways, now, I have an idea to present the solution in one single string mixed by premutation and integer.

I found this example under customization of Pymoo: https://pymoo.org/customization/mixed.html Usage of "Mask" to divide the decision variables into two types.

• In the above example, there are only a few variables. So they can use the mask one by one for each variable. If we have a large number of variables, how can we indicate that the first "n" variables are integers and the following "m" variables are real, etc.
• Is it possible to use permutation with mask. That is, first n variables are permutation variables and the following m are integers. Can we use mask in such a case?

If using the Mask for premutation is possible, I believe it will help to improve the solution quality because we can use different types of crossover and mutation operators for each type. Thanks in advance.