Journal of Global Research in Computer Sciences
MenuISSN: 2229-371X
ISSN: 2229-371X
Sawsan Amous Kallel1, Younes Boujelbene2
|
| Corresponding Author: E-mail: amoussawsan@yahoo.fr, Boujelbene.Younes@fsegs.rnu.tn |
| Related article at Pubmed, Scholar Google |
Visit for more related articles at Journal of Global Research in Computer Sciences
The Heterogeneous Fleet Vehicle Routing Problem (HVRP) is a variant of the classical Vehicle Routing Problem in which customers are served by a heterogeneous fleet of vehicles with various capacities, fixed and variable costs. Due to its complexity, there’s no exact algorithm for this problem. A new scheme based on a clustering genetic algorithm heuristic for the HVRP is proposed in five steps. This study considers, in one hand, a version of the vehicle routing problem with fixed cost only with priority of client, and the customer demands are random variables, in the other hand. Computational experience with the benchmark test instances confirms that our approach produces acceptable quality solutions both in terms of the generate solutions and the processing time for this new problem.
Keywords |
| The Heterogeneous Fleet Vehicle Routing Problem, genetic algorithm heuristic, k-means clustering. |
INTRODUCTION |
| The logistic problem is known as one of important combinatorial optimization problems that is taken great interest of the researchers. Huge research efforts have been devoted to the study of logistic problems and thousands of papers have been written on many variants of this problem such as Traveling salesman problem (TSP), vehicle routing problem (VRP), supply chain management (SCM) and so on [5]. |
| The Vehicle Routing Problem (VRP) is one of the most studied combinatorial optimization problems and it consists of the optimal design of routes to be used by a fleet of vehicles to satisfy the demands of customers. In general, the number of vehicles used is a variable decision. |
| The Heterogeneous Fleet Vehicle Routing Problem (HVRP) is an important variant of the VRP when a fleet of vehicles characterized by different vehicle types in which customers are served by a heterogeneous fleet of vehicles with various capacities, fixed and variable costs. |
| In the literature, three HVRP versions have been studied. The first one was introduced by Golden and al. [10], which variable costs are uniformly given over all vehicle types with the number of available vehicles assumed to be unlimited for each type. This version is also called the vehicle fleet mix (VFM) [18], the fleet size and mix VRP [10] or the fleet size and composition VRP [7]. This version is the one consider with in this paper. |
| The second version considers the variable costs, dependent on vehicle type, which is ignored in the first version. This version referred to as the HVRP [6], the VFM with variable unit running costs [17] or the mix fleet VRP [22]. |
| The third one, called the VRP with a heterogeneous fleet of vehicles [19] or the heterogeneous fixed fleet VRP [20], generalizes the second version by limiting the number of available vehicles of each type. |
HETEROGENEOUS VEHICLE ROUTING PROBLEM WITH PRIORITY CLIENT |
| The Heterogeneous Vehicle Routing Problem: |
 |
| The number of vehicles of each type is assumed to be unlimited. With each arc ïÃâ¬Ã¨ ïÃâ¬Ã© i j v ,v is associated a distance ij C . The HVRP consists of designing a set of vehicle routes, each starting and ending at the depot, and such that each customer is visited exactly once, the total demand of a route does not exceed the capacity of the vehicle assigned to it, and the total cost is minimized [6]. |
| All the HVRP variants are NP-hard as they include the classical VRP as a special case. All the presented studies have thus focused on developing heuristic algorithms as a substitute of exact algorithms. They can be generally grouped into two kinds: classical heuristics [10], [17], [15]. Frequently derived from the classical VRP heuristics, and meta-heuristics like the tabu search method [6], [20]. For more information, see [17] and [20] for a review of HVRP variants. |
| In our approach, we propose to introduce the priority of the customers in the HVRP. |
| Proposed problem: |
| Practically, there are uncertain factors in VRP, such as demands of customers that have been studied by Taillard [19], Gendreau and al. [6], Ismail and Irhamah [11]... Other uncertain factors like travel times between customers, customers to be visited, locations of customers, capacities of vehicles, and number of vehicles available have been dealt with by Prins [14], Renaud [15]… |
| In these cases, they called stochastic vehicle routing problems. This fact provides a motivation to study uncertain VRP because they are close to real world. |
| In the vehicle routing problem with stochastic demands a vehicle has to serve a set of customers whose exact demand is known only when it arrives at the customer’s location. The objective is to find a permutation of the customers (an a priori tour) that minimizes the expected distance traveled by the vehicle. A comprehensive overview of the Vehicle Routing Problem and its stochastic variant can be found in [21]. |
| For the problem under study, we will combine HVRP and stochastic VRP including the priority of customers. We will present in this paper, a mathematical model for stochastic vehicle routing problems with heterogeneous fleet. |
| Hence, the mathematical formulation is similar to that of general HVRP with the introduction of the principle of gain priorities by client. Note = 1 if the client i is at the rank r and 0 otherwise. |
| The modeling of the problem is similar to standard HVRP [8] and it’s as follows : |
 |
 |
