In this chapter, the authors show how knowledge engineering techniques can be used to guide the definition of evolutionary algorithms (EA) for problems involving a large amount of structured data, through the resolution of a real problem. Various representations of the fitness functions, the genome, and mutation/crossover operators adapted to different types of problems (routing, scheduling, etc.) have been proposed in the literature. However, real problems including specific constraints (legal restrictions, specific usages, etc.) are often overlooked by the proposed generic models. To ensure that these constraints are effectively considered, the authors propose a methodology based on the structuring of the conceptual model underlying the problem, as a labelled domain ontology suitable for optimization by EA. The authors show that a precise definition of the knowledge model with a labelled domain ontology can be used to describe the chromosome, the evaluation functions, and the crossover and mutation operators. The authors show the details for a real implementation and some experimental results.
TopIntroduction
In this article, we will show that the use of knowledge engineering can greatly enhance the definition of an evolutionary algorithm for a real case. This study is the result of a collaboration between our team and an Alsatian Patient Transportation Service (PTS), which has provided the real data.
The project is developed under the health care system environment, specifically oriented to the transportation of patients, normally from or to some health care center. The need to develop a specific application arises from the fact that companies that take care of the logistics of the trips must manage many requirements and restrictions when making an itinerary. This logistics affects many enterprise resources, like employees and vehicles, which should be assigned in an efficient way to guarantee, among other things, the satisfaction of the patient and the conformity of numerous law regulations.
The problem consists in satisfying the daily requests of the patients while maximizing the benefits, minimizing the costs and fulfilling different constraints. The requests are basically for pick-ups and/or deliveries of the patients to or from their house to some health care center.There are different types of vehicles than can be used for a journey and each of them has an associated cost. There are also the costs for the assignment of a crew, composed by a set of one or two employees, to a given vehicle or for a given patient.
This case of Vehicle Routing Problem (VRP) can be defined as a Rich Vehicle Routing Problem (RVRP). According to a recent literature review (Lahyani et al. 2014), RVRP is defined as a problem which simultaneously includes several types of challenging and complicating features. It is associated with the complexity of real-life routing problems.
Many studies concern the Vehicle Routing Problem (Raghavan&Wasil, 2008). These studies can be categorized along two axes:
- •
The solving approach; mainly exact algorithms or metaheuristics (stochastic or nature inspired algorithms) (Russell &Norvig, 2009).
- •
The variants of the problem; including time windows constraints (Giraldez et al. 2005) or multiple heterogeneous vehicles with pick-up and delivery (Tasan& Gen, 2012), among others.
We have chosen to follow an approach based on Evolutionary Algorithms (EAs) for this specific problem to solve, since we will show in this article that some families of EA and Genetic Algorithms (GA) in particular are suitable for a knowledge driven definition.Genetic algorithms are stochastic search algorithms based on abstraction of the process of Darwinian evolution. They are based on a simple principle: better individuals survive and reproduce more often than other individuals. A classic genetic algorithm maintains a population of individuals, each of them encodes a candidate solution to a given problem. Each individual is evaluated by a fitness function, which measures the quality of its corresponding candidate solution. Then, a selection mechanism identifies the fittest individuals of the current population to serve as parents of the next generation. Hence, the better the quality of an individual, the higher the probability it reproduces and breed to form a next generation. This process is repeated until some stopping criterion. Usual stopping criteria are that the fitness value is beyond a threshold or that a number ofgenerationshave been reached. To explore the search space, different genetic operators are used during the evolutionary process. Classic genetic algorithms use two operators: mutation and crossover. However, several other operators can be chosen according to the kind of problem.