Routing and scheduling optimization for UAV assisted delivery system: A hybrid approach

Sajid, M; Mittal, H; Pare, S; Prasad, M

Routing and scheduling optimization for UAV assisted delivery system: A hybrid approach

Sajid, M Mittal, H Pare, S Prasad, M

Permalink

Publisher:: Elsevier
Publication Type:: Journal Article
Citation:: Applied Soft Computing, 2022, 126, pp. 109225
Issue Date:: 2022-09-01

Closed Access

	Filename	Description	Size
	1-s2.0-S1568494622004501-main.pdf	Published version	2.29 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Sajid, M
dc.contributor.author	Mittal, H
dc.contributor.author	Pare, S
dc.contributor.author	Prasad, M https://orcid.org/0000-0002-7745-9667
dc.date.accessioned	2023-03-24T09:50:41Z
dc.date.available	2023-03-24T09:50:41Z
dc.date.issued	2022-09-01
dc.identifier.citation	Applied Soft Computing, 2022, 126, pp. 109225
dc.identifier.issn	1568-4946
dc.identifier.uri	http://hdl.handle.net/10453/168358
dc.description.abstract	This paper proposes a joint-optimization framework for UAV-routing and UAV-route scheduling problems associated with the UAV-assisted delivery system. The mixed-integer linear programming (MILP) models for UAV-routing and UAV-route scheduling problems are proposed considering the effect of incidental processes and the varying payload on travel time. A hybrid genetic and simulated annealing (HGSA) algorithm is proposed for the UAV-routing problem to minimize travel time. In HGSA, genetic algorithm (GA) employs a novel stochastic crossover operator to search for the optimal global position of customers, whereas simulated annealing (SA) utilizes local search operators to avoid the local optima. A UAV-Oriented MinMin (UO-MinMin) algorithm is also proposed to minimize the makespan of the UAV-route scheduling problem. It employs a UAV-oriented view to generate the route-scheduling order with minimal computational efforts without affecting the quality of the makespan. A Monte Carlo simulation-based sensitivity analysis is conducted to evaluate the impact of the hybridization probability of GA and SA in the proposed HGSA algorithm. To assess the performance of the HGSA algorithm, a set P of 24 benchmark instances is adopted and adjusted to meet the constraints of the UAV-Assisted delivery system. The proposed HGSA outperforms the state-of-the-art algorithms such as genetic algorithm (GA), Particle Swarm Optimization & Simulated Annealing algorithm (PSO-SA), Differential Evolution & Simulated Annealing (DE-SA), and Harris-hawks optimization (HHO). For all 24 instances, the aerial routes generated by HGSA have been used to evaluate the effectiveness of the UO-MinMin algorithm for different numbers of UAVs. The proposed UO-MinMin algorithm outperforms the base algorithms such as minimum completion time (MCT) and opportunistic load balancing (OLB).
dc.language	en
dc.publisher	Elsevier
dc.relation.ispartof	Applied Soft Computing
dc.relation.isbasedon	10.1016/j.asoc.2022.109225
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject	0102 Applied Mathematics, 0801 Artificial Intelligence and Image Processing, 0806 Information Systems
dc.subject.classification	Artificial Intelligence & Image Processing
dc.title	Routing and scheduling optimization for UAV assisted delivery system: A hybrid approach
dc.type	Journal Article
utslib.citation.volume	126
utslib.for	0102 Applied Mathematics
utslib.for	0801 Artificial Intelligence and Image Processing
utslib.for	0806 Information Systems
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - AAII - Australian Artificial Intelligence Institute
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
utslib.copyright.status	closed_access	*
dc.date.updated	2023-03-24T09:50:39Z
pubs.publication-status	Published
pubs.volume	126

Abstract:

This paper proposes a joint-optimization framework for UAV-routing and UAV-route scheduling problems associated with the UAV-assisted delivery system. The mixed-integer linear programming (MILP) models for UAV-routing and UAV-route scheduling problems are proposed considering the effect of incidental processes and the varying payload on travel time. A hybrid genetic and simulated annealing (HGSA) algorithm is proposed for the UAV-routing problem to minimize travel time. In HGSA, genetic algorithm (GA) employs a novel stochastic crossover operator to search for the optimal global position of customers, whereas simulated annealing (SA) utilizes local search operators to avoid the local optima. A UAV-Oriented MinMin (UO-MinMin) algorithm is also proposed to minimize the makespan of the UAV-route scheduling problem. It employs a UAV-oriented view to generate the route-scheduling order with minimal computational efforts without affecting the quality of the makespan. A Monte Carlo simulation-based sensitivity analysis is conducted to evaluate the impact of the hybridization probability of GA and SA in the proposed HGSA algorithm. To assess the performance of the HGSA algorithm, a set P of 24 benchmark instances is adopted and adjusted to meet the constraints of the UAV-Assisted delivery system. The proposed HGSA outperforms the state-of-the-art algorithms such as genetic algorithm (GA), Particle Swarm Optimization & Simulated Annealing algorithm (PSO-SA), Differential Evolution & Simulated Annealing (DE-SA), and Harris-hawks optimization (HHO). For all 24 instances, the aerial routes generated by HGSA have been used to evaluate the effectiveness of the UO-MinMin algorithm for different numbers of UAVs. The proposed UO-MinMin algorithm outperforms the base algorithms such as minimum completion time (MCT) and opportunistic load balancing (OLB).

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/168358