Home > Explore Content > All Issues > Article View
A Heuristic for Dual Mode Routing with Vehicle and Drone
Journal of The Korea Society of Computer and Information
Abbr :
JKSCI
2016, 21(9), pp.79-84
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science
2016, 21(9), pp.79-84
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science
-
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.
99 Viewed
Print this page
Download PDF