Upper and lower bounds for the sales force deployment problem with explicit contiguity constraints

The sales force deployment problem arises in many selling organizations. This complex planning problem involves the concurrent resolution of four interrelated subproblems: sizing of the sales force, sales representatives locations, sales territory alignment, and sales resource allocation. The objective is to maximize the total profit. For this, a well-known and accepted concave sales response function is used. Unfortunately, literature is lacking approaches that provide valid upper bounds. Therefore, we propose a model formulation with an infinite number of binary variables. The linear relaxation is solved by column generation where the variables with maximum reduced costs are obtained analytically. For the optimal objective function value of the linear relaxation an upper bound is provided. To obtain a very tight gap for the objective function value of the optimal integer solution we introduce a Branch-and-Price approach. Moreover, we propose explicit contiguity constraints based on flow variables. In a series of computational studies we consider instances which may occur in the pharmaceutical industry. The largest instance comprises 50 potential locations and more than 500 sales coverage units. We are able to solve this instance in 1273seconds with a gap of less than 0.01%. A comparison with Drexl and Haase (1999) shows that we are able to halve the solution gap due to tight upper bounds provided by the column generation procedure.