Solver-Informed Evolution of Interpretable Dispatching Rules for the Stochastic Team Orienteering Problem with Time Windows

차량 함대가 흩어져 있는 여러 장소를 방문하며 시계와 싸우며 경주하는 모습을 상상해 보십시오. 각 장소는 서로 다른 보상을 제공합니다. 목표는 단순합니다. 시간이 다 되기 전에 최대한 많은 가치를 수집하는 것입니다. 하지만 세상은 스프레드시트처럼 정교하지 않습니다. 특정 지점에서 과업을 완료하는 데 걸리는 시간은 불확실합니다. 갑작스러운 돌풍이 드론을 지연시키거나, 거친 파도가 보트를 느리게 만들 수 있습니다. 게다가 각 위치는 특정 시간대 동안에만 이용 가능합니다. 만약 차량이 너무 일찍 도착하면 기다려야 하고, 너무 늦게 도착하면 그 기회는 영원히 사라집니다. 이것이 바로 '시간 창이 있는 팀 오리엔티어링 문제(team orienteering problem with time windows)'라고 불리는 복잡한 물류 과제의 본질입니다. 현실 세계에서 이 시나리오는 소방관들이 산불을 진압하려 할 때, 기름 유출 대응팀이 해안에 도달하기 전 기름띠를 차단하기 위해 경주할 때, 또는 의료팀이 중요한 시간 내에 환자들을 방문해야 할 때 실제로 벌어지는 일입니다. 어려움은 현재의 작업이 정확히 얼마나 걸릴지 모르는 상태에서, 그리고 매 초마다 전체 계획을 다시 계산할 수 있는 슈퍼컴퓨터의 사치 없이, 즉각적으로 다음 움직임을 결정해야 한다는 점에 있습니다.

수년 동안 연구자들은 컴퓨터에게 간단한 결정 규칙을 진화하도록 가르쳐 이 문제를 해결하려고 노력해 왔습니다. 이 규칙들은 교통 관제사처럼 작동하여, 현재 상황을 보고 다음에 어느 고객을 방문할지 즉시 결정합니다. 지금까지 가장 성공적인 방법인 NS-GP는 거리나 남은 시간과 같은 11개의 고정된 기본 특징(features)에 의존하여 이러한 선택을 내립니다. 효과적이긴 하지만, 이 방식에는 한계가 있습니다. 이는 마치 백 개의 단어만을 사용하여 소설을 쓰려는 것과 같이, 세상을 설명하는 어휘가 제한적입니다. 브라질 대학의 아우구스토 멘돈사(Augusto Mendonça)와 그의 팀이 이끄는 이번 연구의 연구진은 대담한 질문을 던졌습니다. 만약 컴퓨터가 전문가의 오프라인 계획을 관찰함으로써 더 풍부한 어휘를 배울 수 있다면 어떻게 될까? 그들은 고품질 솔루션에 담긴 숨겨진 논리를 추출하여, 이를 실시간으로 작동하는 단순하고 읽기 쉬운 규칙으로 바꿀 수 있는지 알고 싶었습니다.

연구팀은 SI-GP, 즉 '솔버 정보 기반 유전 프로그래밍(Solver-Informed Genetic Programming)'이라는 새로운 방법을 개발했습니다. 이 과정은 컴퓨터가 추측하는 것이 아니라 관찰하는 것에서 시작됩니다. 먼저, 연구진은 모든 것이 완벽하게 진행된다고 가정했을 때 최적의 경로를 찾아내는 강력하고 빠른 솔버들을 사용하여 40개의 서로 다른 테스트 문제에 대한 경로를 찾았습니다. 그런 다음 이 완벽한 경로들을 현실에서 발생하는 것처럼 무작위적인 지연이 발생하는 시뮬레이션 세계에서 재현했습니다. 완벽한 계획과 실제 발생한 상황을 비교함으로써, 연구진은 완벽한 계획이 수행했지만 표준 규칙들은 놓쳤던 특정 작업들을 식별해 냈습니다. 예를 들어, 최적의 계획은 종종 몇 단계 앞을 내다보며 어떤 보상이 여전히 도달 가능한지를 확인하거나, 현재의 결정에 전념함으로써 미래의 기회를 잃을 위험을 계산한다는 것을 발견했습니다.

