A Branch-and-cut algorithm for the split-demand one-commodity pickup-and-delivery travelling salesman problem
研究有容量限制的车辆在允许拆分客户需求和临时中转存储条件下，设计最小成本路线的问题，提出分支切割算法求解，在60客户基准实例上表现优于现有方法。
This paper deals with the problem of designing a minimum-cost route for a capacitated vehicle moving a commodity between a set of customers, allowing two features uncommon in the pickup-and-delivery literature. One feature is that a customer accepts to be visited several times, i.e., splitting a customer demand is allowed. The other feature is that a customer may be used as an intermediate location to collect and deliver commodity temporarily. The problem is called Split-Delivery One-Commodity Pickup-and-Delivery Travelling Salesman Problem, and finds applications in bike sharing systems where a single vehicle moves bikes between bike stations of a city district during the night to set the network to an initial configuration. The paper proposes a new branch-and-cut algorithm to find optimal solutions. A master problem solves a relaxed Mixed Integer Programming model, i.e., a model allowing all feasible solutions and also some invalid ones. A subproblem checks the feasibility of the master solutions and generates valid cuts when they are infeasible. Computational results on benchmark instances demonstrate the good performance of the algorithm compared with others in the literature. In particular, it solves benchmark instances with 60 customers that were unsolved.