The unit capacity pickup and delivery problem on a one-way loop (Q800829)

We consider the problem of making pickups and deliveries of one unit on a one-way loop with a vehicle of unit capacity. The problem is shown to be equivalent to a travelling salesman problem with distance matrix given by \((a_ j\)-b\({}_ i)\) (modulo r) where \(a_ j\) and \(b_ i\) are the locations of the pickup and delivery points for the jth and ith customers, respectively and r is the circumference of the loop. Following the work of Gilmore and Gomory on a related problem, an optimal solution is found in polynomial time by solving the relaxed assignment problem and patching any resulting subtours. Finally it is shown that the model applies to a problem of minimization of wallpaper waste.