DonNTU   Masters' portal

Abstract

Content

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.[1]

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.[3] 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.). [5] 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 [7].

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.[2]

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.[4]

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.[6] 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. [8]

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 town of Ukraine has a station that uses some number of delivery vehicles with identical capacity Q. There is cargo with weight Pi on N stations,iЄ[1;N]. On each stations,iЄ[1;N],there are Z orders with weight.[10] 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.

Figure 1. – An example of solution of the freight optimal route planning problem
(animation: volume – 133 КБ, size – 600x368, amount of shots – 30, amount of repeated cycles – 7)
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 Cij. 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.[9] The problem of freight optimization can be formulated as minimization of the total cost of all routes with consider the implementation of constraints:
where Cij is the weight of arc, that lead from the node i to the node j, Rij is the subroute from the station i to the station j, Rk is the corresponding route. К is the number of routes, Е is the weight of the already existing load in the train.

The constraint (2) determines that the vehicle can't be loaded with more than its capacity allows. N is the number of stations, Z is the number of cargoes in the station. The constraint (3) is a time limit, the arrival of train at the station shouldn't be later than the deadline.S is the time of arrival of corresponding k-th machine k to the i-th warehouse,a 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 Cij is an arc weight (i,j) (where Cij may be different from Cij), which can either represent the cost of arc (i, j) when Cij or an ordering constraint when Cij=-1. Cij=-1 means that element j must precede, not necessarily immediately, element i.[11]

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. Современные системы планирования и управления транспортом // Склад и Техника. – 2008.
  2. GPS GPRS Слежение. Определение местоположение через спутник.
  3. Васильева Наталья Курьерская почта UPS: быстро и надежно // Бизнес & Балтия. – 2004. – № 222.
  4. Транспортная логистика :: Оптимизация грузоперевозок.
  5. SystemGroup Логистика.
  6. Решение "IT-Box: Грузоперевозки, Логистика, Склад".
  7. Транспортная логистика.
  8. Метод ветвей и границ.
  9. Рейнгольд Э. Комбинаторные алгоритмы. Теория и практика. - М.: Мир, 1980. — 476 c.
  10. Пушкарёва Г.В. Исследование и применение бионических методов и моделей для автоматизированного проектирования маршрутов обхода геометрических объектов. Компьютерная графика и представление GraphiCon 2005: науч.-техн. конф., 20-24 июня 2005г. : - 2005.
  11. Генетический алгоритм.
  12. Бейсенбек Б.М. Обобщённая задача коммивояжёра для определения рациональных маршрутов поставки.
  13. Glover F. Tabu Search Journal of the Operational Research Society. – 1999. – Vol.50, № 1. – pp. 106–107.
  14. Сухарев А.Г. Курс методов оптимизации: Учебное пособие. - [2-е изд]. – М.: ФИЗМАТЛИТ, 2005. – 368 с.
  15. Муравьиный алгоритм.
  16. Штовба С.Д. Муравьиные алгоритмы // Exponenta Pro. Математика в приложениях. - 2003. – № 4. – С. 70-75
  17. Семенюта E.В., Привалов М.В. Применение муравьиных алгоритмов для поиска оптимальных маршрутов грузоперевозок. // Інформаційні управляючі системи та комп'ютерний моніторинг (ІУС та КМ - 2011) / Матеріали II науково-технічної конференції студентів, аспірантів та молодих вчених. — Донецьк, ДонНТУ — 2011. – с. 199-203
  18. Методичні вказівки до виконання лабораторних робіт за курсом “Еволюційні обчислення у технічних задачах” (для студентів спеціальності 7.091503 “Спеціалізовані комп’ютерні системи” (СКС)) / Укл. Ю.О. Скобцов, С.В. Хмільовий, Т. О. Васяєва – Донецьк, 2008. – 91 с.
  19. Батищев Д.И., Неймарк Е.А., Старостин Н.В. Применение генетических алгоритмов к решению задач дискретной оптимизации. Учебно-методический материал по программе повышения квалификации «Информационные технологии и компьютерное моделирование в прикладной математике». – Нижний Новгород, 2007. – 85 с.
  20. Семенюта Е.В., Привалов М. В. Применение муравьиных и генетических алгоритмов для решения задачи коммивояжера с ограничениями на направленность маршрута. // Інформатика та комп’ютерні технології / Збірка праць VII міжнародної науково-технічної конференції студентів, аспірантів та молодих науковців – 22-23 листопада 2011 р., Донецьк, ДонНТУ. – 2011. У 2-х томах, Т. 1 – с. 159-163
  21. Gambardella L.M., Dorigo M. HAS-SOP Hybrid Ant System for the Sequential Ordering Problem Technical Report IDSIA 11-97.
  22. Ascheuer N., Escudero L. F., Grotschel M. and Stoer M., 1993, A Cutting Plane Approach to the Sequential Ordering Problem SIAM Journal on Optimization 3, 25–42. – 355 pp.
Remark. While writing the given abstract the master's work has not been completed yet. The final date of the work completed is December, 2013. 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.