Program > By author > Psychas Iraklis - Dimitrios

A Parallel Multi-Start NSGA II Algorithm for the Solution of Multiobjective Route-based Fuel Consumption Open Vehicle Routing Problems
Iraklis - Dimitrios Psychas  1, *@  , Magdalene Marinaki  1, *@  , Yannis Marinakis  1, *@  , Nikolaos Matsatsinis  1, *@  
1 : Technical University of Crete  (TUC)  -  Website
University Campus 73100 Chania - Crete -  Greece
* : Corresponding author

In this paper, the Parallel Multi-Start NSGA II (PMS-NSGA II) algorithm is proposed and presented for the solution of four different Multiobjective Route-based Fuel Consumption Open Vehicle Routing Problems (MRFCOVRPs). In all problems the first objective function corresponds to the optimization of the total travel time of the vehicles and the second objective function corresponds to the minimization of the fuel consumption of the vehicles taking into account the travel distance, the load of the vehicles and other route parameters when the decision maker plans delivery or pick-up routes. In both cases (delivery or pick-up routes) the algorithm is tested for symmetric and asymmetric cases. The main differences of PMS-NSGA II compared to the NSGA II is the use in the PMS-NSGA II of three different local search methods for the creation of the initial population, the use of more than one populations (Parallel Multi-Start method) that are evolved in parallel, the use of a number of Pareto Fronts (equal to the number of populations) and the way that the Variable Neighborhood Search algorithm is used for the improvement of each solution separately. The results of the PMS-NSGA II and of the NSGA II algorithms are compared using four different evaluation measures in order to prove the effectiveness of the PMS-NSGA II algorithm and of each new characteristic of the proposed algorithm separately. A number of instances are used based on suitable modifications and combinations of classic benchmark instances used for the solution of TSP and CVRP.


Online user: 1