A genetic algorithm based approach for solving optimal toll location problems.

A mathematical approach to second-best tolling and to identifying the optimal toll locations for a general network is categorised as a mathematical program with equilibrium constraint (MPEC). This class of optimisation program is an NP-Hard problem which means there does not yet exist any algorithm to find the exact global optimum. A derivative based approach to solve the optimal toll problem (named CORDON) is demonstrated in this paper for a medium scale network. However, as the properties of MPEC suggests that it is unlikely for the derivative based approach to find the global optimal solution, an alternative genetic algorithm (GA) based approach for finding optimal toll levels for a given set of chargeable links (named GA-CHARGE) is developed to tackle this problem. The GA approach does not stop at a local optimum or rely on the use of derivatives. A variation on the GA based approach is also used to identify the best toll locations (GA-LOCATE) making use of "location indices". However, the location indices adopted often overestimate the benefits and this causes a problem when the implementation costs are included in the analysis. Thus, an alternative method based on the idea of Parallel Genetic Algorithms (PGA) is developed. The PGA based method (named PGA-ALL) is designed to solve the problems of optimal toll location and optimal toll levels simultaneously. These methods are tested with a medium-scale network of Leeds to compare their performance. For the covering abstract see ITRD E124693.