A Compact Convex Quadratically Constrained Formulation for a Class of Delivery Schedule Problems

In this paper, we present a novel and efficient formulation of a common class of delivery schedule optimization problems. We define the overall model structure, which includes warehouses, clients, and service stations that can be visited by delivery agents, as well as the operational constraints the delivery process must abide, aiming at maximizing the number of delivered orders. We first provide a linear problem formulation, constituting the main baseline; hence, we construct an exact and more compact quadratically constrained version, which reduces the number of binary variables involved. Furthermore, we validate the proposed approach on a realistic numerical example, showing how less computational resources are needed, with respect to the baseline version, without excessively slowing down the convergence towards the optimum.