arXiv:2607.06066v1 cs.AI

동적 다중 차량 경로 문제를 위한 보상 밀도 휴리스틱: 성능 및 계산 효율성

Reward-Density Heuristic for Dynamic Multi-Vehicle Routing: Performance and Computational Efficiency

Manish Kolachalam, Rani Malhotra

제출 2026-07-07

한국어 초록

차량 경로 문제(VRP)와 그 변형들은 현대 물류 및 도시 이동성에서 실질적으로 가장 중요한 최적화 과제 중 하나이다. 본 연구에서는 VRP와 오리엔티어링 문제(OP)의 요소를 결합한 동적 온라인 변형을 다루며, 차량 집단이 새로운 작업이 지속적으로 도착하는 상황에서 실시간으로 재계획을 수행하면서 고정된 시간 지평선 내에 수집되는 누적 보상을 최대화해야 한다. 본 연구는 동적 다중 차량 할당을 위한 보상 밀도 휴리스틱을 제안하고 평가하며, 이를 Efficiency 휴리스틱이라 칭한다. 자율 드론 작업 할당과 도시 택시 배차라는 두 가지 응용 도메인에서 다양한 차량 집단 규모 및 작업 규모에 걸쳐 이 방법을 평가한다. 제안된 방법은 네 가지 고전적 구성 휴리스틱과 세 가지 메타휴리스틱 알고리즘(적응형 대규모 이웃 탐색(Adaptive Large Neighbourhood Search), 유전 알고리즘(Genetic Algorithm), 시뮬레이티드 어닐링(Simulated Annealing))과 동일한 조건 하에 비교된다. 테스트된 모든 구성에서 Efficiency 휴리스틱은 최고의 메타휴리스틱 알고리즘과 동등한 솔루션 품질을 달성하면서도 계획 시간은 2~3 자릿수 더 적게 요구하여, 보상 대 계산량 프론티어에서 모든 경쟁 방법에 대해 파레토 지배(Pareto dominance)를 확립한다. 이러한 결과는 실시간 할당 및 배차 시스템을 위한 실용적인 설계 원칙을 시사한다: 동적이고 시간 제약이 있는 경로 환경에서, 신중하게 설계된 탐욕적 휴리스틱은 정교한 탐색 절차와 대등한 결과를 계산 비용의 극히 일부만으로 달성할 수 있으며, 이로 인해 온라인 배포에 더 적합하다.

원문 초록

The Vehicle Routing Problem (VRP) and its variants represent some of the most practically consequential optimization challenges in modern logistics and urban mobility. In this study, we address a dynamic, online variant combining elements of the VRP and the Orienteering Problem (OP), in which a fleet of vehicles must maximise cumulative reward collected within a fixed time horizon while continuously replanning as new tasks arrive. We propose and evaluate a reward-density heuristic for dynamic multi-vehicle assignment, referred to as the Efficiency heuristic. We evaluate this formulation across two application domains: autonomous drone task allocation and urban taxi dispatch, across multiple fleet sizes and task scales. The proposed method is compared with four classical construction heuristics and three metaheuristic algorithms (Adaptive Large Neighbourhood Search, Genetic Algorithm, and Simulated Annealing), all evaluated under identical conditions. Across all tested configurations, the Efficiency heuristic matches the solution quality of the best metaheuristic algorithms while requiring two to three orders of magnitude less planning time, establishing Pareto dominance over all competing methods on the reward-versus-compute frontier. These findings suggest a practical design principle for real-time allocation and dispatch systems: in dynamic, time-constrained routing environments, carefully designed greedy heuristics can match the output of sophisticated search procedures at a fraction of the computational cost, making them preferable for online deployment.

요약

동적 다중 차량 경로 문제(VRP)에서 보상을 이동 시간과 서비스 시간의 합으로 나눈 보상 밀도(reward-density) 휴리스틱(Efficiency heuristic)을 제안하여, 자율 드론 작업 할당 및 도시 택시 배차 환경에서 평가했다. 제안 방법은 ALNS, GA, SA 등 메타휴리스틱 알고리즘과 동등한 솔루션 품질을 달성하면서도 계획 시간은 최대 수천 배 단축되어, 보상 대 계산량 프론티어에서 모든 비교 방법 대비 파레토 지배를 확립했다.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2607.06066v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2610.10867v1cs.LG공통 태그 Computational Efficiency, Combinatorial Optimization

