A capacitated multi pickup online food delivery problem with time windows: a branch-and-cut algorithm

Online food delivery companies, nowadays, allow a customer to place an order for a combination of dishes from one or more restaurants. To meet a customer’s demand, the company then arranges for the pickups from different restaurants, perhaps located distantly, before delivering them to the customer. The company caters to a set of such customers, through a fleet of capacitated vehicles. In this paper, we propose an augmented two-index formulation to find least cost vehicle routes to satisfy the set of customer requests under the constraints of time windows of the pickup and delivery locations along with the capacity constraints of the fleet of vehicles. We use branch-and-cut algorithm to solve the benchmark problem instances. The proposed formulation and the problem specific valid inequalities lead to more efficient solution performance as against the existing formulations. The computational experiments indicate that the proposed approach can solve a majority of benchmark problem instances with 25, 35 and 50 nodes, many of which were reported unsolved using exact solution approaches in the extant literature.