| Given the random character of the needs i q changing continually and availability of trucks, we assume a probability distribution according to the history of the customer's request. |
| In the above formulation, constraints (1) and (2) ensure that the customer is visited exactly once and if a vehicle visits a customer, it must also be the start of him. The maximum number of vehicles available for each type is imposed by constraints (3). Constraints (4) precise that the difference between the quantity of goods that a vehicle has before and after visiting a customer is equal to the demand of the client. Finally, constraints (5) ensure that the vehicle capacity does never exceed the demand of customers. |
CLUSTERING GENETIC ALGORITHM |
| Inspired by the high performance of genetic algorithms; we propose to introduce a clustering process into a genetic algorithm in order to design an efficient tool to deal with complex optimization data. In this domain, some proposals works have appeared recently [3]. |
| In this paper, we propose a new hybrid metaheuristic based on genetic algorithm heuristics and k- means clustering to solve the HVRP. We develop five steps, which begin by clustering method and ending with finding the optimal tours at the same time, they satisfy the demand of customers. |
Genetic Algorithm: |
| The genetic algorithm starts from an initial population of candidate solutions or individuals and proceeds for a certain number of iterations until one or more stopping criteria is (are) satisfied. This evolution is directed by a fitness measure function that assigns to each solution (represented by a chromosome) a quality value. |
| Once the population is evaluated, the selection operator chooses which chromosomes in the population will be allowed to reproduce. The stronger an individual is, the greater chance of contributing to the production of new individuals it has. |
| The new individuals inherit the properties of their parents and may be created by crossover (the probabilistic exchange of values between chromosomes) or mutation (the random replacement of values in a chromosome). Continuation of this process through a number of generations will result in a group of solutions with better fitness in which optimal or near-optimal solutions can be found [1]. |
| When the size of the problem is becoming wider, genetic algorithms find a difficulty in identifying the optimal solution. Nevertheless, the question is why scarifying an approach that can have a good opportunity to develop a new area of expertise and keep the problem in touch with reality? |
| Hence, we divide our vehicle routing problem (search space) in areas to locate the task of AG. Therefore, we will use a two-phase method. It has shown in many applications of the vehicle routing problem and its generalizations, that the set of routes has the important phase of the algorithm. |
| The two-phase method uses the principle of "cluster first - route second" [4]. In the case of TSP, such a method comprises, first, to split the set of vertices (customers) into sub-classes (sets) of customers, then to issue a routing process on each class to have a solution. |
| Diversification of class divisions allows to the method of two phases to provide several solutions to the problem by applying alternatively the classification procedures and routing. |
Clustering Method |
| The specific method used in our approach is the k –means. It’s one of the simplest unsupervised learning algorithms that solve the celebrated clustering problem. K-means consists in partition the data into groups, or "clusters", this result is obtained by positioning "centroids" in regions of space where most population |
| Each observation is then assigned to the closest prototype. Each class therefore contains observations that are nearer to a prototype than any other. |
| Then, the centroids are positioned by an iterative procedure (in each time calculate the centroid of the classes: the weight of a center of gravity is equal to the sum of the weights of the class of individuals) which leads progressively to their final position stable. |
| The weight of a center of gravity aims at minimizing an objective function, in this case a squared error function. The objective function: |
 |
| Once the number of classes is defined in the final partition of the data space into separate classes by hyper -planes based on the central of clusters, it is possible, to run the AG cluster by cluster. |
| Hence, we divide our vehicle routing problem (search space) in areas for locate the task of AG. Therefore, we will use a two-phase method. It has shown in many applications of the vehicle routing problem and its generalizations, that the set of routes has the important phase of the algorithm. |
| The two-phase method uses the principle of "cluster first - route second" (Fisher and Jaikumar, 1981). In the case of TSP, such a method comprises, first, to split the set of vertices (customers) into sub-classes (sets) of customers, then to issue a routing process on each class to have a solution. |
| Diversification of class divisions allows the method to two phases to provide several solutions to the problem by applying alternatively the classification procedures and routing. |
 |
