H. Edwin Romeijn, Dolores Romero Morales
Asymptotic analysis of a greedy heuristic for the
multi-period single-sourcing problem: the acyclic case
The multi-period single-sourcing problem that we address in this paper
can be used as a tactical tool for evaluating logistics network designs
in a dynamic environment. In particular, the objective will be to find
an assignment of customers to facilities, as well as the location, timing
and size of inventories, that minimizes total assignment and inventory
costs. We propose a greedy heuristic, and prove that this heuristic is
asymptotically optimal in a probabilistic sense for the subclass of problems
where the assignment of customers to facilities is allowed to vary over
time. In addition, we prove a similar result for the subclass of problems
where each customer needs to be assigned to the same facility over the
planning horizon, and where the demand for each customer exhibits the same
seasonality pattern. We illustrate the behaviour of the heuristic, as well
as some improvements where the heuristic is used as the starting point
of a local interchange procedure, on a set of randomly generated test problems.