We propose a family of new approaches to the problem known as the Vehicle Routing Problem with Intermediate Replenishment Facilities (VRPIRF).
VRPIRF is defined on a graph where the node set consists of a depot, n clients and p replenishment facilities.
The aim is to find the least cost set of routes that visit each client exactly once, the cost of a route being the sum of the costs of the visited arcs.
Each client has a demand and can be served by one of the homogeneous, fixed capacity vehicles based at the depot.
Furthermore, vehicles can recharge at facilities so as to perform not one but a sequence of routes called a rotation.
However, the rotation of a vehicle must start and end at the depot and its total duration (the sum of the travel, service and recharge times associated with the visited arcs, clients, and facilities, respectively) must not exceed a given shift duration.
VRPIRF is the particular case with only one depot of the Multiple Depot VRP with Inter-depot routes, a generalization of the Multi-Depot VRP problem
in which each depot acts both as the base for the vehicles of its own fleet, and as a facility for vehicles based at other depots.
To solve the VRPIRF, we propose two Branch&Cut algorithms, and a third one that integrates the first two.
The aim is to give a contribution to the literature on this problem, which in our opinion is still very poor for what concerns exact methods.
Both the B&C methods are based on a MILP compact formulation and ensure the respect of capacity constraints by separating Capacity Cuts.
The first method separates the so-called Non-Reachable Facility (NRF) Cuts to ensure that the routes of a vehicle form a non-discontinuous rotation.
The method finds near-optimal solutions in reasonable times.
The second one makes use of replenishment arcs to model a stop at a facility between two clients.
This allows to represent a rotation as an elementary path with both its endpoints on the depot, and thus ensure connectivity by the separation of SECs on a transformation of the graph.
As a consequence, this second method shows both a tighter root gap and a stronger lower bound.
The last method integrates in one framework the first two algorithms, and has been designed with the aim to take advantage of the strong points of both.
Tests have been conducted on medium-sized benchmark instances, leading to very promising results.