💻 컴퓨터 과학

A Joint Learning and Optimization Approach for the Two-Stage Stochastic Service Network Design Problem

본 논문은 계산적으로 다루기 어려운 2단계 확률적 서비스 네트워크 설계 문제를 위해 신경망이 증강된 최적화 프레임框架을 제안하며, 새로운 섭동 기반 데이터 생성 전략이 모델로 하여금 표본 평균 근사법과 대등한 솔루션 품질을 달성하는 동시에 화물 통합 운송업체를 위한 개선된 확장성을 제공할 수 있음을 입증한다.

원저자: Ahmad Baubaid

게시일 2026-10-29

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Ahmad Baubaid

원본 논문은 CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

트럭, 기차 또는 배로 화물을 운송하는 화물 운송 회사들은 끊임없이 높은 이해관계가 걸린 도박에 직면해 있습니다. 이들은 실제 화물이 얼마나 도착할지 정확히 알기도 훨씬 전인 다가올 시즌을 위해, 오늘 얼마나 많은 차량을 배정하고 어떤 경로를 개설할지를 결정해야 합니다. 만약 차량을 너무 적게 계획하면 화물을 놓치고 막대한 위약금을 물게 되며, 너무 많이 계획하면 빈 트럭을 운행하며 돈을 낭비하게 됩니다. 이것이 서비스 네트워크 설계 문제의 핵심입니다. 즉, 비용과 용량 사이의 균형을 맞추는 연결 지도를 만드는 것입니다. 현실 세계에서 미래는 결코 확실하지 않습니다. 수요는 변동하고, 교통 체증이 발생하며, 연료 가격이 요동칩니다. 이를 처리하기 위해 기획자들은 2단계 확률적 프로그래밍(two-stage stochastic program)이라는 방법을 사용합니다. 첫 번째 단계에서는 네트워크 설계를 확정합니다. 두 번째 단계에서는 실제 수요가 드러나면, 초기 계획이 부족할 경우 더 비싼 스팟 마켓(spot-market) 서비스를 이용하는 비용을 지불함으로써 조정을 수행합니다. 목표는 모든 가능한 미래 시나리오를 고려하여 총 기대 비용을 최소화하는 초기 설계를 찾는 것입니다. 그러나 수천 가지의 가능한 결과가 존재하는 현실적인 네트워크에 대해 이를 계산하는 것은 계산량이 너무 많아 표준적인 도구로는 해결이 불가능한 경우가 많습니다.

킹 파드 대학교(King Fahd University of Petroleum and Minerals)의 연구진은 컴퓨터에게 2단계 비용을 추측하도록 가르침으로써 이 불가능한 계산을 해결하는 새로운 방법을 개발했습니다. 연구팀은 모든 가능한 미래 시나리오에 대해 복잡한 수학 문제를 일일이 풀려고 하는 대신, 인공 신경망(neural network)으로 알려진 유형의 인공지능을 사용하여 지름길 역할을 하도록 훈련시켰습니다. 이 네트워크는 사전에 학습한 수천 개의 사례를 바탕으로, 회사가 특정 네트워크 설계를 선택했을 때 직면하게 될 추가 비용을 예측하는 법을 배웁니다. 일단 훈련되면, 이 인공 신경망은 기획 소프트웨어에 직접 삽ins됩니다. 그러면 소프트웨어는 네트워크에 "만약 우리가 이 특정 네트워크를 구축한다면, 미래의 비용은 어떻게 될 것인가?"라고 묻고, 그 답변을 사용하여 최적의 전체 계획을 찾아냅니다. 이는 보통 해결하는 데 영겁의 시간이 걸리는 문제를 빠르게 처리할 수 있는 문제로 바꾸어 놓으며, 물류 관리자들에게 실용적인 도구를 제공합니다.

이 접근 방식의 결정적인 과제는 인공 신경망을 어떻게 효과적으로 가르칠 것인가를 파악하는 것이었습니다. 가능한 차량 일정의 수가 방대하고 경계가 없기 때문에, 단순히 컴퓨터에게 무작위의 일정 예시를 입력하는 것만으로는 제대로 작동하지 않을 것이기 때문입니다. 연구진은 훈련 데이터를 생성하는 세 가지 다른 방법을 테스트했습니다. 첫 번째는 수천 개의 무작위 차량 일정을 만드는 무작위 접근 방식이었습니다. 두 번째는 더 작고 단순한 버전의 문제를 해결하여 도출된 현실적인 일정에서 시작하여, 여기에 작고 국부적인 조정을 가하는 섭동 기반(perturbation-based) 접근 방식이었습니다. 세 번째는 이 두 가지를 혼합한 하이브리드 방식이었습니다. 연구진이 18가지의 서로 다른 네트워크 시나리오에 대해 이 방법들을 테스트했을 때, 결과는 명확했습니다. 무작위 접근 방식은 저조한 예측을 내놓았고 최적이 아닌 계획을 도출했습니다. 반면, 현실적인 시작점에 의존한 섭동 기반 방식과 하이브리드 방식은 매우 정확한 예측을 생성했습니다. 이러한 방법들은 시스템이 무작위 추측보다 훨씬 더 저렴하고 신뢰할 수 있는 네트워크 설계를 찾을 수 있도록 해주었습니다.

