Column Generation-Based Approach for Solving Large-Scale Ready Mixed Concrete Delivery Dispatching Problems

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

  • Mojtaba Maghrebi - , University of New South Wales, Ferdowsi University of Mashhad (Author)
  • Vivek Periaraj - , University of Arizona (Author)
  • S. Travis Waller - , University of New South Wales, National Information Communications Technology Australia (Author)
  • Claude Sammut - , University of New South Wales (Author)

Abstract

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.

Details

Original languageEnglish
Pages (from-to)145-159
Number of pages15
JournalComputer-Aided Civil and Infrastructure Engineering
Volume31
Issue number2
Publication statusPublished - 1 Feb 2016
Peer-reviewedYes
Externally publishedYes

External IDs

ORCID /0000-0002-2939-2090/work/141543815