Login Register Cart 0
Generic placeholder image

Journal of Fuzzy Logic and Modeling in Engineering

Editor-in-Chief

ISSN (Print): 2666-2949
ISSN (Online): 2666-2957

Back
Journal Home About Journal Editorial Board Current Issue Volumes/Issues
Subscribe
Research Article

Multi-Shift Single-Vehicle Routing Problem Under Fuzzy Uncertainty During the COVID-19 Pandemic

Author(s): Francesco Nucci*

Volume 1, Issue 2, 2022

Published on: 06 September, 2022

Article ID: e100522204511 Pages: 12

DOI: 10.2174/2666294901666220510095557

Price: $65

conference banner
Abstract

Background: This work studies the single vehicle routing problem (VRP) with multishift and fuzzy uncertainty. In this case, a company perpetually exploits a vehicle to accomplish demand over a scheduling period of several work shifts. In our problem, a crew performs maintenance jobs at different locations. The working team operates in different shifts with a maximum duration but recurrently returns to the depot by the end of the shift to avoid overtime.

Methods: The objective is to minimize the number of shifts and the completion time (makespan). In addition, we analyze the influence of uncertainty in driving and processing times on the overtime avoidance constraint in shift duration. We develop an Artificial Immune Heuristic to determine optimal solutions considering both makespan and overtime avoidance. We implement a Pareto- based framework to evaluate the impact of uncertainty.

Results: We present several numerical case studies to examine the problem. In particular, we analyze different case study scenarios inferred from the environmental changes in travel and processing times observed in the Apulia region (SE Italy) during the COVID-19 lockdown periods that occurred in spring (started on March 9, 2020) and autumn (after November 6, 2020) of the year 2020.

Conclusion: The work program was revised as soon as the Italian COVID-19 restrictions were implemented in the spring and autumn of 2020 due to the changing environment. Our approach allowed for the rapid release of new robust maintenance programs. Results show significant improvements with the presented approach.

Keywords: Heuristics, Uncertainty, Scheduling, Problem Solving, Decision Making, COVID-19

Graphical Abstract

