A Novel Framework for Solving the Optimal Path Problem in Collaborative Consignment Delivery Systems Using Drones

Agatz, N., Campbell, A.M., Fleischmann, M., Savels, M.: Challenges and opportunities in attended home delivery. The Vehicle Routing Problem: Latest Advances and New Challenges - Operations Research/Computer Science Interfaces 43, 379–96 (2008) Ahmadyfard, A., Modares, H.: Combining pso and k-means to enhance data clustering. In: 2008 international symposium on telecommunications, pp. 688–91 (2008). https://doi.org/10.1109/ISTEL.2008.4651388 Ahmed, M., Seraj, R., Islam, S.M.S.: The k-means algorithm: A comprehensive survey and performance evaluation. Electronics 9(8) (2020). https://doi.org/10.3390/electronics9081295. https://www.mdpi.com/2079-9292/9/8/1295 Akeb, H., Bouchakhchoukha, A., Hifi, M.: A three-stage heuristic for the capacitated vehicle routing problem with time windows, pp. 1–19. Springer International Publishing, Cham (2015). https://doi.org/10.1007/978-3-319-12631-9_1 Applegate, D., Bixby, R., Chvatal, V., Cook, W.: Concorde tsp solver. online. http://www.math.uwaterloo.ca/tsp/concorde/index.html Armano, G., Farmani, M.R.: Multiobjective clustering analysis using particle swarm optimization. Expert Systems with Applications 55, 184–193 (2016). https://doi.org/10.1016/j.eswa.2016.02.009. https://www.sciencedirect.com/science/article/pii/S0957417416 30032X Arthur, D., Vassilvitskii, S.: k-means++: the advantages of careful seeding. In: SODA ’07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 1027–1035. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2007) Barnhart, C., Laporte, G.: Handbooks in operations research & management science: Transportation. Transportation 14 (2007) Battarra, M., Erdogan, G., Vigo, D.: Exact algorithms for the clustered vehicle routing problem. Operations Research 62, 58–71 (2014). https://doi.org/10.1287/opre.2013.1227 Bent, R., Hentenryck, P.V.: A two-stage hybrid local search for the vehicle routing problem with time windows. Department of Computer Science, Brown University, Tech. rep. (2001) Bradley, P.S., Fayyad, U.M.: Refining initial points for K-Means clustering. In: Proc. 15th international Conf. on machine learning, pp. 91–99. Morgan Kaufmann, San Francisco, CA (1998) Budka, M.: Clustering as an example of optimizing arbitrarily chosen objective functions. Advanced Methods for Computational Collective Intelligence 457, 177–86 (2013) Chen, R.M., Hsieh, F.R., Wu, D.S.: Heuristics based ant colony optimization for vehicle routing problem. In: 2012 7th IEEE conference on industrial electronics and applications (ICIEA), pp. 1039–1043 (2012). https://doi.org/10.1109/ICIEA.2012.6360876 Chen, S.M., Chien, C.Y.: A new method for solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques. In: 2010 international conference on machine learning and cybernetics, vol. 5, pp. 2477–2482 (2010). https://doi.org/10.1109/ICMLC.2010.5580809 Cheng, D., Zhu, Q., Huang, J., Wu, Q., Yang, L.: A novel cluster validity index based on local cores. IEEE Trans. Neural Netw. Learn. Syst. 30(4), 985–999 (2019). https://doi.org/10.1109/TNNLS.2018.2853710 Chiang, W.C., Li, Y., Shang, J., Urban, T.L.: Impact of drone delivery on sustainability and cost: Realizing the uav potential through vehicle routing optimization. Appl. Energy 242, 1164–1175 (2019). https://doi.org/10.1016/j.apenergy.2019.03.117. https://www.sciencedirect.com/science/article/pii/S0306261919 305252 Cosma, O., Pop, P., Sitar, C.: A two-level based genetic algorithm for solving the soft-clustered vehicle routing problem. Carpathian Journal of Mathematics 38, 117–128 (2021). https://doi.org/10.37193/CJM.2022.01.09 Dalatu, P.I.: Time complexity of k-means and k-medians clustering algorithms in outliers detection. Global J. Pure Appl. Math. 12(5), 4405–4418 (2016) Dantzig, G., Fulkerson, R., Johnson, S.: Solution of a large-scale traveling-salesman problem. Operations Research 2, 393–410 (1954) Delin, L., Lixiao, Z., Zhihui, X.: Heuristic simulated annealing genetic algorithm for traveling salesman problem. In: 2011 6th international conference on computer science education (ICCSE), pp. 260–264 (2011). https://doi.org/10.1109/ICCSE.2011.6028630 Dorling, K., Heinrichs, J., Messier, G.G., Magierowski, S.: Vehicle routing problems for drone delivery. IEEE Trans. Syst. Man Cybern. Syst. 47(1), 70–85 (2017). https://doi.org/10.1109/TSMC.2016.2582745 Duvvada, H.P., Naidu, G.D.R., Sri, V.D.: K-means cluster analysis of cities based on their inter-distances. Int. J. Eng. Develop. Res. 5(4), 1356–1363 (2017) Expósito-Izquierdo, C., Rossi, A., Sevaux, M.: A two-level solution approach to solve the clustered capacitated vehicle routing problem. Comput. Indust. Eng. 91, 274–289 (2016). https://doi.org/10.1016/j.cie.2015.11.022. https://www.sciencedirect.com/science/article/pii/S0360835215004684 Fränti, P., Sieranoja, S.: How much can k-means be improved by using better initialization and repeats? Pattern Recogn. 93, 95–112 (2019) Gatteschi, V., Lamberti, F., Paravati, G., Sanna, A., Demartini, C., Lisanti, A., Venezia, G.: New frontiers of delivery services using drones: A prototype system exploiting a quadcopter for autonomous drug shipments. In: 2015 IEEE 39th annual computer software and applications conference, vol. 2, pp. 920–927 (2015). https://doi.org/10.1109/COMPSAC.2015.52 Goodchildand, A., Toy, J.: Delivery by drone: An evaluation of unmanned aerial vehicle technology in reducing co2 emissions in the delivery service industry. Transportation Research Part D: Transport and Environment 61(A), 58–67 (2018) Gordon-Spears, D.F., Spears, W.M.: Analysis of a phase transition in a physics-based multiagent system. In: Formal approaches to agent-based systems, pp. 193–207. Springer, Berlin (2003) Hamerly, G., Elkan, C.: Alternatives to the k-means algorithm that find better clusterings. In: CIKM ’02: Proceedings of the eleventh international conference on Information and knowledge management, pp. 600–607. ACM, New York (2002). https://doi.org/10.1145/584792.584890 Hamerly, G., Elkan, C.: Alternatives to the k-means algorithm that find better clusterings. In: CIKM ’02: Proceedings of the eleventh international conference on Information and knowledge management, pp. 600–607. ACM, New York (2002). https://doi.org/10.1145/584792.584890. https://portal.acm.org/citation.cfm?id=584890 Hu, W., Liang, H., Peng, C., Du, B., Hu, Q.: A hybrid chaos-particle swarm optimization algorithm for the vehicle routing problem with time window. Entropy 15(4), 1247–1270 (2013). https://doi.org/10.3390/e15041247. https://www.mdpi.com/1099-4300/15/4/1247 Johannessen, K.A.: A conceptual approach to time savings and cost competitiveness assessments for drone transport of biologic samples with unmanned aerial systems (drones). Drones 6(3) (2022). https://doi.org/10.3390/drones6030062. https://www.mdpi.com/2504-446X/6/3/62 Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Proceedings of ICNN’95 - international conference on neural networks, vol. 4, pp. 1942–1948 (1995). https://doi.org/10.1109/ICNN.1995.488968 Khan, S.S., Ahmad, A.: Cluster center initialization algorithm for k-means algorithm. Pattern Recogn. Lett. 25(11), 1293–1302 (2004) Kim, S., Kwon, Y., Choi, S., Lee, J., Ko, S., Chung, B., Moon, I., Ko, C.: Development of mathematical models for parcel delivery service network design. Journal of the Korean Institute of Industrial Engineers 45, 203–212 (2019) Kitjacharoenchai, P., Ventresca, M., Moshref-Javadi, M., Lee, S., Tanchoco, J.M., Brunese, P.A.: Multiple traveling salesman problem with drones: Mathematical model and heuristic approach. Computers & Industrial Engineering 129, 14–30 (2019). https://doi.org/10.1016/j.cie.2019.01.020. https://www.sciencedirect.com/science/article/pii/S0360835219 300245 Kyriakakis, N.A., Stamadianos, T., Marinaki, M., Marinakis, Y.: The electric vehicle routing problem with drones: An energy minimization approach for aerial deliveries. Cleaner Logistics and Supply Chain 4, 100041 (2022). https://doi.org/10.1016/j.clscn.2022.100041. https://www.sciencedirect.com/science/article/pii/S2772390922 000142 Lawler, E.L.: The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley & sons (1985) Li, L., Wang, W., Xu, X.: Multi-objective particle swarm optimization based on global margin ranking. Inform. Sci. 375, 30–47 (2017). https://doi.org/10.1016/j.ins.2016.08.043. https://www.sciencedirect.com/science/article/pii/S0020025516 306156 Liu, F., Deng, Y.: Determine the number of unknown targets in open world based on elbow method. IEEE Trans. Fuzzy Syst. 29(5), 986–995 (2021). https://doi.org/10.1109/TFUZZ.2020.2966182 Liu, X., Zhang, B., Du, F.: Integrating relative coordinates with simulated annealing to solve a traveling salesman problem. In: 2014 Seventh international joint conference on computational sciences and optimization, pp. 177–180 (2014). https://doi.org/10.1109/CSO.2014.39 Lloyd, S.P.: Least squares quantization in pcm. IEEE Trans. Inform. Theory 28(2), 129–137 (1982) Marc, A.H., Fuksz, L., Pop, P.C., Dănciulescu, D.: A novel hybrid algorithm for solving the clustered vehicle routing problem. In: Onieva, E., Santos, I., Osaba, E., Quintián, H., Corchado, E. (eds.) Hybrid artificial intelligent systems, pp. 679–689. Springer International Publishing, Cham (2015) van der Merwe, D., Engelbrecht, A.: Data clustering using particle swarm optimization. In: The 2003 congress on evolutionary computation, 2003. CEC ’03., vol. 1, pp. 215–220 (2003). https://doi.org/10.1109/CEC.2003.1299577 Moshref-Javadi, M., Hemmati, A., Winkenbach, M.: A truck and drones model for last-mile delivery: A mathematical model and heuristic approach. Appl. Math. Model. 80, 290–318 (2020). https://doi.org/10.1016/j.apm.2019.11.020. https://www.sciencedirect.com/science/article/pii/S0307904X19 306936 Murray, C.C., Chu, A.G.: The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Research Part C: Emerging Technologies 54, 86–109 (2015). https://doi.org/10.1016/j.trc.2015.03.005 Nagata, Y., Bräysy, O., Dullaert, W.: A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows. Comput. Operat. Res. 37(4), 724–737 (2010). https://doi.org/10.1016/j.cor.2009.06.022. https://www.sciencedirect.com/science/article/pii/S0305054809 001762 Ochieng, W.O., Ye, T., Scheel, C., Lor, A., Saindon, J., Yee, S.L., Meltzer, M.I., Kapil, V., Karem, K.: Uncrewed aircraft systems versus motorcycles to deliver laboratory samples in west africa: a comparative economic study. Lancet Global Health 8(1) (2020). https://doi.org/10.1016/S2214-109X(19)30464-4 Pe\(\widetilde{n}\)a, J.M., Lozano, J.A., Larra\(\widetilde{n}\)aga, P.: An empirical comparison of four initialization methods for the k-means algorithm. Pattern Recogn. Lett. 20(10), 1027–1040 (1999). https://doi.org/10.1016/S0167-8655(99)00069-0 Pop, P., Chira, C.: A hybrid approach based on genetic algorithms for solving the clustered vehicle routing problem. In: 2014 IEEE congress on evolutionary computation (CEC), pp. 1421–1426 (2014). https://doi.org/10.1109/CEC.2014.6900422 Raykov, Y.P., Boukouvalas, A., Baig, F., Little, M.A.: What to do when k-means clustering fails: A simple yet principled alternative algorithm. PLOS ONE 11(9), 1–28 (2016). https://doi.org/10.1371/journal.pone.0162259 Rizkallah, L., Farouk, M., Darwish, N.: A clustering algorithm for solving the vehicle routing assignment problem in polynomial time. Int. J. Eng. Technol. 9 (2019). https://doi.org/10.14419/ijet.v9i1.22231 Rubin, S.H., Bouabana-Tebibel, T., Hoadjli, Y., Ghalem, Z.: Reusing the np-hard traveling-salesman problem to demonstrate that p np (invited paper). In: 2016 IEEE 17th international conference on information reuse and integration (IRI), pp. 574–581 (2016). https://doi.org/10.1109/IRI.2016.84 Sevaux, M., Sörensen, K.: Hamiltonian paths in large clustered routing problems. In: Proceedings of the EU/MEeting 2008 workshop on metaheuristics for logistics and vehicle routing, EU/ME (2008) Sunny, C., kumar K. B., S.: Refined pso clustering for not well-separated data. Journal of Experimental & Theoretical Artificial Intelligence pp. 1–17 (2021). https://doi.org/10.1080/0952813X.2021.1970238 Vidal, T., Battarra, M., Subramanian, A., Erdoğan, G.: Hybrid metaheuristics for the clustered vehicle routing problem. Comput. Operat. Res. 58, 87–99 (2015). https://doi.org/10.1016/j.cor.2014.10.019. https://www.sciencedirect.com/science/article/pii/S0305054814 002767 Xie, L., Zeng, J., Cui, Z.: General framework of artificial physics optimization algorithm. In: 2009 World congress on nature biologically inspired computing (NaBIC), pp. 1321–1326 (2009). https://doi.org/10.1109/NABIC.2009.5393736 Xu, X., Li, J., Zhou, M., Xu, J., Cao, J.: Accelerated two-stage particle swarm optimization for clustering not-well-separated data. IEEE Trans. Syst. Man Cybern. Syst. 50(11), 4212–4223 (2020). https://doi.org/10.1109/TSMC.2018.2839618 Yadav, V., Narasimhamurthy, A.: A heuristics based approach for optimizing delivery schedule of an unmanned aerial vehicle (drone) based delivery system. In: \(9^{th}\) international conference on advances in pattern recognition (ICAPR), vol. 2, pp. 920–927 (2015) Yan, H., Chen, Y., Yang, S.H.: Uav-enabled wireless power transfer with base station charging and uav power consumption. IEEE Trans. Vehicular Technol. 69(11), 12883–12896 (2020). https://doi.org/10.1109/TVT.2020.3015246 Yijun, W.: Distribution route optimization of logistics enterprise based on genetic algorithm. In: World automation congress 2012, pp. 1–4 (2012) Yoo, H.D., Chankov, S.M.: Drone-delivery using autonomous mobility: An innovative approach to future last-mile delivery problems. In: 2018 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), pp. 1216–1220 (2018). https://doi.org/10.1109/IEEM.2018.8607829 Zailani, M.A.H., Sabudin, R.Z.A.R., Rahman, R.A., Saiboon, I.M., Ismail, A., Mahdy, Z.A.: Drone for medical products transportation in maternal healthcare: A systematic review and framework for future research. Medicine 99(36) (2020). https://doi.org/10.1097/MD.0000000000021967 Zhang, Y., He, Y., Jin, Y., Qin, H., Azhar, M., Huang, J.Z.: A robust k-means clustering algorithm based on observation point mechanism. Complexity 2020 (2020). https://doi.org/10.1155/2020/3650926 Zhou, Y., Chen, L., Yang, Y., Li, Y., Cheng, G., Fu, Y., Zhu, C., Liu, Y., Mao, H.: Electric vehicle routing problem: Model and algorithm. In: 2020 12th international conference on measuring technology and mechatronics automation (ICMTMA), pp. 1049–1054 (2020). https://doi.org/10.1109/ICMTMA50254.2020.00225 Zhou, Y., Kou, Y., Zhou, M.: Bilevel memetic search approach to the soft-clustered vehicle routing problem. Trans. Sci. (2022). https://doi.org/10.1287/trsc.2022.1186