Static pickup and delivery problems: a classification scheme and survey. (With comments and rejoinder) (Q2644426)

This thirty page article provides a comprehensive survey on ``Static pickup and delivery problems'' and a good selection of references out of the huge number of papers concerned with this topic. The authors propose a three-field classification scheme (like those used in queuing theory or scheduling theory) for static scenarios on complete directed graphs with arc weights obeying the triangle inequality. Special side constraints (time windows, precedence constraints, Euclidean spaces, vehicles with different capacities, etc.) or multi-criteria problems as well as dynamic or stochastic aspects are not within the focus of the paper, besides very few exceptions. Within the choosen frame the authors give excellent insight into the variety of problems, interesting special structures and algorithms/heuristics for exact or approximately solving these problems, emphasing worst-case-guarantees as well as empirical results.