Good chromosome representation in a VRPTW genetic algorithm

I have a genetic algorithm for a vehicle routing problem with time windows and I need to implement certain modifications. I am not sure what would be the best chromosome representations.

I have tasks which can be divided into 3 sub-tasks with certain ordered time windows, they have to processed in order and all 3 (they represent collecting certain goods in a storage, delivering them and returning packaging to another storage). In the algorithm crossover part these tasks are combined together and evaluated. They have to processed in order according to their task number, i.e. combination A1, B1, B2, A2, B3, A3 is correct, but A1, B2, A2, B3, A3, B1 or A1, A2, B1 is not. The problem is, I don't know how to assure the order of events will be kept. How can I represent this demand in chromosomes? Or, where in the algorithm should I keep this demand?

In the previous version of the algorithm we used only the whole task A or B without distinguishing the subtasks, which is now not sufficient. I am relatively new to genetic algorithms, so pardon me if it's something obvious.

Topic representation genetic-algorithms optimization

Category Data Science

1
answered at

Given you want to maximize fitness function $\phi:\Bbb{R}^n\rightarrow\Bbb{R}$, make $\phi(\vec{x})=-\infty\ \forall \vec{x}\ \notin X$ where the feasible region is $X\subset \Bbb{R}^n$. Then you can initialize the population $P=\{p\ |\ p\in X\}$ and if the GA tries any $p\notin X$, that solution would be killed off. This forces the GA to "learn" the feasible region.

About

Geeks Mental is a community that publishes articles and tutorials about Web, Android, Data Science, new techniques and Linux security.