균등 배차를 고려한 유전 알고리즘 기반 항만 물류 AI 자동 배차 최적화 방법

Ⅰ. 서 론

한국의 수출입 화물 운송은 도로, 철도, 연안 해상 운송을 통해 이루어지며, 그 중 도로 운송은 대부분 컨테이너 트럭에 의해 수행되고 있다. 컨테이너 화물의 도로 운송 시 교통혼잡, 대기오염, 대형교통사고, 도로파손 등 문제의 해결책으로 철도 및 연안 운송이 부각되고 있지만, 아직까지 한국은 도로 운송에 과도하게 의존하고 있다. 한국교통연구원에서 발간한 2023년도 화물운송시장동향 연간보고서에 따르면 2023년도 도로 수송량 수단부담률이 95.4%수준에 달하는 것으로 나타났다. 한편, 전 세계적으로 컨테이너 선박 대형화가 지속적으로 진행되고 있으며, 이러한 추세는 앞으로도 계속될 것으로 전망된다. 이에 따른 물량 증가에 대응하기 위해 국내 물류산업 분야에서는 운송 관련 제도·절차 개선, 물류 시설의 확충, 도로 화물 수송의 효율화를 포함한 종합적인 대응 마련이 필요하다.

도로 화물 수송의 효율화를 위해서는 수요관리와 함께 화물자동차 운행 효율화가 이루어져야 한다. 화물자동차 운행 효율화는 G. B. Dantzing, et al.[1]가 차량경로문제(VRP, Vehicle Routing Problem)로 제안한 이후로 꾸준히 연구되고 있는 분야이다. 컨테이너 운송 배차 계획 문제는 VRP 문제 중 하나로, 운송회사에서 화주의 화물 운송 요청을 운송회사에 소속된 차주(컨테이너 트럭)에 적절히 배차하기 위해 수립하는 계획을 의미한다. 기존의 배차 계획 업무는 배차 업무원들의 직관적 판단에 의존하는 형태였으나, 최근에는 정보화 및 자동화 기술의 도입으로 AI 기술을 활용하여 객관적 판단을 통해 효율적이고 보다 합리적인 대책을 수립하고 있다. AI 기반 배차 계획은 급증하는 운송 수요 충족시키고, 운송 비용을 효과적으로 절감하고 배송 신뢰성을 높일 수 있다. 다양한 AI 기술이 배차 최적화 연구에 활용되고 있다[2][3]. 대표적인 예시로 E. Lee et al.[4]은 Random forest 기법을 도입하였고, A. Nazari et al.[5]은 강화학습 기법을 활용하였으며, B. M. Baker, et al.[6]은 VRP를 위한 유전알고리즘 모델을 제안하였다. 대부분의 배차 최적화 연구들은 화주 중심의 관점에서 운송 비용 최소화를 목표로 이루어진다. 그러나 차주의 권익 보호 문제는 오래전부터 꾸준히 제기되어 왔음에도 불구하고, 대부분의 연구에서는 이를 충분히 고려하지 못하고 있다. 특히 차주 간의 과도한 경쟁은 근로 조건 악화와 도로 안전 문제로 이어질 수 있어 공정성과 안정성을 확보하는 것이 매우 중요하다.

또한, 실시간으로 급변하는 화물 운송 관련 데이터에 대응하여 배차 계획을 수립하기 위해 빠른 학습 속도 및 처리 속도가 요구된다. 이전 연구[7]에서는 강화학습 기반 AI 배차 계획 수립 연구를 진행하였으나, 단순화된 환경에서 3일 이상의 학습 시간이 걸려 실무에 적용하기에 어렵다는 점을 문제점으로 안고 있었다. 유전 알고리즘과 강화학습의 성능은 여러 분야에 걸쳐 비교되어 왔으며, 여러 연구들[8]-[10]에서 유전 알고리즘이 강화학습의 성능을 뛰어넘는 결론을 내어왔다.

