Українська   Русский
Go to DonNTU site   Go to DonNTU Master's portal

Abstract

Content

Introduction

Transport logistics is a set of measures to organize the delivery of goods with minimal time and / or financial costs. Transport logistics can be represented as six consecutive tasks, so each of these tasks can be started only after the previous one has been completed. These tasks are:

  1. Accounting for goods in warehouse.
  2. Accounting and processing of applications for the supply of goods.
  3. Vehicle load calculation.
  4. Clustering problem.
  5. Traveling salesman problem.
  6. Backpack problem [1].

Transport logistics includes a large number of tasks, for each of which a separate information system or subsystem can be created. Therefore, within the framework of this master's work, it was decided to concentrate on the traveling salesman problem.

1. Theme urgency

In the presence of daily changing demand for certain groups of goods, there is a need for the regular creating of freight routes. At the same time, an important aspect is the minimization of financial and time costs for the transportation of goods.

Taking into account such factors as different load-carrying capacity of vehicles, the presence of special devices for loading / unloading, vehicle occupancy, trailer availability, conditions for approaching unloading points, daily changing demand, the need to maximize the use of own cars, it is reasonable to use the automation of building route sheets, namely – an automated system for the formation of routes for the delivery of a certain type of goods [2]. In addition, the automation of building routes is an important aspect for any enterprise from an economic point of view. The introduction of such a system minimizes the influence of the human factor, speeds up the process of the logistics department, leads to a reduction in vehicle downtime under loading and unloading goods. Accordingly, the acceleration of the transportation process leads to cost minimization, and accordingly – to an increase in profits.

2. Target and tasks of the research

The target of the study is to create an information system that will be designed to reduce the cost of delivering medicines from the pharmacy warehouse to retail outlets. This can be achieved through the following parameters:

In addition, this information system is designed to facilitate and speed up the work of the logistics department.

The described target can be achieved by solving the following tasks:

3. Overview of existing systems

In the software market there are a significant number of various information systems aimed at solving logistics problems. Each of them represents its own functionality, using a specific optimization criterion.

  1. Муравьиная логистика. Online service for the calculation of optimal delivery routes. The service is provided for free use for a trial period, after which it requires the purchase of a license for use, the number of points in the route may be limited depending on the type of license, and the number of routes per day is limited regardless of the type of license [3].
  2. ABM Rinkai TMS. Specializes in building the best routes for the delivery of goods. The ABM Rinkai TMS system is paid and does not provide a demo version for review. Formation of routes in ABM Rinkai TMS provides 3 different optimization methods, each of which has its own logic for the process of building routes. Takes into account all key parameters necessary for building optimal routes [4].
  3. Zig-Zag. Service management of transport logistics for companies whose business is related to the delivery of goods. The service allows to create optimal routes and effectively plan the loading of drivers and couriers. The service is free for non-commercial use only. It contains such features as teamwork, operational changes and performance analysis. In addition, there is a mobile version [5].
  4. Maxoptra. Web-based logistics management system. Automatically distributes work among performers and plans the best routes for delivery on time and with minimal costs. With its help, the user has the ability to control and, if necessary, adjust the movement of employees in real time. Maxoptra provides a trial period for use, after then requires the purchase of a license [6].

4. Analytical formulation of the problem

The traveling salesman problem is the task of finding the shortest Hamiltonian path in a complete finite graph with N vertices. A traveling salesman leaving a vertice wants to visit the N-1 of other vertices and return to the starting vertice. The distances between all these vertices are known. It is required to establish the order in which he should visit cities so that the total distance traveled is minimal [7].

To solve the problem, an additional condition for balancing the routes is necessary, in particular, by the number of points included in the routes. Such a task, called the set traveling salesman problem, belongs to the class of NP-difficult problems. For k traveling salesmans on a set of n + 1 points, k closed routes are built according to the following rules:

4.1 Route optimization criteria

The route can be considered optimal based on the following criteria:

It is worth noting that the shortest route is not always the least expensive, so these two criteria should be considered as separate.

In the master's work, the task of forming the optimal route is supposed to be solved using an aggregate criterion; thus, the route is the most profitable in terms of time, distance, and financial costs.

4.2 Limitations affecting the construction of the route

The formation of the optimal route can be influenced by a number of additional factors, which are commonly called constraints. For the traveling salesman task, the limitations are:

4.3 Mathematical apparatus

The traveling salesman problem can be described as follows. There are n vertices, the cost between which is given by the matrix C. The traveling salesman should visit each vertice once and return to the starting vertice of the route, while spending a minimum of funds [8]. Mathematically, this can be represented by the following formula, which also represents the objective function:

pic2

where n – amount of vertices on the map;

cij – inter-vertex cost matrix;

xij – component transition matrix:

    xij = 1, if the route involves moving from point i directly to point j;

    xij = 0, otherwise.

