We address the logistics and planning problem of delivering Ready Mixed Concrete (RMC) to a set of demand customers from multiple depots. The RMC Dispatching Problem (RMCDP) is closely related to the Vehicle Routing Problem (VRP) with the difference that demand nodes in the RMCDP may be visited more than once by a truck. This class of routing problems can be represented using Mixed-Integer Programming (MIP) and is known to be NP-hard. Solving RMC delivery problems is often achieved through heuristics and meta-heuristic based methods as exact solution approaches are often unable to find optimal solutions efficiently, in particular when multiple depots are represented in the model. Although a variety of methods are available to solve MIP models, in this paper we attempt to solve the RMCDP using a Lagrangian relaxation technique. Namely, we derive a solution algorithm based on Lagrangian relaxation to reduce the complexity of the initial MIP model and show that the proposed relaxation is able to provide promising computational results on a realistic dataset representative of an active RMCDP in the region of Adelaide, Australia

Keywords