Transportation model with the limitation of carrying capacity, moving time and quantity of transport

Authors

  • Анастасия Сергеевна Шевченко National Technical University of Ukraine “Kyiv Polytechnic Institute”, Peremohy Avenue, Kyiv, Ukraine, 030056, Ukraine
  • Дарья Сергеевна Шевченко National Technical University of Ukraine “Kyiv Polytechnic Institute”, Peremohy Avenue, Kyiv, Ukraine, 030056, Ukraine

DOI:

https://doi.org/10.15587/2312-8372.2013.19325

Keywords:

problem of transport routing, optimal solution, meta heuristic method, routing cost

Abstract

This иarticle dwells upon meta heuristic approach of problem solving of transport routing for industry that has scarce resources in its activity. Such resources are: carrying capacity, moving time and quantity of transport.

The general algorithm of developed method bases on imperative problem solving without accounting one of limitation. Simplified problem is solving for quantity unserved consumers of meta heuristic method. The main idea of a method is to merge solving method of Clarke-Wright with the method of simulated annealing.

To solve the problem and analyze the effectiveness of developed algorithm the program product has been created. In the present paper the results of calculated experiments and calculated deviation of model solution from received results have been demonstrated. Mean error of the method and the time of finding the solution witnesss that developed method have an ejective solution for acceptable time.

Author Biographies

Анастасия Сергеевна Шевченко, National Technical University of Ukraine “Kyiv Polytechnic Institute”, Peremohy Avenue, Kyiv, Ukraine, 030056

Information Technology Department

Дарья Сергеевна Шевченко, National Technical University of Ukraine “Kyiv Polytechnic Institute”, Peremohy Avenue, Kyiv, Ukraine, 030056

Information Technology Department

References

  1. Кларк, Г. Планування транспортних засобів від центрального депо до ряду пунктів постачання [Текст]/ Г. Кларк, Дж. В. Райт // Дослідження Операцій. – 1964. – №12. – С. 568-581.
  2. Гендрау, М. Мета-евристики для транспортної задачі [Текст]/ М. Гендрау, Г. Лапорте, Ж.-И. Потвин // Технічний звітСРТ-963. – Центр досліджень транспорту, Університет Монреалю, 1999.
  3. Транспортна задача [Електронний ресурс]. – Режим доступу: www/ URL:http://neo.lcc.uma.es/radi-aeb/WebVRP
  4. Сарікліс, Д. Евристичний метод вирішення транспортної задачі [Текст]/ Д. Сарікліс, С. Павел // Журнал суспільства дослідження операцій. – 2000. – №51. – С. 564–573.
  5. Ральфс, Т. Задача маршрутизації транспортних засобівз обмеженою вантажопідйомністю та деякі пов’язані проблеми [Текст]/ Т. Ральфс, Дж. Хартман, М. Галаті. – Університет індустрії та системної інженерії Лехайгу, УниверситетРутгерс, 2001. – С. 1-31.
  6. Пічбібула, Т. Покращений алгоритм Кларка-Райта для задачі маршрутизації транспортних засобів з обмеженою вантажопідйомністю [Текст]/ Т. Пічбібула, Р. Кавтумача // Наукова Азия. – 2012. – №38. – С. 307–318.
  7. Молчановський, О. І. Побудова початкового розв’язку для задачі маршрутизації транспортних засобів з підбором та доставкою [Текст]/ О. І. Молчановський, А. Л. Любонько// Матеріали III Всеукраїнської науково-практичної конференції «Інформаційні технології - 2012». – 2012. – С. 256-260.
  8. Метод Кларка-Райта [Електронний ресурс] – Режим доступу: www/ URL:http://lib.convdocs.org/docs/index-152162.html?page=4
  9. Метод імітації відпалу [Електронний ресурс]. – Режим доступу: www/ URL:http://ru.wikipedia.org/wiki/Simulatedannealing
  10. Розуміння імітації відпалу[Електронний ресурс]. – Режим доступу: www/ URL:http://www.heatonresearch.com/node/727
  11. Тестові приклади задач [Електронний ресурс]. – Режим доступу: www/ URL: https://www.assembla.com/code/victorillac/git/nodes/ 5e17b1fcfed9fef7da913a0773279b578d6a911a/Instances/cvrp/augerat.sol
  12. Clarke, G.,Wright, J. W. (1964). Scheduling of vehicles from a central depotto a number of delivery points. Operations Research, 12, 568-581,
  13. Gendreau, M., Laporte, G., Potvin,J.-Y. (1999). Metaheuristics for thevehicle routing problem. Technical Report CRT-963. Centre deRecherchesur les Transports, Universite de Montreal.
  14. The VRP. Available:http://neo.lcc.uma.es/radi-aeb/WebVRP
  15. Sariklis, D., Powell, S. (2000). A heuristic method for the open vehicle routing problem. Journal of the Operational Research Society, 51, 564–573.
  16. Ralphs, T., Hartman, J., Galati, M. (2001). Capacitated Vehicle Routing and Some Related Problems. Industrial and system engineering Lehigh University, Rutgers University, 1-31.
  17. Pichpibula, T., Kawtummacha, R. (2012). Animproved Clarke and Wright savings algorithm for the capacitated vehicle routing problem. Science Asia, 38, 307–318.
  18. Molchanovskiy, O., Lyubon'ko, A. (2012). Construction of initial solution for the vehicle routing problem with pick up and delivery. Materials of III Ukrainian scientific-practical conference «Information technologies - 2012», 256-260.
  19. Clarke-Wright method. Available: http://lib.convdocs.org/docs/index-152162.html?page=4
  20. Simulated annealing. Available: http://ru.wikipedia.org/wiki/Simulated annealing
  21. Understanding Simulated Annealing. Available: http://www.heatonresearch.com/node/727
  22. Testexamples. Available: https://www.assembla.com/code/victorillac/git /nodes/5e17b1fcfed9fef7da913a0773279b578d6a911a/Instances/cvrp/augerat.sol

Published

2013-11-28

How to Cite

Шевченко, А. С., & Шевченко, Д. С. (2013). Transportation model with the limitation of carrying capacity, moving time and quantity of transport. Technology Audit and Production Reserves, 6(1(14), 47–51. https://doi.org/10.15587/2312-8372.2013.19325

Issue

Section

Technology audit