УДК 656.078 ADVANTAGES AND DISADVANTAGES OF METHODS OF ROUTING OF PART-LOAD CONSIGNMENT Shytiy M.I. (Kharkiv) Scientific advisor: Nefedov V.N. Language supervisor: Gubareva O. S.
Summary: The article considers the advantages and disadvantages of routing of part-load consignment’s methods and determination of a rational route of load dispatch. Key words: rational route, method, load dispatch. Стаття: У статті розглядаються переваги та недоліки засобів транспортування відправки дрібної відправки вантажу, та визначення раціонального маршруту розподілу завантаження. Ключові слова: раціональний маршрут, метод, розподіл завантаження. Статья: В статье рассматриваются преимущества и недостатки способов транспортировки мелкой отправки груза, и определение рационального маршрута распределение загрузки. Ключевые слова: рациональный маршрут, способ, распределение загрузки.

The task of determination of a rational route of load dispatch is based on the classic mathematical task of determination a ring route passing through a few separate points which are visited once and the point of start and destination is the same point (so-called “the traveling salesman problem”). The route having the time spent for load supply, the expenditures, the fare and the distance minimum is considered to be optimum depending on the aim. The task of routing of transportation of a part-load consignment is known to have two performances, that is “the traveling salesman problem” – when there is the one route of transportation for one truck to be developed in order to pass through all the points of destination and “vehicle routing problem” – when there are a few routes to dispatch the loads by the only one carrier [5]. As known, to define optimum routes of transportations of loads is a complicated mathematical problem. This problem consists of two independent questions, the first one is to route (that is to set the point of a transport network) and the second one is to order these set of points. Thus, in the process of planning of these kinds of transportation there is a task of routing when the carrying capacity of the selected cars does not exceed the norms and total distance is minimum. Zhytkov [5] says that the task solving of routing of a part-load consignment needs the following developed set of methods presented below: 1. Exact ones mean dynamic programming; integer linear programming; branch and bounds algorithm (method). 2. Approximate ones are methods of local optimization; methods of random search; heuristic methods. Application of the first group methods provides the task solving appropriate to the objective optimum of the efficiency function (it is usually the

minimum mileage). The methods of the second group give rational solutions but not optimum ones. Therefore they are named the methods of approximate tasksolving. The first attempt to receive the exact solution of “the traveling salesman problem” was to use the method of the dynamic programming [2, p. 6]. These methods allow to find optimum solution of 12 – 15 points tasks. The scientific work written by Azizov and others [1] says that the “the travelling salesman problem” presents a task integer programming. The basic idea of this approach consists in joining the basic system of linear equations with additional limits determining the conditions under which the variables are integral numbers there is no subcycle in the optimum task-solving. Branch and bounds method [3] is the most popular. At first, among the great number of feasible solutions the minimum limit presented by the lowest number is determined. The task-solving consists in the continuous gradation of a great number of feasible solutions for less and less submultitudes where the minimum limit is defined and the following submultitude is chosen with its own the most minimum value of the limit. As a result the subdivision with the only solving the lowest limit of which is equal to the value of the efficiency function is chosen. This method is the least laborious. As it was above mentioned, the approximate task-solving methods of “vehicle routing problem” consist of 3 groups of methods: random search, local optimization and heuristic methods. Methods of random search mean, which are the most optimum, is chosen from the great number of variants of route (by the random generator of numbers). Its advantage is of very low labourious. The disadvantages are based on the low quality of decision. Local optimization joins other methods and is used for optimization of early made task solutions in order to improve them. The most known method of local optimization is an inversion method. The inversion method means that on every stage of the task solving the route is inversed in such a way that a vehicle on its way back must pass the same point. A choice is made taking in consideration the minimum length of the route. The basic idea of this method consists in dividing an existing route for 2 parts by cancelling 2 random links which are then reunited in one consolidated route by including the links different from the cancelled ones. To renew such a route there are only 2 links and one variant is to reunite the route. Thus, one of the parts will be passed in the opposite to the initial direction, so it will be inversed. The most widespread methods of “vehicle routing problem” task solving are heuristic ones divided into two groups: 1. Methods projecting the man’s actions in modeling the routes: the sweep algorithm, an angle method, model and dynamic method. 2. Methods realizing ones ideas about the best route: a Danzig-Ramster method, a Clark-Wright method, a total-count method. The sweep algorithm is the most known [8]. Two points of destination are chosen. A ray is drawn between 2 points. This ray can be moved for or against an

