Transportation planning with minimal costs

E. V. Khizhnyakova

Matematičeskaâ fizika i kompʹûternoe modelirovanie, Tome 23 (2020) no. 4, pp. 51-55.

Résumé

In this paper, the classical problem of optimal transport plan is considered taking into account the capacity of certain sections of the transport network. Let $v_{pq}$ units of goods be delivered from point $p$ to point $q$. At the same time, each section of the transport network has a limited capacity, which is expressed in a certain volume of goods that can be passed through it per unit of time. The goal is to distribute goods flows along different routes in such a way that all transport needs are completely satisfied, the roads are not overloaded, and at the same time the total transport costs (for example, in the form of fuel consumption,time costs, etc.) reach their minimum. It should be noted that without restrictions on capacity, the task is solved trivially: it is necessary to distribute all transportation from point $p$ to point $q$ on the shortest route. To solve this problem, a mathematical model of the transport network is formulated. It is proposed to reduce the solution of this problem to the solution of the linear programming problem. As a result, we propose an algorithm for planning transportation in such a way that the total costs will be the lowest. In addition, one of the algorithm steps required solving the problem of finding the $q$-th path along the length between $2$ nodes. To solve this problem, the corresponding algorithm is proposed. This algorithm is recursive.

Détail

Keywords: transport network, the shortest path, flow, capacity, linear programming.
Mots-clés : transportation