Large transportation networks with finite-dimensional state space. Asimptotic approach.

August 1998

L.G. Afanassieva, D.V. Khmelev

Department of Mathematics and Mechanics

Moscow Lomonosov State University

e-mail dima@vvv.srcc.msu.su

Consider an open network consisting of N nodes (stations) and V(N) cars, which circulate among the stations. The network is divided into n clusters. As N increases the number of clusters does not change. Cluster j contains d^N_j N stations, Е_{j = 1}ⁿ d^N_j = 1. There exists d_j > 0 so that [(жN(d_j^N-d_j) N®Ґ) || (® 0)] for j = [`1,n]. Later j and v denote cluster numbers and they take values from 1 to n. The arrival process to a station of cluster j is a Poisson one with the rate l_j.

If arrived customer finds a car at the node he takes it to reach his destination. Cluster v is chosen via routing matrix P = {p_jv}_{j,v = [`1,n]}. The destination station in the cluster v is chosen uniformly. After having reached their destinations, customers leave the network.

The fully symmetric network was considered in [1]. Our model represents an asymmetric generalization of [1]. The travel time from a station in cluster j to a station in cluster v is exponentionally distributed with a parameter m_jv. The travel time between two stations in cluster j is also exponentionally distributed with a parameter m_jj. A customer which upon arrival does not find an available car and finds free waiting place joins the queue. Otherwise he leaves the network. Capacities of waiting rooms for customers in cluster v are supposed limited by k_v for each station. There are m_v parking lots for servers at each station. If a car finds a station in cluster v empty and number of cars at the station is less then m_v, it stops and waits for the next customer at this node. Otherwise, it is directed to cluster l via routing matrix [P\tilde] = {[p\tilde]_vl}_{v,l = [`1,n]}. The car chooses a station inside cluster l uniformly.

Initially, each station in cluster j has r_j servers where r_j is integer from 0 to m_j, V(N) = (r₁d₁^N+ј+r_nd_n^N)N. Matrix P[P\tilde] is assumed to be ergodic.

Let x_j,i(t) be a fraction of nodes in state i at cluster j among all N stations, Е_{i = -kj}^m_jx_j,i(t) = d^N_j. Let [M\tilde]_jv(t) denotes the number of cars driving from cluster j to cluster v at the moment t. One can describe the state of the network as a vector x н R^a with a = n²+Е_{v = 1}ⁿ (k_v+m_v+1) components: x = (M₁₁, M₁₂, ј, M_1n, M₂₁, ј, M_nn, x_1,-k1, x_1,-k1+1, ј, x_1,m1, x_2,-k2, ј, x_n,mn), where M_jv(t) = [M\tilde]_jv(t)/N. It is clear that the stochastic process X^N_t = x(t) is the ergodic Markov chain.

Let x_t(x) be a solution of the following system of ordinary differential equations with the initial point x₀(x) = x:

. x   j,-kj  = (lj dj xj,-kj+1 - Mj xj,-kj )/dj, . x   j,i  = (lj dj xj,i+1- (lj dj + Mj )xj,i + Mj xj,i-1)/dj, . x   j,mj  = (-lj dj xj,mj + Mj xj,mj-1 )/dj, . M   jv  = pjv Ф Х lj dj Sj++ Mj Sj- Ж Ь -mjvMjv+ dj Mj xj,mj ~ p   jv

for j, v = [`1,n], i = -[`(k_j+1,m_j-1)]. Here S_j⁺ є d_jЕ_{i = 1}^m_j x_j,i, S_j^- є d_jЕ_{i = -kj}^-1x_j,i, M^j є Е_{l = 1}ⁿ m_lj M_lj. Let e_x denote a distribution which is concentrated in a point x н R^a.

Theorem.

If X^N₀ ® e_x weakly then

(i) [(sup_{0 ё s ё t} |X^N_s-x_s(x)| P) || (® 0)] for all t Ё 0 as N®Ґ,

(ii) proceses жN(X^N_t-x_t(x)) weakly converges to a continuous process Y with independent increments and covariation function [^C](x). Here [^C](x) = Р₀^t c(x_s(x))ds and c is a matrix function which can be written in explicit form.

The results obtained allow to study some parameters of X^N_t with the help of non-linear dynamical system x_t(x).

[1] L.G. Afanassieva, G. Fayolle, S.Yu. Popov. Models for transportation networks.

---

Last modified Fri May 24 19:47:23 BST 2002