Collection depots problem

Given is a set of customers or demand points $C = \{ c_1,c_2,\ldots,c_n \}$ where each customer $c_i$ is associated with weight $w_i$. Also given is a set of collection depots $D = \{ d_1,d_2,\ldots,d_p \}$. A facility serving a customer dispatches a vehicle that visits the customer and returns to the facility through the collection depot which provides the shortest route. The goal is to minimize the travelled Euclidean weighted distance (minmax or minsum).

The collection depots problem was first introduced by Drezner and Wesolowsky [34]. They investigated the minsum version of the problem, and presented properties of its solutions and an iterative procedure that converges to local minima. Properties of solutions to minmax and minsum versions of the collection depots location problem on networks were investigated by Berman et. al. [13]. Tamir and Halman [54] studied various versions of the minmax version of the problem, with the additional assumption that the choice of depots available to each customer is restricted to a subset of $D$. In addition to studying generalizations to more than one service center (which they showed to be NP-hard), they examined path and tree network versions of the problem. Techniques for solving for the minsum version of the problem with multiple facilities on a network and properties of the solutions are presented in [14].

Significant results have been achieved [11,10]. We provide the first algorithms to solve the minsum 1 and $p$ facility problems in trees with time complexities $O(n\log n)$ and $O(pn^2)$ respectively. We also give, for the first time linear time algorithms to solve the discrete and continuous 1 facility collection depot minmax problem. We are currently looking at ways to extend these results to partial k-trees. For the planar case we showed that the collection depot problem can be transformed to $O(p^2n^2)$ classical minsum and minmax problems and this bound is tight. Extending these results to higher dimensions is a challenging open problem.