Status : Verified
| Personal Name | Rollan, Patrick G. |
|---|---|
| Resource Title | Modified greedy algorithm on game-theoretic traffic assignment |
| Date Issued | 18 December 2018 |
| Abstract | Traffic assignment, from the point of view of microscopic traffic simulation, can be said as the result of multiple travellers concurrently finding their own best path from their origin to their destination points. This scenario can be looked at as a game-theoretic problem where the players decide which path to take, with costs assigned to each choice. An objective function can be used to direct the costs of the travellers, hence their decision, converting the game-theoretic problem into an optimization problem. This study attempts to use greedy algorithm with backtracking as a way to improve the results to solve the simplified version of the game-theoretic wayfinding problem. The road network used is a 3-route network with one entry and one exit node. The vehicles considered are homogenous and enter the road network at constant time intervals, and the pay-offs considered are the travel times obtained from running the traffic simulation using LocalSIM. The objective functions used in the study were developed based on two of Wardrop's principles: User Equilibrium and System Optimal. In addition, the study used 30 different initial conditions partitioned into two types; the non-observed vehicles making unbalanced route choices and non-observed vehicles making balanced route choices. A benchmarking methodology was introduced to first measure the performance of the greedy algorithm in comparison to the brute-force algorithm using both User Equilibrium and System Optimal objective functions. The results show that for optimizing a small number of vehicles (1 ≤ n ≤ 9), the distribution of the discrepancies between the greedy algorithm and the global optimal is skewed towards 0. Hence, for most cases, even without backtracking, the results produced by the greedy algorithm are already close to the optimal case. In addition, the greedy algorithm and the greedy algorithm with backtrack were also compared by running both algorithms, optimizing fixed (n = 100) vehicles. A metric was then defined in order to find the optimal number of backtracks for the greedy algorithm. |
| Degree Course | MS Computer Science |
| Language | English |
| Keyword | traffic assignment ; greedy algorithm ; optimization ; game theory |
| Material Type | Thesis/Dissertation |
Preliminary Pages
1.60 Mb