A genetic algorithm for vehicle routing problems with temporal synchronization constraints

This paper presents a Genetic Algorithm for the Vehicle Routing and Scheduling Problem with time windows and temporal synchronization constraints. That means that as opposed to the usual procedure, in addition to the usual task covering, some vertices must be served by more than one vehicle at the same time. The chromosome coding used here is based on a proposed solution representation by Mankowska et al. [19]. The Genetic Algorithm is able to solve their instance types up to 20 vertices near to optimality. Even in greater instances with 100 vertices the solution quality of the Genetic Algorithm outperforms the Local Search presented by Mankowska et al. [19], however with losses in runtime. In order to get more comparable results, both solution approaches are evaluated at the well-known benchmark instances of Bredstrom and Ronnqvist [6]. This includes the presentation of a simple repair algorithm during the chromosome crossover based on an insertion heuristic in order to achieve the hard time window constraints of the benchmarks.