Abstract: Effective scheduling and routing of employees and vehicles determines the efficiency of car-sharing systems. Aiming at the scheduling of shared cars within one day, with the objective of minimizing the total system costs and personnel costs, a bi-level optimization model for multiple traveling salesman problem with time windows is established. A genetic algorithm with multi-chromosome coding and the optimized complex mutation operator are developed for the problem solution. From the comprehensive computational experiments, it can be concluded that the total numbers of vehicles and employees with the joint routing plans satisfying the order constraints can be obtained in minimum total costs.

Key words: car-sharing, multiple traveling salesman problem, bi-level programming, multi-chromosome genetic algorithm, mutation operator tree