The formulation of the problem can be formulated as follows: find the minimum of the function Z when the constraints are satisfied and the values of the matrix X are nonnegative [9]. The constraint system can be represented as follows:

pic2

where n – amount of vertices on the map;

xij – component transition matrix:

ui, uj – arbitrary non-negative integers.

In addition, each of the restrictions expresses the following conditions:

To implement the above equalities, it suffices to introduce penalty functions, putting:

pic2

where k = p;

cijmax – maximum value for all cij.

Conclusion

As a result of the work done, materials relating to transport logistics, optimizing freight traffic and solving the traveling salesman problem were collected and studied. The methods, models and algorithms used to optimize the routing and cargo transportation tasks were investigated, and the software already available on the market for logistic tasks was also considered. In addition, the advantages and disadvantages of the existing methods, models and algorithms were identified, and their classification was carried out. According to the results of the analysis, the direction of further research in the field of finding optimal routes for the delivery of goods was chosen, the mathematical formulation of the problem was formulated.

In view of the research [13, 14, 15], it can be concluded that to solve the traveling salesman problem, it is most advisable to use ant colony optimization algorithms that have been developed specifically to solve this problem and are most effective in this area. However, besides the algorithm itself, one should not forget about the optimization criteria, which indicate in which direction the algorithm should work. This is important from the point of view that the same algorithm can give different results for different optimization criteria when solving the same problem. In addition, it is worth taking into account the limitations that will affect the operation of the algorithm and the final result. These restrictions can be represented as input. [1].

Notes

At the time of writing this abstract the master's work is not yet completed. Final completion date: June 2019. The full text of the work and materials on the topic can be obtained from the author or his scientific adviser after the specified date.

References

  1. Савкин В.Ю. Анализ методов решения задачи коммивояжёра / В.Ю. Савкин, В.А. Светличная, Радзывыло К.Г. // Материалы IX Международной научно-технической конференции. – Донецк: ДонНТУ, 2018. – с.6–10.
  2. Семенов Ю.Н. Автоматизация построения маршрутов перевозок крупнопартионных грузов / Ю.Н. Семенов, О.С. Семенова // Вестник Кузбасского государственного технического университета. – Кемерово: КузГТУ, 2015. – с.131–134.
  3. Автоматизация транспортной логистики – онлайн сервис для планирования оптимальных маршрутов доставки [Электронный ресурс] – Режим доступа: [Ссылка]
  4. Управление транспортом, транспортная логистика, TMS система – ABM Rinkai [Электронный ресурс] – Режим доступа: [Ссылка]
  5. Zig-Zag: Оптимизация транспортной логистики [Электронный ресурс] – Режим доступа: [Ссылка]
  6. Maxoptra: Система управления логистикой, программа для логистики транспорта, система логистики предприятия [Электронный ресурс] – Режим доступа: [Ссылка]
  7. Товстик, Т.М. Алгоритм приближённого решения задачи коммивояжёра / Т.М. Товстик, Е.В. Жукова // Вестник СПбГУ. – 2013. – №1. – с. 101-109.
  8. Петрунин, С.В. Использование метода последовательной сепарации (ПС) для решения задачи коммивояжёра // Научный вестник МГТУ ГА. – 2009. – №143. – с. 87-90.
  9. Задача коммивояжёра. [Электронный ресурс] – Режим доступа: [Ссылка]
  10. Борознов, В.О. Исследование решения задачи коммивояжёра // Вестник АГТУ. Сер: Управление, вычислительная техника и информатика. – 2009. – №2. – с.147-151.
  11. Костюк, Ю.Л. Эффективная реализация алгоритма решения задачи коммивояжёра методом ветвей и границ // Прикладная дискретная математика: Научный журнал – Томск : Национальный исследовательский Томский государственный университет – 2013 – №2. – с.78-90.
  12. Гараба, И.В. Сравнительный анализ методов решения задачи коммивояжёра для выбора маршрута прокладки кабеля кольцевой сети кольцевой архитектуры // Молодёжный научно-технический вестник. – 2013. – №1. – с.173-188.
  13. Мурзин, Б.П. Использование алгоритма муравьиной колонии для определения оптимального маршрута доставки грузов / Б.П. Мурзин, В.А. Светличная // Інформаційні управляючі системи та комп'ютерний моніторинг (ІУС КМ-2011) / Збірка матеріалів IІ всеукраїнської науково-технічної конференції студентів, аспірантів та молодих вчених – 11-13 квітня 2011 р., Донецьк, ДонНТУ – 2011, с. 183-186.
  14. Курейчик, В.М. О некоторых модификациях муравьиного алгоритма / В.М. Курейчик, А.А. Кажаров // Известия ЮФУ. Технические науки. – 2009. – №1. – с.7-12.
  15. Семенкина, О.Е. Effectiveness Comparison of Ant Colony and Genetic algorithms for solving combinatorial optimization problems // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева. – 2012. – №1. – с.96-97.