COMPARISON OF METHODS OF SOLVING THE PROBLEM OF OPTIMAL LOADING OF A VEHICLE

Abstract

This paper is devoted to a comparison of methods for solving the problem of optimal vehicle loading. The problem under consideration is one of the tasks that clearly demonstrate the advantages of mathematical modeling in the processes of development and decision making in transportation planning. In addition, this task is one of the essential components of the logistics program when planning the delivery of goods.

The aim of the study was to compare various solution methods using the example of one vehicle optimal loading problem.

This problem belongs to the class of integer linear programming problems. There are a number of methods for solving it. The article discusses some of them.

The graphical method is the simplest and most visual. But its usage becomes impossible if the number of goods is more than three.

The cutting-plane method is based on cutting off from the feasible solutions space to a problem with weakened constraints on parts that do not contain integer solutions. However, if there are a variety of solutions, it does not allow to find all the optimal plans.

The branch-and-bound method permits to find all the solutions. However, it requires solving a large sequence of linear programming problems.

The method of dynamic programming is one of the effortless and does not require cumbersome calculations when solving problems of small dimension.

To demonstrate the advantages and disadvantages of these methods, an abstract example of the optimal loading problem, which has several solutions, is considered. The process of solving this problem by each method is described. Application of the cutting-plane method does not allow to finding all optimal solutions. The branch-and-bound method makes it necessary to solve eleven linear programming problems. Using the dynamic programming method shows that it is efficient and not so time-consuming.

In conclusion, it is noted that with an increase in the number of goods, the dynamic programming method requires a significant increase in the volume of calculations. Тhe application of this method is difficult when solving the problem of more than one vehicle optimal loading.