분류 성능의 지표로서 라이프-유사 네트워크 오토마타 규칙의 형태 불규칙성

Shape irregularity of Life-Like Network Automaton rules as an indicator of classification performance

복잡 네트워크(Complex Network, CN) 분류는 스케일 불변(scale-invariant)이면서도 계산적으로 효율적인 고수준의 구조적 특성화를 필요로 합니다. 라이프-유사 네트워크 오토마타(Life-Like Network Automata, LLNA) 기반 방법은 사전에 제공된 특징 없이도 창발적 시간 패턴을 활용하여 네트워크 기술자(descriptor)를 추출하는 흥미로운 방식을 제공하지만, 그 효과는 오토마타 전이 규칙의 선택이라는 높은 비용의 조합 최적화 문제로 인해 병목 현상을 겪습니다. 기존 연구들은 대규모 응용에 실현 불가능한 전수 탐색(exhaustive search)에 의존하는 반면, 본 연구는 규칙 공간이 LLNA 전이 함수와 톱니 형태의 유사성을 정량화하는 '들쭉날쭉함(jaggedness)'이라는 특성으로 근본적으로 구조화되어 있음을 밝힙니다. 우리는 이 지표가 혼돈성(chaoticity)과 민감도(sensitivity)에 대한 이론적 대리 지표로 작용함을 입증하며, 이러한 특성은 네트워크 범주 간의 식별력 있는 동적 동작을 생성하는 데 필수적입니다. 나아가, 우리는 들쭉날쭉함을 활용하여 규칙 선택을 유도하는 휴리스틱 탐색 전략을 도입합니다. 실험 결과에 따르면 본 접근법은 전수 탐색 방식에 비해 계산 오버헤드를 90% 줄이면서도 전역 최적값 대비 5% 이내의 분류 정확도를 달성합니다. 우리의 발견은 패턴 인식을 위한 오토마타 기반 방법을 최적화하는 새롭고 효율적인 프레임워크를 제공합니다.

arXiv:2610.02670v1cs.LG공통 태그 Decision Making, Computational Efficiency

LEAP: LLM 에이전트를 위한 효율적인 행동 제안 학습

LEAP: Learning Efficient Action Proposals For LLM Agents

대규모 언어 모델(LLM) 에이전트는 롤아웃(rollout) 과정이 느린 것으로 알려져 있습니다. 에이전트는 한 번에 한 단계씩 작업을 완료합니다. 각 단계에서 에이전트는 추론을 수행한 후 실행할 행동을 선택합니다. 다음 단계와 행동은 이전 단계가 끝날 때까지 시작될 수 없습니다. 추측 디코딩(speculative decoding)은 추론 토큰을 초안 작성(drafting)하고 검증함으로써 추론 단계에서의 롤아웃 속도를 가속합니다. 최근 연구들에서는 행동 단계에도 유사한 아이디어를 적용하기 시작했습니다. 이러한 연구들은 타깃 모델(target model)이 검증할 수 있도록 행동 제안 초안을 작성하기 위해 기존에 구축된 상용 모델(off-the-shelf model), 주로 대형 모델을 사용합니다. 대형 초안 모델은 타깃과 더 자주 일치하지만 제안을 작성하는 데 더 오랜 시간이 걸리는 반면, 소형 상용 모델은 빠르지만 타깃과 동일한 결정을 내리는 경우가 드뭅니다. 본 논문에서는 더 일반적인 질문을 던집니다. 행동 추측의 엔드투엔드(end-to-end) 가속을 결정하는 요인은 무엇인가? 이에 답하기 위해, 본 연구에서는 추측 라운드에 대한 지연 시간(latency) 프레임워크를 개발합니다. 이 프레임워크는 한 라운드에서 얻는 이득과 소요되는 비용을 비교합니다. 이득은 초안 모델이 타깃을 얼마나 잘 예측하는지, 그리고 작업이 종료되기까지 얼마나 많은 단계를 거칠 수 있는지에 따라 달라집니다. 비용은 초안 작성, 타깃의 검증 대기 시간, 도구 실행에서 발생합니다. 이 프레임워크를 바탕으로, 본 연구에서는 초안 모델의 크기를 작게 유지하면서 타깃의 행동 시퀀스로 학습(training)시켜 정확도를 높이는 LEAP(Learning Efficient Action Proposals)을 소개합니다. 0.6B 크기의 소형 모델을 사용하는 LEAP은 대부분의 결정에서 타깃과 일치하며, 작업 성공률의 체계적인 변화 없이 에이전트의 엔드투엔드 실제 소요 시간(wall clock time)을 최대 60% 단축합니다. 다양한 데이터셋, 타깃 모델 및 초안 모델에 걸쳐 본 프레임워크는 측정된 속도 향상의 대부분을 설명합니다. 또한 사전 트레이스 수집 없이도 초안 모델을 온라인 학습할 수 있으며 오프라인 학습의 성능과 일치함을 입증하여, LEAP이 실제 환경에 배포하기에 실용적임을 보여줍니다.

