유전알고리즘을 활용한 차량-드론 중복방문 분할배송문제 연구
Vehicle-Drone Multi-visit Split Delivery Problem Using Genetic Algorithm
0
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
ROK military is promoting the introduction of various types of unmanned combat systems for future warfare. Prior to the fully unmanned combat phase, it is expected that unmanned systems will assist the current human combatants. ROK military is also making efforts to introduce various types of military drones and Unmanned Ground Vehicles. The problem of delivering goods using vehicle and drones has already been studied in various ways, but since single and one-time delivery is common, it is difficult to directly apply to the military logistic situations in battlefield. The purpose of this study is to find out the fastest route and assignment of nodes to vehicle(UGV) and drones which has completely different capacities and velocities in the battlefield environment. In this study, it is allowed that demands of each node could devided and also UGV and drones could visit each nodes multiple times if they need. This study suggests a mathematical formula model to solve this problem. It also suggests a method of genetic algorithm and develop a chromosome representation composed of three strings to solve this model in polynomial time. Numerical experiments were performed on various cases by comparing the proposed mathematical model with a genetic algorithm, and the results were compared to verify the mathematical model and the efficiency of the proposed algorithm.
Abstract
ROK military is promoting the introduction of various types of unmanned combat systems for future warfare. Prior to the fully unmanned combat phase, it is expected that unmanned systems will assist the current human combatants. ROK military is also making efforts to introduce various types of military drones and Unmanned Ground Vehicles. The problem of delivering goods using vehicle and drones has already been studied in various ways, but since single and one-time delivery is common, it is difficult to directly apply to the military logistic situations in battlefield. The purpose of this study is to find out the fastest route and assignment of nodes to vehicle(UGV) and drones which has completely different capacities and velocities in the battlefield environment. In this study, it is allowed that demands of each node could devided and also UGV and drones could visit each nodes multiple times if they need. This study suggests a mathematical formula model to solve this problem. It also suggests a method of genetic algorithm and develop a chromosome representation composed of three strings to solve this model in polynomial time. Numerical experiments were performed on various cases by comparing the proposed mathematical model with a genetic algorithm, and the results were compared to verify the mathematical model and the efficiency of the proposed algorithm.
참고문헌 (26)
- 김여근, "메타휴리스틱스" (2017), 전남대학교출판부
- 민윤홍, "차량과 드론을 혼용한 최적 라우팅을 위한 휴리스틱", 한국컴퓨터정보학회논문지, 21(9), pp.79~84 (2016), 한국컴퓨터정보학회
- 서명길, "예방교체를 고려한 드론 배송 스케쥴링 및 적정 운용 대수 산출에 관한 연구", 로지스틱스연구, 26(1), pp.65~80 (2018), 한국로지스틱스학회[DOI]
- 신승진, "무인항공기(드론)를 통한 물류배송 가능성과 해외사례", 월간교통, 16(4), pp.45~53 (2016)
- 신해웅, "분할배달이 가능한 차량경로문제의최적해법", 경영과학, 6(1), pp.29~40 (1989)
- 양병학, "드론-차량 배송시스템에서 용량제약이 있는 복수 차량의 도착지 위치-경로-배정 문제", 한국SCM학회지, 19(1), pp.45~56 (2019), 한국SCM학회[DOI]
- 임무균, "유전자 알고리듬을 이용한 운행비용 최소화 다용량 차량경로문제", 산업공학(IE interfaces), 20(2), pp.103~111 (2007), 대한산업공학회
- 전건욱, "수정 유전자 알고리듬을 이용한중복방문, 다중차고 차량경로문제", 산업공학(IE interfaces), 17, pp.28~36 (2014)
- 조승용, "시간제약이 있는 이기종 차량경로문제를 위한 개미집단 최적화", 한국경영과학회, 2008 춘계학술대회 논문집, pp.1441~1445 (2008)
- Agatz, N., "Optimization approaches for the traveling salesman problem with drone", Transportation Science, 42(4), pp.965~981 (2018)
- Archetti, C., "Complexity of the VRP and SDVRP", Transportation Research Part C : Emerging Technologies, 19(5), pp.741~750 (2011)
- Archetti, C., "A tabu search algorithm for the split delivery vehicle routing problem", Transportation Science, 40(1), pp.64~73 (2006)
- Carlsson, J. G., "Coordinated logistics with a truck and a drone", Management Science, 64(9), pp.4052~4069 (2018)
- Dantzig, G., "Solution of a large-scale traveling-salesman problem", Journal of the operations research society of America, 2(4), pp.393~410 (1954)
- Dror, M., "Split delivery routing", Naval Research Logistics, 37(3), pp.383~402 (1990)
- Ferrandez, S. M., "Optimization of a truck-drone in tandem delivery network using K-means and genetic algorithm", Journal of Industrial Engineering and Management, 9(2), pp.374~388 (2016)
- Vehicle routing with time windows and split deliveries, "Feillet, D.", ~, pp.Technical Paper, 851 (2006)
- Golden, B., "The fleet size and mix vehicle routing problem", Computers & Operations Research, 11(1), pp.49~66 (1984)
- An introductory analysis with applications to biology, control, and artificial intelligence. Adaptation in Natural and Artificial Systems, "Holland, J. H.", The University of Michigan, ~ (1975)
- Jin, M., "A two-stage algorithm with valid inequalities for the split delivery vehicle routing problem", International Journal of Production Economics, 105(1), pp.228~242 (2007)
- Lee, C. G., "A shortest path approach to the multiple-vehicle routing problem with split pickups", Transportation research part B : Methodological, 40(4), pp.265~284 (2006)
- "Lab Showcases Futuristic Resupply Vehicle" (2016)[URL]
- Miller, C. E., "Integer programming formulation of traveling salesman problems", Journal of the ACM, 7(4), pp.326~329 (1960)
- Murray, C. C., "The flying sidekick traveling salesman problem : Optimization of droneassisted parcel delivery", Transportation Research Part C : Emerging Technologies, 54, pp.86~109 (2015)
- Taillard, É. D., "A heuristic column generation method for the heterogeneous fleet VRP", RAIROOperations Research-Recherche Opérationnelle, 33(1), pp.1~14 (1999)
- Wilck IV, J. H., "A genetic algorithm for the split delivery vehicle routing problem", American Journal of Operations Research, 2, pp.207~216 (2012)