A hybrid genetic algorithm for the vehicle scheduling problem with due times and time deadlines

In this paper, I propose a hybrid genetic algorithm (HGAV) incorporating a greedy interchange local optmization algorithm for the vehicle scheduling problem with service due times and time deadlines where three conflicting objectives of the minimization of total vehicle travel time, total weighted tardiness, and fleet size are explicitly treated. The vehicles are allowed to visit the nodes exceeding their service due times with a penalty, but within their latest allowable times. The HGAV employs a mixed farming and migration strategy along with a variant of partially mapped crossover and several mutation operators newly developed while maintaining the solution feasibility during the whole evolutionary process. The HGAV is extensively evaluated on the various types of test problems, including a sensitivity analysis with varied genetic parameters on the weighted sum of three objectives of a solution. The results show that the HGAV always attains better solutions than the BC-saving algorithm, but with a much longer computation time.