arXiv:2610.03296v1cs.AI공통 태그 Computational Efficiency, Combinatorial Optimization

JOVE: 자원 인지형 LLM 태스크 그래프를 위한 공동 실행 및 검증

JOVE: Joint Execution and Verification for Resource-Aware LLM Task Graphs

복잡한 추론 질의는 방향성 비순환 그래프(DAG) 형태의 태스크 그래프로 분해되어 이종 대규모 언어 모델(LLM)에 분산될 수 있으며, 이를 통해 병렬 처리를 통한 지연 시간을 줄이고 더 작은 모델이 복잡한 태스크를 해결하도록 지원할 수 있습니다. 그러나 실제로는 주어진 서브태스크에 대한 특정 LLM의 적합성을 사전에 알 수 없을 수 있으며, 단순 실행만으로는 출력의 정확성을 파악할 수 없습니다. 본 논문에서는 실행기 LLM을 할당하는 동시에 유료 검증을 거칠 중간 출력을 함께 선택하는 온라인 프레임워크인 JOVE를 제안합니다. 검증은 비동기식으로 실행되며 향후 할당 결정을 개선하는 데 사용되므로, 시스템은 현재 실행에 드는 비용과 향후 학습을 위한 지출 사이의 균형을 유지해야 합니다. 본 연구에서는 확률적이며 초기에는 알려지지 않은 LLM 서비스 품질, 호출 비용 및 실행 시간 환경에서 장기 예산과 질의별 지연 시간 제약 조건 하에 이러한 트레이드오프를 최적화하는 방법을 연구합니다. JOVE는 질의별 일련의 혼합 정수 선형 계획법(MILP) 문제를 해결하여 실행 및 검증 결정을 내립니다. 온라인 학습은 검증 피드백을 기반으로 LLM 품질에 대한 태스크 의존적 추정치를 업데이트하며, 정보 이득 보너스를 통해 학습의 가치를 할당 결정에 반영합니다. 자연스러운 일련의 가정 하에 본 연구는 JOVE의 준선형(sublinear) 품질 학습 후회(regret)를 입증합니다. 4가지 추론 벤치마크 전반에서 JOVE는 표준 추론(inference) 베이스라인 대비 경쟁력 있는 정확도를 달성하는 동시에 평균 비용과 지연 시간을 최소 3.17배 단축합니다.

arXiv:2610.00126v1cs.CR공통 태그 Decision Making, Combinatorial Optimization

검증자가 정답을 유출할 수 있다: 폐루프 에이전트 디버깅에서 최적화에 앞선 진단 가능성

A Verifier Can Leak the Answer: Diagnosability Before Optimization in Closed-Loop Agent Debugging

