현대 도시 교통 및 물류 시스템의 핵심인 차량 경로 설정 문제는 복잡한 최신 최적화 알고리즘과 방대한 양의 컴퓨팅 자원을 필요로 합니다. 카이스트 연구진이 기존 방식보다 성능이 월등히 뛰어난 새로운 머신러닝 기반 알고리즘을 개발해 대규모 차량 경로 설정 문제에서 정확한 최적 해법을 찾고 컴퓨팅 시간을 단축할 수 있는 가능성을 입증했습니다.

일반적인 분리 문제는 그 자체로NP-hard 문제이기 때문에 휴리스틱 알고리즘이 사용되어 왔습니다. 카이스트 산업 및 시스템공학과 연구진이 현재 가장 널리 사용되는 휴리스틱 알고리즘을 능가하는 머신러닝 기반 알고리즘을 개발했습니다. 이 새로운 알고리즘은 소규모 훈련 인스턴스에서 최적의 솔루션을 학습하고 message-passing graph neural network와 graph coarsening 기법을 이용하여 학습한 알고리즘을 대규모 문제에 적용합니다.

그림 2는 널리 사용되는 휴리스틱 알고리즘(CVRPSEP)과 새로운 알고리즘(NeuralSEP)을 비교한 것입니다. Optimality Gap이 작을수록 솔루션 품질이 더 우수하다는 것을 의미합니다. 고객 수가 1,000명인 가장 큰 규모의 문제에서 NeuralSEP는 CVRPSEP보다 훨씬 뛰어난 성능을 보이며, 이는 전체 BCP 알고리즘의 실행에서 수십시간에서 수십일의 컴퓨팅 시간을 절약할 수도 있습니다.

이 연구를 설명하는 전체 원고는 다음 링크에서 확인할 수 있습니다.

https://arxiv.org/abs/2306.17283