In the paper, authors analyze information and communication technology (ICT) for planning and optimization of transport routes with time windows. This analysis helps to choose the method for solving a vehicle routing problem with time windows (VRPTW) with optimal result for decision-maker, as well as determine the influence of the internal parameters of the selected method on the result of its application. Currently, there are several well-known methods and algorithms in ICT for planning and optimization of transport routes with time windows, in particular: saving and sweeping algorithms, ant colony optimization (ACO) method, artificial bee colony (ABC) method, etc. The result of the analysis showed that: a) the speed and quality of the search for solutions can be improved by adjusting internal parameters of researched methods, b) depending on the size and specificity of the in-coming data, different methods can be more or less suitable. In this paper, the authors discussed the features of using the ACO method and the ABC method to solve VRPTW and influence of their application on the optimality of the results. Simulation results show the need and feasibility of using ICT in VRPTW.
The development and globalization of the market contributes to increased competition
in it. That is why many companies have to expand their sphere of influence,
expanding the sales area of their goods or services. Along with this, the delivery process is
becoming more expensive. The share of logistics costs continues to grow, as supply
chains are becoming more complicated, and requirements to the quality of service and
the provision of the necessary service are growing [
The quality of customer service can also affect transportation planning. Each client
also plans his day and work and is interested in the efficient use of his time. That is
why, he wants to be served in a specific period of time. If the company cannot serve it
Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
at this time (for those cases when the client and the carrier company have agreed on
the delivery time), then the rating of the company drops sharply, which means that the
company may lose the client and its profit [
Due to the large number of methods for planning and optimizing routes, the
company is faced with the need to choose one of them. Depending on the initial
conditions and factors that are taken into account, it is better to use different methods, since
they give different percentages of accuracy and error of the results [
This paper is devoted to the analyze information and communication technology
(ICT) for planning and optimization of Vehicle Routing Problem with Time Windows
(VRPTW) using various meta-heuristic methods [
The problem of transportation planning has existed since the first vagrant merchants
appeared who transported their goods from city to city. The first written mention of
this problem dates back to 1882 in the book "Salesman – how he should behave and
what he must do in order to be successful and mark success in business – the advice
of the old courier" and it was first mathematically described in 1930 by Karl Menger.
It was called Travelling Salesman Problem. It consisted of the formation of a
minimum route along which all cities will be visited at least once and which will close in
the first city [
But in the era of capitalization and globalization, the problem of transportation
planning covered not only the sphere of trade and became much more complex than a
traveling salesman problem. Routes can be formed not for one, but for several
vehicles of one or different types, and other factors can be taken into account during their
formation, except for the minimum path length [
So, vehicle routing problem (VRP) is a combinatorial optimization problem in
which a set of routes to several remote points of consumption should be defined for a
fleet of vehicles located in one or more depots [
The task refers to NP-hard classes, that is, the number of options for solving the
problem and the time to find the best option with an increase in the number of nodes
grows exponentially [
Methods of forming transport routes are divided into several groups. They include
[
The probabilistic component of metaheuristic methods gives them a significant
advantage when choosing them for solving a VRPTW, since they also allow to take into
account those solutions that in other methods can be truncated by the indicated
restrictions, because, despite this, they may be in part of the solution domain with target
function with the best value [
For further research were selected Ant Colony Optimization method (АСО),
Artificial Bee Colony method (АВС) [
The principle of the ACO method (Fig. 1) is based on the behavior of the ant colony
in nature, namely the labeling of more successful pathways with a large amount of
pheromone [
In general, ants move in search of food in random order. If one of them finds food,
then he goes back to the anthill, marking the path with pheromones. Other ants,
finding a trail of pheromones, go to the place of discovery, following the path and
supplementing it with their pheromones. If there are two paths from the find point, then
more ants will have time to go along the short path, which means that more
pheromones will remain on it, and it will be more attractive. Over time, the pheromones
erode and the trail loses its appeal [
The ABC method (Fig. 2) operates on the principle of the behavior of a bee colony
in nature, namely the exploration of the space around the hive in order to search for
nectar with its subsequent collection. For this, there are various types of bees in the
colony: scout bees and working forager bees (in addition to them, there are drones and
a uterus in the colony that are not involved in the collection of nectar). Scouts conduct
research on the space surrounding the hive and report information on promising
places where the largest amount of nectar was found (there is a special mechanism called
bee dance for exchanging information in the hive). Then, in the most promising areas,
worker bees fly out, which collect nectar, while simultaneously updating the
information of scouts on the amount of nectar in a certain area indicated by the scout. The
work of these types of bees in the hive provides effective exploration of the
surrounding space and the collection of nectar [
According to the ABC method, each scout bee finds a certain random solution, and
depending on whether this area is assigned to the best or promising areas, forager bees
search in the vicinity of these solutions [
For the test, a task with eleven nodes was selected: one “zero” storage and ten nodes to which it was necessary to deliver the ordered quantity of goods in a specific period of time.
ACO method. The so-called “greed” parameter α of ACO method is a parameter
that determines the degree of influence of the pheromone concentration when
choosing the next node [
The larger the parameter α, the greater the influence of pheromone concentration on the edge when calculating the probability of choosing a particular node (Fig. 3).
Thus, on Fig. 3, e it is seen that the larger the parameter α, the faster the search for the optimal solution is performed. It is clearly seen that the best average time use efficiency (percentage of time spent on the journey and for unloading and placing orders) was obtained at α = 0, but the smallest deviation from the best found path length and the least time was obtained at α = 0.3, therefore, for further testing decided to leave it.
The larger the parameter β, the more the time spent on its maintenance with the corresponding fines affects the probability of choosing a node.
The Fig. 4, e shows that the faster the search is performed at β = 0.75 and the highest accuracy of the results is achieved when β = 0.6.
ABC method. In different sources and for different types of combinatorial
optimization problems, a different ratio of different types of bees in the colony is
recommended. For the transport task in [
Fig. 5 shows that the most suitable number of bees in the colony for the given test data is 100 bees, because with it the result is the most accurate.
Next, these methods are compared according to criteria. Thus, the results of a comparison of the two methods can be seen in Table 1. So, from the table it becomes clear that the ACO method for a number of parameters gives better results than the ABC method. These parameters are deviation of route lengths from the best solution found by both methods; time efficiency in routes, solution search time.
In this paper, the importance of considering customer service waiting times and the main factors that affect customer service time were considered.
The influence of the values of the main internal parameters of the ABC and AСO methods on the found solution was examined and a comparative analysis of both methods was performed. As a result of the analysis, it was found that the AСO method is more suitable for solving VRPTW according to most criteria.