Premium
Column Generation‐Based Approach for Solving Large‐Scale Ready Mixed Concrete Delivery Dispatching Problems
Author(s) -
Maghrebi Mojtaba,
Periaraj Vivek,
Waller S. Travis,
Sammut Claude
Publication year - 2016
Publication title -
computer‐aided civil and infrastructure engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 2.773
H-Index - 82
eISSN - 1467-8667
pISSN - 1093-9687
DOI - 10.1111/mice.12182
Subject(s) - column generation , mathematical optimization , computer science , vehicle routing problem , simplex algorithm , linear programming , domain (mathematical analysis) , routing (electronic design automation) , mathematics , computer network , mathematical analysis
Ready mix concrete (RMC) dispatching forms a critical component of the construction supply chain. However, optimization approaches within the RMC dispatching continue to evolve due to the specific size, constraints, and objectives required of the application domain. In this article, we develop a column generation algorithm for vehicle routing problems (VRPs) with time window constraints as applied to RMC dispatching problems and examine the performance of the approach for this specific application domain. The objective of the problem is to find the minimum cost routes for a fleet of capacitated vehicles serving concrete to customers with known demand from depots within the allowable time window. The VRP is specified to cover the concrete delivery problem by adding additional constraints that reflect real situations. The introduced model is amenable to the Dantzig–Wolfe reformulation for solving pricing problems using a two‐staged methodology as proposed in this article. Further, under the mild assumption of homogeneity of the vehicles, the pricing sub‐problem can be viewed as a minimum‐cost multi‐commodity flow problem and solved in polynomial time using efficient network simplex method implementations. A large‐scale field collect data set is used for evaluating the model and the proposed solution method, with and without time window constraints. In addition, the method is compared with the exact solution found via enumeration. The results show that on average the proposed methodology attains near optimal solutions for many of the large sized models but is 10 times faster than branch‐and‐cut.