Using Lagrangian Relaxation to Solve Ready Mixed Concrete Dispatching Problems

The logistics and planning problem of delivering ready mixed concrete (RMC) to a set of demand customers from multiple depots is addressed. The RMC dispatching problem (RMCDP) is closely related to the vehicle routing problem, with the difference that a truck may visit demand nodes in the RMCDP more than once. This class of routing problems can be represented by using mixed-integer programming (MIP) and is known to be NP-hard. Solving RMC delivery problems is often achieved through heuristics and metaheuristic-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 an attempt is made to solve the RMCDP by using a Lagrangian relaxation technique. Namely, a solution algorithm based on Lagrangian relaxation is derived to reduce the complexity of the initial MIP model and show that the proposed relaxation is able to provide promising computation results on a realistic data set representative of an active RMCDP in the region of Adelaide, Australia.