Stochastic Scenario-Based Model And Algorithm For Transportation Network Flow Problem

Following the background of transportation network, this paper considers a transportation network flow problem on the long term (strategic) planning level. Specifically, considering the uncertainties of capacities of links and nodes, we formulate an integer programmimg model based on the stochastic scenario-based capacity representation and unique solution constraints cross different scenarios. Furthermore, in view of more complex uncertain environment, we particularly setup a scenario-based random chance-constrained model and fuzzy chance-constrained model on the basis of uncertain programming methods. Lagrangian relaxation solution approach and a genetic algorithm are designed in order to obtain an approximate optimal solution. Finally, the numerical experiments are implemented to demonstrate the efficiency and effectiveness of the proposed approaches.(1) Scenario-based uncertain programmimg fomulationsTo capture the randomness of the network, the stochastic scenario-based link and node capacity representation is employed as the input data. Based on the unique solution constraints, we firstly propose a stochastic scenario-based integer programmimg model to seek the least expected total transportation cost. Then, considering fuzziness and birandomness, we futher formulate a random chance-constrained model and a fuzzy chance-constrained model based on the stochastic scenario-based data. The crisp equivalents of the complex chance-constraints are also investigated.(2) A Lagrangian relaxation solution approachTo obtain a tight lower bound of original problem, we are intended to present a lagrangian relaxation-based approach to dualize hard constraints. Note that capacity constraints and unique solution constraints corss different scenarios are complex, three sets of multipliers are introduced for dualizing these specific constraints. To solve the Lagrangian dual model,we especially decompose it into D X K sub-problems,where each sub-problem is equivalent to the shortest path problem that can be easily solved by modified label correcting or setting algorithms.A sub-gradient algorithm is designed to update the Lagrangian multipliers iteratively along the sub-gradient direction of the objective function in Lagrangian dual model, and the largest objective value encountered is treated as the best lower bound. (3) A genetic algorithmA genetic algorithm is proposed here to search an approximate optimal objective. In this algorithmic procedure, the first step is to seek all the potential paths for each OD using a branch and bound based searching strategy. After that, the technical details of genetic algorithm, including selection, crossover and mutation operations, are designd to search for the optimal tranportation network flow and optimal objective,where the obtained lower bound can be used to evaluate the quality of the optimal objective.(4) Numerical experimentsTo test the quality and computational efficiency of the proposed approaches, two sets of numerical experiments are implemented on a simplified network and a medium-scale network. The performance of the algorithm is analyzed.