경로 할당

경로 할당, 경로 선택 또는 교통 배정은 운송 네트워크에서 출발지와 목적지 사이의 경로(대체로 호출되는 경로)의 선택에 관한 것이다. 기존 교통예측모형의 네 번째 단계로, 트립 발생, 트립 분포, 모드 선택 등에 이은 것이다. 트립 분포의 지역적 교환 분석은 원점-목적 트립 표를 제공한다. 모드 선택 분석은 어떤 여행자가 어떤 모드를 사용할지 알려준다. 시설 필요성과 비용 및 편익 등을 판단하기 위해서는 각 경로와 네트워크의 링크(경로는 단순히 출발지와 목적지 사이의 연결 고리의 연쇄일 뿐)에 대한 여행자 수를 알 필요가 있다. 우리는 교통(또는 여행)의 임무를 수행할 필요가 있다. 고속도로와 교통 시스템의 네트워크와 제안된 추가가 있다고 가정합시다. 우리는 먼저 현재의 교통 지연 패턴과 추가가 이루어지면 어떻게 되는지 알고 싶다.

일반 접근 방식

오랜 기법

노선별로 얼마나 많은 이용자가 있는지 추정하는 문제는 오래 서 있다. 고속도로와 고속도로가 개발되기 시작하면서 기획자들은 그것을 열심히 보기 시작했다. 고속도로는 지역 도로 시스템을 넘어서는 우수한 수준의 서비스를 제공했고, 교통을 지역 시스템으로부터 우회시켰다. 처음에는 기분 전환이 기술이었다. 비용, 편안함 및 서비스 수준을 고려하여 강화된 이동 시간 비율을 사용했다.

시카고 지역 교통 연구(CATS) 연구진은 고속도로 대 지방 도로의 전환 곡선을 개발했다. 캘리포니아에도 많은 일이 있었다. 왜냐하면 캘리포니아는 초기 고속도로 계획을 경험했기 때문이다. 전환 작업 외에도, CATS는 복잡한 네트워크와 함께 작업할 때 발생하는 몇 가지 기술적 문제를 공격했다. 한 가지 결과는 네트워크에서 최단 경로를 찾기 위한 Bellman-Ford-Moore 알고리즘이었다.

전환 접근방식이 다루지 않은 문제는 링크와 노선의 트래픽 양으로부터 받은 피드백이었다. 많은 차량이 시설을 이용하려 하면 시설이 혼잡해지고 이동시간이 늘어난다. 피드백을 고려할 수 있는 어떤 방법이 없어서 초기 계획 연구(실제로 1960-1975년 대부분)는 피드백을 무시했다. 그들은 최단 경로를 결정하기 위해 무어 알고리즘을 사용했고 모든 트래픽을 최단 경로에 할당했다. 그것은 i에서 j까지의 모든 트래픽이 경로를 따라 이동하거나 그렇지 않기 때문에 전부 또는 무 할당이라고 불린다.

전부 또는 전혀 또는 최단 경로 할당은 기술 컴퓨팅 관점에서 사소한 것이 아니다. 각 교통 구역은 n - 1 구역에 연결되어 있으므로 고려해야 할 경로가 많다. 게다가, 우리는 궁극적으로 링크에서의 트래픽에 관심이 있다. 링크는 여러 경로의 일부일 수 있으며, 경로에 따른 트래픽은 링크에 의해 합산되어야 한다.

논쟁은 전부 또는 아무것도 아닌 접근법에 찬성할 수 있다. 이 방법은 다음과 같다. 기획연구는 모든 링크에서 좋은 수준의 서비스가 제공될 수 있도록 투자를 지원하는 것이다. 계획된 서비스 수준과 관련된 이동 시간을 이용하여, 계산은 개선사항이 시행되면 트래픽이 어떻게 흐르는지 나타낸다. 링크 상의 트래픽 양을 알면, 원하는 서비스 수준을 만족시키기 위해 공급될 용량을 계산할 수 있다.

휴리스틱 절차

교통 부하가 이동 시간 및 교통 평형도에 미치는 영향을 감안하여 여러 가지 경험적 계산 절차를 개발하였다. 한 번의 휴리스틱은 점진적으로 진행된다. 할당될 트래픽은 부분(보통 4)으로 나뉜다. 트래픽의 첫 번째 부분을 할당하십시오. 새 이동 시간을 계산하고 트래픽의 다음 부분을 할당하십시오. 모든 트래픽이 할당될 때까지 마지막 단계를 반복한다. CATS는 여기에 변형을 사용했고, O-D 테이블에서 한 줄씩 할당했다.

FHWA의 컴퓨터 프로그램 컬렉션에 포함된 휴리스틱스는 다른 방식으로 진행된다.

