The customer assignment and traveling salespersons problem

In recent literature it is proposed to assign (potential) customers to salespersons via sales territory alignment such that the total expected profit margin will be maximized. By this approach sales coverage units (SCUs) will be clustered into larger geographic areas called sales territories where the number of designed sales territories is equal to the number of salespersons, i.e. each sales territory will be unequivocally assigned to a salesperson. Usually, a concave objective function is considered measuring for each SCU the expected profit margin in dependence of the selling time (= driving time + visiting time) a salesperson is allocating to a SCU. One critical point of using such a function is that a known constant relation between driving time and selling time is assumed. How suitable the profit margin function is can only be seen afterwards in a second step when constructing tours for each salesperson. In the case that we observe that the proportionality between driving time and selling time is not as assumed the sales territory alignment results may be non-optimal. To avoid this problem we propose to consider an integrated approach in which the driving times and visiting times of the salespersons are explicitly taken into account, i.e. customer assignment is done by solving a multi-period traveling salespersons problem with time windows. For the solution we propose a set packing approach in which the columns are representing feasible tours. We show that the problem can be solved with column generations with a high solution quality.