An optimization problem of multi-modal transportation is investigated. The multi-step decision-making process is constructed. Dynamic programming method for solving the problem is proposed. It should be noted that the dynamic programming is not provided computational advantages, but facilitates changes and modifications of tasks.
Copyright c by the paper’s authors. Copying permitted for private and academic purposes. carrier of the goods for a given initial point of departure and final destination of its receipt. Optimization of the decision–making process is carried out by the dynamic programming method. 2
Integrated route planning may include: • Estimation of the cost of services for each carrier; • The study of the geographic features and limitations in terms of binding to the warehouses, railway stations, sea and river ports; • Analysis of the cost of transhipment of goods; • The timetable for delivery.
In the model scheme shown in Fig.1, is planned four segments of the route with three overloads: the supplier – the initial segment AB or AC is serviced by road transport to the station B or C, next segment – by railway from the stations B or C to D or E ports, then by sea transport from port D or E to the ports of F or G, the final section – motor transport from ports F or G to the consumer H.
Selection of decision maker is to implement a route through nodes B or C, D or E or F and G in such a way that the total transportation cost was minimal. Possible taking into account additional criteria, such as delivery time or the various risks. To construct a mathematical model of a multi–modal transportation, allowing the use of dynamic programming for finding a solution to the optimal route search task required to describe a multi–step decision–making process, the scheme of which is shown in Fig.2.
Suppose that the system is in the state X0. As a result of the decision U0 system goes into a state of X1 and the price of such decision is C(X0, U0). From the standpoint of a model example (see Fig.1), the state X0 corresponds to locating the goods from the supplier A, solution U0 is to use the first motor carrier to station B or C. Next, the system will be in the state X1, i.e. at station B or C. As a result of the decision U1 system goes into a state of X2 which corresponds to the carriage by rail to stations of D or E, and the price of the decision will be C(X1, U1). This process will continue until the final state of X4 when the goods will be delivered to the consumer.
Optimization of the above constructed multi–stage decision–making process is carried out by the method of dynamic programming [Wag75]. 4
Using the method of dynamic programming and Bellman’s principle of optimality [Bel53] will provide greater flexibility in terms of possible inclusion in the model of various modifications, for example in case emergency situations. The minimum of decision-making price in i steps from the j state will be described by the Bellman’s recurrence relation fi(Xj ) = mUijn{C(Uj , Xj ) + fi−1(Xj−1)}. (1) Here Uj is control on step j, C(Uj , Xj ) is the price of making a decision on step j. As Uj implemented to set the minimum price of j–th freight. Algorithm transitions from one state to another (see Fig.2) is described below.
1–st step. Suppose that the system was in the penultimate state X3. Then the price for the decision of the final step according to (1) will be 2–nd step. Suppose that the system was in the state X2. Then the price decision of the last two steps will be (2) (3) (4) (5) 3–rd step. If the system was in a state X1 then the price of the decision in the last three steps can make one of the alternatives
f1(X3) = mUi3n{C(U3, X3)}. f2(X2) = mUi2n{C(U2, X2) + f1(X3)}. f3(X1) = mUi1n{C(U1, X1) + f2(X2)}. f4(X0) = mUi0n{C(U0, X0) + f3(X1)}.
f1(X3 ⊃ F ) = min{60} = 60 , 4–th step. Finally, let the system is in the initial state X0. Then the price decision for all four steps will be This price corresponds to the minimum value of the entire carriage.
Now, using the data shown in Table 1, it is possible to construct the optimal route for multi–modal transportation for model example (see. Fig.1) in accordance with the above algorithm.
1–st step. Price decision U3 at a final step in the transition of the system from the penultimate state X3 will be 2–nd step. Being in a state X2 and making decision U2 the price of the last two steps will be f2(X2 ⊃ D) = min f2(X2 ⊃ E) = min ( 60 + f1(X3) )
90 + f1(X3) ( 70 + f1(X3) ) 80 + f1(X3) = min = min
3–rd step. Suppose that the system was in a state X1. Then the price decision of the last three steps can make one of the alternatives
This price corresponds to the minimum value of the entire carriage.
To find a proper sequence of the optimal route with a minimum value of 180 enough to write a minimum prices decision-making at each step.
f3(X1 ⊃ B) = min f3(X1 ⊃ C) = min ( 40 + f2(X2) )
50 + f2(X2) ( 20 + f2(X2) ) 30 + f2(X2) 4–th step. Finally, let the system is in the initial state X0. Then the price decision for all four steps will be = min = min = min The optimal scheme (see. Fig.3) for the considered model example of multi–modal transportation following
A → C → D → F → H . 5
The model example of multi–modal transportation is studied. The Multi–Step Decision–Making Process is constructed. Optimization of the decision–making process is carried out by the dynamic programming method. Using the method of dynamic programming and Bellman’s principle of optimality will provide greater flexibility in terms of possible inclusion in the model of various modifications, for example in case emergency situations [Zav15]. Acknowledgements The investigation was supported by the Russian Foundation for Basic Research, project no. 17-08-01123-a. [Flo11]