Source-linked AI summary
Smart routes: a system for development and comparison of algorithms for solving vehicle routing problems with realistic constraints
Andrew Soroka, German Mikhelson, Alexander Mescheryakov, Sergey Gerasimov
TL;DR
현실적 제약이 있는 경로 최적화는 exact method가 지수적 복잡도에 직면함에 따라 어려워진다. 이 논문은 CVRPTW를 대상으로 exact, heuristic, deep-learning 접근법을 비교하는 Smart Routes를 개발하고, 작은 인스턴스에서는 heuristic과 JAMPR이 더 빠르게 exact에 가까운 품질을 제공하는 반면 큰 인스턴스에서는 exact method의 확장성이 낮음을 보인다.
문제
인스턴스 크기가 증가하면 exact CVRPTW method는 지수적 복잡도에 직면하므로, 효과적인 해 품질과 탐색 시간 간 trade-off에 대한 실증이 필요하다.
방법
이 논문은 Smart Routes를 개발하고 CVRPTW에 대해 SCIP와 LKH, 2-OPT, 3-OPT, OR-Tools, JAMPR을 비교한다.
결과
50-point 인스턴스에서는 heuristic 및 reinforcement-learning 해가 SCIP의 5% 이내를 유지했으며, 100-point 인스턴스에서는 exact method가 초기 해를 얻는 데 13배 더 오래 걸리고 경로 비용이 최대 50% 더 높았다.
시사점 및 한계
실험한 50-point 인스턴스에서는 heuristic 및 neural 접근법이 exact method보다 더 나은 해 품질/탐색 시간 trade-off를 제공하지만, 100-point에서는 exact method가 실용성을 잃는다.
시사점 및 한계
실험에서는 방문하지 않은 지점을 허용하는 SOFT CVRPTW 설정을 사용하고, missed_nodes cost term을 통해 해당 지점에 패널티를 부과한다.
Abstract
from arXiv · showhide
The problem of route optimization with realistic constraints is becoming extremely relevant in the face of global urban population growth. While we are aware of approaches that theoretically provide an exact optimal solution, their application becomes challenging as the problem size increases because of exponential complexity. We investigate the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) and compare solutions obtaining by exact solver SCIP with heuristic algorithms such as LKH, 2-OPT, 3-OPT, the ORTools framework, and the deep learning model JAMPR. We demonstrate that for problem of size 50 deep learning and classical heuristic solutions became close to SCIP exact solution but requires less time. Additionally for problems with size 100, SCIP exact methods around 13 times slower that neural and classical heuristics with the same route cost and on around 50% worse for the first feasible solution on the same time. To conduct experiments, we developed the Smart Routes platform for solving route optimization problems, which includes exact, heuristic, and deep learning models, and facilitates convenient integration of custom algorithms and datasets.
1. 서론
이 논문은 문제 규모의 증가와 현실적 제약, 특히 고객의 time windows, service times, vehicle capacities를 고려한 차량 경로 설정을 다룬다. 또한 일반적인 최적화 방법을 비교하면서 exact, heuristic, deep reinforcement 접근법을 통합하는 플랫폼으로 Smart Routes를 소개한다.
- 동기: Vehicle Routing Problems는 운송 자원 비용, 경로 비용, 화물 배송 시간을 줄이는 것을 목표로 하지만, 고객과 도시의 수가 증가하면서 자원을 효율적으로 사용하기가 점점 더 어려워진다.더 짧은 경로는 서비스 품질을 유지하면서 자원 활용도를 높일 수 있다.
- 문제: 현실적인 경로 설정에서는 문제 규모가 커질수록 solution quality와 search time 사이의 균형을 유지하면서 고객의 time windows, service times, and vehicle capacities를 고려해야 한다.여러 제약하에서 알고리즘을 개발하고 수정하는 일은 여전히 어렵다.
- 기여: 이 논문은 Smart Routes 플랫폼과 일반적인 경로 최적화 방법에 대한 비교 분석을 제시하며, heuristics, deep reinforcement networks, exact SCIP method를 포함한다.비교는 제약이 있는 차량 경로 문제에 초점을 둔다.
- 시스템: Smart Routes는 다양한 차량 경로 문제를 위해 exact, heuristic, and deep reinforcement approaches를 통합하고, 물류 실무자와 새로운 아이디어의 테스트를 모두 지원한다.이 시스템은 경로 최적화 실험을 위한 원스톱 플랫폼으로 설계되었다.
2. 관련 연구
관련 연구는 경로 최적화 방법을 heuristic, exact, deep-learning 접근법으로 분류한다. 선행 비교 연구에서 exact 방법의 활용, 문제 규모, 현실적 제약조건을 충분히 다루지 못한 공백을 강조한다.
- 선행 연구는 exact 접근법을 생략하거나 제한된 문제 규모만 고려하거나 제약조건을 제외하는 경우가 많아, 경로 최적화 알고리즘에 대한 보다 포괄적인 비교가 필요하다.
- Heuristic 알고리즘: Heuristic 방법은 높은 품질의 실행 가능해를 신속하게 구축하는 constructive heuristics와, 더 높은 계산 비용을 감수하는 대신 해 공간을 더 유연하게 탐색하는 metaheuristics로 구성된다.
- Exact 알고리즘: Exact 접근법은 선형 또는 혼합정수 선형계획을 수립하고 Branch&Bound, Cutting Plane, Branch&Cut 등의 방법을 사용해 정수해를 구하거나 실행 불가능성을 증명한다.
- Exact 알고리즘: CPLEX, SCIP [1], Gurobi 와 같은 MILP solver는 여러 exact 알고리즘을 구현하지만, 높은 차원과 정수 변수로 인해 메모리 사용량과 해 도출 시간이 지수적으로 증가할 수 있다.
- Deep learning: Deep-learning 연구는 Nazari et al.'s 의 CVRP용 Pointer Network 변형에서 시작되었으며, RNN encoder를 공유 파라미터를 사용하는 선형 계층으로 대체했다. 이후 Kool et al.'s [12]의 attention-based transformer model이 제안되었다.
3. 알고리즘 및 모델
이 절에서는 제약이 있는 차량 경로 설정 문제를 위한 exact, 고전적 heuristic, deep reinforcement-learning 접근법을 제시한다. Local search, SCIP, OR-Tools, 그리고 학습 가능한 constraint-specific mask를 적용한 modified JAMPR model에 초점을 둔다.
- 고전적 heuristic: Local-search heuristic은 해의 품질과 탐색 효율 사이의 균형을 위해 선택되었으며, metaheuristic과 genetic algorithm도 지원한다 [18].
- 고전적 heuristic: 주요 고전적 heuristic은 Lin-Kernighan [2]으로, 실행 가능하거나 무작위화된 초기 경로에 대해 개선되는 경로 교환을 반복 적용하여 더 이상의 개선이 발견되지 않을 때까지 탐색한다.
- Exact optimization: SCIP [1]는 Branch&Bound, cutting planes, constraint propagation, heuristic, decomposition, integer programming을 포함한 방법으로 mixed-integer optimization을 해결한다.
- Optimization frameworks: OR-Tools 는 vehicle-routing, combinatorial, linear, integer, scheduling 및 관련 optimization 문제를 위한 다목적 framework로 포함되었다.
- Deep reinforcement learning: Modified JAMPR model [4]는 attention-based encoder-decoder reinforcement learning을 사용하고, decoder policy를 변경하기 위해 학습 가능한 constraint-specific masks를 추가한다.경로는 순차적 의사결정 과정으로서 점진적으로 구성되며, coordinates, cargo weights, time windows와 같은 node features를 먼저 encoding한 후 decoding한다.
4. Smart Routes 시스템
Smart Routes는 공통 제약조건하에서 vehicle-routing 알고리즘을 해결하고 비교하기 위한 웹 기반 플랫폼으로, 대규모 및 실제 데이터셋을 지원한다. 모듈식 아키텍처를 통해 exact, heuristic, neural 방법, 사용자 정의 알고리즘, 시각화, metric, API 접근을 통합한다.
- 시스템 요구사항: Smart Routes는 vehicle capacity와 time windows를 포함한 VRP 제약조건을 지원하고, approximately 1000 points까지 확장되며, 지정된 형식의 실제 데이터를 처리한다.또한 classical heuristic, exact, deep reinforcement network 접근법 전반에 걸친 실험을 지원한다.
- 시스템 아키텍처: 플랫폼은 데이터 준비, 알고리즘 학습 및 평가, metric 생성, route 시각화, 웹 상호작용을 위한 Dataset, Algorithm, and Solution modules로 구성된다.사용자는 route 결과를 받기 전에 problem type, algorithm, time limit, dataset 및 선택적 generation parameters를 지정한다.
- 시스템 아키텍처: 각 task에서 사용자는 최종 route cost와 customer visitation order를 얻으며, metric과 전체 graphical route를 보여주는 두 개의 그래프도 함께 제공받는다.metric 그래프는 지정된 time limit 내의 route-cost 변화를 보여주고, visualizer는 route 자체를 표시한다.
- 확장성: 사용자는 base classes를 상속하고 필요한 methods를 구현하여 integrate custom VRP algorithms할 수 있으며, 내장 접근법은 classic heuristics, exact methods, neural methods를 포괄한다.이러한 확장성은 기존 toolkit에서 model을 이해하고 구현하는 데 필요한 시간과, 더 큰 instance에서 exact methods의 탐색 시간이 증가하는 문제를 해결한다.
- 플랫폼의 장점: Smart Routes는 automatic route visualization, performance charts, 내장 접근법을 위한 API, user-friendly interface를 통해 실험을 간소화한다.저자들은 이러한 기능이 기존 software와 비교하여 development, testing, experimentation을 단순화한다고 설명한다.
5. 데이터
본 연구는 방문하지 않은 지점을 건너뛰고 페널티를 부과하는 SOFT 설정에서 CVRPTW 알고리즘을 평가한다. 실험에는 문제 크기 50과 100, 그리고 지정된 용량, 시간 범위, 서비스 시간이 적용된 Solomon R201 인스턴스를 사용한다.
- 문제 설정: CVRPTW 인스턴스는 방문하지 않은 지점을 건너뛸 수 있는 SOFT 설정을 사용하며, 해당 지점은 경로에서 제외되고 missed_nodes penalty가 증가한다.이 설정은 여러 제약이 동시에 존재할 때 알고리즘의 동작을 평가한다.
- 인스턴스: 실험에서는 50개와 100개 지점의 문제 크기에 대해 R201 통계 를 기반으로 Solomon reference 인스턴스를 선정한다.
- 인스턴스 파라미터: 트럭 용량은 Q50 = 750 및 Q100 = 1000이며, 두 문제 크기 모두에 대해 a0 = 0 및 b0 = 1000으로 설정한다.각 지점의 서비스 시간 hi는 균일하게 10으로 설정한다.
6. 실험
50개 및 100개 지점 CVRPTW 인스턴스에서 Smart Routes를 사용해 SCIP와 고전적 heuristic 및 JAMPR를 비교했다. Exact method는 최종 해의 품질은 높았지만 시간이 훨씬 더 걸렸고, JAMPR와 heuristic은 특히 100개 지점에서 빠르게 경쟁력 있는 해를 생성했다.
- 실험 설정: 실험에서는 50개 및 100개 지점 문제에 대해 각각 100개의 인공 인스턴스를 사용했으며, 시간 제한은 100초와 200초였다. SCIP에는 1000초와 2000초를 할당했다.Smart Routes 플랫폼은 parameter 설정을 간소화했으며, 사용 가능한 processor에 task를 병렬화했다.
- 전체 비교: 문제 차원을 두 배로 늘리자 SCIP의 solution time은 약 14배 증가했으며, 이는 100개 이상의 지점을 포함하는 인스턴스에서 exact method의 적용 가능성이 제한적임을 보여준다.비교 결과는 Figure 3에 요약되어 있으며, 축에는 평균 solution time과 평균 route cost가 표시된다.
- 50개 지점 인스턴스: 50개 지점 인스턴스에서 SCIP는 결국 최상의 해를 얻었지만, heuristic과 JAMPR는 수 초 이내에 suboptimal solution을 생성했으며 한 자릿수 배 더 빨랐다.약 10초 후에는 SCIP가 LKH, OR-Tools, JAMPR보다 열세였지만, 100초 후에는 SCIP가 이들을 앞섰고 최종 JAMPR–SCIP gap은 5% 미만이었다.
- 100개 지점 인스턴스: 13× 더 오래 걸림: SCIP는 첫 100개 지점 해를 얻는 데 900초 이상이 필요했으며, JAMPR와 OR-Tools는 유사한 plateau에 도달했다. SCIP의 첫 해는 cost가 약 50% 더 높았다.할당된 2000초 이내에도 SCIP는 optimal solution을 얻지 못했다.
- 100개 지점 인스턴스: 100개 지점 인스턴스에서 JAMPR는 solution quality 측면에서 고전적 heuristic을, 해를 찾는 시간 측면에서 exact method를 능가했다.JAMPR의 초기 greedy solution은 LKH보다 GAP가 약 10% 더 우수했으며, 최종 GAP는 LKH를 약 50% 앞섰다.
7. 결론
결론은 50개 지점 CVRPTW 인스턴스에서 heuristic 및 reinforcement-learning 접근법이 빠르고 거의 최적인 해를 제공하는 반면, 100개 지점에서는 exact 방법이 실용적이지 않음을 보여준다. Smart Routes 플랫폼은 향후 경로 최적화 연구를 위해 이러한 접근법의 해법 탐색과 비교를 지원한다.
- 범위: 이 연구는 Time Windows가 있는 Capacitated Vehicle Routing Problem에 대해 SCIP [1]와 heuristic 및 learning-based 접근법을 비교한다.문제 크기가 증가하면 지수적 복잡도 때문에 exact 최적화가 어려워진다.
- 플랫폼 기여: 보고된 모든 metric은 여러 해법 접근법을 지원하고 연구 및 결과 비교를 용이하게 하는 Smart Routes 플랫폼을 사용해 산출되었다.저자들은 이 플랫폼을 다양한 제약이 있는 경로 최적화의 향후 연구를 위한 중요한 구성 요소로 제시한다.
- 실험 결과: 50개 지점 인스턴스에서 classical heuristic 및 reinforcement-learning 접근법은 SCIP 결과 대비 5% GAP 이내의 빠른 suboptimal solution을 제공했다.이 결과는 두 접근법 모두 exact 방법에 대한 효과적인 대안이 될 수 있음을 보여준다.
- 실험 결과: 100개 지점 인스턴스에서 exact 방법은 초기 해를 찾는 데 13배 더 많은 시간을 필요로 했으며, 최적화 중 최대 50% 높은 경로 비용을 산출했다.주어진 시간 내에 optimal solution을 제공하지 못한 반면, JAMPR와 OR-Tools는 해의 품질에서 classical heuristic을 능가했다.