[ Article ]

The Journal of Korean Institute of Information Technology - Vol. 21, No. 6, pp.1-7

ISSN: 1598-8619 (Print) 2093-7571 (Online)

Print publication date 30 Jun 2023

Received 16 Jan 2023 Revised 13 Jun 2023 Accepted 16 Jun 2023

DOI: https://doi.org/10.14801/jkiit.2023.21.6.1

항만 물류 환경에서 다중 에이전트 강화학습 기반 최적 배차 모델링 방법

이효준^*

; 장우석^*

; 이성진^**

; 김동규^***

*(주)컨테인어스 개발자
**(주)컨테인어스 대표이사
***(주)컨테인어스 연구소장(교신저자)

Optimal Dispatch Modeling Method based on Multi-agent Reinforcement Learning in Port Logistics Environment

Hyo-June Lee^*

; Woo-Seok Jang^*

; Seong-Jin Lee^**

; Dong-Gyu Kim^***

Correspondence to: Dong-gyu Kim ContainUs Co., 49-1, Haegwan-ro, Jung-gu, Busan, Republic of Korea Tel.: +82-70-4940-2040, Email: donggyukim@containus.kr

초록

항만 물류 환경에서 배차 업무원은 화주가 등록한 컨테이너 화물을 화물 운송 기사에게 매칭하는 배차 업무를 진행한다. 하지만, 사람이 항만 물류 환경에서의 여러 복합적인 요소들을 모두 고려하며 배차하기 어려운 문제가 있다. 이러한 문제를 해결하기 위해 투입할 운송기사, 경로, 순서 등을 결정하는 차량 경로 문제(VRP, Vehicle Routing Problem)가 연구되어 왔고, 여러 가지 제약에 따른 다양한 유형의 문제들이 연구되어 왔다. 본 연구에서는 다양한 유형의 VRP 중 컨테이너 운송기사의 위치 및 컨테이너의 상차 또는 하차 위치를 고려하여 운송기사가 컨테이너를 싣지 않고 이동하는 거리인 공차거리를 최소화하는 연구를 진행하였다. 또한, 본 연구의 확장을 위한 제약 조건 추가를 용이하게 하기 위해 강화학습 기반 최적 배차 모델링 방법을 제안하고 그 분석 결과를 제시한다.

Abstract

In a port logistics environment, dispatchers carry out dispatching tasks that match container cargo registered by shippers with freight forwarders. However, there is a problem in that it is difficult for a person to allocate vehicles while considering all of the various complex factors in the port logistics environment. In order to solve this problem, a vehicle routing problem (VRP) that determines the driver, route, and order to be input has been studied, and various types of problems according to various constraints have been studied. In this study, among various types of VRP, a study was conducted to minimize the tolerance distance, which is the distance that a transport driver moves without loading a container, considering the location of the container driver and the location of loading or unloading the container. In addition, in order to facilitate the addition of constraints for the expansion of this study, we propose a reinforcement learning-based optimal allocation modeling method and present the analysis results.

Keywords:

port logistics, dispatch, vehicle routing problem, reinforcement learning, multi-agent system, double deep q network

Ⅰ. 서 론

항만 물류 환경에서 배차 업무원은 화주가 등록한 운송 예약된 컨테이너를 컨테이너 운송기사에게 배차하는 업무를 수행한다[1]. 배차 효율을 최적화하기 위해서는 컨테이너 운송기사가 컨테이너 화물을 상차 또는 하차하는 지점까지 화물을 싣지 않고 이동하는 공차거리를 최소화하는 것이 필요하다[2]. 하지만, 업무환경에서는 배차 업무원 개인의 경험에 기반한 판단으로 배차를 수행하고 있으며, 이로 인해 배차 효율은 고려하지 않고 순차적으로 배차하는 등 물류 최적화가 어려운 실정이다[3][4].

이러한 투입할 운송기사, 경로, 순서 등을 결정하는 문제는 운송 분야의 중요한 차량 경로 문제(VRP, Vehicle Routing Problem)로 연구되어 왔고, 이 문제는 여러 가지 제약에 따라 다양한 유형으로 나뉜다[5].

