A memetic algorithm for solving rich waste collection problems

J. Ruesch

doi:10.1016/j.ejor.2022.11.023

2023-07-01

DOI：10.1016/j.ejor.2022.11.023

原文链接

查看原文

摘要

En 中文

Inspired by a real-life case in the Brussels Capital Region, Belgium, this paper provides a Memetic Al-gorithm with Sequential Split procedure (MASS) for solving a large variety of waste collection problems with multiple depots, a restricted vehicle fleet at each depot, multiple (intermediate) processing facil-ities, capacity restrictions per processing facility and partial pick-ups. MASS first generates satisfactory initial solutions which are feasible w.r.t. the shift duration and the vehicle capacity using a novel pro-cedure in which (1) a giant tour is split into vehicle routes, (2) intermediate processing facilities are introduced and (3) waste pick-ups can be split further if profitable. Second, MASS improves these solu-tions through local search. New test instances are created, which are used to evaluate the performance of MASS's components. We show that MASS provides high-quality feasible solutions by comparing MASS with an exact approach on a small example. Furthermore, MASS is tested on existing instances for the multiple-depot vehicle routing problem (MDVRP), (multi-depot) vehicle routing problem with intermedi-ate facilities ((MD)VRPIF) and the multi-depot vehicle routing problem with inter-depot routes (MDVRPI). MASS shows competitive results for the MDVRP, the VRPIF and the MDVRPI. For the MDVRPIF, MASS ob-tains better results than those currently found in the literature. To assess its practical value, MASS is used to solve a real-life waste collection problem in the Brussels Capital Region in which alternative scenarios for municipal bio-waste collection and treatment are compared.(c) 2022 Elsevier B.V. All rights reserved.

Keyword:

Routing

Waste collection

Multiple depots

Intermediate facilities

Partial pick-ups