본문 바로가기
  • Home

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 : Engineering > Computer Science

Yun-Hong Min 1 Chung Yerim 2

1삼성전자종합기술원
2연세대학교

Accredited

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.

Citation status

* References for papers published after 2023 are currently being built.