# Mathematical Models Concerning Location of Vehicular Gas-Filling Stations within Cities

A.P Kuznetsov

► To cite this version:

A.P Kuznetsov. Mathematical Models Concerning Location of Vehicular Gas-Filling Stations within Cities. Mechanics, Materials Science & Engineering Journal, 2017, 7, 10.2412/mmse.52.18.599. hal-01508584

HAL Id: hal-01508584

https://hal.science/hal-01508584

Submitted on 14 Apr 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Mathematical Models Concerning Location of Vehicular Gas-Filling Stations within Cities

Kuznetsov A.P.¹,ª

1. Department of Transport Management, National Mining University, Dnipro, Ukraine

a. taran_70@mail.ru

<figure><img src="image_2.png" /></figure>

DOI 10.2412/mmse.52.18.599

**Keywords:** optimality criterion, location, NGV-RCS, distribution of vehicle flows, modelling, vehicle flow.

**ABSTRACT.** The optimal criterion concerning NGV-RCSs locations in the cities and the mathematical model of vehicle flow distribution on the road network of cities were analysed. It has been determined that optimization of NGV-RCS locations is a multi-criterion problem having no definite solution. The criterion for solving the problem can be the number of vehicle flows within street and road network which requires solving the problem of forecast; in turn, the forecasting problem consists of two subproblems – formation of vehicle flows and optimization of vehicle flow distribution within street and road network. The problems are of NP type; moreover, there are no algorithms making it possible to obtain accurate solutions.

**Introduction.** All known concepts of transport and road system of the world cities involve the improvement of ecological and sanitary and epidemiological conditions at the expense of solving both ecological and energy problems.

Implementations of the measures are complicated due to scientific difficulties connected with uncertainty of effect by components of transport systems; among other things that concerns the effect of location of NGV-filling compressor stations (NGV-RCSs) on the efficiency of transport systems and extraordinary labour intensity in the process of the parameters determination in the context of available street and road networks.

Thus, solving the problem of the improvement of efficiency of transport systems of cities at the expense of decrease in environmental pollution and reduction in the above fuel consumption reduction in terms of commercial success of projects concerning modernization of transport systems of cities is important practical task. The problem can be solved providing that important problem connected with formation of automobile transport infrastructure in cities is solved.

**Statement of the problem.** Both theory and practice of automobile transport infrastructure formation in cities pays much attention to determination of rational quantity and location of car services, gasoline stations, and NGV-filling compressor stations (NGV-RCSs). In this context, opinions of researchers as for parameters concerning estimation of alternatives and ways to solve the problem vary.

The problem concerning optimization of development decisions and transport infrastructure location within territory of a city was analysed intensely both in Ukraine and abroad. In the context of automobile transport, the following may be listed as principal directions in the field: the development of street and road network and components of transport infrastructure (all types of filling stations, car services, garages etc.).

**Analysis of the research and publications.** Studies belonging to the latter tendency may be divided into two large groups. One part of them concerns the optimization of the capacity of components of transport infrastructure; another one concerns their optimum location. Both tendencies involve all the aspects of transport infrastructure organization. However, their main
disadvantage is the fact that while focusing on current situation and state of transport system they do not involve prospects of its development and possibilities of the problem comprehensive solution.

Thus, papers [1, 2] propose mathematical models and approaches based upon queuing theory for one car service or gasoline station. In this context, such optimization is aimed at minimization of cumulative expenditures resulting from idle time of equipment and idle time of transport in terms of isolated component of transport infrastructure. Such an approach cannot be applied to optimize transport system on the whole.

Solution of the problems of optimum location of transport infrastructure components proposes models based upon the assumption concerning uniform distribution of transport means over region territory [3, 4, 5]. Despite the fact that the models take into consideration rather wide range of factors, the assumption diminishes greatly the accuracy of forecast models as it does not correspond to real conditions. The fact is taken into account by many researches [6, 7, 8]. In [3, 10, 11, 9, 12] papers, authors, recognizing the necessity to consider both temporary and spatial irregularity of transport flows, propose various forecast models to distribute transport flows within street and road network – entropy models [3, 9] and kinematic ones [10, 11, 12].

However, the models describe a process of traffic without taking into consideration the traffic process goal, i.e. without taking into account the requirements or tasks of a driver. That is why the proposed models are characterized by large errors; as a result, they could not find their practical use.

