Article Preview
Top1. Introduction
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 a large number of 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 in order 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 particular 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 can be that the fitness value is beyond a threshold or that a number of generationshave 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.
Even if this problem belongs to the family of Rich Vehicle Routing Problems (RVRP), it soon became clear that the solutions proposed in the literature, as specific as they are (Parragh et al.,2008), (Kilcher&Calvo, 2013), (Paquette et al, 2013) were not intended to take into account all the specific constraints of this particular VRP problem. In addition, we believe that this situation is found in many other optimization problems when the parameters are numerous and varied in nature. Thus, in our example, legal constraints such as the working time of ambulance attendants, or medical constraints such as the disinfection of the vehicles, or the personnel qualification, cannot be overlooked while minimizing costs or distances.