Models And Algorithms For Eco-reliable Path Finding Problems In Time-variant And Stochastic Networks

The CO2 emission problem in the transportation sector has been increasingly serious,and taking the CO2 emission constraint into individual trips is the new concept to reduce CO2 emissions in traffic trips. In the complex traffic network, it is of great practical significance to research in the eco-reliable path finding problem, providing travelers with optimal paths which satisfy the CO2 emission constraint and reliability of travel time. Considering the complexly time-varying and stochastic characteristics of real traffic networks, this paper adopts the discretization of time horizons and the sample-based method to describe the time-varying and stochastic link travel times and CO2 emissions in networks. In this paper, we study the eco-reliable path finding problem in time-varying and stochastic networks, and then construct the eco-reliable path finding model and the least emission path finding model with the path travel time reliability and the expected CO2 emissions as evaluation criterions respectively. Based on this, the Lagrangian relaxation algorithm is designed to solve models and obtain the approximate optimal solution of the original problem. Finally, three sets of numerical experiments are tested to demonstrate the efficiency and performance of models and algorithms. The main contents of this paper include:(1) To characterize the dynamics and randomness of the network, we consider two types of time-variant link weights, i.e., link travel times and link CO2 emissions. In detail, we should analyze the quadratic functions of link CO2 emission-average link speed and the inverse relationship between average link travel times and the average link speeds. A sample-based representation method is used to capture the randomness,in which each sample corresponds to time-variant link travel time and link emission data.(2) The eco-reliable path finding model is formulated in time-variant and stochastic networks. Firstly, the time threshold is set in the time-varying and stochastic network to verify whether the space-time route is the on-time arrival route. Finally, the reliability of physical path is defined according to the probability of on-time arrival space-time routes mapped to this physical path. The objective function of this model is the smallest probability of late arrival, and the model adopts CO2 emission standards to restrict paths’ expected CO2 emissions.(3) The least emission path finding model is formulated in time-variant and stochastic networks. The objective function of this model is the least expected CO2 emissions. And the time threshold is set according to the traveler’s expextion to restrict paths’ expected travel time. Finally, we analyze the complexity of the model detailedly,and point out that it is necessary to design the heuristic algorithms to effectively solve the large-scale transportation network problems.(4) The Lagrangian relaxation approach is introduced to relax the primal model into a relaxed model by dualizing hard constraints. The dualzied model is further decomposed into two types of sub-problems (i.e., a standard shortest path problem and a simple univariant linear problem) and a constant, which can be solved by the label-correcting algorithm, a simple single-value linear programming and the given Lagrangian multipliers, respectively. The sub-gradient method is developed to obtain the tight gaps between lower and upper bounds.(5 ) Three sets of numerical experiments (i.e., the tiny three-node network, the medium-scale transportation network and the large-scale transportation network) are tested to demonstrate the efficiency and performance of models and algorithms. In the experiment of the small-scale three-node network, the enumeration method and the Lagrangian relaxation algorithm are employed to solve the model and compare their results. Based on backgrounds of Sioux Falls network and Salt Lake City network,numerical experiments are designed to analyze the quality of solutions and the sensitivity of the time threshold and emission threshold in the model.