The static bicycle relocation problem with demand intervals
A variant of the One-Commodity Pickup and Delivery Traveling Salesman Problem is studied. The supply/demand of a vertex is represented by an interval rather than a single value. An integer programming formulation and a branch-and-cut algorithm are developed. Valid inequalities have been adapted from 1-PDTSP and Covering Tour Problem. The algorithm is capable of solving instances with up to 50 customers within two hours of CPU time.
pickup and delivery traveling salesman branch-and-cut