• 0. 전체 또는 무절제 절차를 사용하여 모든 트래픽을 로드하는 것으로 시작하십시오.
• 1. 결과 이동 시간을 계산하고 트래픽을 재할당한다.
• 2. 이제 무게를 이용하여 재할당하기 시작한다. 이전 두 개의 적재에서 가중 이동 시간을 계산하고 다음 할당에 사용하십시오. 최근의 반복은 0.25의 가중치를 가지며, 앞의 반복은 0.75의 가중치를 가진다.
• 3. 계속.

이 절차들은 "아주 잘" 작동하는 것 같지만 정확하지는 않다.

프랭크-울프 알고리즘

다페르모스(1968)는 교통 평형 문제를 다루는 데 사용할 수 있는 프랭크-울프 알고리즘(1956, 플로리안 1976년)을 적용했다. 우리가 고속도로망을 고려하고 있다고 가정하자. 각 링크에는 저항과 트래픽 볼륨 사이의 관계를 나타내는 기능이 있다. 공공도로국(BPR)은 링크(arc) 혼잡(또는 볼륨 지연) 또는 링크 성능(link performance) 기능을 개발했는데, 우리는_a 이를 S(v_a)라고 할 것이다.

${\displaystyle S_{a}\좌({v_{a}}\우)=t_{a}\좌({1+0.15\좌({1+0.15\좌({v_{a}}}}{c_{a}}}\우)^{4}}$

• t_a = 링크의 시간 단위당 자유 흐름 이동 시간
• v_a = 시간 단위당 링크의 트래픽 볼륨(더 정확하게: 링크 a를 사용하려고 시도하는 흐름)
• c_a = 시간 단위당 링크 용량
• S_a(v_a)는 링크 a에서 차량의 평균 이동 시간이다.

다른 혼잡 기능이 있다. CATS는 오랫동안 BPR이 사용하는 기능과 다른 기능을 사용해 왔지만, CATS와 BPR 기능을 비교했을 때 결과 차이가 거의 없어 보인다.

평형 할당

교통량을 경로와 링크에 할당하기 위해서는 규칙이 있어야 하고, 잘 알려진 워드롭 평형 조건들이 있다.^[1] 이것들의 본질은 여행자들이 출발지에서 목적지까지 최단거리(최저저항)의 길을 찾기 위해 노력할 것이고, 네트워크 평형은 어떤 여행자도 새로운 경로로 전환하여 여행 노력을 줄일 수 없을 때 발생한다. 이러한 조건은 사용자 최적 조건이라고 불리며, 시스템이 평형을 이루면 사용자가 이동 경로를 변경하여 얻을 수 없기 때문이다.

다음의 비선형 프로그래밍 문제를 해결함으로써 사용자 최적 평형을 찾을 수 있다.

${\displaystyle \min \sum _{a}{0}^{v_{a}}{S_{a}\왼쪽(x\오른쪽)}dx}$

대상:

${\displaystyle v_{a}=\sum _{i}{j}{j}{j}}{r}{r}}{r}^{ij}x_{ij}^{r}}}}}}}}$

${\displaystyle \sum _{r}{x_{ij}^{r}=T_{ij}}}$

${\displaystyle v_{a}\geq 0,\;x_{ij}^{r}\geq 0}$

