Ground Vehicle and UAV Collaborative Routing and Scheduling for Humanitarian logistics using Random Walk Based Ant Colony Optimization

Document Type : Article

Authors

1 Computer Science and Engineering Department, Maharishi Markandeshwar (Deemed) University, Mullana, India

2 Computer Science Department, Government College, Naraingarh, Ambala, India

3 Computer Science Engineering Department, Punjabi University, Patiala, India

Abstract

A well-planned humanitarian logistics involving rescuing people and providing on-time lifesaving facilities to disaster-affected areas can significantly mitigate the aftermath of disasters. However, damaged bridges and blocked roads can hinder last-mile deliveries in disaster-affected areas by ground vehicles only. So, in this paper, we propose a ground vehicle (GV) and unmanned air vehicle (UAV) collaborative delivery system in such areas. Here, a fleet of homogenous ground vehicles each equipped with a certain number of UAVs is deployed for last-mile deliveries. UAVs make the flight from GVs, deliver to end locations and return to the GV for battery replacement and/or start another flight. The objective of the model is to minimize the total delivery time within UAV flight endurance and payload constraints. Firstly K-means clustering algorithm has been used to cluster the disaster-affected region into different sectors. Then GV_Touring and UAV_Routing have been scheduled using nearest neighbor heuristic to serve ground approachable locations and UAV served locations respectively. Finally, the random walk based ant colony optimization-based (ACS_RW) has been developed to further optimize the overall travel time. Experimentation results show the potential benefits of the proposed algorithm over other available truck-drone collaborative transportation models.

Keywords

References

