Decision-Making Models in the Problem of Building a Minimum Cost Road System
, Evgenia S. Kogan1, - DOI
- 10.2991/aebmr.k.220208.073How to use a DOI?
- Keywords
- minimal spanning tree; weighted complete graph; graph with random weights; decisive rules; the game with nature
- Abstract
The article proposes methods for solving the problem of building a system of roads of minimum cost in the case when the costs of constructing roads are random variables. Earlier in the scientific literature, the issues of estimating the probabilistic characteristics (of such problems as, for example, the average weight of the edge of the minimal spanning graph), or the asymptotics of numerical characteristics were discussed. The authors of this article have set a goal that is to find the decision rules that can be used to implement the construction of a road system in practice since the totality of the results of previous studies does not allow us to eliminate the uncertainty in choosing a specific solution that is applicable in practice. The present article examines the cases when the distribution of the cost of constructing roads is discrete (in general) or continuous (using the example of three towns and independent and uniform distribution of the costs of building roads). In the discrete case, the authors propose decision-making methods in the form of the most probable minimum spanning tree, or a tree that maximizes the expected utility or minimizes the expected risk in the game with nature, associated with the original problem. In the continuous case, the authors consider an analytical approach (in situations with a small number of towns), which can be used to find the probability distribution on the set of minimum spanning trees, as well as a solution method based on the transition to the average values of the construction costs for each road. If there are a large number of towns, it is advantageous to use numerical approximations that is replacing a continuous distribution with a discrete one, or computational experiments in which the values of the cost of constructing roads are generated according to the given distributions, and then the resulting array of values is statistically processed.
- Copyright
- © 2022 The Authors. Published by Atlantis Press International B.V.
- Open Access
- This is an open access article under the CC BY-NC license.
Cite this article
TY - CONF AU - Anatoly A. Zabelin AU - Evgenia S. Kogan PY - 2022 DA - 2022/02/25 TI - Decision-Making Models in the Problem of Building a Minimum Cost Road System BT - Proceedings of the International Scientific and Practical Conference Strategy of Development of Regional Ecosystems “Education-Science-Industry” (ISPCR 2021) PB - Atlantis Press SP - 515 EP - 520 SN - 2352-5428 UR - https://doi.org/10.2991/aebmr.k.220208.073 DO - 10.2991/aebmr.k.220208.073 ID - Zabelin2022 ER -