A hybrid genetic algorithm for the multiobjective vehicle scheduling problems with service due times

In this paper, l propose a hybrid genetic algorithm (HGAM) incorporating a greedy interchange local optimization procedure for the multiobjective vehicle scheduling problems with service due times where three conflicting objectives of the minimization of total vehicle travel time, total weighted tardiness, and fleet size are explicitly treated. The vehicle is allowed to visit a node exceeding its due time with a penalty, but within the latest allowable time. The HGAM applies a mixed farming and migration strategy in the evolution process. The strategy splits the population into sub-populations, all of them evolving independently, and applies a local optimization procedure periodically to some best entities in sub-populations which are then substituted by the newly improved solutions. A solution of the HGAM is represented by a diploid structure. The HGAM uses a modified PMX operator for crossover and new types of mutation operator. The performance of the HGAM is extensively evaluated using the Solomons test problems. The results show that the HGAM attains better solutions than the BC-saving algorithm, but with a much longer computation time.