The Concrete Delivery Problem

Abstract

From an operational point of view, Ready-Mixed Concrete Suppliers are faced with challenging operational problems such as the acquisition of raw materials, scheduling of production facilities, and the transportation of concrete. This paper is centered around the logistical and distributional part of the operation: the scheduling and routing of concrete, commonly known as the Concrete Delivery Problem (CDP). The problem aims at finding efficient routes for a fleet of (heterogeneous) vehicles, alternating between concrete production centers and construction sites, and adhering to strict scheduling and routing constraints. Thus far, a variety of CDPs and solution approaches have appeared in academic research. However, variations in problem definitions and the lack of publicly available benchmark data inhibit a mutual comparison of these approaches. Therefore, this work presents a more fundamental version of CDP, while preserving the main characteristics of the existing problem variations. Both exact and heuristic algorithms for CDP are proposed. The exact solution approaches include a Mixed Integer Programming (MIP) model and a Constraint Programming model. Similarly, two heuristics are studied: the first heuristic relies on an efficient best-fit scheduling procedure, whereas the second heuristic utilizes the MIP model to improve delivery schedules locally. Computational experiments are conducted on new, publicly accessible, data sets; results are compared against lower bounds on the optimal solutions.