The problem that the authors consider here deals with a single vehicle of a given capacity that needs to serve N customers: some of the customers require a delivery of stock from the warehouse, whereas other need to deliver stock from their location to the warehouse. The objective is to find a shortest feasible tour visiting all customers, emanating from and ending at the warehouse. The authors introduce an efficient (O(N’2)) heuristic for this problem. The heuristic improves the worst-case bound known in the literature from 2.5 to 2. However, its average performance is shown in the present numerical study to be slightly worst than that of a previously published (O(N3)) solution method.
