A branch-and-cut algorithm for the one-commodity pickup and delivery location routing problem
研究了一个结合选址与路径规划的新问题，提出两种数学模型和分支切割算法，能求解最多100个节点的实例，对物流网络设计有参考价值。
This paper introduces a new problem that combines characteristics of the Location and Routing Problem and the One-commodity Pickup and Delivery Traveling Salesman Problem. We are given a set of customers that provide or demand given amounts of a product, and a set of potential facility locations that can be opened or not in order to give service to the customers. Each facility has an opening cost and is the depot of a vehicle with capacity Q. The problem consists in deciding which facilities to open, assigning customers to open facilities, and designing the routes that connect each facility with its customers. The objective is to minimize the sum of the cost of the routes and the facilities. This NP-hard problem has not been previously studied. We propose for it two mathematical formulations, compare them, and present a branch-and-cut algorithm able to solve instances with up to 100 nodes.