따라서 본 논문에서는 AI 기술 중 메타 휴리스틱 알고리즘 분야의 유전 알고리즘을 기반으로 하여 빠른 최적 배차 수립을 진행하며, 균등 분배를 통해 화주와 차주의 입장을 균형있게 고려하여 효율성과 공정성을 동시에 확보할 수 있는 AI 자동 배차 최적화 방법을 제시한다. 화물 자동차의 운행 효율을 나타내는 공차 거리율을 최소화하여 불필요한 비용과 시간을 효과적으로 절감하였고, 차주 간 균등 배차를 통해 운송업체 간의 경쟁을 완화하여 공정성을 확보한다.

본 논문의 구성은 다음과 같다. 2장에서는 메타 휴리스틱 알고리즘을 소개하며, 그 중에서도 유전 알고리즘에 대해 기술한다. 3장에서는 배차 계획 문제를 해결하기 위한 유전 알고리즘의 모델을 정의하고 균등 분배를 고려한 배차 최적화 적합도 함수에 대해 자세하게 기술한다. 4장에서는 본 연구에서 제시한 알고리즘의 성능 평가하고, 그 결과를 분석한다. 5장에서는 결론을 제시하고, 연구의 한계점 및 향후 연구 방향에 대해 논의한다.

Ⅱ. 관련 연구

2.2 유전 알고리즘

유전 알고리즘은 생물의 진화를 모방한 기법으로일반적인 최적화 이론에서 사용되는 목적 함수의 미분 연산이 없어 비교적 구현하기 쉽고, 빠르게 최적해를 찾는 기법이다[14]. 유전 알고리즘에서의 최적화는 다음과 같이 진행된다. 먼저 최초의 해(염색체) 집합을 생성하고 이를 초기 세대로 설정한다. 이후, 해당 세대의 적합도를 평가하여 교차(교배)에 사용할 부모 해를 선택한다. 선택된 부모 해를 기반으로 교차와 변이과정을 거쳐 새로운 해 집합을 생성하며, 이를 다음 세대로 설정한다. 이러한 과정을 반복하며 최적해를 탐색한다. 이러한 과정을 그림 1에 나타내었다.

Fig. 1.

Structure of genetic algorithm

Ⅲ. 제안하는 알고리즘

3.1 유전알고리즘 모델 정의

컨테이너 차량의 배차 계획 문제는 다수의 운송 요청을 운송업체에 소속된 차주들에게 적절히 할당하는 것이다. 이를 유전 알고리즘 모델로 표현하면, 하나의 차주(Trucker)는 하나의 유전자(Gene)가 된다. 유전자 안에는 차주와 체결된 여러 개의 운송 정보가 존재하고, 운송 정보는 화물 정보, 상차지, 하차지 등을 포함한다. 이렇게 전체 유전자(차주)에 대해 수립된 배차 계획이 하나의 염색체(Chromosome) 즉, 최적화 하고자하는 해가 된다. 배차 수립의 염색체 표현을 그림 2에 나타내었으며, 각 유전자와 염색체는 그림 1에 따라 유전 알고리즘에 적용된다. 이 때, 트럭 n의 경우 i번째 운송에서 하차지의 위도를 $$ {\varphi }_u^i$$, 경도를 $$ {\omega }_u^i$$, i+1번째 운송 요청에서 상차지의 위도를 $$ {\varphi }_n^{i+1}$$, 경도를 $$ {\omega }_n^{i+1}$$으로 정의하고, 3.2에서 공차 거리를 계산한다.

Fig. 2.

Chromosome representation of the dispatch plan

Ⅳ. 성능 분석

한국교통연구원에서 2025년 1월 발행한 물류브리프에 따르면, 컨테이너 트럭 수가 32,889대, 2024년 7월 발행한 화물자동차 운송·주선업체 조사보고서에 따르면 운송주선사는 총 1,239개로, 각 운송주선사는 평균 27명의 차주를 운용한다고 볼 수 있다. 단, 본 연구는 자체 배차 시스템 제작이 어려운 영세 운송주선사를 대상으로 한 것으로, 이보다 적은 차주를 운용하는 환경을 구성하였다.

따라서 제안한 알고리즘의 성능 평가를 위해서 본 연구에서는 실제 컨테이너 운송회사 G사의 1개월간 배차계획의 평균 운송 주문수 66개, 평균 차주 수 17명의 환경[17]에서 κ는 1/10000으로 설정하여 시뮬레이션 하였다. 균등 분배 제약의 효과를 검증하기 위해 적합도 F의 라그랑주 승수 λ를 조절하면서 100번씩 반복하였다.

