Summary: We address an optimization problem that requires deciding the location of a set of facilities, the allocation of customers to those facilities under capacity constraints, and the allocation of customers to trucks at those facilities under truck travel-distance constraints. We present a hybrid approach that combines integer and constraint programming using logic-based Benders decomposition. Computational experiments demonstrate that the Benders model is able to find and prove optimal solutions up to three orders-of-magnitude faster than an existing integer programming approach; it also finds better feasible solutions in less time when compared with an existing tabu search algorithm.