| The general outline of the method in two phases |
| K-means is an algorithm that has been adapted to many problem domains. As we are going to see, it is a good candidate for extension to work with fuzzy feature vectors. |
| The purpose of implementation of genetic algorithms is to see a hamiltonian cycle for clusters identified that means the genetic algorithm are applied cluster by cluster and the result for this step is the turns for clusters. The purpose of implementation of genetic algorithms is to see a hamiltonian cycle for clusters identified that’s means the genetic algorithm are applied cluster by cluster and the result for this step is the turns n T ,T ,...,T 1 2 for clusters n K ,K ,...,K 1 2 . |
| In the last stage, we must find the complete tour by eliminating some edges and joining clusters. We will take the adjacent centoides and choose the arcs that we must eliminate and repeat until having only one tour. |
EXPERIMENT RESULTS |
| In our research, we include the k-means method to classify data into identical classes in order to facilitate the procedure of the genetic algorithm and it tackles the travelling salesman problem with many cites. The performances of the heuristics have all been tested, with a few exceptions, on two sets of benchmark instances: the first one consists of the 20 VFM instances [10], and the second contains 8 instances only with fixed costs [19]. |
| The following table illustrates the results found by comparing the clustering genetic algorithm (Clu.GA) with a classical genetic algorithm (Cla.GA) (two-function point mutation by inversion), including the minimum length of the tour and finally the ratio = average / optimal for different instances of benchmarks from TSP library LIB see table 1. |
 |
| Table 1. Examples of instances per cluster |
| Results from the experiment in table 1 show the advantages of the proposed algorithm concerning quality of the solution. Since, the proposed algorithm, clu. GA, is compared with standard genetic algorithm considering a set of instances from the TSP LIB. Experimental results prove the efficiency of the proposed algorithm in many instances. Our GA results are also compared to the best-found solutions of Taillard [19] and, it produces comparative quality of the solutions especially when we compare it in the processing time. cplex algorithm gives optimal solution for small instances but it takes much time to find this solutions. We test also, our problem “the Heterogeneous Routing problem with stochastic demand and client priority” in a small instance with CPLEX algorithm to compare the process time. |
| The resolution of the problem shows that our algorithm needs less time to solve big instances. |
| Let’s the following instances with a number of different cities. We compare our algorithm with [12], [19] and [10]. The results are summarized in the following table: |
 |
| Table 2. Comparable instances |
| The results presented in the table 2 show that our algorithm produces solutions with comparable quality to those of Osman and Salhi[12] and Taillard [19] and improve the computational time. Comparisons with other authors are the only way to evaluate our solutions because it’s a new problem in the literature (to the best of our knowledge). In the first series, the performance of the results found by clu.GA is near that of [12], but it’s lower, not by a wide margin, than those of Taillard [19]. |
| Our algorithm has better performance on instances with fixed costs. Here, our average solution values are worse than those of Taillard in most cases, but it allows a good classification of trucks and their fixed costs, and allocate customers as butter as that presented by Golden (See table 3). |
 |
| Table 3. Examples of instances with fixed cost |
| Here is a sample output generated by our algorithm for the example G 14 of taillard: |
 |
| Figure: 1 |
| EDGE_WEIGHT_TYPE" is the data type of the example treated. This type denoted by "EUC_2D" indicates Euclidean distances in two dimensions. |
| The second line gives the sequence of customers as they are visited. The value of the sum is shown in the third line named "SOMME". It is, in fact, the value of the minimum tour found in the second line. |
| The execution time of the algorithm is shown in the fourth line in milliseconds. |
| The next line is the sum of customer demand and also the sum of the last column "DEMAND". Moving to the second part, which is the clustering. "NBR cluster" indicates the number of cluster set for example 5 in this case. We will take the 1/10 of the total number of clients. |
| Subsequently, we give each cluster the sequence customer named "cluster n°1". |
| "S. Distance" is the sum of the distance from the first cluster while "S. Demand" is the sum of the customer demand for the same cluster. |
| The third part is to assign the trucks according to the clusters found in the second part. First of all, "VEHICLES" indicates the number of vehicles available in our example G 14. Then, the word "VEHICULES_KINDS" shows the different types of vehicles. In our case, we have 6 types of 8 vehicles. |
| The capacity of each vehicle is given in the following line under the name "CAPACITIES" while fixed costs specific to each type are shown in the line after "FIXED COSTS." They are often distinctions between vehicles. Capacity is not the same, they are not all the same age, or it may be differences in the type of vehicle that’s why they have different costs. |
| The capacities of vehicles that are used in various clusters to optimize routes are presented in "capacity optimized vehicles." The algorithm selected vehicles that are assigned to clusters in order to minimize all costs. In our example, we used the vehicle capacity 120 and 160 for cluster 1. |
| Finally, the algorithm sets out optimized vehicle capacity and the demand exceeded in each cluster as well as the exceeding percentage denote k ïÃÂñ . |
CONCLUSIONS ET PERSPECTIVES |
| The various experiments give indication on the sensitivity of the algorithms in different configurations. They can exhibit the advantage of using a definition of compromise proposed to be specifically incorporated into an evolutionary algorithm. In this study, we have investigated a class of stochastic optimization problems. These algorithms need to be evaluated on other classes of problems including other variants and constraints. |
References |
|