**Solving the problem.** The paper considers substantiation of optimality criterion to locate NGV-RCSs in cities and mathematical model to distribute traffic flows within street and road network of cities. Selection of location areas for NGV-RCSs involves time consuming multicriteria problem to optimize their location. Solution of the problem should involve: first, provision of maximum attractiveness of NGV-RCSs for potential clients; second, provision of minimum additional environmental load on a city resulting from distance to gas stations; third, minimization of negative effect of NGV-RCSs availability on urban matrix; fourth, provision of maximum efficiency of the NGV-RCS performance. The two former requirements come into conflict with the two latter ones as they need as many NGV-RCSs as possible to be located within the city area while the third requirement is to minimize their quantity, and the last one needs partial decision making.

In this context, it is required to take into consideration criteria factors of NGV-RCSs location relative to available objects of municipal infrastructure – garages, industrial enterprises, traffic centers, points where passenger traffic flows are formed and those where they are merged, car services, and gas stations. In the context of the problem all factors as well as criteria ratios may be united into the four large groups: ecological, environmental, technical, and technological. Efficiency criterion to develop a project for NGV-RCSs construction as well as value of one or another location area for NGV-RCSs is specific efficiency for marketing of 1 cubic meter of methane being calculated as follows

$$E = \frac{C - S_M - H}{S_M}, \qquad (1)$$

where C – is prime cost of 1 cubic meter of methane, UAH/cubic meter;

S_M – is production cost of 1 cubic meter of methane, UAH/cubic meter;

H – is tax amount (value added tax, profit tax, land tax) in terms of 1 cubic meter of methane, UAH/cubic meter;

Production cost for filling with 1 cubic meter of methane is calculated by the formula
$$S_M = S_{en} + S_{ekspl} + 3 + A + S_b \quad (2)$$

where $S_{en}$ – are expenses connected with electric power consumption, UAH/cubic meter;

$S_{ekspl}$ – are expenses connected with day-to-day operation of equipment, UAH/cubic meter;

3 – are wages of operating personnel, UAH/cubic meter;

A – is amortization of fixed assets, UAH/cubic meter;

$S_b$ – is input NGV-RCS price, UAH/cubic meter.

Determination of specific values of components of production cost and assessment of the designs are possible when suppliers of the equipment for NGV-RCS are regulated.

As for the question two (that is mathematical model to distribute automobile traffic flows within street and road network being analyzed in the paper) the description of the problem concerning distribution of automobile traffic flows in the context of cities is as follows.

There is unoriented $G(N, P)$ network with a set of $N, n = |N|$ nodes and a set of $P, p = |P|$ arcs where integer matrix $A = \|a_{ij}\| n \times n$ of single traffic flows is specified. Flows $a_{ij}$ are subject to single transfer from $i$ sources into $j$, $(i,j = 1...n)$ in certain transportation blocks of internodal connections. The connections addressed to various acceptors should be transferred within the network in general transportation blocks on a periodic predetermined base. Following values are known: block capacity $w \gg a_{ij}$ set with the help of the number of flow units being housed in it and timeframe of the flows departure.

It is required to minimize a functional

$$F = \sum_{i,j \in S} f_{ij}(u_{ij}, d_{ij}) + \sum_{i=1}^{n} f_i(x_i, q_i) + \sum_{i=1}^{n} \varphi_i(u_i) \quad (3)$$

Under following limitations:

$$t_{ij} \le T_{ij}, \text{ for all } i,j \in S; \quad (4)$$

$$x_i \le h_i, \quad i = 1...n, \quad (5)$$

Where

$$x_i = \sum_{j=1}^{n} (x_{ij} + x_{ji}) \quad (6)$$

$$q_i = \sum_{j=1}^{n} \delta_{ij}; i = 1..n; \delta_{ij} = \begin{cases} 1, & \text{if } u_{ij} \neq 0; \\ 0, & \text{if } u_{ij} = 0; \end{cases} \quad (7)$$

$$u_i = \sum_{j=1}^{n} (u_{ij} + u_{ji}); \quad i = 1...n, \quad (8)$$

$S$ – is a set of ordered pairs of flow indices determined on Cartesian product $nxn$;
$u_{ij} = \left[ \frac{x_{ij}}{w} \right]$ – is a flow of transportation blocks from i to j (first all $x_{ij}$ are equal to $a_{ij}$);

