Optimizing location-routing and demand allocation in the household waste collection system using a branch-and-price algorithm

In catering to the rapid development of urbanization and the growing urban population, it is essential to design an efficient and effective household waste collection system for guaranteeing a favorable ecological environment in cities. This paper focuses on a location-routing and demand allocation problem (LRDAP) in the household waste collection system where the household waste is initially allocated and transported to a set of intermediate transfer stations using a category of small garbage vehicles, and subsequently a fleet of large garbage vehicles visits each transfer station and transports the collected household waste to the waste disposal center for harmless treatment. The purpose is to simultaneously determine the location of transfer stations, the demand allocation of household waste collection and the routing plan of garbage vehicles while maximizing the efficiency of household waste collection within the whole system. Then, we formulate the proposed LRDAP into a mixed integer program. To solve our LRDAP, an exact branch-and-price (B&P) algorithm is developed along with several acceleration strategies involving column generation (CG) stabilization and heuristic dynamic programming (DP). Finally, we illustrate the proposed model and solution methodology by dealing with real-world problem instances with respect to household waste collection in China. Computational results are presented that explore the performance of our proposed B&P algorithm, analyze the optimized location-routing and demand allocation plan, discuss the impact of selected parameters, and gain some managerial insights in designing an efficient and effective household waste collection system under different decision-making conditions.