Coordinated Covering Tour Problems (CCTP) represents a class of routing problems that involve a primary vessel that is equipped with one or more secondary vessels who undergo a launch and recovery process from the primary vessel. The secondary vessels are constrained to meet up with the primary vessel at various nodes in the network and possibly many times, presumably due to the coverage limitations of the secondary vessels. The problem is thus one of simultaneously determining which nodes should be visited by which vessel, in what order each vessel must visit its assigned nodes, and at which nodes the secondary vessels should be launched and recovered by the primary vessel. Last-mile delivery of parcels using trucks (as the primary vessel) and drone (as the secondary vessel) is an example of Coordinated Covering Tour Problems with application in logistics. This problem has received a lot of attention in the last seven years since its seminal definition in 2015. Various authors have extended this problem by including multiple primary/ secondary vehicles, defining new network configurations for the vehicles, and by incorporating environmental and drone dynamics within the model. However, it being an NP-hard problem, there is no way we can solve a problem of modest size in polynomial time. The key lies in developing heuristics that are both efficient and fast, and it has been observed that there is space for considerable improvement in this research area. I propose developing a novel ‘order and split’ heuristic which is an improvement to the best heuristic to date. Furthermore, the algorithm is extended to several variants of the CTTP, and likewise, its accuracy and efficiency are evaluated.
Abhishake Kundu (Sun,) studied this question.