다양한 유형의 연구 중 다수의 차량 및 다수의 컨테이너를 가지면서 방문 시간 제약을 가지는 컨테이너 차량의 배차계획 문제이며, 공차거리의 최소화에 관한 연구[6]에서는 각 컨테이너 운송기사가 매 운송마다 1개의 컨테이너만 수송하며, 차량의 최대 운행 시간의 제약에 관한 고려를 더하여 진행하였다. 하지만 항만 물류 환경에서 고려해야할 요소들은 단순히 거리와 시간에 대한 조건만이 아니며, 화물의 크기, 위험물/냉동화물 등의 운송 차량의 조건에 대한 제약, 항만 내의 교통 상태, 운송 경로 상의 교통 상태 등의 여러 복합적인 요소들이 고려되어야만 한다.

본 연구에서는 이러한 문제를 해결하기 위해, 기존 연구의 컨테이너 내륙수송에서의 차량배차에 대한 모형에 대해 인공지능 기술 중 강화학습을 활용하여 항만물류 환경에서의 배차 문제를 해결하고자 한다. 화물 운송 차량을 에이전트로 하여 환경, 보상, 행동의 모델링을 통해 우선적으로 기존 연구 모형을 세부화하여 제시하였기 때문에, 차후 연구들에서 본 연구에서 제시한 강화학습 모델에 여러 제약 조건들을 추가함으로써 확장할 수 있을 것으로 기대한다.

따라서 본 연구에서는 공차거리를 최소화하는 보상함수를 설계하고, 이를 기반으로 강화학습을 수행하는 최적 자동 배차 시스템에 대한 모델링 방안과 그 분석 결과를 제시한다.

Ⅱ. 관련 연구

2.1 차량 경로 문제(VRP, Vehicle Routing Problem)

차량 경로 문제는 주어진 고객 집합에 서비스를 제공하기 위해 차량이 수행해야하는 최적의 경로 집합을 결정하는 문제이며, 많이 연구된 조합 최적화 문제 중 하나이며, 수십년간 많은 연구자들에 의해 다양한 유형으로 연구되어 왔다[7].

특히, 차량 경로 문제는 NP-hard 문제로 알려져 있으며, node의 개수가 증가함에 따라 경우의 수가 무한히 늘어나게 되어 알고리즘으로 최적 경로를 찾는데 한계가 있는 문제이다. 이 한계점을 극복하기 위해 최근엔 강화학습을 이용해 최적 경로를 찾는 연구가 활발히 이루어지고 있다[8].

2.2 Double DQN(Deep Q Network) 알고리즘

강화학습의 목표는 최적의 정책(Optimal policy)을 학습하는 것으로, 동적 환경에서 학습을 수행할 경우 Q-러닝이 널리 이용되고 있다.

Q-러닝은 강화학습의 한 종류로, 에이전트가 상태(State)와 행동(Action)을 통해 최적의 보상(Reward)을 얻는 방법을 학습하며, Q-함수를 사용하여 각 상태-행동 쌍에 대한 누적된 미래의 보상을 높이는 방향으로 학습된다.

DQN은 Q-러닝 알고리즘에 신경망을 도입하여 Q-함수를 근사하는 방식으로, 복잡하고 연속적인 상태 공간을 다룰 수 있게 되었다. 하지만, DQN(Deep Q-Network) 학습에서는 action의 선택과 평가 시 동일한 파라미터 θt를 사용하기 때문에 Q-Value가 지나치게 과대화(Overestimate)되는 경향이 존재하며, 이를 보완하기 위해 DDQN(Double Deep Q-Network)이 제안되었다[9].

DDQN은 기본적으로 DQN과 동일하지만 action의 선택과 평가를 분리한 아이디어가 도입되었다. 각 경험을 무작위로 업데이트하여 두 가지 가치 함수 중 하나를 배우도록 하며, θ와 θ’의 두 가지 가중치 집합이 있다. 매 업데이트마다, 한 가중치 집합은 greedy policy를 결정하는 데 사용되고, 다른 가중치 집합은 그 가치를 결정하는 데 사용된다. 이에 따라 DDQN에서의 예측값인 target Y는 다음 식 (1)과 같이 표현된다.

Y t D o u b l e Q ≡ R t + 1 + γ Q S t + 1, arg ⁡ m a x a Q S t + 1, a; θ t; θ' t

(1)

매 step(t)마다 현재 네트워크의 가중치(Weight) θt를 적용하여 action을 선택, 다음 네트워크의 가중치 θ’_t를 적용하여 action을 평가하며 학습을 진행한다. 또한, 공정한 평가를 위하여 θ_t와 θ’_t의 역할을 바꾸어 대칭적으로 업데이트할 수 있다.

2.3 다중 에이전트 강화학습