References
[1]      Luo,Z., Liu, Z., and Shi, J. , “A Two-Echelon Cooperated Routing Problem for a Ground Vehicle and Its Carried Unmanned Aerial Vehicle,” Sensors (Basel)., vol. 17, no. 5, 2017.
[2]      Ferrandez , S. M., Harbison, T., Weber, T., Sturges, R., and Rich, R., “Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm,” J. Ind. Eng. Manag., vol. 9, no. 2, pp. 374–388, 2016.
[3]      Murray, C. C. and Chu, A. G., “The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery,” Transp. Res. Part C Emerg. Technol., vol. 54, pp. 86–109, 2015.
[4]      Kenneth, S., “Metaheuristics — the metaphor exposed,” Int. Trans. Oper. Res., vol. 22, no. 1, pp. 3–18, 2015.
[5]      Akbarpour, N., Kia,R., and Hajiaghaei-keshteli, M., “A new bi-objective integrated vehicle transportation model considering simultaneous pick-up and split delivery,” Sci. Iran., pp. 1–32, 2020.
[6]      Yegane, B. Y., Kamalabadi, I. N., and Farughi, H., “Influence of two different producers in a competitive location problem,” Sci. Iran., vol. 27, 2020.
[7]      Peng, H., Ying, C., Tan, S., Hu, B., and Sun, Z., “An Improved Feature Selection Algorithm Based on Ant Colony Optimization,” IEEE Access, vol. 6, pp. 69203–69209, 2018.
[8]      Deng, W., Xu, J., and Zhao, H., “An improved ant colony optimization algorithm based on immunization strategy,” IEEE Access, vol. 7, pp. 20281–20292, 2019.
[9]      Goel, R. K. and Bansal, S. Rani, Hybrid algorithms for rich vehicle routing problems: a survey. Elsevier Inc., 2020.
[10]    Jovanovic, R., Tuba, M., and Voß, S.,  “An efficient ant colony optimization algorithm for the blocks relocation problem,” Eur. J. Oper. Res., vol. 274, no. 1, pp. 78–90, 2019.
[11]    American Red Cross, “Drones for Disaster Response and Relief Operations,” no. April, p. 51, 2015.
[12]    Mosterman, P. J., Sanabria, D. E., Bilgin, E., Zhang, K., and Zander, J., “A heterogeneous fleet of vehicles for automated humanitarian missions,” Comput. Sci. Eng., vol. 16, no. 3, pp. 90–95, 2014.
[13]    Chowdhury, S., Emelogu, A., Marufuzzaman, M., Nurre, S. G.,  and Bian, L., “Drones for disaster response and relief operations: A continuous approximation model,” Int. J. Prod. Econ., vol. 188, no. February, pp. 167–184, 2017.
[14]    Rabta, B., Wankmüller, C., and Reiner, G., “A drone fleet model for last-mile distribution in disaster relief operations,” Int. J. Disaster Risk Reduct., vol. 28, no. August 2017, pp. 107–112, 2018.
[15]    Silva, L. de O., Bandeira, R. A. de M. and Campos, V. B. G.  “Proposal to planning facility location using UAV and geographic information systems in a post-disaster scenario,” Int. J. Disaster Risk Reduct., vol. 36, no. February, p. 101080, 2019.
[16]    Chauhan, D., Unnikrishnan, A., and Figliozzi, M., “Maximum coverage capacitated facility location problem with range constrained drones,” Transp. Res. Part C Emerg. Technol., vol. 99, no. December, pp. 1–18, 2019.
[17]    Kitjacharoenchai, P.,  Ventresca, M., Moshref-Javadi, M., Lee, S., Tanchoco, J. M. A., and Brunese, P. A., “Multiple traveling salesman problem with drones: Mathematical model and heuristic approach,” Comput. Ind. Eng., vol. 129, no. June 2018, pp. 14–30, 2019.
[18]    Murray, C. C. and Raj,R., “The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones,” Transp. Res. Part C Emerg. Technol., vol. 110, no. February 2019, pp. 368–398, 2020.
[19]    Liu,Y.,  Liu,Z., Shi,J., Wu,G., and Pedrycz,W., “Two-Echelon Routing Problem for Parcel Delivery by Cooperated Truck and Drone,” IEEE Trans. Syst. Man, Cybern. Syst., no. September 2016, pp. 1–16, 2020.
[20]    Abbatecola,L., Fanti, M. P., Fellow,I., Pedroncelli,G., Ukovich,W. and Ieee,M.,“A New Cluster-Based Approach for the Vehicle Routing Problem with Time Windows,” in 2018 IEEE 14th International Conference on Automation Science and Engineering (CASE), 2018, pp. 744–749.
[21]    Nalepa, J. and Blocho, M., “Adaptive guided ejection search for pickup and delivery with time windows,” J. Intell. Fuzzy Syst., vol. 32, no. 2, pp. 1547–1559, 2017.
[22]    Alparslan, A. and Science, T., “COMPARISON OF DIFFERENT CLUSTERING,” Int j simul Model, vol. 18, no. 4, pp. 574–585, 2019.
[23]    Liu, J., Yang, J., Liu, H., Tian, X. and Gao, M., “An improved ant colony algorithm for robot path planning,” Soft Comput., vol. 21, no. 19, pp. 5829–5839, 2017.
[24]    Kamaruzaman, A. F. and Zain, A. M.  “Levy Flight Algorithm for Optimization Problems – A Literature Review Levy Flight Algorithm for Optimization Problems – A Literature Review,” no. September, 2013.
[25]    Goel, R. and Maini, R. “A hybrid of ant colony and firefly algorithms ( HAFA ) for solving vehicle routing problems,” vol. 25, pp. 28–37, 2018.
[26]    Goel, R. and Maini, R. and Bansal, S. “Vehicle routing problem with time windows having stochastic customers demands and stochastic service times : Modelling and solution,” J. Comput. Sci., vol. 34, pp. 1–10, 2019.
[27]    Zhu, H., You, X. and Liu, S. “Multiple Ant Colony Optimization Based on Pearson Correlation Coefficient,” IEEE Access, vol. 7, pp. 61628–61638, 2019.
[28]    Metawa, U. J, N., Shankar, K.  and Lakshmanaprabu, S. K., “Financial crisis prediction model using ant colony optimization,” Int. J. Inf. Manage., vol. 50, no. November 2018, pp. 538–556, 2020.
[29]    Bansal, S. Rani, Goel, R. K., and Maini, R., “An improved ant colony algorithm based on levy flight distribution,” Adv. Math. Sci. J., vol. 9, no. 6, pp. 3907–3916, 2020.
[30]    Li, Y., Soleimani, H. and Zohal, M. “An improved ant colony optimization algorithm for the multi-depot green vehicle routing problem with multiple objectives,” J. Clean. Prod., 2019.
[31]    Rao, T. S., “An Ant Colony and Simulated Annealing Algorithm with Excess Load VRP in a FMCG Company,” in IOP Conference Series: Materials Science and Engineering, Volume 577, International Conference on Advances in Materials and Manufacturing Applications (IConAMMA-2018) 16–18 August 2018, Bengaluru, India, 2019.
Scientia Iranica
Volume 29, Issue 2
Transactions on Computer Science & Engineering and Electrical Engineering (D)
March and April 2022
Pages 632-644

Files

History

  • Receive Date: 12 May 2021
  • Revise Date: 20 August 2021
  • Accept Date: 01 November 2021

Share

How to cite

Statistics