여객·소포 통합 운송 문제를 위한 정확 해법과 휴리스틱의 결합
A Hybrid Exact-Heuristic Solver for the Integrated Passenger and Parcel Transportation Problem
한국어 초록
SOICT 2026 대회 2라운드의 여객·소포 통합 운송 문제에 제출한 해법을 설명한다. 이 문제는 시간 제약, 개방형 경로, 서로 다른 유형의 택시를 고려하여 요청을 선택하고 승하차 및 수거·배송 경로를 정하는 문제다. 해법은 표준 라이브러리만 사용하는 단일 파일 Python 프로그램이며, 세 가지 기법을 결합한다. 첫째는 최종 허용 도착 시각까지 남은 여유를 이용하는 상수 시간 삽입 검사다. 둘째는 탐욕적 삽입, 국소 탐색, 모의 담금질의 채택 기준을 사용하는 적응형 대규모 이웃 탐색(ALNS)이다. 셋째는 정확한 경로 선택 엔진이다. 각 택시에 대해 요청 집합마다 실행 가능한 최적 경로를 열거한 뒤, 얻어진 집합 패킹 문제를 분기 한정법으로 푼다. 경로 기반 대규모 이웃 탐색, 라그랑주 경계, 감소 비용을 이용한 변수 고정으로 이를 강화한다. 문제 사례의 크기에 따라 엔진을 자동 선택하며, 독립 검증기와 감시 장치로 유효한 답을 항상 출력하도록 한다. 공식 평가의 채점 대상 38개 사례와 5분 제한에서 총 이익 487,237을 얻었다. 모든 실행은 277초 안에 끝났고 메모리는 최대 279MB를 사용했다. 38개 사례 중 28개는 제한 시간보다 훨씬 일찍 종료했다.
원문 초록
We describe the solver we submitted to the second round of the SOICT 2026 contest on the Integrated Passenger and Parcel Transportation problem, a selective pickup-and-delivery routing problem with time windows, open routes and heterogeneous taxis. The solver is a single-file, standard-library Python program that combines (i) a constant-time insertion test based on latest-arrival slack, (ii) greedy insertion, local search and an Adaptive Large Neighborhood Search (ALNS) with simulated-annealing acceptance, and (iii) an exact route-selection engine that enumerates, for every taxi, the best feasible route for each request set and then solves the resulting set-packing problem by branch-and-bound strengthened with route-based large neighborhood search, Lagrangian bounds and reduced-cost fixing. The engine is chosen automatically from the instance size, and an independent verifier and a watchdog guarantee that a valid answer is always printed. On the official evaluation (38 scored instances, 5-minute limit) the solver obtained a total benefit of 487,237, finished every run within 277 s and used at most 279 MB; 28 of the 38 instances terminated well before the limit.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2611.22043v2제출 시각 미확인
- arXiv:2611.22043v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.