Dual Probability Learning Based Local Search for the Task Assignment Problem

The task assignment problem (TAP) is concerned with assigning a set of tasks to a set of agents subject to the limited processing and memory capacities of each agent. The objective to be minimized is the total assignment cost and total communication cost. TAP is a relevant model for many practical applications, yet solving the problem is computationally challenging. Most of the current metaheuristic algorithms for TAP adopt population-based search frameworks, whose search behaviors are usually difficult to analyze and understand due to their complex features. In this work, unlike previous population-based solution methods, we concentrate on a single trajectory stochastic local search model to solve TAP. Especially, we consider TAP from the perspective of a grouping problem and introduce the first probability learning-based local search algorithm for the problem. The proposed algorithm relies on a dual probability learning procedure to discover promising search regions and a gain-based neighborhood search procedure to intensively exploit a given search region. We perform extensive computational experiments on a set of 180 benchmark instances with the proposed algorithm and the general mixed integer programming solver CPLEX. We assess the composing ingredients of the proposed algorithm to shed light on their impacts on the performance of the algorithm.