Method of elements-by-elements multicriterial composition of optimal routes in transport networks

Authors

DOI:

https://doi.org/10.20998/2079-0023.2018.22.05

Keywords:

search for optimal routes, transport task of linear programming, multicriteria, model of system based on the oriented graph, special operation commutation of matrices, additive measure set of criteria

Abstract

A simple method is proposed for finding optimal routes in the transport problem of linear programming. The task is solved using a set of criteria: the average total cost of transportation, the duration and reliability of plan. The task model is an oriented graph. The vertices of the graph correspond to intermediate points on a number of ways connecting production and consumption points. The arcs connecting the vertices of the graph are marked with numbers specifying the average cost of transporting a product unit through the route section corresponding to the arc, the average duration of transportation along this section and the probability of overcoming it. To solve the task, a measure efficiency use of plots is proposed, which has property of additivity, that is, the measure of result for combination of two sites is equal to the sum of the measures for these sections. The measure takes into account the values for all three criteria. A computational procedure is described that implements a method that does not require a combinatorial enumeration options and ensures the possibility of obtaining a compromise result quickly. The procedure is based on the use of proposed special operation for switching matrices. This operation provides the possibility calculating the effectiveness measure of all possible two-step, then three-step and further k-step paths. The operation is iteratively continued until a route measure connecting the start point to the end point is found. An important additional advantage of method is its ability to use it to find efficient routes in complex transport networks with a large number of intermediate points. In this case, if the transition from one point to another can be carried out through some intermediate point from some of their sets, then the method allows to find the best possible route. Examples of task for different formulations of multicriteria transport task are considered.

References

Intriligator М. Matematicheskie metodyi optimizatsii ekonomicheskaya teoriya [Mahematical optimization and economic theory]. Мoscow, Airis–Press Publ., 2002. 564 p.

Ventcel E. S. Issledovanie operatsiy [Operations research]. Мoscow, Vysshaya shkola Publ., 2001. 208 p.

Kuznetcov A. V.,Sakovich V. A., Holod N. I. Vyisshaya matematika. Matematicheskoe programmirovanie [Higher mathematics. Mathematical Programming]. Minsk, Vyshjejshaja shkola Publ., 2001. 351 p.

Raskin L. G. Analiz slozhnyih sistem i elementyi teorii optimalnogo upravleniya [Analysis of complex systems and elements of optimal control theory]. Мoscow, Sovetskoe radio Publ., 1979. – 344 p.

Raskin L. G. Matematicheskie metodyi issledovaniya operatsiy i analiza slozhnyih sistem vooruzheniya PVO [Mathematical methods of investigation of operations and analysis of complex air defense systems]. Kharkov, WIRTA 1988. 177 p.

Raskin L. G., Sira O. V. Nechetkaya matematika [Fuzzy Mathematics]. Kharkov, Parus Publ., 2008. 352 p.

Ehrgott M. Multicriteria Optimizahion. Springer Publ., 2005. 323 p.

Steuer R. E. Multiple Criteria Optimizahion. New York, John Wiley Publ., 1986. 546 p.

Sira O. V., Klimeko T. A.,Samorodov V. B. Vyibor kriteriya optimizatsii v zadache upravleniya mnogonomenklaturnyimi zapasami [Selection of optimization criterion in the multinomenclature inventory management problem]. Vestnik Har'kovskogo nacional'nogo avtomobil'no-dorozhnogo universiteta i Severo-Vostochnogo nauchnogo centra Transportnoj akademii Ukrainy: sb. nauch. tr. [Bulletin of the Kharkov National Automobile and Highway University and the North-Eastern Scientific Center of the Transport Academy of Ukraine: Sat. sci. tr.]. Kharkov, KhNADU Publ., 2009.Vol. 45.P. 31–34.

Zubarev V. V., Kovtunenko A. P. Raskin. L. G. Matematicheskie metodyi otsenki i prognozirovaniya tehnicheskih pokazateley ekspluatatsionnyih svoystv radiotehnicheskih sistem [Mathematical methods estimation and forecasting technical indicators of operational properties of radio engineering systems]. Кiev, NAU Publ., 2005. 184 p.

Sobol I. M., Vyibor optimalnyih parametrov v zadachah s mnogimi kriteriyami [Choice of optimal parameters in tasks with many criteria]. Мoscow, Drofa Publ., 2006. 175 p.

Pawlak Z. Rough sets. International Journal of Information and Computer Sciences. 1982, vol. 11, no. 5, p. 341–356.

Pawlak Z. Rough Sets approach to knowledge–based decision support. European Journal of Operational Research. 1997, vol. 99. no. 1, p. 48–57.

Slowinski R., Vanderpooten D. A generalized definition of rough approximations based on similarity. IEEE Transactions on Knowledge and data Engineering. 2000, vol. 12, no. 2, p. 331–336.

Alefeld G., Herzberger, J. Introduction to Interval Computations. New York, Academic Press Publ., 1983. 352 р.

Hansen E. Global Optimization Using Interval Analysis. New York, Marcel Dekker Publ., 1992. 230 р.

Zadeh L. A. Fuzzy sets as a basis for a theory of possibility. Fuzzy Sets and Systems. 1978, vol. 1, p. 3–28.

Kaufman A., Gupta M. Introduction to Fuzzy Arithmetic: Theory and Applications. New York, VN Reinhold Publ., 1985. 334 p.

Dubois D., Prade H. Possibility Theory: an Approach to Computerized Processing of Uncertainty. New York, Plenum Press Publ., 1988. 263 p. (Rus. ed.: Dubois D., Prade H. Teoryia vozmozhnostei. Prylozhenye k predstavlenyiuznanyi v ynformatyke. Moscow, Radyo i sviaz Publ., 1990. 286 p.).

Liu B., Zhao B. Stochastic Programming and Fuzzy Programming. Beijing, Tsinghua University Press Publ., 1998. 312 p.

Raskin L., Sira O. Method of solving fuzzy problems of mathematical programming. Eastern–european journal of enterprise technologies. 2016, vol 5, no. 4 (83), p. 23–28.

Raskin L., Sira O. Fuzzy models of rough mathematics. Eastern– European Journal of Enterprise Technologies. 2016, vol. 6, issue 4, p. 53–60.

How to Cite

Raskin, L., Sira, O., & Parfeniuk, Y. (2018). Method of elements-by-elements multicriterial composition of optimal routes in transport networks. Bulletin of National Technical University "KhPI". Series: System Analysis, Control and Information Technologies, (22), 27–36. https://doi.org/10.20998/2079-0023.2018.22.05

Issue

Section

SYSTEM ANALYSIS AND DECISION-MAKING THEORY