에이전트(agent) 개발자들은 시뮬레이터 기반 검증자(verifier)를 통해 프롬프트, 도구, 정책 및 진단 알고리즘을 비교하는 방식을 점점 더 많이 활용하고 있습니다. 그러나 검증자는 솔버(solver) 비교를 무의미하게 만들 수도 있습니다. 즉, 검증자의 프로브(probe)나 술어(predicate)가 타깃의 식별 정보를 인코딩하고 있다면, 정확한 옵티마이저(optimizer)는 어떠한 실질적인 모호성도 해결하지 못한 채 효과적인 것처럼 보일 수 있습니다. 본 연구에서는 폐루프(closed-loop) 의사결정 에이전트를 위한 집계 트레이스 디버거에서 발생하는 이러한 실패 사례를 보고합니다. 정확한 최소 적중 집합(Minimum Hitting Set, MHS)과 전파 인식 탐욕 알고리즘(propagation-aware greedy method)은 12개 개발 사례 모두에서 동일한 지지 집합(support)을 반환했으며, 9/12 사례에서 동일한 주입 결함(planted fault) 복구를 달성했습니다. 후속 감사 결과, 정확한 앵커(exact-anchor) 술어가 9/9 사례에서 주입된 쌍을 생성한 것으로 확인되었습니다. 해당 앵커들을 제거한 후 전체 주입 쌍 복구율은 8/9였습니다. 그럼에도 불구하고 하드 프로브 싱글톤(hard-probe singleton) 쌍은 9/9 사례에서 주입된 쌍과 일치했으며, 전파 후 비어 있지 않은 잔여 충돌군(residual conflict family)이 유지된 사례는 전무했습니다(0/9). 옵티마이저는 올바르게 작동했으나, 검증자가 이미 정답을 노출하고 있었던 것입니다. 이에 본 논문에서는 솔버 우선 평가 방식을 지지 집합 기반 게이팅(support-gated) 검증 규약으로 대체합니다. 먼저 클린 참조 맵(clean reference map)을 통해 반복적인 컴포넌트 노출을 입증해야 하며, 그다음 일치된 참조/현재 게이트를 통해 비교 가능한 런타임 증거를 확립해야 하고, 그 이후에만 독립적으로 보정된 신호 규칙이 탐지 결과를 반환할 수 있습니다. 1,440개의 사례와 21,600개의 파티션 행으로 구성된 사전 등록된 홀드아웃(heldout) 평가에서, 55/72 체제-컴포넌트(regime-component) 단위가 참조 게이트를 통과했고, 54/55가 런타임 게이트를 통과했으며, 표현된 컴포넌트의 안정적 위허용(stable false admission)은 단측 정확 95% 상한선 0.1391과 함께 0/20을 기록했습니다. 승인된 단위 내에서는 영향을 받은 정상 트래픽이 공칭 결함 셀 비율(nominal fault-cell fraction)보다 탐지를 더 잘 예측했습니다. 본 연구의 핵심적인 구조적 교훈은 컴포넌트 선택기를 최적화하기 전에 증거의 적격성과 비공개성(non-revelation)을 먼저 검증해야 한다는 점입니다. 그렇지 않으면 더 강력한 솔버가 단지 더 강력한 검증자 아티팩트(artifact)를 인증하는 것에 불과할 수 있습니다.

arXiv:2610.00437v1cs.AI공통 태그 Decision Making, Computational Efficiency

JevSpawn: 구성적 행동 공간을 통한 적응형 에이전트 추론

JevSpawn: Adaptive Agentic Inference through Compositional Action Spaces

대규모 언어 모델(LLM) 에이전트는 중간 추론과 행동을 토큰 단위로 생성하므로, 장기적인 상호작용 시 속도가 느리고 연산 비용이 많이 듭니다. Jev 방식의 모델은 유한한 체(finite fields)에 대해 빠른 확률적 예측을 제공하지만, 이러한 대상을 사전에 지정해야 한다는 한계가 있습니다. 이러한 요구 조건은 사용 가능한 행동을 자연어 지시사항으로부터 도출하고 상호작용을 통해 적응시켜야 하는 자율적인 과업 해결을 제한합니다. 본 논문에서는 자연어 과업 명세와 유한 확률적 탐험을 연결하는 구성적 정책인 JevSpawn을 소개합니다. 병렬 행동 생성(action spawning)은 피드백 기반 분기 선택, 표현 수정, 유지된 대안으로부터의 복구와 결합됩니다. 공유된 행동 구조와 모델 접두사는 추가적인 학습 없이도 반복적인 생성 및 컨텍스트 연산을 줄여줍니다. 7개의 에이전트 베이스라인 및 TypeSafe Jev 변형을 대상으로 한 8개 벤치마크 과업 평가를 통해, JevSpawn이 과업 성능 향상과 더 빠른 탐색을 실현하며 구조화된 에이전트 추론에 유망한 접근법임을 입증합니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.