$d_{ij}$ – is distance between nodes i and j;

$f_{ij}$, $f_i$, $\phi_i$ – are certain linear as well as non-convex expenditure functions to transfer flows and process them processing in general case;

$t_{ij}$, $T_{ij}$ – are estimated time and predetermined time to transfer single flows from i to j;

$h_i$ – is capacity of i-th node.

The formulated problem belongs to a class of combinatorial optimization problems being NP-complete. Thus, to solve it approximation method based upon a scheme of sequential analysis of variants and a series of heuristic algorithms are used. Development of the heuristic algorithms is substantiated by the fact that it is rather difficult to determine $f_{ij}$, $f_i$, $\phi_i$ functions for real communication networks though the functions characterize expenditures connected with flow processing and transferring adequately.

However, the problem definition dismisses a possibility for a driver to select traffic route freely, which deforms real traffic operations within street and road network. Thus, the problem should be completed in terms of distribution of traffic flows within real street and road network. A process of the problem solving assumes that any driver selecting traffic route acts in such a way to provide maximum traffic efficiency under the current conditions.

That is why it is required to solve a problem concerning optimum distribution of automobile traffics within street and road network being as follows.

It is necessary to minimize the functional

$$F = \sum_{k=1}^{l} f_k \left( \left( \sum_{\eta, \xi \in q_k} \sum_{i, j \in S} x_{ij,k}^{\eta, \xi} \right), d_k \right) + \sum_{\beta=1}^{n} \phi_{\beta} \left( \sum_{\alpha=1}^{n} \sum_{k=1}^{l} \sum_{i, j \in S} (y_{ij,k}^{\alpha, \beta} + y_{ij,k}^{\beta, \alpha}) \right), \quad (9)$$

under the limitations

$$\sum_{\beta=1}^{n} \sum_{k=1}^{l} y_{ij,k}^{\alpha, \beta} - \sum_{\beta=1}^{n} \sum_{k=1}^{l} y_{ji,k}^{\alpha, \beta} = \begin{cases} a_{ij}, & \text{if } i = \alpha; \\ 0, & \text{if } i \neq \alpha, j \neq \alpha; \\ -a_{ij}, & \text{if } j = \alpha; \end{cases} \quad (10)$$

$\alpha = 1..n, i, j \in S,$

$$\sum_{\alpha=1}^{n} \sum_{k=1}^{l} \sum_{i, j \in S} (y_{ij,k}^{\alpha, \beta} + y_{ij,k}^{\beta, \alpha}) - \sum_{j=1}^{n} a_{\beta j} - \sum_{j=1}^{n} a_{j \beta} \le 2b_{\beta}; \beta = 1..n, \quad (11)$$

$$\sum_{i, j \in S} x_{ij,k}^{\eta, \xi} \le W^k \quad \text{for all } \eta, \xi \in q_k, k = 1..l, \quad (12)$$
$$ (\sum_{\beta=1}^{n} \sum_{i,j \in S} (y_{ij,k}^{\alpha\beta} + y_{ji,k}^{\beta\alpha})) \cdot t^o \leq t_{\alpha}^k, \alpha \in v_k, k = 1..l, \quad (13) $$

$$ t_{ij} \leq T_{ij}, i, j \in S, \quad (14) $$

$$ y_{ij,k}^{\alpha\beta} \in \square, x_{ij,k}^{\eta\xi} \in \square. \quad (15) $$

Nomenclature for expressions (9) – (15):

$\{m_k\}, k = 1..l$ – is a set of routs of vehicles or communication channels; each of them consists of sequence of nodes and topological arcs of GM network uniting starting node and final node of route or communication channel;

GM(N, PM) – is a route network where N is a set of the network nodes, PM is a set of its oriented route arcs (route arc is available between any i and j nodes of GM network if at least one route of vehicle connects them with $\{mk\}$);

$A = \|a_{ij}\| n \times n$ – is a matrix of flows of transportation communications;

$B = \|b_i\|, i = 1..n$ – is a vector of capacities of nodes as for transit flows processing;

$y_{ij,k}^{\alpha\beta}$ – is a flow in $p_{\alpha\beta} \in P$ arc obtained from $m_k$ route ($y_{ij,k}^{\alpha\beta}$ determine arc flows within route network $G_M$);

