정전식 아크 라우팅 문제

Capacitated arc routing problem

수학에서, 정전 아크 라우팅 문제(CARP)는 제설기, 거리 청소기 또는 겨울 그리터를 나타내는 그래프를 따라 움직이는 물체에 대한 용량 제약 조건이 주어진 무방향 모서리와 방향 아크가 있는 혼합 그래프의 최소 그래프/이동 거리를 가진 최단 투어를 찾는 문제입니다.또는 용량 제약이 있는 다른 실제 개체.이 제약 조건은 차량이 중앙 보관소로부터 떨어져 있는 시간, 또는 총 주행 거리, 또는 서로 다른 가중치 요인을 가진 두 가지의 조합에 대해 부과될 수 있습니다.

아크 라우팅 책에 설명된 CARP에는 다양한 변형이 있습니다.앙헬 코르베란과 길버트 [1]라포르테의 문제, 방법 및 적용

CARP를 해결하려면 그래프 이론, 아크 라우팅, 운영 연구 및 지리적 라우팅 알고리즘을 연구하여 최단 경로를 효율적으로 찾는 작업이 필요합니다.

CARP는 NP-하드 아크 라우팅 문제입니다.

CARP는 볼록 껍질을 포함한 조합 최적화로 해결할 수 있습니다.

대규모 정전 아크 라우팅 문제(LSCARP)는 정전 아크 라우팅 문제의 변형으로, 대규모 복잡한 [2]환경을 현실적으로 시뮬레이션하고 모델링하기 위해 수백 개의 에지와 노드에 적용됩니다.

레퍼런스

  1. ^ Prins, Christian (2015-02-05), "Chapter 7: The Capacitated Arc Routing Problem: Heuristics", Arc Routing, MOS-SIAM Series on Optimization, Society for Industrial and Applied Mathematics, pp. 131–157, doi:10.1137/1.9781611973679.ch7, ISBN 978-1-61197-366-2, retrieved 2022-07-14
  2. ^ Mei, Yi; Li, Xiaodong; Yao, Xin (June 2014). "Cooperative Coevolution With Route Distance Grouping for Large-Scale Capacitated Arc Routing Problems". IEEE Transactions on Evolutionary Computation. 18 (3): 435–449. doi:10.1109/TEVC.2013.2281503. ISSN 1089-778X. S2CID 4851980.