Multiple agents maximum collection problem with time dependent rewards

In this paper, we study Multiple Agents Maximum Collection Problem with Time Dependent Rewards (MAMCP-TDR) which is a variant of Multiple Tour Maximum Collection Problem (MTMCP) (Butt & Cavalier, 1994). In MAMCP-TDR, there are multiple agents to collect linearly decreasing rewards over time. The objective is to maximize total surplus (total reward collected minus total travel cost) by routing multiple agents from a central depot. We propose a mathematical formulation for the problem. Since the problem is strongly NP-hard, we develop a heuristic algorithm, called Cluster-and-Route Algorithm (CRA), to find near-optimal solutions. In CRA, first we cluster the targets/rewards using the well-known k-means clustering algorithm. Then, we find tours by solving a single agent problem for each cluster. To solve the single agent problem, we propose several routing algorithms. Finally, we implement several improvement ideas to improve the final solution. We conduct computational experiments on randomly generated instances and instances of a related problem in the literature to test the performance of routing algorithms for single agent case and the CRA for MAMCP-TDR in terms of solution time and solution quality. Compared to the mathematical formulation, we conclude that CRA provides solutions with similar quality for small instances and performs significantly better both in terms of solution time and solution quality on medium and large instances. (C) 2013 Elsevier Ltd. All rights reserved.