이 새로운 학습 기반 방법이 기존의 솔루션과 경쟁할 수 있는지 확인하기 위해, 연구진은 샘플 평균 근사법(Sample Average Approximation)이라 불리는 표준 산업 기술과 비교했습니다. 이 전통적인 방법은 좋은 답을 찾기 위해 서로 다른 무작위 시나리오 세트를 사용하여 문제를 반복적으로 해결하는 방식으로 작동합니다. 연구 결과, 학습 기반 접근 방식은 특히 섭동 또는 하이브리드 데이터 생성 방법을 사용할 때 전통적인 방법과 대등한 품질의 설계를 만들어냈습니다. 많은 경우, 새로운 접근 방식은 수십 번의 복잡한 계산을 실행하는 대신 단 하나의 간소화된 모델을 해결함으로써 그와 똑같이 훌륭한 솔루션을 찾아냈습니다. 연구진은 이 새로운 방법이 훈련 데이터를 생성하고 네트워크를 훈련시키는 데 선행적인 시간 투자가 필요하지만, 의사결정을 빠르게 내려야 하거나 전통적인 솔버로는 감당하기 어려운 규모의 네트워크를 가진 기업들에게 강력한 대안이 된다고 언급했습니다. 연구는 현실적인 사례로부터 학습함으로써 인공지능이 화물 계획의 불확실성을 성공적으로 헤쳐 나갈 수 있으며, 서비스 네트워크 설계를 위한 실행 가능하고 효율적인 경로를 제공한다는 결론을 내립니다.

기술 요약: 2단계 확률적 서비스 네트워크 설계 문제를 위한 결합 학습 및 최적화 접근 방식

문제 정의
본 논문은 화물 집하 운송업체(예: LTL, 택배 및 복합 운송업체)의 핵심적인 전술적 계획 과제인 2단계 확률적 서비스 네트워크 설계(SSND) 문제를 다룹다. 이 맥락에서 운송업체는 불확실한 수요 하에 다가오는 시즌 동안 터미널 간에 운영할 서비스 용량(차량 대수)을 결정해야 한다. 문제는 다음과 같이 2단계 확률 계획법으로 정식화된다:

1단계: 수요가 실현되기 전에 네트워크 아크(arc) 상에서 운영할 차량 수를 결정하는 결정(설계 변수)이 포함된다. 이는 일반 정수 변수이다.
2단계: 수요가 드러나면, 운송업체는 선택된 네트워크를 통해 화물을 운송한다. 만약 계획된 용량이 부족할 경우, 더 높은 비용으로 추가적인 "스팟 시장(spot market)" 차량을 확보하게 된다(회수 결정).
목표는 1단계 설계 비용과 기대 2단계 회수 비용의 합을 최소화하는 것이다. 이 문제는 대규모 혼합 정수 성격의 모델과 불확실성을 표현하기 위해 필요한 시나리오의 기하급수적 증가로 인해 현실적인 네트워크 규모에서는 계산적으로 매우 까다롭다.

방법론
저자는 계산 비용이 많이 드는 2단계 회수 비용 하위 문제를 학습된 대리 모델(surrogate model)로 대체하는 신경망 증강 최적화 프레임워크를 제안한다. 핵심 방법론은 다음과 같다:

대리 모델링(Surrogate Modeling): 1단계 설계 벡터 $r$ 이 주어졌을 때 기대 회수 비용 $E_\omega[Q(r, \omega)]$ 를 근사하도록 ReLU 활성화 함수를 사용하는 피드포워드 신경망(NN)을 학습시킨다.
MIP로의 임베딩: ReLU 함수는 혼합 정수 제약 조건을 사용하여 정확하게 표현될 수 있기 때문에, 학습된 신경망을 혼합 정수 계획법(MIP) 정식화에 직접 임베딩한다. 이를 통해 전체 문제를 단일 결정론적 MIP로 해결할 수 있는 "대리 MIP"가 생성되며, 여기서 2단계 하위 문제의 제약 조건과 목적 함수는 신경망의 수학적 표현으로 대체된다.
데이터 생성 전략: 본 방법론의 상당 부분은 라벨링된 훈련 데이터(설계 벡터 $r$ $r$ 과 그에 따른 실제 기대 회수 비용 쌍)를 생성하는 데 집중되어 있다. 1단계 변수는 일반 정수(경계가 없음)이므로 무작위 샘플링은 불충분하다. 저자는 다음 세 가지 전략을 도입하고 비교한다:
- 무작위(Random): 전역 용량 제한을 충족하도록 스케일링된 상태에서 아크 전반에 걸쳐 차량 수를 균등하게 생성한다.
- 섭동(Perturbation): 단일 시나리오 결정론적 하위 문제의 정확한 해로부터 훈련 샘플을 시딩(seeding)한다. 그 후, 고품질 설계의 국소적 근방을 탐색하기 위해 이러한 기본 해에 작은 정수 섭동을 적용하여 추가 샘플을 생성한다.
- 하이브리드(Hybrid): 섭동 방식과 무작위 방식을 결합한 것으로, $\alpha$ (섭동을 통해 생성되는 샘플의 비율)라는 매개변수에 의해 제어된다.
벤치마킹: 제안된 접근 방식은 유한한 시나리오 집합을 샘플링하여 기대 비용을 근사하는 표준 기술인 표본 평균 근사(SAA) 방법과 벤치마킹된다.

