Modeling And Solution Methods For Lane Reservation Problems In Transportation Planning

The classic transpotation planning problems such as the shortest route problem (SRP), the traveling salesman problem (TSP), and the vehicle routing problem (VRP) have been widely studied. With the progress of social production and the development of culture and economy, there are new transportation planning problems to be solved. These problems come from practical applications. For example, one of them is the lane reservation problem (LRP) when a large sport games is held in a large city. Due to the limitation of road traffic resources, under some situations, there are special requirements to perform some unusual transportation tasks. In such cases, the only way to accomplish such transportation tasks is to select some sections and set up reservated-lanes in existing transportation network. Moreover, it should be done in an urban area where the daily public traffic is very heavy. Thus, by lane reservation, it seriously affects the daily transportation. We need to consider the effect of lane reservation on the public transportation, i.e., the LRP needs to guarantee that the special transportation tasks can be completed according to their requirements by setting up reservated-lanes, while the effect on the public transportation is minimized. The LRP is a new problem in operations research and combinatorial optimization field, which can be applied in emergency traffic for large special events and urban public transportation management. As far as we know, there are few studies in this field at home and abroad. This motivates us to study this problem on its standardized description, formalization, modeling for the basic problem, its extensions, solution methods, etc.Compared with these classic path planning problems, especially the open vehicle routing problem with time windows, the LRP is different in several aspects. For example, in the the LRP, nodes are visited by more than one task, it needs to set up reservated-lanes and they are shared by multiple tasks, and a task should be completed within a given time. In this thesis, the standard LRP is formally described and defined based on the practical application background of reservated-lanes in transport network for large-scale sport games. Then, a 0-1 integer linear programming model is developed. Furthermore, the LRP has been proved to be NP-hard.Based on the analysis of the components of the LRP, three extension problems are proposed. The first problem is the lane reservation problem with transportation task merging. By this model, one can reduce the number of planning lines and the cost of traffic management by adding conditions in some vehicle routes. The second problem is the lane reservation problem for hazardous chemical transportation. It can be derived by removing the conditions for completing tasks. The third problem is the lane reservation problem with multi-objective, which adds minimizing the number of vehicles as the second objective. The models of these problems have been proved correctly and are aaplicable to practical applications.It is well-known that it is nearly impossible to get an exactly optimal solution for such large scale 0-1 integer linear programming problems. Thus, a structural heuristics algorithm is proposed. By this algoritghm, every time, one section with the maximum value of the ratio of time and cost is selected to set up reservated lane under the constraint conditions. Until the time constraints of all tasks are met. Numerical experiments and comparison are done to evalutate the performance of the heuristics algorithm. It is shown that it outperforms the existing ones.A metaheuristic algorithm can obtain a higher quality solution. However, it may not be good enough if each metaheuristic algorithm is used independently. Therefore, hybrid genetic and tabu search algorithm (HGTSA) is developed for the LRP. Experiments show that it can effectively improve the solution quality.