Mobility System Optimization (MSO)

• Background and research motivation

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.

• Area 1: Vehicle routing problem (VRP) 

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.

• Loop-wise route representation & Its optimization formulation for vehicle routing problems

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.

• Area 2: Shortest path problem (SPP)

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

Papers

1.  G. Kim, H. Jin, M. Kim, K. Kim, I. G. Jang, "Loop-wise Route Representation and Its Optimization Formulation for Symmetric Vehicle Routing Problems," IEEE Transactions on Intelligent Transportation Systems, Accepted, 2023 (Impact factor: 9.551).

2.  G. Kim, S. Kim, and I. G. Jang, "Loopwise route representation-based topology optimization for the shortest path problems," IEEE Access, vol. 10, pp. 128835 - 128846, 2022, doi: 10.1109/ACCESS.2022.3227388 (Impact factor: 3.476).

Patents

1. I. G. Jang, G. Kim, S. Kim, K. Jang, "Loop-wise route representation method for vehicle routing problem and the corresponding optimization formulation", KR Patent, Application Number: 10-2022-0071371, 2022. 

2. I. G. Jang, G. Kim, S. Kim, K. Jang, “Loop-wise route representation method for vehicle routing problem and the corresponding optimization formulation”, PCT Patent, Application Number: PCT/KR2023/000080, 2023.

3. I. G. Jang, G. Kim, S. Kim, K. Jang, “LOOP-WISE ROUTE REPRESENTATION METHOD FOR VEHICLE ROUTING PROBLEM AND THE CORRESPONDING OPTIMIZATION FORMULATION”, US Patent, Application Number: 18/150,267, Confirmation Number: 2176, 2023.

4. I. G. Jang, G. Kim, S. Kim, K. Jang, “LOOP-WISE ROUTE REPRESENTATION METHOD FOR VEHICLE ROUTING PROBLEM AND THE CORRESPONDING OPTIMIZATION FORMULATION”, EP Patent, Application Number: 23150607.2, 2023.

Projects

1. 저탄소 청정 제주(CFI Jeju)를 위한 냉장 전기차량 기반 신선물류 배송체계 구축 기술 개발 (국토교통과학기술진흥원, KAIA)

2. 인프라 센싱 기반 자율 주행 전기 자동차 개발 연구 (KAIST-KU 공동연구센터)

3. mobility Operating System project (조천식 모빌리티 대학원 & 전산학과 대학원)

4. 클라우드 엣지 기반 도시교통 브레인 핵심기술 개발 (정보통신기획평가원, IITP)