본 논문에서는 다수의 컨테이너 차량에 대해 배차가 이뤄질 때마다 배차 대기 중인 컨테이너가 달라지는 동적 환경에서 다중 에이전트 간 상태 공유, 상태에 따른 보상을 설계함으로써 상호간 협력 또는 경쟁에 관한 모델링이 필요하다. 이에 따라 복잡한 실세계의 개념을 구체화 해나가는 모델로 널리 이용되고 있는 먹이 추적 문제[10][11]에서 착안하여 본 연구를 진행하였다.

먹이 추적 문제는 복잡한 현실 세계의 개념을 구체화 해나가는 모델로, N by N 크기의 환경에서 최소 4개의 에이전트가 1개의 먹이를 4방향에서 포획하는 문제이며, 각 에이전트들은 1개의 먹이를 포획하기 위해 상호 협력한다[12].

본 연구에서는 이에 착안하여 컨테이너 운송 차량을 각 에이전트로, 운송할 컨테이너를 먹이로 대치하며 그 개수를 늘렸고, 포획이라는 개념을 컨테이너에 도착하는 것으로, 포획하기 위해 상호 협력하는 부분을 서로 겹치지 않는 컨테이너에 도착하기 위한 협력으로 대치하여 진행하였다.

Ⅲ. 강화학습 모델

강화학습 모델은 환경의 상태, 행동, 그리고 환경의 상태를 매 Episode마다 초기화 하는 reset, 한 Episode 내에서 환경의 상태가 행동을 결정할 때마다 환경의 상태를 변경하고 보상을 부여하는 step으로 구성된 환경(Environment) 총 3가지 요소를 통해 도출된다. 최적 배차 모델을 도출하기 위하여 상태, 행동, 보상과 학습하는 환경은 다음과 같이 구성하였다.

Fig. 1.

Algorithm pseudocode

3.1 환경의 상태

그림 2에서 6×6 격자(grid) 환경은 3개의 에이전트(Ai)와 6개의 컨테이너(Ci), 6개의 도착지(Di)로 구성되어있으며, 각각의 화물과 도착지는 쌍을 이룬다. 환경의 상태는 각 에이전트, 컨테이너, 도착지의 좌표 및 상태로 구성하였으며, 각 에이전트, 컨테이너, 도착지의 상태는 각각 대기 중, 배차 완료, 운송 중, 운송 완료의 4가지로 정의하였다.

Fig. 2.

6×6 grid environment

초기 환경의 상태는 각 에이전트의 좌표와 상태(대기 중), 각 화물의 좌표와 상태(대기 중), 각 도착지의 좌표와 상태(대기 중)로 구성하였다. 매 step마다 에이전트들은 각각이 배정받은 목표 지점으로 이동하며, 목표 지점 배정 절차는 그림 1과 같다.

에이전트(Ai)의 상태가 대기 중일 때는 운송 가능한 컨테이너(Cj) 좌표 중 한 곳이 목표 지점으로 배정되고 해당 목표 지점에 도달할 때까지 에이전트의 상태는 배차 완료로 변경된다.

운송 가능한 컨테이너가 없을 경우에는 대기 중을 유지하며 이동하지 않는다.

에이전트의 상태가 배차 완료일 때는 배정받은 목표 지점(컨테이너 좌표)으로 이동하며, 배정받은 목표 지점에 도달했을 경우 에이전트의 상태는 운송 중으로 변경되며, 해당 위치에 있던 컨테이너(Cj)의 도착지(Dj) 좌표가 목표 지점으로 배정된다.

에이전트의 상태가 운송 중일 때는 배정받은 목표 지점(도착지)으로 이동하며, 배정받은 목표 지점 즉 도착지에 도착했을 경우 에이전트의 상태는 대기 중으로 변경되며 각 컨테이너의 상태와 도착지의 상태는 도착 완료로 변경된다.

3.2 행동

3.1에서 상술했듯이 에이전트가 대기 중일 때 운송 가능한 컨테이너 좌표 중 한 곳이 목표 지점으로 배정되는데, 해당 목표 지점을 고르는 행위가 행동(action)이며, 이 때 행동 값은 식 (2)와 같이 ε-greedy 정책에 따라 s(state, 환경의 상태), a(action, 행동)에 따른 Q값이 최대가 되게 하는 값으로 결정된다.

Π s = a r g m a x a ∈ A Q s, a

(2)

3.3 보상

매 step마다 각 에이전트의 상태가 배차완료일 경우 –1의 보상(reward)을, 운송 중일 때는 +1의 보상을, 대기 중일 때는 0의 보상을 얻는다. 이를 통해 학습이 진행될수록 각 에이전트는 가장 가까운 위치에 있는 컨테이너를 운송한다.