$x_{ij,k}^{\eta\xi}$ – is a flow in topological arc $p_{\eta\xi} \in P$ within $m_k$ route;

$q_k$ – is ordered set of arcs consisting of P making $m_k$ route;

$v_k$ – is ordered set of nodes consisting of N within $m_k$ route;

$$ \varphi: y_{ij,k}^{\alpha\beta} \rightarrow \{x_{ij,k}^{\eta\xi}\}, p_{\alpha\beta} \in P_M, p_{\eta\xi} \in P, i, j \in S, k = 1..l, $$

where $\varphi$ – is certain operator reflecting a flow in route arc per corresponding subset of topological arcs;

$f_k$ – is piecewise and convex function determining dependence of expenditures on the number of transportation blocks transferred along $m_k$ route and the route distance $d_k$;

$\varphi_{\beta}$ – is nonlinear function of expenses connected with processing of transportation blocks within $\beta$ node;

$W^k$ – is the capacity of $m_k$ route;

$t^o$ – is the time required to transfer one block of;

$t_{\alpha}^k$ – is limitation of vehicle waiting period within $m_k$ route $\alpha$ node;

$t_{ij}, T_{ij}$ – is calculated and predetermined time to transfer blocks of vehicles from i to j.

Conditions (10) provide flow continuity and (11) – (14) are node capacity limitations, route traffic capacities, time for recommutation of transit blocks of vehicles within all the nodes of each route.

The formulated problem belongs to the class of discrete multiflow problems with nonlinear and nonconvex functional. The problems of the type are NP-complete and to solve it accurate
polynomially limited in terms of labour intensity algorithms are unknown. In this connection the paper proposes following heuristic algorithm.

In the context of the model of street and road network (Fig.1) expert method is applied to determine main (flow-forming and flow-merging) nodes subjecting to obligatory analysis (they are represented as forms with solid contour line).

They are sure to include peripheral crossroads along main roads where city ingresses/egresses are located.

For the determination total number of such nodes is assumed as one node per 40-50 thousand residents.

Within the points, visual technique is applied during rush hours to determine intensity of traffic flow, its components, and traffic directions. After observation data processing total traffic flows entering each node are capacities of nodes in terms of arrival and total traffic flows leaving each node are capacities of nodes in terms of departure.

To predict the values of traffic flows within the areas of street and road network being out of observation, gravitational model is used. The model is based upon following hypothesis [13]

$$b_{ij} = k \cdot HO_i \cdot HP_j \cdot f(C_{ij}), \quad (1)$$

where $b_{ij}$ – are ideal communications between districts;

$HO_i$ – is the number of vehicles leaving the i district;

$HP_j$ – is the number of vehicles arriving to j district;

$f(C_{ij})$ – is a certain function of total expenditures by passengers to move from district i to district j;

$k$ – is a certain constant.

Ratio (16) should be carried out together with following limitations

$$\sum_{j=1}^{n} b_{ij} = HO_{i}, \quad (17)$$

$$\sum_{i=1}^{n} b_{ij} = HP_{j} \quad (18)$$

where $n$ – is the number of districts.

Standard gravitational model can be expressed mathematically as follows [13]

$$h_{ij} = \frac{HO_{i} \cdot HP_{j} \cdot k_{j} \cdot d_{ij}}{\sum_{j=1}^{n} (HP_{j} \cdot k_{j} \cdot d_{ij})}, \quad (19)$$

where $h_{ij}$ – are communications between areas i and j districts;

$HO_i$ – is the capacity of i area in terms of departure;
$HP_j$ – is the capacity of j area in terms of arrival;

$k_j$ – is the coefficient leveling attraction of travels into j district;

$d_{ij}$ – is the attraction function between i and j districts;

n – is the number of districts;

i – is the number of district where travels originate.

<figure><img src="image_3.png" /><figcaption>Fig.1. Physical model of street and road network.</figcaption></figure>

Iteration technique is used to calculate correspondence matrix. After each iteration, leveling attraction coefficient is calculated by the formula

$$k_{jk} = \frac{HP_{jk}}{\sum_{j=1}^{n} h_{ij}} \qquad (20)$$