주요 기여
본 논문은 문헌에 네 가지 주요 기여를 한다:

일반 정수를 위한 새로운 프레임워크: 1단계 변수가 이진(binary) 변수로 제한되었던 기존 연구를 확장하여, 일반 정수 1단계 변수를 구체적으로 다루는 최초의 학습 기반 SSND 접근 방식을 제시한다.
고급 데이터 생성: 무작위 샘플링보다 정수 설계 변수의 경계가 없는 해 공간을 더 효과적으로 커버하도록 설계된 새로운 데이터 생성 기술(섭동 및 하이브리드)을 제안하고 검증한다.
실증적 검증: 18개의 서로 다른 네트워크 인스턴스에 대한 실험을 통해, 데이터 생성 방법의 선택이 솔루션 품질에 상당한 영향을 미친다는 것을 입증한다. 섭동 및 하이브리드 방식은 예측 정확도(MAE, MSE)와 결과적인 네트워크 설계의 실현 비용 모두에서 무작위 방식보다 일관되게 우수한 성능을 보였다.
SAA와의 비교 분석: 학습 기반 접근 방식을 SAA와 비교하였다. 결과에 따르면 섭동 및 하이브리드 방식은 (최적해와의 평균 격차가 각각 0.94%와 1.02%로) SAA와 유사한 솔루션 품질을 제공하면서도, 계산 노력과 확장성 측면에서 다른 트레이드오프를 제공함을 보여준다.

결과

예측 정확도: 섭동 기반 방식은 테스트 세트에서 가장 낮은 평균 절대 오차(MAE = 9.11)와 평균 제곱 오차(MSE = 161.95)를 달eric하여, 무작위 및 하이브리드 방식보다 우수한 성능을 보였다.
솔루션 품질: 섭동 및 하이브리드 데이터 전략을 사용하여 생성된 설계는 무작위 전략을 사용한 설계보다 실제 총 비용이 낮았다. 섭동 방식은 추정 비용과 실제 비용 사이의 가장 밀접한 일치(평균 편차 1.33%)를 보였으며, 무작위 방식은 현저히 높은 편차(10.81%)를 보였다.
데이터셋 크기 민감도: 훈련 데이터셋의 크기를 늘리면 일반적으로 오차 지표가 감소하며, 약 4,000개의 샘플 이후 성능이 안정화되었다.
하이브리드 매개변수 ( $\alpha$ ): 하이브리드 매개변수( $\alpha$ , 섭동 대 무작위 샘로의 비율)를 변화시킨 결과, $\alpha = 0.75$ 가 최적의 균형을 제공하여 특히 큰 네트워크 구성에서 대부분의 인스턴스에 대해 가장 낮은 실제 비용을 산출했다.
SAA 비교: SAA가 대규모 인스턴스에서 가끔 약간 더 나은 솔루션을 찾기도 했지만, 학습 기반 접근 방식은 여러 시나리오 기반 MIP를 풀어야 하는 SAA와 대조적으로 단일 대리 모델을 해결함으로써 경쟁력 있는 결과를 달성했다.

의의 및 주장
본 논문은 제안된 프레임워크가 SSND 문제에 직면한 화물 집하 운송업체에게 실행 가능한 휴리스틱 대안을 제공한다고 주장한다. 계산이 불가능한 2단계 하위 문제를 신경망 대리 모델로 대체함으로써 최적화 과정을 단순화한다. 저자는 정수 설계 변수를 다룰 때 훈련 데이터가 관련 솔루션 영역을 적절히 커버하도록 보장하는 특정 데이터 생성 전략(섭동 및 하이브리드)이 이 방법의 성공에 결정적임을 강조한다. 본 연구는 훈련 단계에서 라벨을 생성하기 위한 계산 노력이 필요하지만, 이후의 최적화는 효율적이며, 전통적인 SAA와 같은 방법과 상호 보완적인 트레이드오프를 제공한다는 점을 시사한다. 저자는 이를 기존의 학습 지원 최적화의 확장으로 겸손하게 위치시키며, 향후 연구에서 다양한 네트워크 인스턴스에 대해 단일 일반화 모델을 학습시키거나 네트워크 구조를 더 잘 활용하기 위해 그래프 신경망(GNN)을 활용할 수 있음을 언급한다.

유사한 논문