Pavlenko A. Route modeling and optimization in transportation networks

The dissertation is devoted to the topic of modeling and optimizing routes in transportation networks, in particular, application development for constructing optimal routes by cost criteria in time-dependent air networks, taking into account user's limitations and real time calculations requirement. Time dependent optimal traveler's path by cost criteria problem is defined with given user’s limitations: source and target points, travel time window, maximum number of transit points and duration of the trip, desired and prohibited intermediate points. The main difference of this problem from existing ones is taking into account network properties, since it’s time dependent and costs are dynamic. Analysis of models presentations of various transport networks showed their differences and the possibility of applying heuristic approaches to the problem. Multicriterial labelling based algorithm and several ant colony system (ACS) based modifications were proposed to solve the problem. The labeling algorithm showed satisfactory results for small networks, however execution time significantly increased with network growth, comparing to ant algorithm. Developed ACS-based algorithm has been modified with consideration of the specifics of the problem, applying backtracking operation, route fixing, method of branches and bounds, several local search procedures, tabu-lists. To reduce error ratio for international routes, a diversified algorithm of ant colony systems was proposed. To find return or multiregional routes, bidirectional ACS was proposed. To meet the requirements of adaptability and real-time execution, a preliminary data processing algorithm was proposed that uses ACS to search for optimal paths for all pairs of vertices of the network and then uses this information to build relative estimates of the quality of each connection based on cost criteria. Quality ratios are used to find the route in real time. Described problem and solution approaches are relevant for development of techniques for finding optimal traveler’s routes in real time in the public transport network.