=Paper=
{{Paper
|id=Vol-2740/20200365
|storemode=property
|title=ICT for Planning and Optimization of Transport Routes with Time Windows
|pdfUrl=https://ceur-ws.org/Vol-2740/20200365.pdf
|volume=Vol-2740
|authors=Nadiia Ukhan,Galyna Kondratenko,Ievgen Sidenko,Yuriy Kondratenko
|dblpUrl=https://dblp.org/rec/conf/icteri/UkhanKSK20
}}
==ICT for Planning and Optimization of Transport Routes with Time Windows==
https://ceur-ws.org/Vol-2740/20200365.pdf
ICT for Planning and Optimization of Transport Routes
with Time Windows
Nadiia Ukhan[0000-0002-1776-5558], Galyna Kondratenko[0000-0002-8446-5096],
Ievgen Sidenko[0000-0001-6496-2469], Yuriy Kondratenko[0000-0001-7736-883X]
Intelligent Information Systems Department, Petro Mohyla Black Sea National University,
68th Desantnykiv Str., 10, Mykolaiv, 54003, Ukraine
nadiiaukhan@gmail.com, halyna.kondratenko@chmnu.edu.ua,
ievgen.sidenko@chmnu.edu.ua, yuriy.kondratenko@chmnu.edu.ua
Abstract. In the paper, authors analyze information and communication tech-
nology (ICT) for planning and optimization of transport routes with time win-
dows. 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 meth-
ods, 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.
Keywords: Information and Communication Technology, Planning, Optimiza-
tion, Transport Route, Time Window, Ant Colony Optimization Method, Arti-
ficial Bee Colony Method.
1 Introduction
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, expand-
ing 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 [1-4].
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 [1].
Due to the large number of methods for planning and optimizing routes, the com-
pany is faced with the need to choose one of them. Depending on the initial condi-
tions 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 [3].
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 [5-7].
2 Related Works and Problem Statement
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 mini-
mum route along which all cities will be visited at least once and which will close in
the first city [2].
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 vehi-
cles of one or different types, and other factors can be taken into account during their
formation, except for the minimum path length [4].
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 [5].
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 [2, 4].
Methods of forming transport routes are divided into several groups. They include
[8-10]:
1. Exact methods - give the greatest accuracy of the result, but require a lot of time
and resources. These include: the branch and bound method, the clipping branch
method, the exhaustive search method [8];
2. Heuristic methods - require less time, but do not give such accuracy, but it is quite
large. Among them: Clark-Wright algorithm, a method based on coincidences;
sweeping algorithm and the like [2, 7];
3. Metaheuristic methods - based on a more thorough study of the most promising
parts of the solution space. They give greater accuracy than heuristic methods. The
following algorithms exist: ant algorithm, wolf pack algorithm, genetic algorithm,
bee colony algorithm, swarm of particles, taboo search [3, 10].
The probabilistic component of metaheuristic methods gives them a significant ad-
vantage 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 re-
strictions, because, despite this, they may be in part of the solution domain with target
function with the best value [11-15].
For further research were selected Ant Colony Optimization method (АСО), Arti-
ficial Bee Colony method (АВС) [16-18, 21, 22].
3 Using of ACO and ABC methods for solving VRPTW
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 [16, 17].
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, find-
ing a trail of pheromones, go to the place of discovery, following the path and sup-
plementing 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 phero-
mones will remain on it, and it will be more attractive. Over time, the pheromones
erode and the trail loses its appeal [18-20].
Fig. 1. ACO method.
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 plac-
es 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 infor-
mation 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 surround-
ing space and the collection of nectar [21, 22].
Fig. 2. ABC method.
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 [4, 21, 22].
4 Modeling Results and Comparative Analysis of ACO and
ABC Methods
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 choos-
ing the next node [16-20].
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.
Fig. 3. The dependence of the results on α: a) the effectiveness of the use of spring; b) transport
load efficiency; c) deviations from the best found length; d) deviation from the best found time;
e) search time.
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 high-
est accuracy of the results is achieved when β = 0.6.
Fig. 4. The dependence of the results on β: a) the effectiveness of the use of spring; b) transport
load efficiency; c) deviations from the best found length; d) deviation from the best found time;
e) search time.
ABC method. In different sources and for different types of combinatorial optimi-
zation problems, a different ratio of different types of bees in the colony is recom-
mended. For the transport task in [4, 7, 23-25] it is recommended to choose the fol-
lowing ratio: 20% inactive bees, 50% active and 30% scout bees.
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.
Fig. 5. The dependence of the results on the total number of bees in the colony: a) the
effectiveness of the use of spring; b) transport load efficiency; c) deviations from the best found
length; d) deviation from the best found time.
Fig. 6 shows that the best accuracy in length is obtained at MV = 100, but the
search speed is better at MV = 200.
Fig. 6. The dependence of the results on the total number of bees in the colony: a) the effec-
tiveness of the use of spring; b) transport load efficiency; c) deviations from the best found
length; d) deviation from the best found time.
Next, these methods are compared according to criteria. Thus, the results of a
comparison of the two methods can be seen in Table 1.
Table 1. The result of a pairwise comparison of ABC and AСO methods.
Criterion АВС АСО
Deviation of route lengths from the best solution found by both methods *
Deviation of service time of routes from the best solution found by both methods *
Time efficiency in routes *
Transport load efficiency * *
Solution search time *
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.
5 Conclusions
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 meth-
od is more suitable for solving VRPTW according to most criteria.
References
1. Golden, B., Raghavan, S., Wasil, E.: The Vehicle Routing Problem: Latest Advances and
New Challenges. Springer, Boston, MA (2008). DOI: 10.1007/978-0-387-77778-8.
2. Liu, B.: Vehicle Routing Problem. In: Theory and Practice of Uncertain Programming.
Studies in Fuzziness and Soft Computing, vol. 239, pp. 147–155. Springer, Berlin, Heidel-
berg (2009). DOI: 10.1007/978-3-540-89484-1_10.
3. Pillay, N., Qu, R.: Vehicle Routing Problems. In: Hyper-Heuristics: Theory and Applica-
tions. Natural Computing Series, pp. 51–60. Springer, Cham (2018). DOI: 10.1007/978-3-
319-96514-7_7.
4. Marinakis, Y.: Metaheuristic Algorithms for the Vehicle Routing Problem. In: Floudas. C.,
Pardalos. P. (eds.) Encyclopedia of Optimization. Springer, Boston, MA (2008). DOI:
10.1007/978-0-387-74759-0
5. Pisinger, D., Ropke, S.: A general heuristic for vehicle routing problems. Computers, Op-
erations Research 34(8), 2403–2435 (2007). DOI: 10.1016/j.cor.2005.09.012.
6. Desrochers, M., Desrosiers, J., Solomon, M.: A Column Generation Algorithm for the Ve-
hicle Routing Problem with Time Windows. In: Akgül, M., Hamacher, H.W., Tüfekçi, S.
(eds.) Combinatorial Optimization, NATO ASI Series, vol. 82, pp. 249–252. Springer,
Berlin, Heidelberg (1992). DOI: 10.1007/978-3-642-77489-8_17.
7. Samarov, K.L.: Maths. The educational-methodical manual for students in the section
"Transport task". Training center "Resolvent", Moscow, Russia (2009). (in Russian).
8. Kondratenko, Y.P., Encheva, S.B., Sidenko, E.V.: Synthesis of Inelligent Decision Support
Systems for Transport Logistic. In: Proceeding of the 6th IEEE International Conference
on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Ap-
plications, IDAACS, vol. 2, pp. 642–646 (2011). DOI: 10.1109/IDAACS.2011.6072847.
9. Laporte, G.: The vehicle routing problem: An overview of exact and approximate algo-
rithms. European Journal of Operational Research 59(3), 345–358 (1992).
10. Chen, H.-K., Hsueh C.-F., Chang, M.-S.: Production scheduling and vehicle routing with
time windows for perishable food products. Computers & operations research 36(7), 2311–
2319 (2009).
11. Arbelaitz, O., Rodriguez, C., Zamakola I.: Low cost parallel solutions for the VRPTW op-
timization problem. In: Proceedings International Conference on Parallel Processing
Workshops, Spain (2002).
12. Werners, B., Kondratenko, Y.: Alternative Fuzzy Approaches for Efficiently Solving the
Capacitated Vehicle Routing Problem in Conditions of Uncertain Demands. In: Berger-
Vachon, C., Gil Lafuente, A., Kacprzyk, J., Kondratenko, Y., Merigó, J., Morabito,C.
(eds.) Complex Systems: Solutions and Challenges in Economics, Management and Engi-
neering. Studies in Systems, Decision and Control, vol. 125, pp. 521–543. Springer, Cham
(2018). DOI: 10.1007/978-3-319-69989-9_31.
13. Pureza, V.: Vehicle routing with multiple deliverymen: Modeling and heuristic approaches
for the VRPTW. European Journal of Operational Research 218(3), 636–647 (2012).
14. Schulze, J., Fahle, T.A.: A parallel algorithm for the vehicle routing problem with time
window constraints. Annals of Op. Research 86, 585–607 (1999).
15. Kondratenko, G.V., Kondratenko, Y.P., Romanov, D.O.: Fuzzy Models for Capacitive
Vehicle Routing Problem in Uncertainty. In: Proc. 17th International DAAAM Symposi-
um "Intelligent Manufacturing and Automation: Focus on Mechatronics & Robotics", pp.
205–206. Vienna, Austria (2006).
16. Dorigo, M., Gambardella, L.M.: Ant Colony System: A Cooperative Learning Approach to
the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation 1(1),
53–66 (1997).
17. Dorigo, M., Maniezzo V., Colorni, A.: Ant System: Optimization by a Colony of Cooper-
ating Agents. IEEE Trans. Sys., Man, Cybernetics 26, 29–41 (1996).
18. Shi, W., Weise, T.: An Initialized ACO for the VRPTW. Intelligent Data Engineering and
Automated Learning, 93–100 (2013).
19. Wang, Y.: A Hybrid Approach Based on Ant Colony System for the VRPTW. Advanced
Technology in Teaching. In: Proceedings of the 2009 3rd International Conference on
Teaching and Computational Science (WTCS 2009), pp. 327–333 (2009).
20. Qi, C., Sun, Y.: An improved ant colony algorithm for VRPTW. In: 2008 International
Conference on Computer Science and Software Engineering, pp. 455–458 (2008).
21. Basturk, B., Karaboga, D.: An Artificial Bee Colony (ABC) Algorithm for Numeric func-
tion Optimization. In: IEEE Swarm Intelligence Symposium (2006).
22. Karaboga, D., Basturk, B.: A powerful and efficient algorithm for numerical function op-
timization: artificial bee colony (ABC) algorithm. Journal of Global Optimization 39, 459–
471 (2007).
23. Kondratenko, Y.P., Klymenko, L.P., Sidenko, I.V.: Comparative Analysis of Evaluation
Algorithms for Decision-Making in Transport Logistics. In: Jamshidi, M., Kreinovich, V.,
Kazprzyk, J. (eds.) Advance Trends in Soft Computing, Series: Studies in Fuzziness and
Soft Computing, vol. 312, pp. 203–217 (2014). DOI: 10.1007/978-3-319-03674-8_20.
24. Encheva, S., Kondratenko, Y., Solesvik, M.Z., Tumin, S. Decision Support Systems in
Logistics. In: AIP Conference Proceedings 1060, 254–256 (2008). DOI:
10.1063/1.3037065.
25. Teodorović, D., Dell’Orco, M.: Bee colony optimization - a cooperative learning approach
to complex transportation problems. In: Proceedings of the 10th EWGT Meeting, Poznan,
pp. 13–16 (2005).