The article is devoted to the analysis of input data of a two-factor multivariate transport problem with weighting factors. The article aims to develop and describe an algorithm for bringing this problem to a form suitable for the application of one of the existing methods of solving the classical transport problem. The developed algorithm should be such that it can be relatively easily programmed in one of the existing programming languages. The input data for the development of the algorithm is the presence of two independent optimization criteria; different values of weighting factors of two factors for each pair "supplierconsumer"; a different number of options for transportation of goods for each pair "supplierconsumer" with the corresponding values of both factors. According to the goal, the algorithm must choose the objectively best of several options for transportation of goods for each pair "supplier-consumer", taking into account the two-factor and the presence of weights. The issues related to the choice of the best of the options for transportation of goods for a single pair "supplier-consumer" taking into account the weight coefficients are considered on the examples. An analysis of the influence of the values of the factors of one pair "supplier-consumer" on the resulting criteria of other pairs. Developed an algorithm for bringing the initial data to a single numerical range, calculating the resulting criteria, and determining the best transportation option for each pair "supplier-consumer".
The value of r and will be the resulting criterion, and the corresponding transportation option - the best of the proposed.
In real conditions, different suppliers and different consumers may have different priorities when transporting goods: someone needs to receive the goods as quickly as possible, someone needs to minimize the cost of transportation, someone is looking for a balanced solution, etc. Thus, there is a need to vary the "weight" of factors for each pair "supplier-consumer" within one transport task.
Assuming the presence of weight coefficients for each of the factors (kc, kt), there is a problem of choosing an objectively better option from the proposed for each pair of "supplier-consumer". Note that for each variant of a certain pair "supplier-consumer" weight coefficients are constant values.
Taking into account the weight coefficients, formula 1 takes the following form:
r minc1 kc t1 kt ; c2 kc t2 kt ; c3 kc t3 kt (
r kc kt minc1 t1; c2 t2 ; c3 t3 (
From formula 3 it can be seen that the resulting best option is still chosen as the minimum of three pair wise products of the values of factors C and T. The weight coefficients only equally increase each of the products in kc×kt times and in no way affect the choice of the best option. This method eliminates the very essence of weight coefficients as levers of influence when choosing the best option.
Simple pairwise multiplication of the values of the factors and their weight coefficients with the subsequent choice of the smallest of the obtained values does not allow to choose the objectively best of the proposed options.
Nowadays mathematical methods solve many problems of operational planning for transportation. Many scientists dedicate their work to the topic of transport optimization.
Chyzhmotria O. et al. [4] on an example considered the problems connected with the search of the optimum plan of transportations simultaneously on two quality criteria. They conducted a comparative analysis of the four transportation plans according to the condition of the example.
Burduk A., Musial K. [2; 3] solved the problem of optimization using genetic algorithms. They described genetic algorithms, their properties, and their capabilities in solving computational problems. To solve the problem under study, the authors used the program MATLAB.
Prifti V. et al. [6] considered a real problem of linear programming in detail by taking an example in an Albania company. For the company under consideration the problem of minimizing transportation costs was solved by solving 3 methods: The North West Corner Method, the Least Cost Method, and the Vogel's Approximation Method. The calculations showed that based on the demand from the 9 geographical sites (destinations) and the capacity offered by the two manufacturing plants (sources), the most optimal solution turns out to be the one obtained by Vogel's method.
Sun Y. et al. [8] in their study presented a systematic review of the problem of planning route transportation of goods in a multimodal transport network. In this study, the formulation characteristics are divided and classified into six aspects, and optimization models in recent studies are determined based on the respective formulation characteristics.
Gunantara N. [5] in his work considered two methods of multi-objective optimization (MOO) that do not require complicated mathematical equations. These two methods are Pareto and scalarization.
In the article by Zhang Y. et al. [10] an optimization method for multiple batches of express freight demands is proposed for the shippers of railway express freight to select the most suitable transportation products to transport, considering the priority of shippers and capacity constraints. Five transport attributes, the most common concerns of express freight shippers, including freight transit time, transport cost, convenience, safety, and reliability, are selected as main indexes. Furthermore, a solution algorithm is designed by considering important clients who prioritize choosing transportation products.
Badica A. et al. [1] proposed a method for declarative modeling and optimization of freight transportation brokering using agents and constraint logic programming.
Stoilova S. [7] in her study proposed a step-by-step approach to determining the transport plan of passenger trains. In the first step, criteria for optimizing the transport plan were defined. In the second stage, variants of the transport plan were formulated. In the third stage, the weight coefficients of the criteria were determined. Multi-purpose optimization was performed in the fourth step. The impact of changes in passenger traffic on the choice of the optimal transport plan was studied in the fifth stage.
In the article of the authors Zabolotnii S. and Mogilei S. [9] a study of existing methods for constructing support plans for the transportation problem with several means of cargo delivery is conducted, and the task itself is defined as multimodal. Based on the criterion of reducing the number of numerous iterations in finding solutions to such a problem, a more perfect method of constructing its support plans, the so-called Steiner method, is proposed. And also a general formulation of the multimodal transport problem is implemented - its objective function (criterion) of optimization and an admissible set of solutions are formalized.
The article aims to develop and describe an algorithm for bringing this problem to a form suitable for the application of one of the existing methods of solving the classical transport problem. The developed algorithm should be such that it can be relatively easily programmed in one of the existing programming languages.
Consider and analyze the following method of choosing the best option, taking into account the weight coefficients kc and kt. The essence of the method will be to add the values of the two factors C and T, multiplied by the corresponding weight coefficients.
The following example 1 should provide an answer as to the feasibility or inadmissibility of this method. The input data will be the values of the factorsc1 = 900, c2 = 850, t1 = 1, t2 = 5.In example 1, we will deal with two options for transporting goods from point A to point B. The weight coefficients will change in the range from 0 to 1 in steps of 0.1. The sum of the coefficients will always be equal to 1.
The best option for transportation and the value of the resulting criterion will be sought by
the formula:
r minc1 kc t1 kt ; c2 kc t2 kt
(
The results of the calculations are summarized in table 1:
Calculation of values and selection of the resulting criterion 900 850 r2 810,1 765,5 r2 720,2 681 r2 630,3 596,5 r2 540,4 512 r2 450,5 427,5 r2 360,6 343 r2 270,7 258,5 r2 180,8 174 r2 90,9 89,5 r2
1 5 r1
Let us analyze the data in Table 1, according to which it is seen that with a decrease in the influence of factor C and a corresponding increase in the influence of factor T, the difference between the values of the resulting criteria r1 and r2 decreases. But even when the weight of the factor T acquires a conditional 90% (kt = 0.9), still the smaller of the two values of the resulting criterion remains r2. And this even though under the condition of the example, the value of t2 is five times greater than the value of t1. This result can be considered distorted and biased, and the method of adding the values of the two factors C and T multiplied by the corresponding weight coefficients should be considered unacceptable as such.
It should be noted that in this example we were dealing with two different numerical ranges, one of which was hundreds of times larger than the other. From the very beginning of the calculations, this range of values dominated and, accordingly, the corresponding factor dominated. This had a direct impact on the value of the resulting criterion and the choice of the best freight option. Even the use of weight coefficients could not significantly affect the final result. The difference in the values of the two ranges was so great that the weight coefficients could not perform their direct function in terms of influencing the choice of the best option, for which they were generally introduced into the mathematical model. Thus, the reason for the biased results was a large difference in the values of the numerical ranges of the two factors. It can also be argued that even a small difference can also negatively affect the objectivity of the result.
In this study, we consider an algorithm that will get rid of the distortion of the results due to the difference in the values of the two numerical ranges. The essence of the algorithm will first be represented schematically: Figure 1: Scheme of the algorithm for bringing data to a single numerical range
At the first stage of the algorithm, it is necessary to determine the largest value for each factor.
For factor C:
cmax maxc1, c2 ,, cm
(
cmax tmax
where GCD is the greatest common divisor.
To find the largest common divisor, as an option, you can use the well-known Euclidean algorithm. The algorithm contains a loop with a premise and several branches and can be easily programmed.
It should be noted that at the beginning of the Euclidean algorithm, all input data must be integers, so, if necessary, it is necessary to simultaneously increase the input data by 10n times.
In the third stage, additional factors are determined for each of the factors.
For factor C:
cam LCM cmax ,tmax cmax
tam LCM cmax , tmax tmax
(
tmax maxt1,t2 ,,tm
When programming to find the maximum value, as in the case of finding the minimum value, use arrays, cyclic structures with a precondition or postcondition, and branching structures.
In the second stage of the algorithm, it is necessary to calculate the least common multiple (LCM) for the values
For factor T:
In the last, fourth stage, each value of each of the factors must be multiplied by the corresponding additional factor (cam or tam, respectively).
At the end of the algorithm, you can proceed to search by formula 4 the value of the resulting criterion and choose the best option.
Let's return to the above example 1. The input data in the example were the values of the factors c1 = 900, c2 = 850, t1 = 1, t2 = 5.
According to the algorithm for bringing data to a single numerical range (see Fig. 1) step by step
we get:
cmax = max{900, 850} = 900, tmax = max{1, 5} = 5.
LCM(cmax,tmax) = LCM(
tam = LCM(cmax,tmax) / tmax = 900 / 5 = 180. c1'= c1×cam =900× 1 = 900; c2' = c2×cam = 850× 1 = 850; t1' = t1×tam =1× 180 = 180; t2' = t2×tam =5× 180 = 900.
The value of the resulting criterion and the best option for transportation will be sought by formula 4. The weight coefficients will be changed in the range from 0 to 1 in steps of 0.1.
The results of the calculations are summarized in table2:
The results shown in table 2 are radically different from the results in table 1. From table 2 we see that after reducing the initial data to a single numerical range, even the minimum effect of factor T (kt = 0.1 or 10%) was sufficient to the resulting criterion was the criterion r1 '. This choice is logical, because the factor T in its values differs from the minimum to the maximum 5 times, while the factor C - only 1.06 times. Accordingly, the effect of factor C should be minimal. At the same time, it is the T factor that should play a key role in choosing the best transportation options, as demonstrated by the proposed algorithm.
The resulting criterion r' will thus participate in the further solution of the two-factor transport problem. r1' = c1'×kc+t1'×kt r2' = c2'×kc+t2'×kt
To analyze the possible influence of factor values of one pair "supplier-consumer" on the resulting criteria of other pairs and to address the issue of different numerical ranges of factor values for different pairs "supplier-consumer" it will suffice to use two pairs "supplier-consumer" (in our example pairs A1-B3 and A3-B2). The same two pairs "supplier-consumer" will develop an algorithm for bringing a two-factor multivariate transport problem with weight coefficients to a unified form, suitable for the application of one of the existing methods of solving problems of the corresponding type.
It will be recalled that before that it was a question of transportation of cargo from supplier A to consumer B. However, the transport task assumes the presence of m departure points A1, A2, ..., Am and n consumers B1, B2, ..., Bn. For each pair "supplier-consumer" within the research topic, the variability of the values of each of the two factors is allowed. Also, each pair "supplier-consumer" for the problem may have different values of weights for these factors. Thus, there is a task of developing an algorithm for bringing a two-factor multivariate transport problem with weight coefficients to a unified form, suitable for the application of one of the existing methods for solving problems of the corresponding type. Separate questions are the possible influence of factor values of one "supplierconsumer" pair on the resulting criteria of other pairs and the probable different numerical ranges of factor values for different "supplier-consumer" pairs.
For further analysis and development of the algorithm as example 2 consider a fragment of a twofactor multivariate transport problem, given in the tabular form:
To begin with, we determine the best transportation option and the value of the resulting criterion separately for each pair A1-B3 and A3-B2. To do this, we use formula 4 and the algorithm for bringing data to a single numerical range (see Fig. 1, formulas 5-9).
For the A1-B3 pair we have two options for cargo transportation. According to the algorithm step
by step we get:
c13max = max{15, 10} = 15, t13max = max{6, 9} = 9.
LCM(c13max,t13max) = LCM(
For the pair A3-B2 we have four options for cargo transportation. According to the algorithm step
by step we get:
c32max = max{4, 5, 2, 3} = 5, t32max = max{6,5, 13, 9} = 13.
LCM(c32max,t32max) = LCM(
For both pairs A1-B3 and A3-B2, the algorithm for calculating the value of the resulting criterion and finding the best option yielded results. They can be considered objective, but only separately for each couple. If we analyze and compare the calculations for both pairs, we see that the values of the factors in these pairs were in different numerical ranges. For the pair A1-B3, the numerical range with the largest value of 45 was obtained, and for the pair A3-B2, the numerical range with the largest value of 65 was obtained. The case with different numerical ranges has already been considered and described above. It has also been concluded that it is inadmissible to use the obtained values in this form for further calculations.
To solve this problem in the study it is proposed to combine the values of each of the factors of all options from both pairs "supplier-consumer" of the current problem. This option is perfectly acceptable, because under the condition of the transport problem, the load is homogeneous, and the factors together with the units of measurement are the same for all pairs of "supplier-consumer" of the current problem. In this case, the algorithm for bringing data to a single numerical range, shown in Fig. 1, remains unchanged. Also, we have the opportunity to identify and analyze the possible influence of the values of the factors of one pair "supplier-consumer" on the resulting criteria of other pairs.
For the current example, after performing the first three steps of the algorithm, we obtain: cmax = max{15, 10, 4, 5, 2, 3} = 15,
tmax = max{6, 9, 6, 5, 13, 9} = 13; LCM(cmax,tmax) = LCM(15, 13) = 195; cam = LCM(cmax,tmax) / cmax = 195 / 15 = 13;
tam = LCM(cmax,tmax) / tmax = 195 / 13 = 15.
For pair A1-B3 the fourth step of the algorithm: c131'= c131×cam = 15 × 13 = 195;
c132' = c132×cam = 10× 13 = 130; t131' = t131×tam = 6 × 15 = 90; t132' = t132×tam = 9 × 15 = 135.
For the pair A3-B2, the fourth step of the algorithm:
Adjusted calculation of values and selection of the resulting criterion for the pair A1‐B3
Adjusted calculation of values and selection of the resulting criterion for the pair A3‐B2 Let's analyze the results.
For pair A1-B3 we compare the data of tables 4 and 6. In table 4 at weight coefficients of 0,5 / 0,5 both variants of transportation of freight have identical result: r13' = r13 1' = r13 2'.
After combining the values of each of the factors of all options from both pairs "supplierconsumer" of the current problem at the same weight coefficients of 0.5 / 0.5, the resulting criterion was chosen r13 2': r13' = r13 2'.
Given the invariance of the initial data in the pair A1-B3, it is possible to draw an unambiguous conclusion about the direct impact on the result in the pair A1-B3 values of the second pair A3-B2.
For the pair A3-B2, we compare the data from Tables 5 and 7. Here we see even greater differences in the results: for six of the eleven pairs of weight coefficients, the best option for transporting cargo from the four existing ones has changed. Here, too, with constant initial data, the significant influence of the values of the pair A1-B3 is obvious.
For a two-factor multivariate transport problem with weight coefficients, the method of pair wise multiplication of factor values and their weight coefficients with subsequent selection of the smallest of the obtained values does not allow to choose the objectively best of the proposed options, as in this case weight coefficients do not affect the choice of the best option.
The difference in the values of the numerical ranges of the two factors leads to biased results, as the weight coefficients, in this case, can not fully perform their direct function to influence the choice of the best option. Therefore, it is mandatory to bring the values of the numerical ranges of the two factors to a single range both within a single pair "supplier-consumer" and within the entire transport task.
The proposed algorithm for bringing the initial data to a single numerical range, calculating the resulting criteria, and determining the best option for transportation for each pair "supplier-consumer" has fully performed its function. The obtained resulting criteria are ready for use in the further solution of the transport problem by one of the existing methods.
The algorithm allowed us to draw an important conclusion about the influence of the values of the factors of a single pair "supplier-consumer" on the resulting criteria of other pairs.
The developed algorithm can be relatively easily programmed in one of the existing programming languages. To write a program according to the given algorithm will require knowledge, skills, and abilities to work, in particular, with one-dimensional and multidimensional arrays, cycles of different types, branching design.