用GA算法解决了双层规划问题【国外】【研究生】.zip

# USER-EQUILIBRIUM-SOLUTION User equilibrium is a classical problem on the traffic flow assignment in the field of Transportation Engineering, its main idea is: Every driver cannot reduce his travel time by unilaterally change his travel route. ## THEORY OF USER EQUILIBRIUM SOLUTION Please refer to [User-Equilibrium-Solution.pdf](static/user-equilibrium-solution.pdf). ### Abstract We have given an equivalent formulation, which is a convex optimization problem, of finding user equilibrium solution in the traffic flow assignment, with proof of the equivalence. For the equivalent formulation, we have demonstrated the existence and uniqueness of minimizer. Moreover, the variant of Frank-Wolfe Algorithm is introduced for numerically solving the equivalent formulation. ### Contents + Statement of Problem + Decision Variables and Parameters + Objective and Definition of User Equilibrium + Equivalent Mathematical Formulation + Statement of Equivalent Formulation + Existence of Minimizer + Convexity of Equivalent Formulation + Review on Constrained Problems + Demonstration of Equivalence + Introduction to Frank-Wolfe Algorithm ## INSTRUCTIONS OF PROGRAM All the things are done within 3 main procedures, implement them in `main.py`: ### 1. Data input All the data must be introduced into model by the constructor `TrafficFlowModel.__init__`. ### 2. Solve Invoke `TrafficFlowModel.solve`. ### 3. Output report Invoke `TrafficFlowModel.report`. Then you can just run `$ python main.py`. ## TIPS 1. Parameters in the link performance function such as `TrafficFlowModel._alpha` and `TrafficFlowModel._beta` are directly exposed to users, one can revise them if necessary. 2. Notice the mutual correspondence between the input data while writing them into the `data.py`. 3. When the program doesn't go well, please firstly use `TrafficFlowModel.__str__` (which is already contained in `TrafficFlowModel.report`) to print all the current parameters for ensuring all the data having been introduced into model correctly. 4. In the file `main.py`, all the most-used methods of `TrafficFlowModel` class are given, which are guidelines for the user; and all functions in the repository are more or less with illustrations. 5. It happens that the travelling time of paths in each group are not approximately equal (Thanks to [@Sword-holder](https://github.com/Sword-holder) and his team members for pointing out this phenomenon), since some paths have zero flow. However, in general the number of paths is greater than that of links, which implies the linear mapping from `path_flow` to `link_flow` cannot be injective, so we cannot mathematically obtain the `path_flow` from the `link_flow`, since the inverse mapping does not exist. But this does not influence the existence of unique optimal `path_flow`, the optimal `link_flow` obtained by Frank-Wolfe algorithm is the image of optimal `path_flow` under aforementioned linear mapping. 6. This program might not be numerical stable when it encounters big road network. 7. If you have trouble with implementing of model, or find some bugs, please contact [me](mailto:zheng.andrea.li@gmail.com). ## SAMPLE This sample was provided by Prof. [F. Xiao](https://scholar.google.com/citations?user=prn-uaQAAAAJ) within his lectures at [Southwest Jiaotong University](https://english.swjtu.edu.cn/), and you can find all the data of this toy sample in `data.py`. ### Graph display  ### Parameters of links | LINK | LENGTH | NO. OF LANES | FREE FLOW SPEED | CAPACITY PER LANE| | :-----: | :----: | :----------: | :-------------: | :---------------:| | 5 - 7 | 10.0 | 2 | 60 | 1800 | | 5 - 9 | 10.0 | 2 | 60 | 1800 | | 6 - 7 | 10.0 | 2 | 60 | 1800 | | 6 - 8 | 14.1 | 2 | 60 | 1800 | | 7 - 8 | 10.0 | 2 | 60 | 1800 | | 7 - 10 | 10.0 | 2 | 60 | 1800 | | 8 - 11 | 10.0 | 2 | 60 | 1800 | | 8 - 12 | 14.1 | 2 | 60 | 1800 | | 9 - 10 | 10.0 | 2 | 60 | 1800 | | 9 - 16 | 22.4 | 2 | 60 | 1800 | | 10 - 11 | 10.0 | 2 | 60 | 1800 | | 10 - 13 | 10.0 | 2 | 60 | 1800 | | 11 - 14 | 10.0 | 2 | 60 | 1800 | | 12 - 15 | 10.0 | 2 | 60 | 1800 | | 13 - 14 | 10.0 | 2 | 60 | 1800 | | 13 - 16 | 10.0 | 2 | 60 | 1800 | | 14 - 15 | 10.0 | 2 | 60 | 1800 | | 14 - 17 | 10.0 | 2 | 60 | 1800 | | 16 - 17 | 10.0 | 2 | 60 | 1800 | ### Origin-destination pairs and demands | DEMAND | 15 | 17 | | ------ | :--- | :--: | | 5 | 6000 | 6750 | | 6 | 7500 | 5250 | ### Report of solution (printed in console) ```python # -------------------------------------------------------------------------------- # TRAFFIC FLOW ASSIGN MODEL (USER EQUILIBRIUM) # FRANK-WOLFE ALGORITHM - PARAMS OF MODEL # -------------------------------------------------------------------------------- # -------------------------------------------------------------------------------- # LINK Information: # -------------------------------------------------------------------------------- # 0 : link= ['5', '7'], free time= 10.00, capacity= 3600 # 1 : link= ['5', '9'], free time= 10.00, capacity= 3600 # 2 : link= ['6', '7'], free time= 10.00, capacity= 3600 # 3 : link= ['6', '8'], free time= 14.10, capacity= 3600 # 4 : link= ['7', '8'], free time= 10.00, capacity= 3600 # 5 : link= ['7', '10'], free time= 10.00, capacity= 3600 # 6 : link= ['8', '11'], free time= 10.00, capacity= 3600 # 7 : link= ['8', '12'], free time= 14.10, capacity= 3600 # 8 : link= ['9', '10'], free time= 10.00, capacity= 3600 # 9 : link= ['9', '16'], free time= 22.40, capacity= 3600 # 10 : link= ['10', '11'], free time= 10.00, capacity= 3600 # 11 : link= ['10', '13'], free time= 10.00, capacity= 3600 # 12 : link= ['11', '14'], free time= 10.00, capacity= 3600 # 13 : link= ['12', '15'], free time= 10.00, capacity= 3600 # 14 : link= ['13', '14'], free time= 10.00, capacity= 3600 # 15 : link= ['13', '16'], free time= 10.00, capacity= 3600 # 16 : link= ['14', '15'], free time= 10.00, capacity= 3600 # 17 : link= ['14', '17'], free time= 10.00, capacity= 3600 # 18 : link= ['16', '17'], free time= 10.00, capacity= 3600 # -------------------------------------------------------------------------------- # OD Pairs Information: # -------------------------------------------------------------------------------- # 0 : OD pair= ['5', '15'], demand= 6000 # 1 : OD pair= ['5', '17'], demand= 6750 # 2 : OD pair= ['6', '15'], demand= 7500 # 3 : OD pair= ['6', '17'], demand= 5250 # -------------------------------------------------------------------------------- # Path Information: # -------------------------------------------------------------------------------- # 0 : Conjugated OD pair= 0, Path= ['5', '7', '8', '11', '14', '15'] # 1 : Conjugated OD pair= 0, Path= ['5', '7', '8', '12', '15'] # 2 : Conjugated OD pair= 0, Path= ['5', '7', '10', '11', '14', '15'] # 3 : Conjugated OD pair= 0, Path= ['5', '7', '10', '13', '14', '15'] # 4 : Conjugated OD pair= 0, Path= ['5', '9', '10', '11', '14', '15'] # 5 : Conjugated OD pair= 0, Path= ['5', '9', '10', '13', '14', '15'] # 6 : Conjugated OD pair= 1, Path= ['5', '7', '8', '11', '14', '17'] # 7 : Conjugated OD pair= 1, Path= ['5', '7', '10', '11', '14', '17'] # 8 : Conjugated OD pair= 1, Path= ['5', '7', '10', '13', '14', '17'] # 9 : Conjugated O