A MULTI-MODAL ROUTE PLANNING APPROACH WITH AN IMPROVED GENETIC ALGORITHM

摘要

The purpose of multi-modal route planning is to provide the traveler with optimal, feasible and personalized route between origin and destination, which may involve public and private transportation modes. The strategy driven approach (i.e. routing by certain predefined transfer order) is useful but can hardly provide free combination of multiple travel modes and some feasible results may be consequently missed. A genetic algorithm (GA) is proposed in this paper to solve the multi-modal route planning problem. Variable length chromosomes with several parts (subchromosome) are utilized to represent routes in multi-modal travel environment, where each part describes a kind of transportation mode. Crossover and mutation operators are redefined in single mode; two new operators, hypercrossover and hypermutation, are defined as inter-mode operation. A multi-criteria evaluation method using a p-dimensional vector to represent multiple criteria is adopted in the fitness function for selecting the optimal solutions. The experimental results show a various mode combination, and some results conform experience well.