이러한 관찰을 바탕으로 연구진은 18개의 새로운 결정 특징 라이브러리를 구축했습니다. 이 중 16개는 기존의 스케줄링 개념에 기반하였고, 나머지 2개는 결정의 비용과 잠재적 이득을 저울질하도록 설계된 완전히 새로운 조합이었습니다. 이 새로운 어휘는 컴퓨터가 문제를 훨씬 더 미묘하게 이해할 수 있는 능력을 부여했습니다. 그러나 선택지가 많다고 해서 반드시 결과가 좋아지는 것은 아닙니다. 때로는 너무 많은 선택지가 시스템을 혼란스럽게 할 수도 있습니다. 이를 해결하기 위해 연구진은 각 특정 문제에 대한 최적의 특징 부분 집합을 선택하기 위해 두 번째 지능 계층을 사용했습니다. 그들은 서로 다른 특징 조합을 진화시키고 엄격하게 테스트하는 토너먼트 방식으로 이 선택 과정을 처리했습니다. 이는 그래픽 카드에서 실행되는 맞춤형 엔진 덕분에 가능했는데, 이를 통해 과거에 단 하나의 조합을 테스트하는 데 걸렸던 시간 동안 수천 개의 조합을 테스트할 수 있었습니다.

결과는 놀라웠습니다. 40개의 벤치마크 문제에서 새로운 방법은 기존 표준보다 성능이 떨어지지 않았습니다. 38개의 사례에서 이 시스템은 이전의 최고 기록을 뛰어넘는 새로운 규칙을 진 evolved(진화)시켰습니다. 평균적으로 새로운 규칙은 모든 테스트에서 총 수집된 보상을 1.0% 개선했으며, 개선의 여지가 남아 있던 문제들에서는 1.3%를 개선했습니다. 10개의 특정 사례에서는 개선 효과가 통계적으로 유의미했으며, 해당 시나리오에 대해 중대한 돌파구로 간 만큼의 큰 폭을 기록했습니다. 무엇보다 중요한 점은 새로운 규칙들이 단순하고 읽기 쉬운 상태를 유지했다는 것입니다. 그것들은 아무도 이해할 수 없는 블랙박스 알고리즘이 아니라, 인간이 읽고 검증할 수 있는 압축된 수학적 표현식이었습니다. 많은 경우, 새로운 규칙들은 더 안정적이어서 무작위 지연이 변하더라도 일관된 결과를 생성한 반면, 기존 규칙들은 때때로 결과가 급격히 요동치기도 했습니다.

이 연구는 또한 왜 이러한 개선이 일어났는지도 밝혀냈습니다. 새로운 규칙은 기준 시스템이 모든 가능한 고객을 방문하는 데 어려움을 겪는 '미포화(unsaturated)' 상황에서 특히 효과적이었습니다. 이러한 상황에서 새로운 어휘는 시스템이 복잡한 트레이드오프를 탐색할 수 있게 해주었는데, 예를 들어 근처의 낮은 가치의 고객을 건너뛰더라도 멀리 떨어진 높은 가치의 고객을 방문하는 것과 같은 결정입니다. 연구진은 새로운 특징들이 시스템의 탐색을 정규화(regularize)하는 데 도움을 주어, 지역적 함정에 빠질 가능성을 줄이고 더 견고한 경로를 찾을 가능성을 높였다는 것을 발견했습니다. 이 방법은 전문가의 경로를 단순히 복제하는 것이 아니라, 고품질 솔루션의 구조로부터 학습함으로써 작동했습니다. 이는 전문가 플래너의 정확한 경로를 흉내 내는 것이 아니라, 그 경로들을 성공적으로 만든 원칙을 학습하여 새로운 불확실한 환경에 적용한 것이었습니다.

이 연구는 복잡한 오프라인 최적화와 빠른 온라인 의사결정 사이의 간극을 메울 수 있음을 보여줍니다. 고품질 솔버의 통찰력을 사용하여 더 나은 어휘를 구축하고, 각 작업에 적합한 도구를 신중하게 선택함으로써, 연구진은 강력하면서도 투명한 시스템을 만들었습니다. 최종 결과물은 차량이나 드론에 직접 삽입될 수 있는 의사결정 규칙 세트로, 중앙 컴퓨터에 연결하거나 복잡한 시뮬레이션을 실행할 필요 없이 마이크로초 단위로 지능적인 선택을 할 수 있게 합니다. 이 접근 방식은 물류 분야의 인공지능에 대한 새로운 길을 제시합니다. 즉, 해석 가능성과 적응성을 중시하며, 중요한 결정을 내리는 기계가 그 기계에 의존하는 인간에 의해 이해될 수 있도록 보장하는 길입니다. 연구진은 자신들의 코드, 데이터, 그리고 발견한 특정 규칙들을 공개하여, 다른 이들이 미래의 불확실한 환경 속 과제들을 위해 이 토대 위에서 연구를 이어갈 수 있도록 초대했습니다.