A VEHICLE ROUTING PROBLEM OPTIMIZATION WITH DRONE USING TABU SEARCH ALGORITHM AND ANALYTICAL HIERARCHY PROCESS

Authors

  • Linda Nuryanti Diponegoro University

Abstract

This research presents optimization of the fastest route using Drone. Vehicle Routing Problem with Drones (VRPD) is used for planning the mapping of areas with minimal makespan. Drone point route design aims to mapping the area with considering the boundaries. In this paper, an optimization method using the Tabu Search algorithm and Analytical Hierarchy Process (AHP) to resolve VRPD problems is proposed. Tabu Search algorithm is suitable for the implementation of Vehicle Routing Problem because it is able to find the closest distance optimally with guiding other processes using a series of movements to change one solution to another. The optimization process using Tabu Search can find a suitable pair of points so that the closest route can be found. AHP is used for the weighting process and determining the hierarchy of route selection by prioritizing routes that meet the criteria and the appropriate weights. The optimization resulted in a 7.08% reduction in the distance and significantly reduce the makespan as well as the metaheuristic approach. Experimental processes and performance analysis are carried out to find that this method can consistently produce better and optimal solutions.

Keywords : Vehicle Routing Problem with Drone; Analytical Hierarchy Process;Tabu Search; Mapping

References

M. Qiu, Z. Fu, R. Eglese, and T. Qiong. “A Tabu Search algorithm for the vehicle routing problem with discrete split deliveries and pickups”, Computers and operations research, 2018, Vol.100, pp.102-116.

A. Karak, and K. Abdelghany. “The hybrid vehicle-drone routing problem for pick-up and delivery services”, Transportation Research Part C, 2019, Vol.102, pp.427-449.

A. Otto, N. Agatz, J. Campbell, B. Golden, and E. Pesch. “Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial Drones: A survey”, Networks, 2018, pp.1-48.

D. Schermer, M. Moeini, and O. Wendt. “A matheuristic for the vehicle routing problem with Drones and its variants”, Transportation Research Part C, 2019, Vol.106, pp.166-204.

Z. Wang, and J. B. Sheu. “Vehicle routing problem with Drones”, Transportation Research Part B, 2019, Vol.122, pp.350-364.

D. Schermer, M. Moeini, and O. Wendt. “A hybrid VNS/Tabu Search algorithm for solving the vehicle routing problem with Drones and en route operations”, Computers and Operations Research, 2019, Vol.109, pp.134-158.

J. Euchi, and A. Sadok. “Hybrid genetic-sweep algorithm to solve the vehicle routing problem with Drones”, Physical Communication, 2021, Vol.44, Article 101236.

O. Hoscan, and S. Cetinyokus. “Determination of emergency assembly point for industrial accidents with AHP analysis”, Journal of Loss Prevention in the Process Industries, 2021, Vol.69, Article 104386.

J. Fang, and F. Y. Partovi. “Criteria determination of analytic hierarchy process using a topic model”, Expert Systems with Applications, 2021, Vol.169, Article 114306.

B. Kallehauge, J. Larsen, O. B. G, Madsen and M. M. Solomon. “Vehicle routing problem with time windows”, Column Generation, 2002.

J. Peng, H. Li, Q. Jiang, Y. Wang, and J. Chen. “An integrative approach for measuring semantic similarities using gene ontology”, BMC Systems Biology, 2014.

T. Aykut. “Determination of groundwater potential zones using Geographical Information Systems (GIS) and Analytic Hierarchy Process (AHP) between Edirne-Kalkansogut (northwestern Turkey)”, Groundwater for Sustainable Development, 2021, Vol.12, Article 100545.

G. Li, and Y. Li. “Optimization spatial pattern method for vegetation landscape in bay based on AHP”, Microprocessors and Microsystems, 2021, Vol.83, Article 104041.

Downloads

Published

2021-04-28