시뮬레이션 컴퓨터의 사양은 표 1에 나타내었고, 유전 알고리즘의 하이퍼파라미터(Hyperparameter)는 표 2와 같다.

Table 1.

Simulation computer specifications

Table 2.

Hyperparameter of genetic algorithm

표 2에서 나타낸 각각의 하이퍼파라미터 값은 공차 거리 감소율이 최댓값일 때의 실험적 결과이다.

총 공차 거리 감소율과 차주 당 운송 개수의 분산을 측정한 결과를 아래 그림 3과 그림 4에 각각 나타내었다. 기존의 균등 분배를 고려하지 않은 연구와 같이 λ가 0으로 균등 분배가 전혀 고려되지 않을 경우, 공차 거리 감소율은 최대 47.9%에 달하지만, 각 차주 당 운송 개수의 분산 역시 최대치로 나타나 배차의 불균형이 존재함을 확인할 수 있다. 반면, λ가 증가함에 따라 분산이 효과적으로 감소하여 균등 분배가 적용되고 있음을 볼 수 있다. 공차 거리 감소율 역시 감소하지만, λ=1로 균등 분배가 완전히 이루어졌을 때도 공차거리 감소율이 21.3%를 유지하여 여전히 효과 있음을 확인할 수 있다. 또한, 유전알고리즘의 평균 학습 시간은 약 6.43초로, 신속한 배차 수립이 가능함을 보여준다.

Fig. 3.

Reduction rate with respect to λ

Fig. 4.

Variance with respect to λ

Ⅴ. 결론 및 향후 과제

최근 컨테이너선의 대형화에 따른 육상운송 물동량 증가로 효율적인 컨테이너 화물 도로운송 시스템 구축의 필요성이 더욱 강조되고 있다. 특히 AI 기반의 자동 배차 시스템은 비용 절감으로 운송 효율을 극대화할 수 있는 뛰어난 기술로 주목받고 있지만 차주의 과잉 업무 및 경쟁 문제에는 충분히 대응하지 못하고 있다. 따라서, 비용 절감뿐만 아니라 차주를 고려한 균형 잡힌 접근이 필요하다.

본 논문에서는 균등 배차를 고려한 AI 자동 배차 최적화 방법을 제안하였다. 신속한 배차 계획 수립을 위해 유전 알고리즘을 활용하였으며, 알고리즘의 최적화 과정에서 균등 분배를 제약 조건으로 적용한 새로운 적합도 함수를 설계하였다. 이를 통해 운송 효율성을 높이고, 과잉 경쟁을 예방할 수 있는 시스템을 구현하였다.

제안한 알고리즘의 성능 평가를 위해 공차 거리 감소율, 차주 당 운송 개수의 분산, 학습 시간을 측정하였다.

그 결과, 제안한 알고리즘이 균등 분배를 만족하면서 공차 거리 감소율을 효과적으로 높이는 배차 계획을 빠르게 수립할 수 있음을 보였다.

그러나 제안 시스템에서 화물차의 종류에 따른 운송 가능한 화물 및 적재용량, 차주의 운송 지역 및 시간대에 대한 개인 선호도를 고려하지 않았다는 점에서 본 연구의 한계를 찾을 수 있다. 따라서 이들 한계점을 극복하기 위한 연구를 본 논문의 향후 과제로 한다.

Acknowledgments

본 성과물은 중소벤처기업부에서 지원하는 2023년도 산학연 Collabo R&D사업(RS-2023-00225422)의 연구수행으로 인한 결과물임을 밝힙니다

References

