Data-driven Optimization Research on Transportation Facility Planning and Scheduling Problems


Student thesis: Doctoral Thesis

View graph of relations



Awarding Institution
  • Kwai Sang CHIN (Supervisor)
  • Zhili Zhou (External person) (External Supervisor)
Award date3 Oct 2018


Transportation is crucial to the development of cities to ensure the competitiveness, economic growth and quality life of cities. With the growing urbanization, most cities are experiencing the dramatic increase in vehicle stocks. The existing transportation infrastructures are unable to satisfy the increasing transportation needs, which cause a series of problems, such as traffic congestion and air pollution. Hence, it is necessary to redesign the existing transportation network or construct new transportation facilities to meet the increasing requirements. Moreover, the emergence of some modern transportation modes, for example public bike sharing, raise new types of optimization problems during their system operations. Therefore, the optimization problems involving transportation facility planning and scheduling is an important topic in the field of urban transportation and logistics.

In the study of system optimization research, models are built based on system appearances that describe the features and structure of the system. One deficiency of previous studies on transportation system optimization is the inaccurate representation of system appearances due to lack of data describing transportation systems. Technological advancement has led to many changes in transportation. Many intelligent transportation systems are being constructed for different purposes in transportation systems. An enormous amount of various transportation data can be collected and stored at low costs, which creates opportunities to improve transportation systems with data science.

This thesis focuses on data-driven optimization research on transportation facility planning and scheduling problems, aiming at integrating data analytics into the studies of transportation system optimization problems. Cluster and prediction methods are applied to transform mass transportation data into information. Optimization models are built with the transformed information as input data. Some exact and heuristic algorithms are developed to tackle the proposed models and conduct computational experiments based on real data. This data-driven research framework is applied to optimizations of three typical public transportation systems, which include lane reservation problem of the bus system, location problem of the public charging system, and bike rebalancing problem of the public bike system. The three research issues are introduced as follows:

First, we study a green lane reservation problem of public transportation with traffic state estimation based on real transportation data. We investigate this problem form the environment’s perspective and incorporate the real traffic state of a city into decision-making. Lane reservation problem is to optimally select reserved lanes in an existing road network to improve the efficiency of special transports with minimum negative impact. The environmental impact of the reserved lanes is evaluated by carbon emission model. The real traffic states are estimated by a gird-based clustering method using GPS (The Global Positioning System) trajectory data from thousands of traveling vehicles. A mixed integer programming model is proposed to facilitate optimal selection of reserved lanes from the viewpoint of minimizing carbon emission caused by reservation strategy. Extensive computational experiments based on real data are conducted to test the effects of several factors. The results suggest that marginal environmental impact of reserved lanes on normal traffic goes down while the number of reserved lanes increases. In a congested area, reserved lanes can achieve more remarkable improvement to special transports but lead to more negative environmental impacts on normal lanes than a smooth area.

Second, we work on the bi-objective location problem of public charging stations with potential charging demand estimation. The lack of charging infrastructure is the major barrier to promote electric vehicles. The model proposed in this part overcomes the difficulty in estimating of potential charging demand and dealing with a variety of charging technologies and strategies. The potential charging demand is estimated based on current vehicle density which is derived from vehicle speed by traffic flow models. The vehicle speed data is estimated based on GPS data of traveling vehicles. A cell-based bi-objective location model is proposed to decide locations, capacity options, and service types for charging stations, in which the city is divided into a grid with estimated charging demand in each cell. Two objective functions are included with one minimizing the total cost and the other maximizing the service quality. A hybrid multi-objective meta-heuristic algorithm is proposed to solve the problem, which is then compared with the ε-constraint method. The solution methods are tested using 36 problem instances and compared via four multi-objective optimization metrics. The results show that the proposed algorithm can address large-scale problems efficiently and thus is more appropriate in practice. A case study is presented which is to design an electric vehicle charging station network for Shenzhen, China with real GPS trajectory data.

Third, we deal with the bike rebalancing and collection problem of the public bike sharing system based on bike usage prediction. This study is advantageous in considering the collection of broken bikes during the rebalancing activity and using historical data to arrange the amount of rebalancing and collection for each station. Specifically, the bike rebalancing problem refers to the redistribution of bikes between stations by vehicles to avoid the stations from becoming empty or full. Leaving broken bikes in stations is not only a waste of space but also decreases customer satisfaction. Therefore, it becomes necessary to collect broken bikes from stations and move them to depots for repairing. Further, we use historical data of the bike sharing system to infer the rebalancing and collection requests based on a bike usage prediction method. Thus, a new type of bike rebalancing and collection problem with bike usage prediction is studied. We first propose an integer programming model for the single-depot and single-vehicle situation. A dynamic programming based exact algorithm is presented to solve it. Next, the model is extended to the multi-depot and multi-vehicle situation. A hybrid heuristic algorithm based on variable neighborhood search is finally proposed to solve the model. For both situations, computational experiments and sensitivity analyses are conducted. The results show that the proposed algorithms can provide high-quality solutions with reasonable computation time.