Evgeniya Semenuta

Abstract

of the qualification master’s work

Development of the computer system for optimal route planning and freight monitoring

Topicality

The dynamics of the market expansion of transport logistics services, observed recently, the discovery of new logistics terminal, increasing competition among operators contribute to the growth need in an integrated solution to the transport logistics tasks to better serve of customers.

Often the planner spends many hours or even days to solve the traffic optimization problem through a variety of mainstream software. As we know, these programs can't consider all real-world settings and requirements that are imposed on them by shippers, transport facilities, consignees, the actual average speed on motorways and other factors. The complexity of the transport network increases with the number of its facilities (warehouse, freight carrier, the shipper, the products) and the number of business restrictions (schedule objects, the characteristics of vehicles, routes, speed on highways, etc.). Visibility of interaction schemes reduces and the choice of the optimal solution becomes much more difficult problem that to solve virtually impossible without a specialized computer program. As a result, the scheduler ignores the fundamental issues that significantly affect the real cost of transportation.

According to international consulting firms, providing services to optimization of transport logistics processes, the use of specialized software helps reduce transportation costs by almost 15%. Interest in systems of planning and monitoring of freight traffic is increasing [1].

Purpose and tasks

The purpose of master's work is to minimize transport costs by finding the best routes and monitoring of freight.

Main tasks:

1. To develop and implement a search algorithm for the initial proposed route.
2. To consider the town ordering constraint in the journey.
3. To experimentally verify the effectiveness of the proposed algorithms.
4. To implement the freight movement monitoring.

Alleged scientific innovation

The solution of the freight problem with loading on the route as the case of asymmetric traveling salesman problem with additional constraints on the direction of the route. The developing of a new approach to NP-hard problems.

The practical value of the work

The automation of management processes of transport logistics of delivery is designed to significantly reduce the costs of logistics planning. As a result, the errors of planning reduce, delivery time and cost of its transportation decrease. That brings an increase in profits of companies engaged in freight delivery, and reduces the cost of services for consumers.

Due to the continuous monitoring of the movement the downtime reduces, and turnover increases. Control the actual mileage and fuel consumption reduces operating costs. The map of location of the vehicle in real time allows to pre-empt or respond quickly and effectively to the extraordinary events. The accumulation of statistical information about routes and modes of motion allows to optimize the performance monitoring service. The permanent control improves discipline of drivers and reduces accident rates. Control the location of vehicles to prevent theft of cargoes and materials.

Formulation of the problem of route optimal planning of freight

It is necessary to solve the sequential ordering problem for planning of courier delivery routes. Each regional center of Ukraine has a warehouse that uses some number of delivery vehicles with identical capacity Q. There is cargo with weight on N warehouses,. On each i warehouse,,there are Z orders with weight,. It is required to make delivery routes from one warehouse to another during 48 hours, and unloading and loading may be in the warehouses along the route of the vehicle.

Complete weighted graph whith nodes N is given. Where nodes correspond to warehouses that have cargo, to each arc is associated the path from the warehouse to warehouse, and assign them to the path cost. The solution for the transport routing problem can be represented in the form of transportation of all available at all stores cargo routes K {R1...Rk}, К --> min. The problem of freight optimization can be formulated as minimization of the total cost of all routes with consider the implementation of constraints: where is the weight of arc, that lead from the node i to the node j, is the subroute from the warehouse i to the warehouse j, is the corresponding route, where, К is the number of routes, Е is the weight of the already existing load in the car.

The constraint (2) determines that the vehicle can't be loaded with more than its capacity allows. is the weight р-th cargo in the i-th warehouse, , N is the number of warehouses, , Z is the number of cargoes in the warehouse. The constraint (3) is a time limit, the arrival of machines at the warehouse shouldn't be later than the deadline. is the time of arrival of corresponding k-th machine k to the i-th warehouse, is the deadline for the service time of i-th warehouse.

The sequential ordering problem can also be formulated as a general case of asymmetric traveling salesman problem based only on the weights of nodes. In this representation is an arc weight (i,j) (where may be different from ), which can either represent the cost of arc (i, j) when or an ordering constraint when =-1. =-1 means that element j must precede, not necessarily immediately, element i.

Conclusions

In the course of research work object of computerization has been studied, ways to automate have been identified; the system of planning and monitoring of freight routes have been reviewed and analyzed, their shortcomings and the necessity of developing a new system have been formulated; the methods of finding the optimal routes have been analyzed. A mathematical formulation of the problem of freight with load on the way has been formulated, methods for its solution have been proposed.

References

1. Современные системы планирования и управления транспортом. [Электронный ресурс]: Режим доступа: URL: http://www.odamis.ru/doc/pub/analit/20080519_2123
2. GPS GPRS Cлежение. Определение местоположение через спутник. [Электронный ресурс]: Режим доступа: URL: http://gribok.kiev.ua
3. Транспортная логистика :: Оптимизация грузоперевозок. [Электронный ресурс]: Режим доступа: URL: http://www.toplogistic.ru/transport_logistics.html
4. SystemGroup Логистика. [Электронный ресурс]: Режим доступа: URL: http://systemgroup.com.ua/solutions/logistics
5. Решение для транспортно-логистических компаний. [Электронный ресурс]: Режим доступа: URL: http://www.itboxcons.ru/content/view/22/39/
6. Транспортная логистика. [Электронный ресурс]: Режим доступа: URL: http://www.nova-it.ru/
7. Метод ветвей и границ. [Электронный ресурс]: Режим доступа: URL: http://ru.wikipedia.org/wiki
8. Рейнгольд Э. Комбинаторные алгоритмы. Теория и практика. - М.: Мир, 1980. — 476 c.
9. Пушкарёва Г.В. Исследование и применение бионических методов и моделей для автоматизированного проектирования маршрутов обхода геометрических объектов Компьютерная графика и представление GraphiCon 2005: науч.-техн. конф., 20-24 июня 2005г. : - 2005. - Режим доступа: URL: http://www.graphicon.ru/2005/proceedings/papers/Pushkaryova.pdf
10. Генетический алгоритм. [Электронный ресурс]: Режим доступа: URL: http://ru.wikipedia.org/wiki
11. Обобщённая задача коммивояжёра для определения рациональных маршрутов поставки. [Электронный ресурс]: Режим доступа: URL: http://econference.ru
12. Glover F. Tabu Search Journal of the Operational Research Society. - 1999. – Vol.50, № 1. – pp. 106–107. - Режим доступа: URL: http://glossary.computing.society.informs.org/notes/spanningtree.pdf
13. Сухарев А.Г. Курс методов оптимизации: Учебное пособие. - [2-е изд]. – М.: ФИЗМАТЛИТ, 2005. – 368 с.
14. Муравьиный алгоритм. [Электронный ресурс]: Режим доступа: URL: http://ru.wikipedia.org/wiki
15. Штовба С.Д. Муравьиные алгоритмы// Exponenta Pro. Математика в приложениях. - 2003. – № 4. – С. 70-75
16. Gambardella L.M., Dorigo M. HAS-SOP Hybrid Ant System for the Sequential Ordering Problem Technical Report IDSIA 11-97. - Режим доступа: URL: http://citeseerx.ist.psu.edu/viewdoc

Remark. While writing the given abstract the master's work has not been completed yet. The final date of the work completed is December, 2011. The text of master's work and materials on this topic can be received from the author or her research guide after the indicated date.

Resume