A Logic Based Benders’ Approach to the Concrete Delivery Problem

Abstract

This work presents an exact Logic Based Benders’ decomposition for the Concrete Delivery Problem (CDP). The CDP is a complex, real world optimization problem involving the allocation and distribution of concrete to construction sites. The key scheduling issue for the CDP is the need for successive deliveries to a site to be sufficiently close in time. We decompose the CDP into a master problem and a subproblem. Based on a number of problem characteristics such as the availability of vehicles, geographical orientation of the customers and production centers, as well as the customers’ demand for concrete, the master problem allocates concrete to customers. Next, the subproblem attempts to construct a feasible schedule, meeting all the routing and scheduling constraints. Infeasibilities in the schedule are communicated back to the master problem via a number of combinatorial inequalities (Benders’ cuts). The master problem is solved through a Mixed Integer Programming approach, whereas the subproblem is solved via a Constraint Programming model and a dedicated scheduling heuristic. Experiments are conducted on a large number of problem instances, and compared against other exact methods presented in related literature. This algorithm is capable of solving a number of previously unsolved benchmark instances to optimality and can improve the bounds for many other instances.