Vehicle routing problems such as the multiagent Dynamic Traveling Repariman Problem (DTRP) are of interest to many fields and of increasing practical importance in light of advances in autonomous vehicles. DTRP is NP-hard, making approximation methods attractive. However current heuristic approaches do not adequately consider issues special to DTRP, such as fairness and variance, discontiguous-space scenarios, or approaches to equitably partitioning the task space. We tackle this problem in a novel way, using a multiagent task allocation technique called bounty hunting. In bounty hunting, agents compete to perform tasks non-exclusively in return for reward, and rapidly learn which agents are more adept at various tasks than others, divvying up the task space. We demonstrate that bounty hunting can perform efficiently in discontiguous environments, and can improve the bias and variance of the system while minimally affecting average waiting time. We show that Bounty Hunting Pareto dominates the current state-of-the-art heuristic, and is particularly good in large-scale scenarios.

Many computer systems, such as Internet datacenters and cloud computing environments, consist of a multitude of servers that process user requests. Incoming requests that find all servers busy have to wait until a server becomes idle. This type of queuing system is known as a G/G/c system and has been extensively studied in the queuing literature under steady state con- ditions. This paper studies multi-server systems subject to workload surges of generic trapezoidal shapes during which the average arrival rate of requests exceeds the system’s capacity. This paper’s main contributions are: (1) Generic equations for surges of any shape. (2) A set of equations to estimate the impact of trapezoidal and triangular shaped surges on response time. (3) The design, implementation, and extensive evaluation of an autonomic controller for cloud server elasticity using a G/G/c simulator previously developed by the authors. The results show that our equations estimate with great accuracy the impact of surges on response time and that our autonomic controllers are able to successfully vary the number of servers to mitigate the impact of workload surges.