hour-hand. The consequent point to be touched by the ray the first, is included into the route. The sweep algorithm is the simplest in calculation but the quality of tasksolving is not very high (in simple enough cases this method does not find an obvious solution). Therefore it is usually used in combination with methods of local optimization allowing forming an initial decision very fast [7]. The angle method likes the sweep algorithm has the same characteristics related to geometrical interpretation of “delivery tasks”. It is simpler that the sweep algorithm but it is more labourious. The disadvantages are low quality solutions. The most widespread method of task-solving of “vehicle routing problem” is a method developed by Clarke and Wright [4]. The pendulum routes form multidrop ones and as a result empty mileage decreases. The main disadvantage is that modeled routes intersect, that increase the mileage. The first method of decision of “vehicle routing problem” is a method offered by Danzig and Ramster [7, p. 8]. This method wasn’t widespread because of unsatisfactory quality of decision, bulkiness and high labour intensiveness of calculation. The principle aimed at uniting points into groups worse than the sweep algorithm because it doesn’t take into account the location of the nearest points. Another approximate mathematical method of task-solving “vehicle routing problem” that is the choice of the shortest distance routes [4]. The method of summation of series is one of the simplest approximate methods used for routing with the known set of the points included in each route and with the symmetric matrix of distances [4]. Its lack of consist in labour intensiveness of calculation with plenty of points of delivery because there is a need to define distance between all the points. In addition, the great number of variants of approximate place’s researching include new points which have to regard. Having conducted the analysis it can be concluded that there are methods which increase the quality of the accepted decisions. Each of them can play an important role in achieving the aim. However, as the practice of application of economical and mathematical methods shows that exact methods can be used only for the task of small multitude (30-40 points) to solve “vehicle routing problem”. However, the method developed by Clarke and Wright has become the most famous but it also has its own disadvantages. A little change in task, introduction of additional limits makes the methods less effective and demands a special way of task-solving for each different problem or dispatcher’s solution improvement. References 1. Азизов Ф.Х. Применение математических методов при планировании перевозок товаров Ф.Х. Азизов, А.И. Ахмедов, В.П. Кочеулов. – М. : Госторгиздат, 1963. – 104 с. 2. Беллман Р. Применение динамического программирования к задаче о коммивояжере / Р. Беллман // Кибернетический сборник – 1964. – Вып. 9. – С. 219 – 222. 3. Горев А. Э. Грузовые автомобильные перевозки. – М. : Издательский центр «Академия», 2008. – 288 с. 4. Грузовые автомобильные перевозки / Воркут А.И. – 2-е изд.,

перераб. и доп. – К. : Вища школа. Головное изд-во, 1986. – 447 с. 5. Житков В.А. Планирование автомобильных перевозок грузов мелкими партиями. – М. : Транспорт, 1976. – 112 с. 6. Хелд М., Карп Р. Применение динамического программирования к задачам упорядочения. // Кибернетический сборник, 1964. Вып. 9. – С. 208 – 218. 7. Christofides N., Eilon S. An algorithm for the vehicle dispatching problem. – Operational Research Quarterly, 1969. – Vol. 20. – № 2. – P. 309 – 318. 8. Gillett В., Miller L.A. heuristic algorithm for the vehicle dispatch problem. – Operational Research, 1974. – Vol. 22. – № 3. – P. 340 – 349.