Branch-and-cut with lazy separation for the vehicle routing problem with simultaneous pickup and delivery

We propose a branch-and-cut algorithm for the VRPSPD where the constraints that ensure that the capacities are not exceeded in the middle of a route are applied in a lazy fashion. The algorithm was tested in 87 instances with 50–200 customers, finding improved lower bounds and several new optimal solutions.

► We propose a branch-and-cut approach over a formulation with only the edge variables.
► Additional route feasibility constraints are applied in a lazy fashion.
► We present improved lower bounds and several new optimal solutions.