Ⅳ. 모델 학습 결과 및 분석

최적 배차 모델의 학습을 위하여 다중 에이전트 환경에서 DDQN알고리즘을 사용하였다.

9000회의 Episode동안 학습을 진행 후 생성된 모델을 분석하였으며 학습 기간은 약 3일 소요되었다. 학습에 사용된 서버의 사양은 표 1과 같으며, 학습에 적용된 초매개변수(Hyper parameter)는 표 2와 같다.

Table 1.

Learning server specs

Table 2.

Hyper parameter

학습 결과, 그림 3의 그래프와 같은 결과를 얻을 수 있다. 그래프의 음영처리 된 부분은 실제 매 Episode마다 획득한 reward의 값이며, 학습이 진행됨에 따라 최댓값인 9 근방의 밀도가 높아짐이 확인된다. 이를 보다 가시적으로 표시하기 위해 매 100Episode마다 reward의 평균값을 짙은 선의 그래프로 나타내었고, 학습이 진행됨에 따라 최댓값인 9에 수렴함을 확인된다. 실제 학습된 모델을 실행했을 때 reward 값이 9가 되는 각 에이전트 별 화물 매칭 순서쌍이 일치함을 확인할 수 있다.

Fig. 3.

Gained reward and average of reward per episode

따라서 본 논문에서 제안한 모델링 방법을 통한 학습 결과, 그림 2와 같이 단순화된 환경에서 각 에이전트들이 최소한의 거리를 이동하며 화물을 운송함을 알 수 있다.

또한, 강화학습 알고리즘의 학습 과정을 평가하기 위한 연구가 이미 이뤄져 있고[13], 해당 연구에 따라서 Rewards의 정규화된 누적 분포 함수 그래프로 나타낸 결과 그림 4와 같이 나타난다. 그림 4의 정규화된 누적 분포 값의 평균을 소수점 다섯째 자리에서 반올림했을 때의 값은 0.3036으로, 해당 연구에서 제시하는 Aggregate Performace 표에서 1위인 0.4623, 2위인 0.4366에 이은 3위의 순위에 해당하므로 해당 연구에서 제시하는 성능 지표 상 우수함을 확인할 수 있다.

Fig. 4.

CDF of cumulative reward by trained model-normalized

Ⅴ. 결론 및 향후 연구 방향

본 연구에서는 다중 에이전트 환경에서 DDQN 알고리즘을 적용하여 최적 배차 문제에 대한 강화학습을 진행하였다. 학습 과정에서 평균 보상 값이 증가하고, 해당 값이 이론적으로 가능한 최대 보상에 접근하는 것을 확인하였다. 또한, Jordan의 강화학습 알고리즘 평가 방법을 사용하여 우수한 성능을 입증하였다.

그러나 본 연구의 한계는 6×6 격자 환경에서 3개의 에이전트와 6개의 목적지를 사용하여 단순화된 환경에서만 학습을 진행하였으며, 이러한 단순화된 환경에서도 학습에 약 3일이 소요되었다는 점이다. 2021년 기준 실제 환경에서는 일일 물동량이 약 8만 건, 운송사 수가 약 1632개, 평균 운송사별 일일 물동량이 약 50건, 컨테이너 트럭 수가 약 3만 대, 평균 운송사별 트럭 보유 수가 약 20대 등, 본 연구의 환경보다 복잡한 상황을 고려해야 한다.

하지만, DDQN은 낮은 차원의 이산적인 행동 공간(Discrete action sapce)에서만 효과적이며, 행동의 종류가 늘어날수록 차원의 저주에 빠지는 단점이 있다. 실제 환경에서는 이러한 단순화된 환경보다 큰 행동 공간을 갖게 되므로, 이를 해결하기 위한 방법이 필요하다.

향후 연구에서는 이산적인 행동 공간을 연속적인 행동 공간(Continuous action space)으로 바꾸고, K-NN알고리즘(K-Nearest Neighbors)을 사용하여 작업을 선택하며, DDQN 대신 연속적인 행동 공간에 적합한 DDPG 알고리즘을 사용하고자 한다[14]. 또한, 실제 환경에 강화학습 모델을 적용하기 위해 환경 로직을 단순화하거나, 또 다른 알고리즘을 적용하여 복잡한 환경에서 보다 짧은 시간 안에 학습을 완료시킬 수 있는 방법을 연구하고자 한다. 이외에도, 다양한 항만물류 환경의 복잡성과 제약 조건들을 고려하는 연구가 추가적으로 필요함을 인식하고 있다.

