University of Twente Student Theses
Improving the upper-level solver for simplified MSMC optimization problems.
Lang, G.S. (2022) Improving the upper-level solver for simplified MSMC optimization problems.
|
PDF
3MB |
| Abstract: | Travel demand origin-destination matrix estimation is a core, but expensive, aspect of transport modeling, especially in the context of large scale modeling. They are used to store, and subsequently generate the trips from an origin to a destination. In this research, the upper level of a bi-level and iterative matrix calibration method, known as multi source matrix calibration (MSMC), is improved upon. This upper-level consists of a convex-quadratic numerical optimization problem, which, by changing OD matrices, aims to minimize the differences between observed and modeled link flows, congestion patterns and delays. This upper-level is implemented in MATLAB and solved by its proprietary solver FMINCON, in combination with the interior-point algorithm. But, this solver shows sporadic, and thus unreliable, tendencies within the upper-level computation times. The first approach taken to improve upon this implementation is to find another, more dependable solver. An initial list of ten solver-algorithm combinations is presented, determined by considering the characteristics of the problem (convex, quadratic and large-scale), as well their capability to integrate with MATLAB. These ten solvers are then evaluated on two separate networks. The first being the smaller academic network Sioux Falls, which is used to filter out the worst performing solvers, by comparing them to the current implementation. With these preliminary tests, this initial list reduced to only five. The second network of the province of Noord-Brabant, being more realistic, is used to assess the solvers for scalability and their performance in a real-world scenario. From this list, none were able to be applied, due to them running out of system memory. After failing to apply these solvers to the Noord-Brabant network due to running out of system memory, a method is stipulated to reduce the problem size. This method makes use of the available gradients, by removing OD-pairs whose absolute gradient values show a low amplitude, as these pairs have a relatively minimal impact on the results of the calibration. Two separate gradient selection methods are then presented. The first is a static method, that selects the OD-pairs based on a set percentage. The second is a dynamic method, which chooses the OD-pairs based on the mean and standard deviation of the distribution of their gradients. This approach of reducing the problem size is shown to have similar convergence in tests on Sioux-Falls, with the dynamic method standing out as the best. Further, when applying this methodology on the network of Noord-Brabant, though the dynamic method shows comparatively worse convergence, the static method, when keeping 50% of the total problem size, is able to reduce the total computation time from 59 to 46 hours, without compromising the final convergence substantially, as the final objective function value is within 1% of the original implementation. It is thus concluded that, with the original implementation, none of the alternative solvers are capable enough to perform in a realistic scenario. Additionally, exploratory results with regards to the problem size reduction are shown to be capable of solving the current issues reliably. Thus, this approach is deemed as an improvement upon the current implementation. |
| Item Type: | Essay (Bachelor) |
| Faculty: | ET: Engineering Technology |
| Programme: | Civil Engineering BSc (56952) |
| Link to this item: | https://purl.utwente.nl/essays/93596 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page