• G. B. Dantzig and J. H. Ramser, "The Truck Dispatching Problem", ManagementScience, Vol. 6, No. 1, pp. 80-91, Oct. 1959. [https://doi.org/10.1287/mnsc.6.1.80]
• A. Bogyrbayeva, et al., "Machine learning to solve vehicle routing problems: A survey", IEEE Transactions on Intelligent Transportation Systems, Vol. 25, No. 6, pp. 4754-4772, Jun. 2024. [https://doi.org/10.1109/TITS.2023.3334976]
• R. Shahbazian, et al., "Integrating Machine Learning Into Vehicle Routing Problem: Methods and Applications", IEEE Access, Vol. 12, pp. 93087-93115, Jul. 2024. [https://doi.org/10.1109/ACCESS.2024.3422479]
• E. Lee and S. Cheon, "A study on the optimal process for efficient logistical transport", Journal of The Korean Data Analysis Society, Vol. 25, No. 2, pp. 509-521, Apr. 2023. [https://doi.org/10.37727/jkdas.2023.25.2.509]
• M. Nazari, A. Oroojlooy, L. V. Snyder, and M. Takáč, "Reinforcement learning for solving the vehicle routing problem", NIPS'18: Proceedings of the 32nd International Conference on Neural Information Processing Systems, Montréal Canada, pp. 9861-9871, Dec. 2018.
• B. M. Baker and M. A. Ayechew, "A genetic algorithm for the vehicle routing problem", Computers & Operations Research, Vol. 30, No. 5, pp. 787-800, Apr. 2003. [https://doi.org/10.1016/S0305-0548(02)00051-5]
• H.-J. Lee, W.-S. Jang, S.-J. Lee, and D.-G. Kim, "Optimal Dispatch Modeling Method based on Multi-agent Reinforcement Learning in Port Logistics Environment", The Journal of Korean Institute of Information Technology, Vol. 21, No. 6, pp. 1-7, Jun. 2023. [https://doi.org/10.14801/jkiit.2023.21.6.1]
• M. Xu, Y. Mei, F. Zhang, and M. Zhang, "Genetic Programming and Reinforcement Learning on Learning Heuristics for Dynamic Scheduling: A Preliminary Comparison", IEEE Computational Intelligence Magazine, Vol. 19, No. 2, pp. 18-33, May 2024. [https://doi.org/10.1109/MCI.2024.3363970]
• T.-S. Ha, D.-B. Jeon, D.-E. Song, K. Y. Kim, and H. W. Lee, "Comparison of Learning Performance of Genetic Algorithms and PPO Algorithms in Virtual Environment", Journal of Next-generation Convergence Technology Association, Vol. 6, No. 9, 1571-1578, Sep. 2022. [https://doi.org/10.33097/JNCTA.2022.06.09.1571]
• K. Park and J. Lee, "A Study on Optimization of Natural Gas Liquefaction Process Using Reinforcement Learning", Korean Chemical Engineering Research(Hwahak Konghak), Vol. 63, No. 1, 50-58, 2025.
• K.-S. Lee and I.-H. Bae, "A Comparison of Heuristic and Genetic Algorithms in Task Allocation Problems", Korean Institute of Information Scientists and Engineers, Vol. 20, No. 1, pp. 669-672, Apr. 1993.
• C.-W. Han and J.-I. Park, "A Study on Adaptive Random Signal-Based Learning Employing Genetic Algorithms and Simulated Annealing", Journal of Institute of Control, Robotics and Systems, Vol. 7, No. 10, 819-826, Oct. 2001.
• F. T. Hanshar and B. M. Ombuki-Berman, "Dynamic vehicle routing using genetic algorithms", Applied Intelligence, Vol. 27, pp. 89-99, Jan. 2007. [https://doi.org/10.1007/s10489-006-0033-z]
• A. H. Gandomi, et al., "Metaheuristic algorithms in modeling and optimization", Metaheuristic applications in structures and infrastructures, Vol. 1, pp. 1-24, 2013. [https://doi.org/10.1016/B978-0-12-398364-0.00001-2]
• C. C. Robusto, "The cosine-haversine formula", The American Mathematical Monthly, Vol. 64, No. 1, pp. 38-40, Jan 1957. [https://doi.org/10.2307/2309088]
• S. D. Silvey, "The Lagrangian multiplier test", The Annals of Mathematical Statistics, Vol. 30, No. 2, pp. 389-407, Jun. 1959. [https://doi.org/10.1214/aoms/1177706259]
• 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, Feb. 2013.