실제로, 본 연구에서 적용한 3개의 에이전트와 6개의 목적지에 대한 배치는 단순화된 시나리오이며, 실제 운송사별로 약 20대의 트럭과 일일 50건의 물동량을 고려한다면, 행동 공간의 크기는 기하급수적으로 증가한다. 이에 대응하기 위해서는 DDQN을 넘어서, 연속적인 행동 공간을 다루는 알고리즘이 필요하다.

따라서 향후 연구에서는, DDPG와 같은 알고리즘을 적용하여 행동 공간의 크기가 큰 실제 환경에서의 최적 배차 문제를 해결하는 것을 목표로 할 것이다. 이를 통해 본 연구의 방법론을 더욱 실용적으로 확장하고, 실제 항만물류 환경에 적용 가능한 강화학습 알고리즘의 성능을 향상시키는 데 기여하고자 한다.

Acknowledgments

본 연구는 중소벤처기업부의 재원으로 중소기업기술정보진흥원의 지원을 받아 수행된 연구임(2023 산학연 Collabo R&D)

이 논문은 2022년도 한국정보기술학회 추계 종합학술대회에서 발표한 논문(항만 물류 환경에서 다중 에이전트 강화학습 기반 최적 배차 모델링 방법)을 확장한 논문임.

References

S. Han, "A Study on Construction plan of Integrated truck allocation system for Export and import Container's inland transportation efficiency improvement", master's thesis Seokyeong University Business School, 2011.
B. Choi, S. Kim, and H. Park, "A Study on Selecting Factors of Container Shuttle Carrier by Logistics Companies in the Port Hinterland", Journal of Korea Port Economic Association, Vol. 37, No. 2, pp. 107-118, Jun. 2021. [https://doi.org/10.38121/kpea.2021.06.37.2.107]
H. Kwon, "A study on Transportation peration Efficiency through Improvements to Shipping Operations", Master's thesis of Seokyeong University Business School, 2010.
J. Kim, "Development of Scheduling System for Container Transportation using Genetic Algorithm", Master's thesis of Dong-A University graduate school of Management Information Systems, pp. 55-65, 2013.
Y. Choi, "A Study on the Integrated Dispatch System for Efficient Truck Operation", Department of Shipping and Port Logistics Graduate School of Marine Finance & Logistics Korea Maritime and Ocean University, 2017.
W. Y. Yoon, C. G. Ahn, and Y. S. Choi, "A Truck Dispatching Problem in the Inland Container Transportation with Empty Container", Journal of the Korean Operations Research and Management Science Society, Vol. 24, No. 4, pp. 63-80, Dec. 1999.
P. Toth and D. Vigo, "VRP with Backhauls", The vehicle routing problem, Society for Industrial and Applied Mathematics, 2002. [https://doi.org/10.1137/1.9780898718515.ch8]
A. Bogyrbayeva, M. Meraliyev, T. Mustakhov, and B. Dauletbayev, "Learning to Solve Vehicle RoutingProblems: A Survey", arXiv:2205.02453, , May 2022. [https://doi.org/10.48550/arXiv.2205.02453]
H. Hasselt, A. Guez, and D. Silver, "Deep reinforcement learning with double q-learning", Proc. of the AAAI conference on artificial intelligence, Vol. 30, No. 1, Mar. 2016. [https://doi.org/10.1609/aaai.v30i1.10295]
P. Stone and M. Veloso, "Multiagent systems: A survey from a machine learning perspective", Autonomous Robots, pp. 345-383, Jun. 2000. [https://doi.org/10.1023/A:1008942012299]
M. Benda, "On optimal cooperation of knowledge sources: an empirical investigation", Technical Report, Boeing Advanced Technology Center, 1986.
H. I. Lee and B. C. Kim, "Multagent Control Strategy Using Reinforcement Learning", The KIPS Transactions:PartB, Vol. 10, No. 3, pp. 249-256, Jun. 2003. [https://doi.org/10.3745/KIPSTB.2003.10B.3.249]
S. Jordan, et al., "Evaluating the performance of reinforcement learning algorithms", International Conference on Machine Learning PMLR, Vol. 119, pp. 4962-4973, 2020. [https://doi.org/10.48550/arXiv.2006.16958]
G. Dulac-Arnold, et al., "Deep reinforcement learning in large discrete action spaces", arXiv:1512.07679, , Dec. 2015. [https://doi.org/10.48550/arXiv.1512.07679]