[1]
S.Y. Tan, and W.C. Yeh, "The vehicle routing problem: State-of-the-art classification and review", Appl. Sci. (Basel), vol. 11, no. 21, p. 10295, 2021.
[http://dx.doi.org/10.3390/app112110295]
[2]
S. Zangeneh-Khamooshi, Z.B. Zabinsky, and J.A. Heim, "A multi-shift vehicle routing problem with windows and cycle times", Optim. Lett., vol. 7, no. 6, pp. 1215-1225, 2013.
[http://dx.doi.org/10.1007/s11590-012-0497-1]
[3]
S. Nucamendi-Guillén, I. Martínez-Salazar, F. Angel-Bello, and J.M. Moreno-Vega, "A mixed integer formulation and an efficient metaheuristic procedure for the k-travelling repairmen problem", J. Oper. Res. Soc., vol. 67, no. 8, pp. 1121-1134, 2016.
[http://dx.doi.org/10.1057/jors.2015.113]
[4]
G. Onder, I. Kara, and T. Derya, "New integer programming formulation for multiple traveling repairmen problem", Transp. Res. Procedia, vol. 22, pp. 355-361, 2017.
[http://dx.doi.org/10.1016/j.trpro.2017.03.042]
[5]
I. Karaoğlan, "A branch-and-cut algorithm for the vehicle routing problem with multiple use of vehicles", Int. J. Lean Thinking, vol. 6, no. 1, 2015.
[6]
R. Bai, N. Xue, J. Chen, and G.W. Roberts, "A set-covering model for a bidirectional multi-shift full truckload vehicle routing problem", Transp. Res., Part B: Methodol., vol. 79, pp. 134-148, 2015.
[http://dx.doi.org/10.1016/j.trb.2015.06.002]
[7]
K. Sparks, C.L. Cooper, Y. Fried, and A. Shirom, The effects of working hours on health: A meta-analytic review.
From Stress to Wellbeing., Palgrave Macmillan UK: London, pp. vol. 1, 292-314, 2013. [http://dx.doi.org/10.1057/9781137310651_14]
[8]
C.C. Caruso, "Negative impacts of shiftwork and long work hours", Rehabil. Nurs., vol. 39, no. 1, pp. 16-25, 2014.
[http://dx.doi.org/10.1002/rnj.107] [PMID: 23780784]
[9]
G. Costa, "Shift work and health: Current problems and preventive actions", Saf. Health Work, vol. 1, no. 2, pp. 112-123, 2010.
[http://dx.doi.org/10.5491/SHAW.2010.1.2.112] [PMID: 22953171]
[10]
C. Lee, K. Lee, and S. Park, "Robust vehicle routing problem with deadlines and travel time/demand uncertainty", J. Oper. Res. Soc., vol. 63, no. 9, pp. 1294-1306, 2012.
[http://dx.doi.org/10.1057/jors.2011.136]
[11]
T.M. Cook, and R.A. Russell, "A simulation and statistical analysis of stochastic vehicle routing with timing constraints", Decis. Sci., vol. 9, no. 4, pp. 673-687, 1978.
[http://dx.doi.org/10.1111/j.1540-5915.1978.tb00753.x]
[12]
M. Gendreau, G. Laporte, and R. Séguin, "Stochastic vehicle routing", Eur. J. Oper. Res., vol. 88, no. 1, pp. 3-12, 1996.
[http://dx.doi.org/10.1016/0377-2217(95)00050-X]
[13]
G. Yaohuang, X. Binglei, and G. Qiang, "Overview of stochastic vehicle routing problems", J. Southwest Jiaotong Univ., vol. 10, no. 2, pp. 113-121, 2002.
[14]
M. Battarra, G. Erdogan, and D. Vigo, "Exact algorithms for the clustered vehicle routing problem", Oper. Res., vol. 62, no. 1, pp. 58-71, 2014.
[http://dx.doi.org/10.1287/opre.2013.1227]
[15]
C. Ma, W. Hao, R. He, X. Jia, F. Pan, J. Fan, and R. Xiong, "Distribution path robust optimization of electric vehicle with multiple distribution centers", PLoS One.
vol. 13, no. 3, pp. e0193789, 2018. [http://dx.doi.org/10.1371/journal.pone.0193789] [PMID: 29518169]
[16]
H. Zhao, W.A. Xu, R. Jiang, W. Xu, and R. Jiang, "The memetic algorithm for the optimization of urban transit network", Expert Syst. Appl., vol. 42, no. 7, pp. 3760-3773, 2015.
[http://dx.doi.org/10.1016/j.eswa.2014.11.056]
[17]
S. Bock, "Solving the traveling repairman problem on a line with general processing times and deadlines", Eur. J. Oper. Res., vol. 244, no. 3, pp. 690-703, 2015.
[http://dx.doi.org/10.1016/j.ejor.2015.02.009]
[18]
Z. Luo, H. Qin, and A. Lim, "Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints", Eur. J. Oper. Res., vol. 234, no. 1, pp. 49-60, 2014.
[http://dx.doi.org/10.1016/j.ejor.2013.09.014]
[19]
R. Schönfelder, M. Leucker, and S. Walther, Efficient Profile Routing for Electric Vehicles. In:.
R.C.H. Hsu, S. Wang, (eds) Internet of Vehicles-Technologies and Services. IOV 2014. Lecture Notes in Computer Science, vol 8662, Springer, Champp. 21-30, 2014. [http://dx.doi.org/10.1007/978-3-319-11167-4_3]
[20]
T. Athanasopoulos, and I. Minis, "Efficient techniques for the multi-period vehicle routing problem with time windows within a branch and price framework", Ann. Oper. Res., vol. 206, no. 1, pp. 1-22, 2013.
[http://dx.doi.org/10.1007/s10479-013-1366-8]
[21]
M. Baum, J. Dibbelt, T. Pajor, and D. Wagner, "Energy-optimal routes for electric vehicles", Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems - SIGSPATIAL’13, p. 2013, pp. 54-63, .
[http://dx.doi.org/10.1145/2525314.2525361]
[22]
T. Dewilde, D. Cattrysse, S. Coene, F.C.R. Spieksma, and P. Vansteenwegen, "Heuristics for the traveling repairman problem with profits", Comput. Oper. Res., vol. 40, no. 7, pp. 1700-1707, 2013.
[http://dx.doi.org/10.1016/j.cor.2013.01.003]
[23]
F. Angel-Bello, A. Alvarez, and I. García, "Two improved formulations for the minimum latency problem", Appl. Math. Model., vol. 37, no. 4, pp. 2257-2266, 2013.
[http://dx.doi.org/10.1016/j.apm.2012.05.026]
[24]
U. Derigs, M. Pullmann, U. Vogel, M. Oberscheider, M. Gronalt, and P. Hirsch, "Multilevel neighborhood search for solving full truckload routing problems arising in timber transportation", Electron. Notes Discrete Math., vol. 39, pp. 281-288, 2012.
[http://dx.doi.org/10.1016/j.endm.2012.10.037]
[25]
J. Xu, F. Yan, and S. Li, "Vehicle routing optimization with soft time windows in a fuzzy random environment", Transp. Res., Part E Logist. Trans. Rev., vol. 47, no. 6, pp. 1075-1091, 2011.
[http://dx.doi.org/10.1016/j.tre.2011.04.002]
[26]
C. Kahraman, B. Öztayşi, and S. Ç. Onar, "A comprehensive literature review of 50 years of fuzzy set theory", Int. J. Comput. Intell Syst..
vol. 9, no. sup1, pp. 3-24, 2016. [http://dx.doi.org/10.1080/18756891.2016.1180817]
[27]
D. Teodorović, and G. Pavković, "The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain", Fuzzy Sets Syst., vol. 82, no. 3, pp. 307-317, 1996.
[http://dx.doi.org/10.1016/0165-0114(95)00276-6]
[28]
K.K. Tan, and K.Z. Tang, "Vehicle dispatching system based on Taguchi-tuned fuzzy rules", Eur. J. Oper. Res., vol. 128, no. 3, pp. 545-557, 2001.
[http://dx.doi.org/10.1016/S0377-2217(99)00373-2]
[29]
L. de C.T. Gomes, and F.J. Von Zuben, "Multiple criteria optimization based on unsupervised learning and fuzzy inference applied to the vehicle routing problem", J. Intell. Fuzzy Syst. Appl. Eng. Technol., vol. 13, no. 2-4, pp. 143-154, 2002.
[30]
Y. He, and J. Xu, "A class of random fuzzy programming model and its application to vehicle routing problem", World J. Modelling Simulation, vol. 1, no. 1, pp. 3-11, 2005.
[31]
D. Sáez, C.E. Cortés, and A. Núñez, "Hybrid adaptive predictive control for the multi-vehicle dynamic pick-up and delivery problem based on genetic algorithms and fuzzy clustering", Comput. Oper. Res., vol. 35, no. 11, pp. 3412-3438, 2008.
[http://dx.doi.org/10.1016/j.cor.2007.01.025]
[32]
S.F. Ghannadpour, S. Noori, R. Tavakkoli-Moghaddam, and K. Ghoseiri, "A multi-objective dynamic vehicle routing problem with fuzzy time windows: Model, solution and application", Appl. Soft Comput., vol. 14, pp. 504-527, 2014.
[http://dx.doi.org/10.1016/j.asoc.2013.08.015]
[33]
A.G.N. Novaes, E.T. Bez, P.J. Burin, and D.P. Aragão Jr, "Dynamic milk-run OEM operations in over-congested traffic conditions", Comput. Ind. Eng., vol. 88, no. C, pp. 326-340, 2015.
[http://dx.doi.org/10.1016/j.cie.2015.07.010]
[34]
D. Muñoz-Carpintero, D. Sáez, C.E. Cortés, and A. Núñez, "A methodology based on evolutionary algorithms to solve a dynamic pickup and delivery problem under a hybrid predictive control approach", Transport. Sci., vol. 49, no. 2, pp. 239-253, 2015.
[http://dx.doi.org/10.1287/trsc.2014.0569]
[35]
H. Ewbank, P. Wanke, and A. Hadi-Vencheh, "An unsupervised fuzzy clustering approach to the capacitated vehicle routing problem", Neural Comput. Appl., vol. 27, no. 4, pp. 857-867, 2016.
[http://dx.doi.org/10.1007/s00521-015-1901-4]
[36]
Z. Zhu, J. Xiao, S. He, Z. Ji, and Y. Sun, "A multi-objective memetic algorithm based on locality-sensitive hashing for one-to-many-to-one dynamic pickup-and-delivery problem", Inf. Sci., vol. 329, no. C, pp. 73-89, 2016.
[http://dx.doi.org/10.1016/j.ins.2015.09.006]
[37]
M. Huiru, J. Limin, Z. Xingchen, M. Jianrui, and S. Jiandong, "Travelling salesman problem in uncertain environments", Open Cybern. Systemics J., vol. 9, no. 1, pp. 313-317, 2015.
[http://dx.doi.org/10.2174/1874110X01509010313]
[38]
M. Avci, and M.G. Avci, "A GRASP with iterated local search for the traveling repairman problem with profits", Comput. Ind. Eng., vol. 113, pp. 323-332, 2017.
[http://dx.doi.org/10.1016/j.cie.2017.09.032]
[39]
E. Zamorano, and R. Stolletz, "Branch-and-price approaches for the multiperiod technician routing and scheduling problem", Eur. J. Oper. Res., vol. 257, no. 1, pp. 55-68, 2017.
[http://dx.doi.org/10.1016/j.ejor.2016.06.058]
[40]
X. Chen, M. Hewitt, and B.W. Thomas, "An approximate dynamic programming method for the multi-period technician scheduling problem with experience-based service times and stochastic customers", Int. J. Prod. Econ., vol. 196, pp. 122-134, 2018.
[http://dx.doi.org/10.1016/j.ijpe.2017.10.028]
[41]
D.M. Miranda, and S.V. Conceição, "The vehicle routing problem with hard time windows and stochastic travel and service time", Expert Syst. Appl., vol. 64, pp. 104-116, 2016.
[http://dx.doi.org/10.1016/j.eswa.2016.07.022]
[42]
S. Yalçındağ, A. Matta, E. Şahin, and J.G. Shanthikumar, "The patient assignment problem in home health care: Using a data-driven method to estimate the travel times of care givers", Flex. Serv. Manuf. J., vol. 28, no. 1-2, pp. 304-335, 2016.
[http://dx.doi.org/10.1007/s10696-015-9222-6]
[43]
J.C. Rivera, H.M. Afsar, and C. Prins, "A multistart iterated local search for the multitrip cumulative capacitated vehicle routing problem", Comput. Optim. Appl., vol. 61, no. 1, pp. 159-187, 2015.
[http://dx.doi.org/10.1007/s10589-014-9713-5]
[44]
E.L. Solano-Charris, C. Prins, and A.C. Santos, Heuristic Approaches for the Robust Vehicle Routing Problem., Springer: Cham, 2014, pp. 384-395.
[http://dx.doi.org/10.1007/978-3-319-09174-7_33]
[45]
X. Chen, B.W. Thomas, and M. Hewitt, "The technician routing problem with experience-based service times", Omega, vol. 61, no. C, pp. 49-61, 2016.
[http://dx.doi.org/10.1016/j.omega.2015.07.006]
[46]
F. Nucci, Multi-shift single-vehicle routing problem under fuzzy uncertainty., Intell. Techniq. Smart Innov. Solut, 2021, pp. 1620-1627.
[http://dx.doi.org/10.1007/978-3-030-51156-2_189]
[47]
C. Kahraman, S.C. Onar, and B. Oztaysi, "Fuzzy multicriteria decision-making: A literature review", Int. J. Comput. Int. Syst., vol. 8, no. 4, pp. 637-666, 2015.
[http://dx.doi.org/10.1080/18756891.2015.1046325]
[48]
M. Köppen, and C. Veenhuis, "Multi-objective particle swarm optimization by fuzzy-pareto-dominance meta-heuristic", Int. J. Hybrid Intell. Syst., vol. 3, no. 4, pp. 179-186, 2006.
[http://dx.doi.org/10.3233/HIS-2006-3401]
[49]
J.C.Y. Zheng, and J. Chen, "A modified multi-objective particle swarm optimization approach and its application to the design of a deepwater composite riser", Acta Mech. Sin., vol. 34, no. 2, pp. 275-284, 2018.
[http://dx.doi.org/10.1007/s10409-017-0703-6]
[50]
Y. Zheng, B. Han, J. Chen, J. Zhong, and J. Li, "Maximizing the load carrying capacity of a variable stiffness composite cylinder based on the multi-objective optimization method", Int. J. Comput. Methods, p. vol. 18, no. 5, pp. 2150001, 2020, .
[http://dx.doi.org/10.1142/S0219876221500018]
[51]
M. Hapke, A. Jaszkiewicz, and R. Słowiński, "Pareto simulated annealing for fuzzy multi-objective combinatorial optimization", J. Heuristics, vol. 6, no. 3, pp. 329-345, 2000.
[http://dx.doi.org/10.1023/A:1009678314795]
[52]
A.A. Aguilar-Lasserre, L. Pibouleau, C. Azzaro-Pantel, and S. Domenech, "Enhanced genetic algorithm-based fuzzy multiobjective strategy to multiproduct batch plant design", Appl. Soft Comput., vol. 9, no. 4, pp. 1321-1330, 2009.
[http://dx.doi.org/10.1016/j.asoc.2009.05.005]
[53]
N. Giannopoulos, V.C. Moulianitis, and A.C. Nearchou, "Multi-objective optimization with fuzzy measures and its application to flow-shop scheduling", Eng. Appl. Artif. Intell., vol. 25, no. 7, pp. 1381-1394, 2012.
[http://dx.doi.org/10.1016/j.engappai.2012.06.011]
[54]
O. Bahri, E.G. Talbi, and N. Ben Amor, "A generic fuzzy approach for multi-objective optimization under uncertainty", Swarm Evol. Comput., vol. 40, pp. 166-183, 2018.
[http://dx.doi.org/10.1016/j.swevo.2018.02.002]
[55]
J. Al-Enezi, M. Abbod, and S. Alsharhan, "Artificial immune systems - models, algorithms and applications", Int. J. Res. Rev Appl. Sci., vol. 3, no. 2, pp. 118-131, 2010.
[56]
D. Corus, P.S. Oliveto, and D. Yazdani, "When hypermutations and ageing enable artificial immune systems to outperform evolutionary algorithms", Theor. Comput. Sci., vol. 832, pp. 166-185, 2020.
[http://dx.doi.org/10.1016/j.tcs.2019.03.002]
[57]
J. Liu, Q. Zhi, H. Ji, B. Li, and S. Lei, "Wheel hub customization with an interactive artificial immune algorithm", J. Intell. Manuf., vol. 32, no. 5, pp. 1305-1322, 2021.
[http://dx.doi.org/10.1007/s10845-020-01613-x]
[58]
A. Bagheri, M. Zandieh, I. Mahdavi, and M. Yazdani, "An artificial immune algorithm for the flexible job-shop scheduling problem", Future Gener. Comput. Syst., vol. 26, no. 4, pp. 533-541, 2010.
[http://dx.doi.org/10.1016/j.future.2009.10.004]
[59]
M. Mobini, Z. Mobini, and M. Rabbani, "An artificial immune algorithm for the project scheduling problem under resource constraints", Appl. Soft Comput., vol. 11, no. 2, pp. 1975-1982, 2011.
[http://dx.doi.org/10.1016/j.asoc.2010.06.013]
[60]
D. Corus, P.S. Oliveto, and D. Yazdani, "Fast Artificial Immune Systems” In: A. Auger, C. Fonseca, N. Lourenço, P. Machado, L. Paquete, D. Whitley, (eds) Parallel Problem Solving from Nature - PPSN XV. Lecture Notes in Computer Science, Springer, Cham",
[http://dx.doi.org/10.1007/978-3-319-99259-4_6]
[61]
K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II", IEEE Trans. Evol. Comput., vol. 6, no. 2, pp. 182-197, 2002.
[http://dx.doi.org/10.1109/4235.996017]
[62]
E. Zitzler, M. Laumanns, and L. Thiele, "SPEA2 - Improving the strength pareto evolutionary algorithm", TIK-Report, p. vol. 103, 2001, .
[http://dx.doi.org/10.3929/ethz-a-004284029]
[63]
E. Zitzler, and S. Künzli, Indicator-Based Selection in Multiobjective SearchPPSN VIII., Berlin, Heidelberg, 2004, pp. 832-842.
[http://dx.doi.org/10.1007/978-3-540-30217-9-84]
[64]
X. Sun, L. Zhao, P. Zhang, L. Bao, and Y. Chen, "Enhanced NSGA-II with evolving directions prediction for interval multi-objective optimization", Swarm Evol. Comput., vol. 49, pp. 124-133, 2019.
[http://dx.doi.org/10.1016/j.swevo.2019.05.009]
[65]
I. Anthony, S. Nggada, and J. Quenum, Distributed Optimisation of Perfect Preventive Maintenance and Component Replacement Schedules Using, vol. SPEA2, In:.
P. Vasant, I. Zelinka, G.W. Weber, (eds) Intelligent Computing and Optimization. ICO 2020. Advances in Intelligent Systems and Computing, vol 1324. Springer, Cham. pp. 297- 310, 2021. [http://dx.doi.org/10.1007/978-3-030-68154-8_29]
[66]
T. Hale, N. Angrist, R. Goldszmidt, B. Kira, A. Petherick, T. Phillips, S. Webster, E. Cameron-Blake, L. Hallas, S. Majumdar, and H. Tatlow, "A global panel database of pandemic policies (Oxford COVID-19 Government Response Tracker)", Nat. Hum. Behav., vol. 5, no. 4, pp. 529-538, 2021.
[http://dx.doi.org/10.1038/s41562-021-01079-8] [PMID: 33686204]
[67]
A. Wiśniewska, S. Bernard, J. Burn-Murdoch, T. Hannen, B. Haslett, C. Nevitt, J. Pong, E. Rininsland, A. Smith, M. Stabe, and C. Tilford, Lockdowns compared: Tracking governments’ coronavirus responses., Financial Time, 2021.

Rights & Permissions Print Cite
Article Metrics
1
© 2024 Bentham Science Publishers | Privacy Policy