UA   RU
DonNTU   Masters' portal

Abstract

Contents

Introduction

The current level of technology development leads to the widespread use of freight in enterprises engaged in various activities. Currently, the most common are trucking, due to both relative cheapness and the possibility of transporting cargo directly from the loading point to the addressee or unloading point due to a fairly extensive network of highways. However, not all enterprises are able to incorporate a cargo vehicle fleet and related infrastructure, and therefore specialized enterprises successfully operate, called transport companies.

The transport company provides transportation of goods between different points for different customers. To carry out such activities, the company has the appropriate infrastructure and keeps records of work using software. Today, the development of transport companies and the increase in their number is occurring at a high rate, in connection with which competition is increasing and there is a need to optimize the operation of the transport company in order to reduce costs and increase profits [1].

1. Theme urgency

Optimization of the transport company involves reducing the cost of shipping, requires long-term arithmetic calculations, so it is done using special software, called logistics systems. Each of the logistic systems uses its own algorithms to optimize performance, and these algorithms are hidden from the end user of the system. Currently, there are a large number of logistic systems, each of which provides its own, distinct from others, functionality, taking into account a large number of factors [2]. However, the rapid development of transport companies causes a constant change in their working conditions, the emergence of new factors that are not fully taken into account by the existing logistics systems.

Algorithms of existing logistics systems are often not adapted to the constantly changing operating conditions of the transport company, and therefore it is becoming increasingly important to modify these algorithms as well as develop new algorithms that take into account all factors affecting the operation of transport companies at present.

2. Goal and tasks of the research

The aim of this work is to optimize the work of the transport company by reducing the cost of transporting goods by applying modified algorithms to solve transport problems, taking into account the restrictions on several loading points and different carrying capacities of vehicles.

Main tasks of the research:

  1. To analyze the existing algorithms, methods and technologies for solving the transport problem;
  2. Develop a mathematical model for the carriage of goods by vehicles, taking into account the restrictions on many different loading points and different load-carrying capacity of vehicles;
  3. Develop a modified algorithm for solving the transportation problem, taking into account the above limitations;
  4. Experimentally test the effectiveness of the algorithm.

3. Description of the path optimization problem

The transport company performs the carriage of cargo by a fleet of vehicles of various carrying capacities and various volumes. The company's fleet of vehicles can be divided into several loading points, therefore, the distances from different loading points for the same unloading point will be different. In addition, each car can carry several loads, with at least one and no more than the carrying capacity of this vehicle.

Each shipment is delivered to a specific place. Each shipment has a certain critical delivery time to the customer, while the actual delivery time of the cargo to the customer must not exceed the critical time limit. Depending on the cargo loaded in one vehicle, the points of discharge are determined, through which the route of the vehicle must pass.

The route is determined by the order of bypassing the points of unloading of cargo, provided that the starting and ending point of the route is the place of loading, and the points of unloading of cargo can go in any order, but take into account the length of routes between points of unloading and the time limit on the delivery of cargo. At the same time, the cost of overcoming the path for one car is defined as the product of the total length of the route and the cost of transporting the cargo by this vehicle per unit distance [1].

Based on the above limitations, it is required to determine such a load of vehicles and routes for which the total cost of overcoming the path by all vehicles with cargo will be minimal. Thus, this work solves the traveling salesman problem and partly the loading problem.

According to the data from the waybill, the car from the carpool is sent to the warehouse, where it receives the cargo and the freight bill of lading. After loading the car according to the waybill is sent to the points of unloading of cargo, the order of arrival in which is indicated in the waybill. When unloading a car, the material flow of the cargo is sent to the unloading point, while at the unloading point an information flow is formed in the form of an act of receiving & transfer of cargo, which is sent to the car. Upon completion of the voyage, acts of acceptance – the transfer of goods through the carpool are sent to the control room.

In this case, since the vehicle moves through several unloading points, the routes between these points may have different lengths in different directions and with a different order, and with different lengths of routes, the cost of transportation also changes. In this regard, it is necessary to optimize transportation by finding the optimal way, that is, to solve the traveling salesman problem.

Considering all of the above, it should be noted that the task in question is related to multi-objective optimization tasks. With a volume of initial data of 200 goods per day and 10 vehicles for their transportation, the range of permissible decisions is so great that the time to solve this problem using exact methods is impossible in a reasonable time [3]. The methods used earlier are not without flaws, and therefore further research is required on this topic.

Conclusion

In the course of the study, a review of the algorithms for solving three groups of transport problems was performed: exact, heuristic, and search. The analysis of the found algorithms was performed, their comparison is applicable to the solution of the traveling salesman problem with restrictions on the parameters of vehicles, and several points of loading of the cargo.

Based on the analysis of algorithms for solving problems, it was determined that no existing algorithm solves the problem given the above limitations, which confirms the relevance of the study of this topic and the development of a modified algorithm.

A description of the work of the transport company was performed, presented in the form of an informational & material flow chart.

The formulation of the cargo transportation optimization problem was formulated and described, the objective function and the limitations of this task were determined.

This master's work is not completed yet. Final completion: May 2019. The full text of the work and materials on the topic can be obtained from the author or his head after this date.

References

  1. Гарнов, А. П. Инструментарий логистики: учебник / А. П. Гарнов, Н. С. Киреева – М.:Креативная экономика, 2009. – 310 с.
  2. Товстик Т.М. Алгоритм приближенного решения задачи коммивояжера / Т.М. Товстик, Е.В. Жукова // Вестник СПбГУ. Серия 1. Математика. Механика. Астрономия. – СПБ:СПбГУ, 2013. – с. 101-106.
  3. Семенкина, О.Е. Effectiveness Comparison of Ant Colony and Genetic algorithms for solving combinatorial optimization problems // Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева. – 2012. – №1. – С.96-97.