A genetic algorithm for multiobjective path optimisation problem

摘要

The conventional information used to guide drivers in selecting their driving paths is the shortest-distance path (SDP). However, driver path selection is a multiple criteria decision process. This paper presents a multiobjective path optimisation (MOPO) model to make a more precise simulation of the decision-making behaviour of driver path selection. Three single-objective path optimisation (SOPO) models were taken into account to establish the MOPO model. They relate to cumulative distance (shortest-distance path), passed intersections (least-node path, LNP) and number of turns (minimum-turn path, MTP). To solve the proposed MOPO problem, a two-stage technique which incorporates a path genetic algorithm (PGA) and weight-sum method were developed. To demonstrate the advantages of the MOPO model in assisting drivers in path selection, several empirical studies were conducted using two real road networks with different roadway types and numbers of nodes and links. The experimental results demonstrate the advantage that the MOPO model provides drivers more diverse and richer information than the conventional SDP. It can be concluded that with the aids of the GIS, the optimal paths of the MOPO and SOPO problems can be easily identified by the PGA in just a matter of seconds, despite the fact that these problems are highly complex and difficult to solve manually.