@article{ART002149211},
author={Yunhong Min and Chung Yerim},
title={A Heuristic for Dual Mode Routing with Vehicle and Drone},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2016},
volume={21},
number={9},
pages={79-84}
TY - JOUR
AU - Yunhong Min
AU - Chung Yerim
TI - A Heuristic for Dual Mode Routing with Vehicle and Drone
JO - Journal of The Korea Society of Computer and Information
PY - 2016
VL - 21
IS - 9
PB - The Korean Society Of Computer And Information
SP - 79
EP - 84
SN - 1598-849X
AB - 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.
KW - Vehicle and Drone;Heuristic;Traveling Salesman Problem;Minimum Spanning Tree;Neighborhood Search
DO -
UR -
ER -
Yunhong Min and Chung Yerim. (2016). A Heuristic for Dual Mode Routing with Vehicle and Drone. Journal of The Korea Society of Computer and Information, 21(9), 79-84.
Yunhong Min and Chung Yerim. 2016, "A Heuristic for Dual Mode Routing with Vehicle and Drone", Journal of The Korea Society of Computer and Information, vol.21, no.9 pp.79-84.
Yunhong Min, Chung Yerim "A Heuristic for Dual Mode Routing with Vehicle and Drone" Journal of The Korea Society of Computer and Information 21.9 pp.79-84 (2016) : 79.
Yunhong Min, Chung Yerim. A Heuristic for Dual Mode Routing with Vehicle and Drone. 2016; 21(9), 79-84.
Yunhong Min and Chung Yerim. "A Heuristic for Dual Mode Routing with Vehicle and Drone" Journal of The Korea Society of Computer and Information 21, no.9 (2016) : 79-84.
Yunhong Min; Chung Yerim. A Heuristic for Dual Mode Routing with Vehicle and Drone. Journal of The Korea Society of Computer and Information, 21(9), 79-84.
Yunhong Min; Chung Yerim. A Heuristic for Dual Mode Routing with Vehicle and Drone. Journal of The Korea Society of Computer and Information. 2016; 21(9) 79-84.
Yunhong Min, Chung Yerim. A Heuristic for Dual Mode Routing with Vehicle and Drone. 2016; 21(9), 79-84.
Yunhong Min and Chung Yerim. "A Heuristic for Dual Mode Routing with Vehicle and Drone" Journal of The Korea Society of Computer and Information 21, no.9 (2016) : 79-84.
