Optimizing Vehicle Routing with Soft Time Windows Using a Hybrid Genetic Algorithm
DOI:
https://doi.org/10.36456/tibuana.9.1.10931Keywords:
Distribution Routing Optimization; VRPTW; Nearest Insertion Heuristic; Hybrid Genetic Algorithm; Soft Time Windows; Total cost minimization.Abstract
Determining delivery routes that
minimize total cost is a key issue in goods
distribution. This study focuses on a bottled
drinking water (AMDK) company in City X that
distributes its products to multiple retail outlets with
different service time requirements. Such conditions
fall within the scope of the Vehicle Routing Problem
with Time Windows (VRPTW). In this study, a soft
time windows approach is adopted, allowing vehicles
to serve retailers beyond their specified time limits
at the expense of penalty costs. The main objective is
to identify optimal delivery routes under the soft
time windows policy while minimizing total cost. The
results demonstrate that the Hybrid Genetic
Algorithm outperforms the initial solution in terms
of total cost reduction. The initial routes are
generated using the Nearest Insertion Heuristic and
subsequently refined through mutation processes
within the genetic algorithm framework.
References
N. R. Putri, B. R. Christata, and R. Primadasa,
"Usulan Rute Pengiriman Es Kristal
Menggunakan Algoritme Sweep dan Algoritme
Nearest Neighbor (Studi Kasus: UMKM XYZ
Kudus)," Jurnal Rekayasa Industri (JRI), vol. 7,
no. 2, 2025.
[2] Z. Ma, J. Zhang, H. Wang, and S. Gao,
"Optimization of Sustainable Bi-Objective ColdChain
Logistics Route Considering Carbon
Emissions and Customers’ Immediate Demands
in China," Sustainability, vol. 15, no. 7, p. 5946.
doi: https://doi.org/10.3390/su15075946
[3] B. Kallehauge, J. Larsen, O. B. G. Madsen, and
M. M. Solomon, "Vehicle Routing Problem with
Time Windows," in Column Generation, G.
Desaulniers, J. Desrosiers, and M. M. Solomon,
Eds. Boston, MA: Springer US, 2005, pp. 67-98.
[4] L. J. Tan, F. Y. Lin, and H. Wang, "BFO
Optimization Algorithms for Vehicle Routing
Problem with Time Windows," Applied
Mechanics and Materials, vol. 543-547, pp.
1884-1887, 2014.
[5] R. Tavakkoli-Moghaddam, M. Gazanfari, M.
Alinaghian, A. Salamatbakhsh, and N. Norouzi,
"A new mathematical model for a competitive
vehicle routing problem with time windows
solved by simulated annealing," Journal of
Manufacturing Systems, vol. 30, no. 2, pp. 83-92,
2011/04/01/ 2011.
[6] D. Mester and O. Bräysy, "Active guided
evolution strategies for large-scale vehicle
routing problems with time windows,"
Computers & Operations Research, vol. 32, no.
6, pp. 1593-1614, 2005/06/01/ 2005.
[7] S. Frifita and M. Masmoudi, "VNS methods for
home care routing and scheduling problem with
temporal dependencies, and multiple structures
and specialties," International Transactions in
Operational Research, vol. 27, no. 1, pp. 291313,
2020/01/01
2020.
[8]
Z. Yudong, J. Genlin, W. Shuihua, P. Preetha, W.
William, and L. Elizabeth, "An Improved GA for
solving multiple depot VRP," in Proceedings of
the 2015 International Industrial Informatics and
Computer Engineering Conference, 2015, pp.
551-554: Atlantis Press.
[9] S. W. Chai, M. R. Kamaluddin, and M. F. F. Ab.
Rashid, "Optimisation of vehicle routing problem
with time windows using Harris Hawks
optimiser," Journal of Mechanical Engineering
and Sciences, vol. 16, no. 3, pp. 9056 - 9065,
%09/%28 2022.
[10] V. Katiyar, "Relative performance of certain
meta heuristics on vehicle routing problem with
time windows," International Journal of
Information Technology and Computer Science,
vol. 7, no. 12, pp. 40-49, 2015.
[11] S. Masrom, S. Z. Z. Abidin, N. Omar, K. Nasir,
and A. S. Abd Rahman, "Dynamic
parameterization of the particle swarm
optimization and genetic algorithm hybrids for
vehicle routing problem with time window,"
International Journal of Hybrid Intelligent
Systems, vol. 12, no. 1, pp. 13-25, 2015/02/01
2015.
[12] R. Lakshmi and K. Vivekanandan, "Performance
analysis of a novel crossover technique on
permutation encoded genetic algorithms," in
2014 International Conference on Advances in
Engineering and Technology (ICAET), 2014, pp.
1-4.
[13] M. Srinivas and L. M. Patnaik, "Adaptive
probabilities of crossover and mutation in genetic
algorithms," IEEE Transactions on Systems,
Man, and Cybernetics, vol. 24, no. 4, pp. 656667,
1994.
[14]
R. E. N. Chunyu, "Applying Genetic Algorithm
for Capacitated Vehicle Routing Problem," in
Proceedings of the 2nd International Conference
on Electronic & Mechanical Engineering and
Information Technology (EMEIT 2012), 2012,
pp. 519-522: Atlantis Press.
[15] C. ShengBing, X. FengYing, L. LongShu, C.
ShengBing, and L. LongShu, "A Novel
Ecological Competitive Genetic Algorithm," in
2008 International Symposium on Information
Science and Engineering, 2008, vol. 2, pp. 585590.
[16]
K. Sun, Y. Gu, K. Wan Fei Ma, C. Zheng, and F.
Wu, "Medical Supplies Delivery Route
Optimization under Public Health Emergencies
Incorporating Metro-based Logistics System,"
Transportation Research Record, vol. 2678, no.
7, pp. 111-131, 2024/07/01 2024.
[17] P. Toth and D. Vigo, Vehicle routing: problems,
methods, and applications. SIAM, 2014.
[18] D. A. Coley, An introduction to genetic
algorithms for scientists and engineers. World
Scientific Publishing Company, 1999.
[19] S. Joshi and S. Kaur, "Nearest neighbor insertion
algorithm for solving capacitated vehicle routing
problem," pp. 86-88: IEEE.
[20] K. Ghoseiri and S. F. Ghannadpour, "Multiobjective
vehicle routing problem with time
windows using goal programming and genetic
algorithm," Applied Soft Computing, vol. 10, no.
4, pp. 1096-1107, 2010.
[21] L. Jianjun and L. Jian, "A modified particle
swarm optimization for practical engineering
optimization," 2009, vol. 3, pp. 177-180: IEEE,
2009.
[22] A. R. Komijan and D. Delavari, "Vehicle routing
and scheduling problem for a multi-period, multiperishable
product system with time window: A case study,"
International Journal of Production Management and Engineering,
vol. 5, no. 2, pp. 45-53, 2017.
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Tibuana : Journal of Applied Industrial Engineering
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