여기서 $x{\displaystyle {}_{}^{}}$ ${\displaystyle i_{}^{}}$ ${\displaystyle j_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$는 출발지 i에서 목적지 j까지 경로 r에 있는 차량 수입니다. 그래서 제약조건 (2)는 모든 여행은 반드시 이루어져야 한다고 말한다 –i = 1 ... n; j = 1 ... n

${\displaystyle {\alpha }_{}^{}}$ ${\displaystyle i_{}^{}}$ ${\displaystyle j_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle r_{}^{}}$ ${\$ = 링크 a가 i에서 j까지의 경로 r에 있는 경우 1이고, 그렇지 않으면 0이다. 그래서 제약조건(1)은 각 링크의 트래픽을 집계한다. 네트워크의 각 링크에는 제약이 있다. 제약 조건 (3)은 음의 트래픽이 없도록 보장한다.

예

Eash, Janson, Boyce(1979)의 예를 들어 비선형 프로그램 문제에 대한 해결책을 설명할 것이다. 노드 1에서 노드 2까지 2개의 링크가 있으며, 각 링크에 대한 저항 기능이 있다(그림 1 참조). 그림 2의 곡선 아래 영역은 등식 1의 0에서 a까지의 통합에 해당하며, 합계는 220,674이다. 링크 b에 대한 함수는 역방향으로 표시된다는 점에 유의하십시오.

${\displaystyle S_{a}=15\좌({1+0.15\좌)({\frac {v_}{a}}}{1000}\우)^{4}}$

${\displaystyle S_{b}=20\좌측({1+0.15\좌측)({\frac {v_}{b}}}{3000}\우측)^{4}}$

${\displaystyle v_{a}+v_{b}=8000}$

그림 1: 두 경로 네트워크

그림 2: 균형 할당 문제에 대한 그래픽 솔루션

그림 3: 평형 조건을 만족하지 않는 차량의 할당

평형상태에서 링크 a에는 2,152대의 차량이 있고 링크 b에는 5847대의 차량이 있다. 이동 시간은 각 경로에서 같다: 약 63.

그림 3은 평형용액과 일치하지 않는 차량의 배분을 나타낸다. 곡선은 변함이 없다. 그러나 새로운 경로에 차량을 할당함에 따라 음영 구역이 솔루션에 포함되어야 하므로 그림 3 솔루션은 음영 구역 면적에 따라 그림 2의 솔루션보다 크다.

여행 선택 사항 통합

도시 교통 계획 모델은 따라야 할 일련의 단계로서 진화했고, 모델은 각 단계에서 사용하기 위해 진화했다. 때때로 로리 모델의 첫 번째 진술에서 그랬듯이 단계 내에서의 단계들이 있었다. 경우에 따라서는 단계를 통합할 수 있다는 점에 주목했다. 보다 일반적으로, 동시에 이루어질 수 있는 결정으로부터 추상적인 단계들이며, 분석에서 그러한 단계를 더 잘 재현하는 것이 바람직할 것이다.

세분화된 수요 모델은 처음에 모드 선택 문제를 다루기 위해 개발되었다. 그 문제는 여행을 가기로 결정했고, 그 여행이 어디로 갈지, 그리고 언제 여행이 이루어질지 가정한다. 그들은 함축된 광범위한 문맥을 다루는데 사용되어 왔다. 전형적으로, 내포된 모델은 예를 들어, 트립이 이루어질 확률을 시작으로, 장소들 사이에서 선택을 검사한 다음, 모드 선택으로 개발될 것이다. 여행하는 시간은 치료하기가 좀 어렵다.

윌슨의 이중 제약 엔트로피 모델은 총체적 수준에서 노력을 위한 출발점이 되었다. 해당 모델에 제약 조건이 포함됨

${\displaystyle t_{ij}c_{ij}=C}$

여기서 $c{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle j_{}}$ ${\$는 링크 이동 비용이고$$ $t{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ j ${\$는 링크의 트래픽을 가리키며$$, C는 모델에 데이터를 장착할 때 크기 조정해야 하는 리소스 제약조건이다. 그러한 형태의 제약을 사용하는 대신, 트래픽 할당에 사용되는 단조롭게 증가하는 저항 기능을 사용할 수 있다. 그 결과는 구역 간 이동을 결정하고 네트워크에 트래픽을 할당하며, 이는 시스템이 작동하는 방식을 보면 이해가 가는 것으로서 – 구역 간 트래픽은 정체로 인해 발생하는 저항에 따라 결정된다.

또는 링크 저항 기능을 객관적인 기능(그리고 제약조건에서 제거된 총비용함수)에 포함할 수 있다.

일반화된 세분화된 선택 접근방식은 일반화된 집합적 접근방식이 있는 것처럼 발전했다. 가장 큰 문제는 그들 사이의 관계에 대한 것이다. 우리가 매크로 모델을 사용할 때, 우리는 그것이 나타내는 세분화된 행동을 알고 싶다. 만약 우리가 마이크로 분석을 하고 있다면, 우리는 그 분석의 총체적인 의미를 알고 싶다.

Wilson은 기원과 목적지의 매력에 대해 무언가를 말해주는 가중 매개변수로 중력 같은 모델을 도출한다. 너무 많은 수학이 없다면 우리는 매력에 근거한 선택 문장의 확률을 쓸 수 있고, 이것들은 몇몇 세분화된 수요 모델들과 비슷한 형태를 취한다.

이동 수요를 경로 할당과 통합

여행 수요는 네트워크 공급에 의해 영향을 받는다는 것은 오래 전부터 인식되어 왔다. 추가 교통을 유도하기 전에는 없었던 새로운 교량 개방의 예는 수세기 동안 언급되어 왔다. 많은 연구가 예측 시스템이 이 현상을 직접 설명할 수 있는 방법을 개발하기 위해 진행되었다. 에반스(1974)는 평형 할당 모델과 중력 분배 모델을 수학적으로 엄격한 결합에 관한 박사 논문을 발표했다. 이 통합의 가장 초기 인용은 어윈과 폰 큐브의 작품이며, 플로리안 외 연구진(1975)은 에반스의 작품에 대해 다음과 같이 논평했다.

"에반스의 작업은 어윈과 본 큐브[Multi-Travel Mode Assignment Programs]의 H.R.B. 게시판 347 (1962)에서 토론토 교통 연구를 위해 개발한 알고리즘과 다소 닮았다. 그들의 작업은 비록 순차적 절차를 적용하지만, 정체된 임무와 트립 분배 사이에 피드백을 허용한다. 분포 문제의 초기 해결책부터 시작하여, 영역간 주행은 초기 최단 경로에 할당된다. 연속적인 반복을 위해, 새로운 최단 경로를 계산하고, 그 길이는 분배 모델을 입력하기 위한 접근 시간으로 사용된다. 새로운 지역간 흐름은 이미 발견된 경로에 어느 정도 비례하여 할당된다. 연속 반복에 대한 영역 간 시간이 준균일 때 절차가 중단된다."

플로리안 외 연구진은 프랭크-울프 알고리즘을 직접 적용하면서 결합배분 할당을 해결하기 위해 다소 다른 방법을 제안했다. Boyce 외 연구진(1988)은 탄력적인 요구를 가진 과제를 포함하여 네트워크 평형 문제에 대한 연구를 요약한다.

토론

세 가지 링크 문제는 그래픽으로 해결할 수 없으며, 대부분의 운송 네트워크 문제는 많은 수의 노드와 링크를 포함한다. 예를 들어, Eash 외 연구진은 약 3만 개의 단방향 링크와 9,500개의 노드가 있는 DuPage County의 도로망을 연구했다. 문제가 크기 때문에 과제 문제를 해결하기 위한 알고리즘이 필요하며, 프랭크-울프 알고리즘(처음 출간된 이후 다양한 현대적 수정사항 포함)이 사용된다. 전부 또는 아무것도 할당하지 않고 먼저 프랭크 울프가 개발한 규칙을 따라 목표 함수의 최소 값에 대해 반복하십시오. (알고리즘은 최적의 솔루션으로의 수렴을 달성하기 위해 연속적으로 실현 가능한 솔루션을 적용한다. 계산을 최적의 솔루션으로 빠르게 이동시키기 위해 효율적인 검색 절차를 이용한다.) 이동 시간은 이 프로그래밍 문제의 이중 변수에 해당한다.

프랭크-울프 알고리즘이 1956년에 사용 가능했다는 것은 흥미롭다. 응용은 1968년에 개발되었고, 제1차 평형 할당 알고리즘이 일반적으로 사용되는 교통 계획 소프트웨어(Emme와 Emme/2, 플로리안 등이 몬트리올에서 개발한 것)에 내장되기까지는 거의 20년이 걸렸다. 우리는 주로 기술 개발의 속도와 패턴에 대한 반대 사례를 찾을 수 있기 때문에 느린 응용 프로그램 관찰로부터 어떤 일반적인 결론도 도출하고 싶지 않을 것이다. 예를 들어, 선형 프로그래밍 문제의 해결을 위한 심플렉스 방법이 많은 프로그래밍 이론이 개발되기 전에 개발되어 널리 적용되었다.

문제 진술과 알고리즘은 토목 공학, 구조, 시공에 걸쳐 일반적인 응용을 가지고 있다. (Hendrickson 및 Janson 1984 참조).

노선선택에 관한 실증적 연구

경로 할당 모델은 최소한 사람들이 네트워크에서 경로를 선택하는 방법에 대한 경험적 연구에 기초한다. 이러한 연구는 일반적으로 특정 모드에 초점을 맞추고 있으며, 명시적 선호도 또는 공개된 선호도 모델을 이용한다.

자전거

자전거 이용자들은 지정된 자전거 도로를 선호하고 가파른 언덕을 피하는 것으로 밝혀졌다.^[2]

대중 교통

대중교통은 오랫동안 노선배정의^[3] 맥락에서 고려되어 왔으며, 환승 노선 선택에 관한 많은 연구가 진행되어 왔다. 다른 요소들 중에서, 환승 사용자들은 총 이동 시간, 시간 또는 거리 걷기, 그리고 환승 횟수를 최소화하려고 노력한다.^[4]

참고 항목

• 경로 선택(동음이의)

메모들

일반 참조

• 다페르모스, 스텔라. C.와 F.T. 스패로우 일반 네트워크의 트래픽 할당 문제." 국가표준국 제 J. 73B, 페이지 91-118. 1969.
• Florian, Michael Ed, 교통 평형법, Springer-Verlag, 1976.
• Eash, Ronald, Bruce N. Janson 및 David Boyce 평형 여행 할당: 실천을 위한 장점과 시사점, 교통 연구 기록 728, 페이지 1–8, 1979.
• 에반스, 수잔 P. "트립 분포와 할당을 결합하기 위한 일부 모델의 분석 및 분석" 교통조사, 제10권, 페이지 37-57 1976
• Hendrickson, C.T. 및 B.N. Janson, "여러 토목 공학 문제에 대한 공통 네트워크 흐름 형성" 토목 공학 시스템 1(4), 페이지 195–203, 1984.