首页|Strong cuts from compatibility relations for the Dial-a-Ride Problem
Strong cuts from compatibility relations for the Dial-a-Ride Problem
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
? 2021 Elsevier B.V.In this paper we study the Dial-a-Ride Problem, which is a variant of the well-studied Vehicle Routing Problem, where a fleet of vehicles has to satisfy a set of transportation requests between given pickup and delivery locations, and the solution is a set of routes satisfying several constraints, and minimizing the transportation costs. Our main goal is to investigate the classes of valid inequalities that can be obtained from the compatibility relation on the arcs. The compatibility relations are derived from the constraints of the problem, such as precedence relations, time windows and the capacity of the vehicles, and their main use is to exclude infeasible vehicle paths. We strengthen the lifting for an existing class of cuts, introduce a new family of valid inequalities, and devise a new exact separation algorithm for all these cuts. We also establish a connection between these cuts and the edge-polytope of a bipartite graph, which gives new insight into the strength of known classes of inequalities as well. Finally, we evaluate the various classes of cuts on benchmark instances from the literature.
Cutting planesEdge-polytopeExact separationPickup and Delivery Problem
Morapitiye S.、Kis T.
展开 >
Budapest University of Technology and Economics (BME)
Institute for Computer Science and Control (ELKH SZTAKI)
NSTL
Elsevier
