차량 배선 문제

이 글은 위키피디아 편집자의 개인적인 감정을 기술하거나 주제에 대한 독창적인 주장을 제시하는 개인적인 성찰, 개인적인 에세이 또는 논쟁적인 에세이처럼 쓰여집니다. 백과사전 형식으로 다시 작성하여 개선하십시오. (2021년 12월) (템플릿 메시지 삭제 방법 및 삭제 시기 확인)

차량 라우팅 문제(VRP)는 조합 최적화 및 정수 프로그래밍 문제로서, "일련의 차량이 특정 고객에게 전달하기 위해 통과해야 하는 최적의 경로 집합은 무엇입니까?"라고 묻는 문제입니다.출장 세일즈맨 문제(TSP)를 개괄적으로 설명합니다.1959년 ^[1]조지 단치히와 존 램저의 논문에 처음 등장했는데, 이 논문에 최초의 알고리즘적 접근법이 쓰여져 휘발유 배달에 적용되었다.이러한 상품을 주문한 고객에게 중앙 창고에 위치한 상품을 배송하는 것이 문맥인 경우가 많다.VRP의 목적은 총 루트 비용을 최소화하는 것입니다.1964년 Clarke와 Wright는 절약 알고리즘이라고 불리는 효과적인 탐욕 알고리즘을 사용하여 Dantzig와 Ramser의 접근 방식을 개선했습니다.

VRP에 대한 최적의 해결책을 결정하는 것은 ^[2]NP-hard이기 때문에 수학적 프로그래밍 또는 조합적 최적화를 사용하여 최적으로 해결할 수 있는 문제의 크기는 제한될 수 있습니다.따라서 상용 해결사는 해결해야 하는 실제 VRP의 크기와 빈도 때문에 휴리스틱스를 사용하는 경향이 있습니다.

VRP는 업계에서 많은 직접 응용 프로그램을 보유하고 있습니다.VRP 라우팅 툴 벤더는 많은 경우 비용을 5%~^[3]30% 절감할 수 있다고 주장합니다.

문제의 셋업

VRP는 배송 회사의 서비스와 관련이 있습니다.주어진 가정용 차량 세트를 가지고 있고 주어진 도로 네트워크를 이동할 수 있는 일련의 운전자에 의해 운영되는 하나 이상의 창고에서 고객에게 물건이 전달되는 방식.모든 고객의 요구사항과 운영상의 제약이 충족되고 글로벌 운송 비용이 최소화되도록 일련의 경로 S(자체 창고에서 출발하고 종료해야 하는 각 차량에 대해 하나의 경로)를 결정할 것을 요구한다.이 비용은 금전적, 거리적 또는 ^[2]기타가 될 수 있습니다.

도로 네트워크는 호가 도로이고 정점이 도로 사이의 교차점인 그래프를 사용하여 설명할 수 있습니다.아크는 일방통행 도로의 존재 또는 각 방향의 비용이 다를 수 있기 때문에 방향을 정하거나 정하지 않을 수 있습니다.각 호에는 일반적으로 차량 종류에 ^[2]따라 달라질 수 있는 길이 또는 이동 시간인 관련 비용이 있습니다.

