Optimization of the waste collection arc routing problem using the physics-based electromagnetism-like algorithm

Date of Publication

2022

Document Type

Master's Thesis

Degree Name

Master of Science in Applied Physics

Subject Categories

Physics

College

College of Science

Department/Unit

Physics

Thesis Advisor

Edgar A. Vallar

Defense Panel Chair

Ma. Cecilia D. Galvez

Defense Panel Member

Prane Mariel Ong
Liz C. Silva

Abstract/Summary

Waste collection is considered as a first objective in planning a sustainable waste management, and provision of substantial collection coverage in urban and rural areas should be satisfied before investing in more sophisticated infrastructure. Therefore, good waste collection service is essential to upgrade further the next levels of a municipal solid waste system. One of the ways to enhance performance on waste collection is to plan effective routing of trucks. The study formulated a Time-Dependent Capacitated Arc Routing Problem with Green Routing (TD- CARP-GR) to model the waste collection routing problem of Parang, Marikina City using three scenarios: baseline, parameter, and collection scenarios. This study focused on the door-to- door method of waste collection and its transport to a Materials Recovery Facility (MRF) in Parang, Marikina City. The objective is to build an optimization problem of waste collection and minimize the distance taken by the truck with their corresponding GHG emissions and fuel consumption. A physics-based algorithm called Electromagnetism-like (EM-Like) is used for the solution process and is executed on a directed, multigraph-based representation of the road network, where edges contain the demand points and nodes will be the intersections and dead- ends. The simulation results revealed that the particle movement boundary and the initialization phase where feasible solutions are generated to start the algorithm, affects the search process. Moreover, using Lilliefors, Kruskal-Wallis, and post-hoc test Tukey-Kramer, the particles were observed to achieve diversity and cooperation in the task to minimize the obtained distance values. The Shannon Entropy measure also quantified the amount of information contained during the search when two parameter scenarios are compared and showed that the traditional formulation of particle movement in [0,1] obtained better search quality. However, the algorithm suffers from slow convergence rate of solutions, as seen from the huge difference between the randomly generated initial solutions and city-block based initialization of which the latter encourages more intelligent way of permuting objects as it tends to order streets that are closer to each other. Therefore, more iterations are needed leading to higher computational expense to eventually reach the range of values generated from the better initialization method implemented in the city-block based distance. Moreover, subjecting the algorithm with a local search procedure significantly improved the obtained values per iteration, with the highest improvement of 21 percent. This trend is evident to all the parameter scenarios. The study also strengthens the recommendation of the implementation of capacity considerations since there is poor correlation between cost and distance in the baseline scenario. For the capacitated scenario, if the cost per meter that the service needs are to be calculated, the TDCARPK100 gives 0.02198 PHP/meter, CARPK50 of 0.02123 PHP/meter, and baseline of 0.02591 PHP/meter. Thus, it can be concluded that capacity considerations of truck are important to attain better efficiency and cost savings. In conclusion, the EM-like with local search and selection strategy mechanism displayed significant minimization abilities of distance values.

Abstract Format

html

Language

English

Format

Electronic

Physical Description

xxvi, 149 leaves

Keywords

Refuse and refuse disposal; Electromagnetism

Upload Full Text

wf_yes

Embargo Period

12-12-2022

This document is currently not available here.

Share

COinS