Fast Heuristics for Mixed Fleet Capacitated Multiple TSP with Applications to Location Based Games and Drone Assisted Transportation

Abstract

The Travelling Salesman Problem (TSP) is one of the most known problems in combinatorics and consists of finding a route so that a salesman visits all destination points exactly once with minimum cost. Applications of the problem have long been studied in various fields of computer science, however, with the modernization of transportation means as manifested by autonomous vehicles and drone based delivery, variations of TSP have seen renewed interest. Simultaneously, in location based games such as Pokemon GO, the problem of defining optimal routes in order to direct a single player or a team of players into visiting a set of locations, leads to solving TSP variations. Inspired by the above, in this paper we tackle the problem of Mixed Fleet Capacitated Multiple TSP (mfcmTSP), whereby a set of couriers (using different vehicle types or drones) must deliver a set of homogeneous parcels to predefined destinations with minimum makespan. All transportation means have capacity measured as the number of parcels they can carry. We motivate mfcmTSP considering a scenario whereby all parcels are available at a single base station and a fleet of one truck with unlimited capacity, a motorbike with k capacity and a drone with capacity of one parcel are available to fulfill delivery orders. We present a fast heuristic to obtain good solution quality with negligible running time overhead and compare it against a yardstick strategy whereby only the truck is used. Experiments demonstrate the merits of our approach. © 2021 ACM.