각 경로의 글로벌 비용을 확인하려면 각 고객과 창고 간의 이동 비용 및 이동 시간을 알아야 합니다.이를 위해 원래 그래프는 정점이 고객 및 창고이고 호가 둘 사이의 도로인 그래프로 변환됩니다.각 아크의 비용은 원래 도로망상의 두 지점 사이의 가장 낮은 비용입니다.이것은 최단 경로 문제가 비교적 해결되기 쉽기 때문에 쉽게 할 수 있습니다.그러면 스파스 원본 그래프가 완전한 그래프로 변환됩니다.각 정점 i와 j 쌍에 대해 완전한 그래프에는 C ${\displaystyle i_{}}$j(\displaystyle $C_{ij})$로 기재되어 i에서j까지의 최단 경로 비용으로 정의되는 호(i,j)가 존재합니다.이동 $시간{\displaystyle {}_{}}$ ${\displaystyle {ti}_{}}$ $({$는 원래 도로 그래프에서 i에서 j까지의 최단 경로 상의 호 이동 시간의 합계입니다.

고객의 요구를 모두 만족시킬 수 없는 경우가 있습니다.이 경우 해결사는 고객의 요구를 줄이거나 일부 고객을 서비스 대상에서 제외시킬 수 있습니다.이러한 상황에 대처하기 위해 각 고객에 대한 우선순위 변수를 도입하거나 각 고객에 대한 서비스 부분 또는 서비스 부족에 대한 패널티를 적용할 수 있습니다.

VRP의 목적 함수는 결과의 특정 응용 프로그램에 따라 크게 다를 수 있지만 보다 일반적인 목적 중 몇 가지는 다음과 같습니다.^[2]

• 전 세계 주행 거리 및 중고 차량 및 운전자와 관련된 고정 비용을 기준으로 글로벌 운송 비용 최소화
• 모든 고객에게 서비스를 제공하는 데 필요한 차량 수를 최소화합니다.
• 이동 시간 및 차량 적재량에서 가장 적은 변동
• 저품질 서비스에 대한 위약금 최소화
• 수집된 이익/점수를 최대화합니다.

VRP 바리안트

차량 배선 문제의 종류와 전문성은 다음과 같습니다.

• 이익과 관련된 차량 라우팅 문제(VRPP): 모든 고객을 반드시 방문해야 하는 것은 아닌 최대화 문제.차량 시간 제한을 준수하면서 고객이 수집한 이익의 합계를 최대화하는 것이 목적입니다.차량은 차고에서 출발하고 종료해야 합니다.가장 잘 알려져 연구되고 있는 VRP 중 다음을 예로 들 수 있습니다.
  • 팀 오리엔티어링 문제(TOP)는 가장 많이 연구된 VRPP의 ^[4][5][6]변형입니다.
  • 캐패시티브 팀 오리엔티어링 문제(CTOP),
  • TOP with Time Windows(TOPTW).
• 차량 라우팅 문제(VRPPD): 특정 픽업 위치에서 다른 배송 위치로 많은 화물을 이동해야 합니다.목표는 일련의 차량이 픽업 및 드롭 장소를 방문할 수 있는 최적의 경로를 찾는 것입니다.
• LIFO 관련 차량 배선 문제: 차량 적재에 추가적인 제한이 가해진다는 점을 제외하면 VRPPD와 유사합니다. 모든 배송 위치에서 배송되는 품목은 가장 최근에 픽업된 품목이어야 합니다.이 스킴에서는, 드롭 하는 아이템 이외의 아이템을 일시적으로 언로드 할 필요가 없기 때문에, 딜리버리 로케이션에서의 로딩과 언로드 시간을 단축합니다.
• 시간 창(VRPTW)에 따른 차량 라우팅 문제:전달 위치에는 전달(또는 방문)을 수행해야 하는 시간대가 있습니다.
• 캐패시티브 차량 라우팅 문제: CVRP 또는 CVRPTW.차량에는 배송해야 하는 물품의 운반 능력이 제한되어 있습니다.
• 다중 트립에 따른 차량 라우팅 문제(VRPMT): 차량이 둘 이상의 경로를 수행할 수 있습니다.
• 개방형 차량 라우팅 문제(OVRP): 차량을 수리소로 반환할 필요가 없습니다.
• IRP(Inventory Routing Problem): 차량은 각 납품 지점의 요구사항을 충족할 책임이 있습니다.
• 다중 보관소 차량 라우팅 문제(MDVRP): 차량의 시동을 걸거나 ^[8]종료할 수 있는 여러 보관소가 있습니다.

여러 소프트웨어 벤더가 다양한 VRP 문제를 해결하기 위해 소프트웨어 제품을 개발했습니다.연구 및 결과에 대한 자세한 내용은 수많은 기사를 참조할 수 있습니다.

VRP는 Job Shop Scheduling 문제와 관련이 있지만 일반적으로 두 가지 문제는 다른 방법을 ^[9]사용하여 해결됩니다.

정확한 솔루션 방법

VRP 모델링에는 세 가지 주요 접근법이 있다.

1. 차량 흐름 공식—차량에서 가장자리를 통과하는 횟수를 카운트하는 각 호와 관련된 정수 변수를 사용합니다.일반적으로 기본 VRP에 사용됩니다.이는 솔루션 비용을 호와 관련된 비용의 합계로 나타낼 수 있는 경우에 적합합니다.그러나 많은 실용적인 ^[2]응용 프로그램을 다룰 수 없습니다.
2. 상품 흐름 공식—추가 정수 변수는 차량이 이동하는 경로를 따라 상품의 흐름을 나타내는 호 또는 모서리와 관련된다.이것은 최근에야 정확한 ^[2]해결책을 찾기 위해 사용되었습니다.
3. 파티션 설정 문제:이들은 각각 다른 실현 가능한 회로와 관련된 기하급수적인 수의 바이너리 변수를 가지고 있습니다.그 후 VRP는 VRP 제약조건을 충족하는 최소 비용으로 회선의 컬렉션을 확인하는 세트 파티셔닝 문제로 공식화됩니다.이것에 의해, 매우 일반적인 루트 ^[2]코스트를 실현할 수 있습니다.

차량 흐름 공식

단치히, 풀커슨 및 존슨의 TSP 공식은 VRP를 위한 두 가지 지수 차량 흐름 공식을 만들기 위해 확장되었다.

$(\displaystyle\text{min}\sum_{i\in V}\sum_{j\in V}c_{ij}x_{ij})$

의 영향을 받는.

$\displaystyle \sum _{i\in V}x_{ij}=1\quad \forall j\in V\backslash \left\{0\right\}$

(1)

$\displaystyle \sum _{j\in V}x_{ij}=1\quad \forall i\in V\backslash \left\{0\right\}$

(2)

$\displaystyle \sum _{i\in {V\backslash \left\{0\right\}}x_{i0}=K}$

(3)

$\displaystyle \sum _{j\in {V\backslash \left\{0\right\}}x_{0j}=K}$

(4)

$\displaystyle \sum _{i\notin S}\sum _{j\in S}x_{ij}\geq r(S),~\forall S\subseteq V\setminus \{0\},S\neq \emptyset }$

(5)

${\displaystyle x_{ij}\in\{0,1\}\quad\forall i,j\in V}$

(6)

이 $공식$에서 ${\displaystyle {\mathrm{ci}}_{}}$j({$displaystyle$$c_{$ij})는 노드$$i({$displaystyle$i})에서$$ $노드{\displaystyle }$j({$displaystyle$j$\})$로 이동하는 비용을 나타냅니다$$.${\displaystyle x_{}}$ ${\displaystyle i_{}}$j({$displaystyle$ $x_{ij})$는 i$({displaystyle$i})에서$$j($displaystyle$$$j$)$로 이동하는 호) 값$1$을 갖는 바이너리 변수입니다.는 솔루션의 일부로 $간주$됩니다.그렇지 않으면$$0$({$$displaystyle$0$})$은 사용 가능한 차량의 $수이고{\displaystyle }$ $(S)$는 세트$$S({$displaystyle$ S$\}$에 필요한 최소 차량 수에$$ 해당합니다.또한 0$({displaystyle$0})이 디포넌트라고 가정하고 있습니다.송부하다

구속조건 1과 2는 각각 정확히 하나의 호가 진입하고 정확히 하나의 정점이 고객과 관련된 각 정점을 떠난다는 것을 나타냅니다.제약 조건 3과 4에는 차량 출고 대수가 진입 대수와 동일하다고 되어 있습니다.제약조건 5는 용량절감 제약조건으로, 이는 경로가 연결되어야 하며 각 경로의 수요가 차량 용량을 초과해서는 안 된다는 것을 부과한다.마지막으로 제약조건 6은 통합 ^[2]제약조건이다.

${\displaystyle 2개}$의 V$displaystyle$2 V$)$ 구속조건$$ 중 하나의 임의 구속조건은 실제로 $나머지{\displaystyle \mathrm{}}$ ${\displaystyle 2개}$의${\displaystyle }$V -$$(\$displaystyle$ 2 V -$$1)에 의해 암시되므로 제거할 수 있습니다.고객 $세트{\displaystyle }$ S$(\displaystyle$ S$)$에 의해 정의된 각 절단 부분에는 r$(\displaystyle$ r$(S$ $이상$의 호가 교차됩니다($세트{\displaystyle }$ S$(\displaystyle$ S$)).$^[2]

용량 삭감 제약조건을 일반화 서브우어 제거 제약조건(GSEC)으로 변환함으로써 대체 제제를 얻을 수 있다.

$\displaystyle \sum _{i\in S}\sum _{j\in S}x_{ij}\leq S -r(S)}$

r${\displaystyle }$(${\displaystyle S}$) { $display$ $style$ r$(S)}$ 이상의 호가 각 고객 $설정{\displaystyle }$ S$(\display$S$)$^[2]에 남습니다.

GCEC와 CCC는 지수적인 수의 제약이 있기 때문에 선형 완화를 해결하는 것은 사실상 불가능합니다.이 문제를 해결할 수 있는 방법은 이러한 제약 조건의 제한된 부분 집합을 고려하고 필요에 따라 나머지를 추가하는 것입니다.

또 다른 방법은 MTZ 제약조건으로 알려진 다항식 카디널리티를 가진 제약조건의 패밀리를 사용하는 것으로, TSP에 대해 먼저 제안되고 이후 크리스토피데스, 밍고지 및 ^[11]토스에 의해 확장되었다.

$(\displaystyle u_{j}-u_{i}\geq d_{j}-C(1-x_{ij})~~~~~\forall i,j\in V\backslash \{0\},i\neq j~~~{\text{s.t.}}d_{i}+d_{j}\leq C}$

$\displaystyle 0\leq u_{i}\leq C-d_{i}~~~~~ V\backslash \{0\}의 모든 i에 대해$

$여기$서 ${\displaystyle u_{}}$ ${\displaystyle \text{i}{}_{}}$, i${\displaystyle v}$ V ${\displaystyle \{}$ { ${\displaystyle 0}$ $}$ { $displaystyle u$_ {$i$ , ~$i\in$V \ $backslash$\ { $0$\ }는$$ 고객을 $방문$한 후 차량에 남아 있는 부하를 나타내는 추가 연속 $변수$이며 d$$$${ $displaystyle$$$$d_{i$}는$$$$ $고객$의 $요구$ 사항입니다$.$이 경우 접속 요건과 용량 요건이 모두 부과됩니다.$x{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ j ${\displaystyle {}_{}}$ {$style x_{ij$} =$$0$}$ 제약 ${\displaystyle \mathrm{조건}}$인 $,$ x ${\displaystyle i_{}}$$$${\displaystyle {}_{}}$ ${\displaystyle 1}${$displaystyle$ $x_${$i}\leq C$$및$ $u$ j$display$ style $u_{j$$}$ $=$$1$이므로 구속력이 $없습니다$.$u_{j}\geq u_{i}+d_{j$

이것들은 Basic VRP(CVRP; 기본 VRP)와 VRPB 모델화에 광범위하게 사용되고 있습니다.하지만, 그들의 힘은 이러한 간단한 문제들로 제한된다.이들은 솔루션 비용이 아크 비용의 합계로 표현될 수 있는 경우에만 사용할 수 있습니다.또한 어떤 차량이 각 호를 가로지르는지도 알 수 없습니다.따라서 비용 및 실현 가능성이 고객 또는 ^[2]사용된 차량의 주문에 따라 달라지는 보다 복잡한 모델에는 이를 사용할 수 없습니다.

수동과 자동 최적 라우팅

차량 경로 문제를 수동으로 해결하는 방법은 여러 가지가 있습니다.예를 들어, 대형 창고의 지게차에서는 최적의 라우팅이 큰 효율성의 문제입니다.가장 효율적인 경로를 결정하기 위한 수동 방법으로는 가장 큰 간격, S자형, 통로별 경로, 복합 및 복합 +가 있습니다.Combined + method가 가장 복잡하여 리프트 트럭 운영자가 가장 사용하기 어렵지만, 가장 효율적인 라우팅 방법입니다.그러나 수동 최적 라우팅 방식과 실제 최적 경로 간의 비율 차이는 평균 13%^[12][13]였습니다.

메타휴리스틱

차량 경로 문제의 대규모 사례를 최적화하는 것이 어렵기 때문에, 유전자 알고리즘, Tabu 검색, 시뮬레이션 어닐링 및 적응형 대형 이웃 탐색(ALNS)과 같은 메타 휴리스틱에 상당한 연구 노력이 투입되었다.차량 경로 문제에 대한 가장 최근의 효율적인 메타 휴리스틱 중 일부는 수백 또는 수천 개의 전달 지점을 ^[14]세는 문제 인스턴스에 대해 최적치의 0.5% 또는 1% 범위 내에서 솔루션에 도달합니다.이러한 방법들은 또한 다양한 측면 구속조건을 다루기 위해 더 쉽게 적응할 수 있다는 점에서 더욱 강력하다.이와 같이 메타휴리스틱 기술의 적용은 종종 복잡한 제약 조건과 의사결정 세트를 가진 대규모 애플리케이션에 선호된다.

솔루션 전략의 분류

차량 배선 문제에 대한 대부분의 해결책은 다음 접근법 ^[15]중 하나로 분류할 수 있습니다.

「 」를 참조해 주세요.

• 중국어 집배원 문제
• 차량 일정 변경 문제
• 아크 라우팅
• 그래프 이론 항목 목록

레퍼런스

추가 정보

• Oliveira, H.C.B.de; Vasconcelos, G.C. (2008). "A hybrid search method for the vehicle routing problem with time windows". Annals of Operations Research. 180: 125–144. doi:10.1007/s10479-008-0487-y. S2CID 32406011.
• Frazzoli, E.; Bullo, F. (2004). "Decentralized algorithms for vehicle routing in a stochastic time-varying environment". 2004 43rd IEEE Conference on Decision and Control (CDC). 43rd IEEE Conference on Decision and Control, 14-17 Dec. 2004, Nassau, Bahamas. Proceedings of the ... IEEE Conference on Decision & Control. Vol. 4. IEEE. doi:10.1109/CDC.2004.1429220. ISBN 0-7803-8682-5. ISSN 0191-2216.
• Psaraftis, H.N. (1988). "Dynamic vehicle routing problems" (PDF). Vehicle Routing: Methods and Studies. 16: 223–248.
• Bertsimas, D.J.; Van Ryzin, G. (1991). "A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane". Operations Research. 39 (4): 601–615. doi:10.1287/opre.39.4.601. hdl:1721.1/2353. JSTOR 171167.
• Vidal T, Crainic TG, Gendreau M, Prins C (2013). "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis". European Journal of Operational Research. 231 (1): 1–21. doi:10.1016/j.ejor.2013.02.053. S2CID 15983279.
• Hirotaka, Irie; Wongpaisarnsin, Goragot; Terabe, Masayoshi; Miki, Akira; Taguchi, Shinichirou (2019). "Quantum Annealing of Vehicle Routing Problem with Time, State and Capacity". arXiv:1903.06322 [quant-ph].