To calculate interchange travels between the areas, each iteration equation of gravitational model with the use of levelled attraction coefficients obtained at the stage of previous iteration.

Thus, the model equation becomes as follows

$$h_{ijk} = \frac{HO_i \cdot HP_{jk} \cdot k_{jk} \cdot d_{ij}}{\sum_{j=1}^{n} HP_{jk} \cdot k_{jk} \cdot d_{ij}} \qquad (21)$$
where $h_{ijk}$ is correspondence between i and j districts in terms of iteration k.

Calculations are performed until following condition is met

$$ \sum_{i=1}^{n} h_{ij} = HP_{j}. \qquad (22) $$

Then the obtained correspondences are “conducted” through street and road network according to the shortest routes which lays of line cross in transit way those points where observations have not taken place. In this context, total value of input transit traffic flows is that very target vehicle density making it possible to forecast operation intensity of NGV-RCSs.

**Summary.** The research performed made it possible to determine following regularities:

1. A problem concerning optimization of NGV-RCSs location is a multicriteria one having no single-valued solution.

2. Intensity of vehicle flows within street and road network can be taken as the integral criterion to solve the problem; that involves solving a problem of the parameter forecasting.

3. The problem concerning vehicle flows intensity forecasting within road and street network consists of two subproblems – formation of vehicle flows and optimization of vehicle flows distribution within road and street network. The both problems are NP-complete and there are no algorithms to find accurate solutions for them.

4. To forecast vehicle flows, heuristic algorithm was proposed. The algorithm is based upon gravitational model providing calculation with such accurateness meeting the requirements in the process of practical problem solving.

5. To initialize output data in the process of the algorithm implementation, field studies are required within street and road city network with the use of basic observation stations.

## References

[1] Govorushchenko N. Ya. System technique to design transport machines / N. Ya. Govorushchenko, A. N. Turenko. – Kharkov, KhNASU, 2004. – 206 pp.

[2] Semionov V. V. Mathematical methods for transport flows modeling // Non-linear world. – 2005. – #6. – Pp. 48–52.

[3] Lobanov E.M. Problems of imitation modeling of transport flows movement within street and road city networks and highway system / E.M. Lobanov // Theoretical and practical problems of automobile and road system development in Russia. – Moscow: MTUSI, 2006. – Pp. 4–7.

[4] Shvetsov V.I. Mathematical modeling of transport flows / V.I. Shvetsov // Automation and telemechanics. – 2003. – #11. – Pp. 41–48.

[5] Smirnov N.N. Mathematical modeling of transport flows / N. N. Smirnov, A. B. Kiseliov, V. F. Nikitin. – Moscow, MSU, 1999. – Pp. 39–47.

[6] Chowdhury D. Statistical physics of vehicular traffic and some related systems / Chowdhury D., Santen L., Schadschneider A. // Physical Reports. – 2000. – Vol. 329. – P. 199–329.

[7] Cremer M. A fast simulation model for traffic flow on the basis of Boolean operations / Cremer M., Ludwig J. // Mathematical Computing Simulation. – 1986. – Vol. 28. – P. 297–303.

[8] Binder P.M. Stochastic model of car routing / Binder P.M., Paczuski M., Barma M. // Physical Review. – 1997. – Vol. 49. – P. 1174.

[9] Daganzo C.F. Remarks on Traffic Flow Modelling and its Applications / Daganzo C.F. //
Berkeley: Department of Civil and Environmental Engineering University of California. – 2001. – 489 p.

[10] Nagel K. Still flowing: Approaches to traffic flow and traffic jam modeling / Nagel K., Wagner R., Woesler R.: Grow Hill, 2003. – 317 p.

[11] Holland J.F. Adaptation in natural and artificial systems. An introductory analysis with application in biology, control and artificial intelligence / Holland J.F. – London: Bradford book edition, 1994. – 211 p.

[12] Kolesov V.I. Dynamic characteristics of uniform transport flow / V. I. Kolesov, S. P. Kolesnikov, G. V. Kolesov // Transport problems of West-Siberian gas and oil producing complex: Interuniversity collection of scientific papers. – Tyumen, Vector Buk, 2002. – Pp. 130–136.

[13] Spirin I.V Management and control of passenger vehicle transportation. / I.V.Spirin. – Moscow, Akademia, 2014. – 400 pp.