Region-Focused Memetic Algorithms with Smart Initialization for Real-World Large-Scale Waste Collection Problems

Wenxing LAN, Ziyuan YE, Peijun RUAN, Jialin LIU, Peng YANG, Xin YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

9 Citations (Scopus)

Abstract

Memetic algorithm (MA) is widely applied to optimize routing problems as it provides one way to combine local search with global search. However, the local search in MA needs to be carefully designed according to the problem's characteristics. In this article, we consider a real-world large-scale waste collection problem with multiple depots, multiple disposal facilities, multiple trips, and working time constraints. Vehicles with a limited capacity and working time can start from different depots, collect waste at different sites, and make multiple trips to different disposal facilities to empty the waste and return to its origin. While the existing work considered problems with multiple trips and time constraints, none have tackled problems with multiple depots, multiple disposal facilities, multiple trips, as well as working time constraints. The change from 'single-depot' to 'multidepot' not only reflects better the situation in real life but also leads to a qualitative different and more complex problem. In this article, we first model this complex problem mathematically. Then, a novel region-focused MA is proposed to tackle this new challenge. Compared to classic MA, this region-focused one is enhanced by two major components: 1) a new heuristic-Assisted solution initialization algorithm and 2) a region-focused local search with novel heuristics. Comprehensive computational studies show that our proposed approaches significantly outperform several state-of-The-Arts on our real problem of thousands of tasks. The new local search procedure and solution initialization method significantly improve the search ability in combination with global search ability of MA. © 1997-2012 IEEE.
Original languageEnglish
Pages (from-to)704-718
Number of pages15
JournalIEEE Transactions on Evolutionary Computation
Volume26
Issue number4
Early online date29 Oct 2021
DOIs
Publication statusPublished - Aug 2022
Externally publishedYes

Keywords

  • Capacitated vehicle routing problem (CVRP)
  • local search
  • memetic algorithm (MA)
  • metaheuristics
  • waste collection

Fingerprint

Dive into the research topics of 'Region-Focused Memetic Algorithms with Smart Initialization for Real-World Large-Scale Waste Collection Problems'. Together they form a unique fingerprint.

Cite this