Mobility System Optimization (MSO)

Over the past decades, many studies have been conducted to solve complex traffic engineering problems from a multidisciplinary perspective. Such multidisciplinary approach has the advantage of more easily approaching traffic problems by using well-stablished models in other disciplines. Our group (MSO) attempts to solve transportation engineering challenges based on well-established circuit theory governing principles.

The vehicle routing problem (VRP) is one of the combinatorial optimization problems that determine the optimal route through the given waypoints. As the number of waypoints to pass through increases, the computing time required to determine the optimal route increases drastically. Thus, this problem belongs to the NP-hard (non-deterministic polynomial-time hardness) category.

Traveling salesman problem (TSP) is one of the representative VRPs that find the minimum-cost route back to the starting point by visiting all the cities only once. TSP can be modified in various forms depending on the problem conditions: asymmetric TSP, TSP with time window, and so on. TSPs have been widely used for trip planning, transportation system operation, and manufacturing.

Tour improvement method: Ant colony algorithm
(made by baobab)

Trour construction method: Self-Organizing Map algorithm (made by Akash Sharma)

We recently the loop-wise route representation which stems from the circuit analysis. In the proposed method, artificial loop variables are defined in a grid network. This loop-wise route representation expresses any arbitrary route between two nodes in terms of the base route and loop variables. This approach requires a smaller number of design variables to represent a given route than conventional link-wise representation. Another advantage of the proposed method is that the traffic flow conservation is always guaranteed at every node without imposing any constraint. The above features make the formulation for the VRPs much simpler and therefore enhance overall computational efficiency.

The proposed method can be applied to various real-world application. For example, if we consider additional cost for line transfer, we can determine an optimal route for a given subway network. The performance of the proposed method is verified for Busan and Seoul metro, as shown below.

Shortest path problem (SPP), one of classical route optimization problems, is defined to find a minimum-cost path between two nodes. To solve a SPP, many researchers have focused on developing graph search methods such as Dijkstra algorithm and its variants due to their characteristic simplicity and computational efficiency. 

Based on the loop-wise route representation, we can simply formulate a shortest path problem with no constraints. Additionally, by virtue of using the inherent traffic flow conservation in the loop-wise route representation, we can use the proposed optimization as a high-quality dataset generator for training neural networks. Thus, we proposed a deep learning-based method for the SPPs with a higher level of computing accuracy and efficiency.  

Papers


Patents


Projects