A LOWER BOUND FOR MIXED INTEGER LINEAR PROGRAMMING OF SOLID WASTE ASSIGNMENT PROBLEM

Abstract

The increasing volume of municipal solid waste generated in Kaduna Metropolis, coupled with the availability of only two operational disposal sites, has resulted in inefficient waste transportation, long distances, and high transportation costs. This study aims to develop a lower bound for a Mixed Integer Linear Programming (MILP) model of the Kaduna Municipal Solid Waste Disposal Assignment Problem (KMSWDAP) using the Lagrangian Relaxation (LR) technique to simplify the optimization process and obtain a cost-effective waste transportation plan. The study formulates the practical assignment of waste from collection points to disposal sites through different conveyance types as a multi-conveyance capacitated transportation-flow model. The complicating demand constraints are relaxed using LR to generate lower bounds for the objective function. The model was implemented in AMPL and evaluated using the supplied Lagrangian subgradient procedure. After 28 subgradient iterations, the best lower bound was ₦180,783,542.83, and the best feasible upper bound was ₦225,100,000.00, giving an optimality gap of 19.69%. The resulting transportation flows, Number of trips by conveyance type, lower-bound subgradient iterations, and Convergence were subsequently analyzed. The optimized transportation plan identifies the selected waste-allocation routes from the seven collection points to the two disposal sites using three conveyance types. The computational results demonstrate how Lagrangian relaxation can provide a lower bound for the capacitated transportation-flow formulation and support route and vehicle allocation decisions. Because the run terminated at the maximum number of iterations rather than the target gap, the reported lower bound is not claimed to be the proven optimal objective value of the original MILP.