Efficient Delivery and Charging Algorithms for Drone
- 주제(키워드) Master’s Thesis in Computer Engineering
- 발행기관 아주대학교
- 지도교수 Jai-Hoon Kim
- 발행년도 2016
- 학위수여년월 2016. 8
- 학위명 석사
- 학과 및 전공 일반대학원 컴퓨터공학과
- 실제URI http://www.dcollection.net/handler/ajou/000000023060
- 본문언어 영어
- 저작권 아주대학교 논문은 저작권에 의해 보호받습니다.
초록/요약
Nowadays, service providers seeks for an effective routing solution for their package delivery problem that create a competitive advantage achieved by deploying all the available resources on effective short delivery distance and time. That minimizes the inconvenience for their customers. Drone package delivery is a big promise of the future, with small flying unmanned aerial vehicle (UAV) carrying goods from warehouse or truck right to customer doorsteps. Drone package delivery routing problem is realistic problem used to find best efficient route of drone package delivery service. In this thesis, we present an approach for solving drone routing problem for package delivery service using two different heuristics algorithms, genetic and nearest neighbor algorithms. We use different instances of customers and package loading capacity and measure performance of each algorithm for each instance. While experimenting we implement and analyze the algorithms for solving the problem efficiently with respect to cost and time. The respective experimental results show that for the range of customers 10 to 50 nearest neighbor and genetic algorithms can reduce the tour length on average by 34% and 40% respectively comparing to FIFO algorithm. Secondly, we also present an approach for solving drone power charging problem using a modified heuristic nearest neighbor algorithms, 1) next nearest neighbor after charging (NNN) and 2) return nearest neighbor after charging (RNN) algorithms. We use different instances of checkpoints and fixed number of charging stations and measure average tour length of each algorithm for each instance. The respective experimental results show that for the range of checkpoints 5 to 25 next nearest neighbor after charging algorithm can reduce the tour length on average by 21% comparing to return nearest neighbor after charging algorithm.
more목차
1. Introduction 1
2. Background and Related Works 4
2.1 Drone Civilian Applications 4
2.2 Heuristic Algorithms 5
2.3 Related Works 6
3. Efficient Algorithms for Drone Package Delivery Route 9
3.1 Problem Formulation 9
3.2 Proposed Solution 11
3.2.1 Genetic Algorithm (GA) 11
3.2.2 Nearest Neighbor Modified Algorithm 13
3.3 Experiment and Result 14
4. Efficient Algorithms for Drone Power Charging 18
4.1 Problem Formulation 18
4.2 Proposed Solution 20
4.2.1 Nearest Neighbor Modified Algorithms 20
4.2.2 Next Nearest Neighbor after Charging (NNN) 21
4.2.3 Return Nearest Neighbor after Charging (RNN) 22
4.3 Experiment and Result 23
5. Conclusion and Future Work 27
