차량과 드론을 혼용한 최적 라우팅을 위한 휴리스틱
A Heuristic for Dual Mode Routing with Vehicle and Drone
0
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
In this paper we consider the problem of finding the triplet , where ⊆ , is a sequence of nodes in and ╲ → for a given complete graph . In particular, there exist two costs, and for ε , and the cost of triplet is defined as ε ╲ . This problem is motivated by the integrated routing of the vehicle and drone for urban delivery services. Since a well-known NP-complete TSP (Traveling Salesman Problem) is a special case of our problem, we cannot expect to have any polynomial-time algorithm unless P=NP. Furthermore, for practical purposes, we may not rely on time-exhaustive enumeration method such as branch-and-bound and branch-and-cut. This paper suggests the simple heuristic which is motivated by the MST (minimum spanning tree)-based approximation algorithm and neighborhood search heuristic for TSP.
Abstract
In this paper we consider the problem of finding the triplet , where ⊆ , is a sequence of nodes in and ╲ → for a given complete graph . In particular, there exist two costs, and for ε , and the cost of triplet is defined as ε ╲ . This problem is motivated by the integrated routing of the vehicle and drone for urban delivery services. Since a well-known NP-complete TSP (Traveling Salesman Problem) is a special case of our problem, we cannot expect to have any polynomial-time algorithm unless P=NP. Furthermore, for practical purposes, we may not rely on time-exhaustive enumeration method such as branch-and-bound and branch-and-cut. This paper suggests the simple heuristic which is motivated by the MST (minimum spanning tree)-based approximation algorithm and neighborhood search heuristic for TSP.
참고문헌 (13)
- M. Savelsbergh, "City logistics:Challenges and opportunities", Transportation Science, 50(2), pp.579~590 (2016)
- "Amazon and drones – here is why it will work"[URL]
- "Drone delivery: DHL ‘parcelcopter’ files to German isle"[URL]
- "Like Amazon, UPS Also Considering Using Unmanned Flying Vehicles"[URL]
- M. R. Garey, "Computers and Intractability; A guide to the Theory of NP-Completeness" (1990), W. H. Freeman & Co.
- G. Nemhauser, "Integer and Combinatorial Optimization" (1988), John Wiley & Sons
- V. V. Vazirani, "Approximation Algorithms" (2003), Springer-Verlag Berlin Heidelberg
- C. C. Murray, "The flying sidekick traveling salesman problem : Optimization of drone-assited parcel delivery", Transportation Research Part C : Emerging Technologies, 54, pp.86~109 (2015)
- Optimization approaches for the traveling salesman problem with drone, "N. Agatz", ERIM, ~, pp.No. ERS-2015-011-LIS (2015)
- "Amazon Prime Air Is Here, but Not in the Expected Form"[URL]
- G. A. Croes, "A method for solving traveling salesman problem", Operations Research, 6(6), pp.791~812 (1958)
- 황준하, "집합 커버링 문제를 위한 정수계획법 기반 지역 탐색", 한국컴퓨터정보학회논문지, 19(10), pp.13~21 (2014), 한국컴퓨터정보학회
- 이주영, "최소신장트리를 위한 크루스칼 알고리즘의 효율적인 구현", 한국컴퓨터정보학회논문지, 19(7), pp.131~140 (2014), 한국컴퓨터정보학회