Dynamic Route Optimization for Smart City
Posted: August 25th, 2021
Dynamic Route Optimization for Smart City
Student’s Name
Institutional Affiliation
Abstract
Waste collection is a key component of the municipal service to the community within the urban set-up. It is a visible service that requires surmountable expenditures while ensuring that clients are satisfied with the service. However, the increase in population particularly in urban centers has continually worsened the problem by increasing costs and time spent in waste collection operation. As outlined in the paper, static route optimization is implemented by adopting the traveling salesman problem to enhance the development of a cost-effective route. Essentially, the advent of technology comes in handy as the appropriate solution to help to solve the waste collection menace in routing planning. The manual methods used in planning the movement of waste collection trucks have proved tedious and time-consuming and eventually fails to yield a reliable solution. The study takes a case of the Al Awali district, Mecca City and attempts to establish the best outlay of the waste collection vehicle movement to optimize their operational route besides ensuring that customers are assured the quality of service. Accordingly, a review of previous researches in the area in parts of the world reveals a positive implication of technologies in waste management. This is based on the understanding of a variety of methods used in solving the problem. Some of the methods highlighted in the study include the traveling salesman problem and the vehicle routing problem. The study focused on utilizing the static route optimization with the traveling salesman problem, which was solved through the incorporation of the Hamiltonian path algorithm. Finally, it became clear that an optimized route is achievable with a concerted approach to an examination of various routes by performing several trials to trace out a cost-effective route that serves all clients efficiently.
Table of Contents
Chapter 1: Introduction and Problem Statement 4
1.2 Waste Collection Issues. 5
1.3.1 The emergence of IOT Smart city. 6
1.3.2 Need for algorithm and backend processing. 6
1.3.3 Working communication system.. 6
Chapter 2: Literature Review.. 9
2.2. Waste Collection Routing Problem.. 11
2.2.1 Arc routing problem.. 11
2.2.2 Node Routing Problem.. 15
2.3 Static Waste Collection Routing Problem.. 17
2.4. Dynamic Waste Collection Routing Problem.. 18
2.5 Smart Waste Collection Routing Problem.. 20
Chapter 3: Research Methodology. 22
3.2.1 Travelling Salesman Problem (TSP) 25
3.2.2 Vehicle Routing Problem (VRP) 27
3.2.3 TSP versus VRP Problem.. 30
3.3.2 Nearest Neighbor Algorithm.. 35
4.2. Map of Case Study Area. 40
4.3. Data Collection Processes. 43
Chapter 5: Preliminary Results. 48
Dynamic Route Optimization for Smart City
Chapter 1: Introduction and Problem Statement
1.1 Overview
West collection constitutes a vital part of waste management. It entails the collection of waste from production points such as residential, commercial, and construction areas to disposal or treatment sites. Precisely, a waste collection system entails the entire process of gathering solid waste for disposal, treatment, and recycling. Most researchers are finding interest in this matter because of its great impact on the growing population, especially in urban centers. Since the waste collection is a sensitive issue to public health, it attracts high expenses due to operational costs. In a bid to concentrate matter and reduce such expenses, determined researchers are investigating possible ways of improving the routing problem by examining defects of solid waste vehicles, convenient location for collection bins, suitable location of disposal facilities, and the minimum number of garbage vehicles. While examining the situation of Alawali city, it was evident that improvement in transportation of garbage is required to enhance efficiency in the routes that facilitate movement of trucks.
Prominent sources of waste in urban areas include households, construction sites, and commercial activities. All unused materials and remains of food particles in a house end up in the waste dump bin.Over time, decomposition of these haphazardly discarded materials begins to decompose while fouling the environment and making some habitats uncomfortable. An urgent responsible decision requires the household to carry the garbage to the city dumpster. As problems continued to plunge residents regarding where to dump, city planners found a solution. In this regard, they deployed a team of experts, well-armed with necessary dirt collection tools, to the households to collect the solid wastes. City cleaning does not only stop at the house level but also in factories and business centers where a large portion of the waste is generated daily.
In commercial areas, production companies derive both liquid and solid wastes. Since space is limited, they have no option but to seek the service of city cleaners. Pipes channel sewage to designated areas for further processing while individuals and machines collect the solid waste in one area as it awaits transportation to dump sites. The process is cumbersome and mostly mechanical, but it has to repeat throughout the week.
Cities of our modern times have sophisticated building structures that accommodate millions of people. An increase in population means more solid waste, which consequently requires more bins and containercollectors. A rise in population leads to the formation of more waste collection points, which can sometimes become challenging to manage. However, route optimization methods are in place to help in the management of the collection process.
1.2 Waste Collection Issues
The solid waste collection remains an issue for IoT Smart Cities for various reasons. Most important is the traffic issues where many vehicles slow down the waste transporters. Second in significance is the high cost of fuel, which makes it expensive to transport frequent trips in a day. Last is the low vehicle maintenance initiative, which leads to frequent breakdown of trucks on the roads. The city can solve problem issues after understanding its waste management routing glitches to plan a feasible solution.
1.3 Three Phases of the Problem
1.3.1 The emergence of IOT Smart city
IoT Smart City faces yet another challenge due to rising volumes of solid wastes. Prevailing waste collection points have become areas of contention because manual collectors are leaving them in the sites unattended for long. Bad smell from the rained decaying waste makes it hard for nearby business people to operate efficiently. Besides, collection points near business are a risk to the health of the people. A smart city should protect its residents’ lives by taking quick response measures.
1.3.2 Need for algorithm and backend processing
An algorithm to automate the waste management process is an urgent necessity for IoT smart city systems. The set of commands in the algorithm coordinates trash collectors to designated collection points in the city. At the backend are systems operators who monitor ongoing events. The individuals are tasked with the role of detecting issues and reporting the matter to the relevant users. When fully functioning, the backend expects to solve redundant routing issues for the city.
1.3.3 Working communication system
Smarty city is failing because vehicle drivers and container location guards do not have communication channels.The decaying container matter remains in the city uncollected when guards fail to communicate (Vecchi et al. 2016). The proposed routing solution expects to contribute to the city’s waste management efficiency.
1.3.4 Research Questions
- What is the impact of inefficient waste management systems on the waste collecting companies?
- How to use IoT Smart Technologies to improve garbage collection?
1.3.5 Research Objectives
- To Identify the impact of inefficient waste management systems on the waste collecting companies
- To implements use of IoT Smart City technologies to improve waste collection across cities.
1.4 Problem Statement
Improper waste management problem has plunged IOT Smart city into shambles, and a viable remedy remains vital. Following the influx of investors, workers, and dwellers, it seems the management was less prepared to handle the surge in population, which resulted in increased waste disposal. Growth in commercial, construction, and domestic solid wastes have messed the IOT Smart city in Alawali district. The streets are littered with unattended smelly containers and disorganized bins. A similar situation replicates in other regions of the city, hence spoiling Smart City’s sprawling reputation. Workers seem to be experiencing waste collection routing problems as they can barely locate the dump points and collect them in time.
Additional problems have emerged in the solid waste collection process. The city does not have convenient locations for placing its waste bins. Most of them are located in estates, house fronts, and remote regions of the city. Access to such collection bins remains a problem especially since the recent suspension of bin collectors. Only a few containers are widely displayed for easy access, but the majority remain in the interior regions. The disorder does not only waste time but increases fuel costs of moving around to fill the truck. Traffic jam is an issue that slows vehicle transporters. Added to increasing fuel costs and many vehicles tasked to collect solid waste, the routing problem at Alawali IoT smart city continues to seem elusive.
However, the matter should soon be an issue of the past because the proposed algorithm expects to solve the issue. The integratedalgorithmis tounravel the mysteries of waste collection routing issues by directing truck collectors to pick the trash at the various routes just in time. It should solve the traffic issue by working on timing. Lastly, it should propose a remedy to a myriad of location issues seen.
1.5 Structure of the Paper
The paper contains five chapters. The first one is the introduction, followed by the literature review. The introduction in chapter 1 provides the study overview while Literature in chapter 2 discusses past studies on the topic to investigate developments on the matter. The third chapter is the proposal, which presents a detailed discussion of the algorithm and plans to be implemented. Following it is an assessment of the results in chapter 5. Finally, chapter 6 presents the conclusion to the study findings and suggested recommendations.
Chapter 2: Literature Review
In this section, the study conducts a review of previous literature that have focused on improving waste management in cities across the world. The aim is to assess their application of the route optimization for waste collection routing problems, as well how solutions are sort to enhance achievement of a technologically enhance cost-effective operation for controlling waste materials.
Figure 1: The number of references used and the year of publication.
From the figure 1, it can be shown that several references were used over the period. The highest number used per year is four (4) indicated by the year 2008. The lowest number used is zero for years 2004 to 2007, 2010 and 2013.
| Classification | Type of waste | Type of bin | Location | Type of problem |
| Residential | Household waste | Bins | Street | Arc routing problem |
| Commercial | Commercial waste | Large containers | Commercial | Node routing problem |
| Roll-on-roll-off | Construction wastes | Large trailers or containers | Construction sites | Node routing and bin packing |
2.1 Classification of Waste Collection Routing Problem
Figure 2: Classification of the west collection routing problems
Waste collection problems have affected cities for a long time. Hina (2016) confirmed the positive association between human populations and generated solid waste. She stresses the rising volume of complicated solid waste, claiming that the world produces an estimated 1.6 billion tons of waste per year (Hina, 2016). Besides, significant budget expenditures are directed towards waste management (Hina, 2016). Precisely, in 1990, Asia alone spent over $25 billion on a year toward waste management, even as the figure expects to rise to $50 billion in 2050. Similarly, the US spent 12.12 billion in 2018 on solid waste management. As all evidence suggests, solid waste management is costly, and nations should use convenient and cost-effective strategies to manage the situation.
Researchers have continuously sought solutions to waste management routing problems. As new technologies emerge, populations grow, while waste collection continues to remain an issue. Waste collection routing is amatter that existsin separate classified units. According to Han and Ponce-Cueto (2015), waste collection exists in three classified groups as designed by Golden et al.: Residential, commercial, and Roll-on-roll-offin Figure 2 (Han & Ponce-Cueto, 2015). Each waste originates from a specified source in the classifications, leading to three types of solid wastes. The types include household waste, commercial waste, and construction waste (Han & Ponce-Cueto, 2015). The classifications continue onwards based on the category of garbage being managed. For instance, classification, according to bins, includes the bins, containers, and large trailers and containers (see Figure 2). Classification, according to the location separated into street, commercial, and construction sites (Han & Ponce-Cueto, 2015). Finally, when classified based on the routing problem, they yield the Arc routing problem, node routing problem, and node routing and bin packing. Algorithm programming applies to each classification unit.
2.2. Waste Collection Routing Problem
2.2.1 Arc routing problem
According to Otoo(2012), the author asserts that an arc routing problem can arise in scenarios where there are multiple locations for the collection of residential waste. In the conducted study, Otoo (2012) has convincingly reviewed other previously conducted studies on the issue of arc routing problems for waste collection in smart cities. Further, Otoo (2012) expansively elaborates on the multi-objective mixed-integer programming model (MIP) and how the application is employed in the analyzation of the optimal path within a geographic information system (GIS) environment in a waste collection network. Satisfactorily, he demonstrates that the integration of GIS and the MIP in a major urban setup to manage solid waste. Also, the study exhibits computation of results of the proposed management scenario, the current scenario and the modified management scenario as the solutions of a similar quality. When examined, the outcome revealed a 36.46% reduction in traveling distance in the two scenarios. Similarly, Otoo (2012) established a 6.03% reduction in collection time, thus depicting a significant improvement in comparison to the current scenario.
In his study, Otoo (2012) has also solved the capacitated arc routing problem (CARP). Unlike in other routing problems affecting waste collection, Otoo (2012)applied two lower-bounding methods to enable incorporation of a three-phase heuristic and side constraints to enhance the generation of the optimal solution in combination with first lower-bounding method. Further, he generated a subsequent feasible solution in situation where the heuristic embodied an upper bound of the identified problem. However, one notable aspect with Otoo’s (2012) study is that the heuristic he developed was a route-first and then cluster-second methods. His study has also highlighted an ant algorithm aimed at designing functional collection routes for smart cities and even urban waste. In this scenario, he there is he establishes that the quality of an algorithm can be ascertained through repeatedly testing it over a real-life instance by focusing on Sant Boi del Llobregat municipality in Barcelona.He also determined the quality of the established algorithm by conduct a test based on the capacitated arc routing problem literature. Moreover, Abdallah, Adghim, Maraqa & Aldahab (2019) in their study have presented a dataset outlining the arc routing problem for waste management.
One notable thing is that Abdallah et al. (2019) computational results fall within 4% of the best-known solution, thus making it relevant for this research. There are instances such as Otoo (2012) whereby his dataset is up to 5.08% of the best-known solution. On the other hand, his study outlines a clear heuristic technique inspired by the waste collection problem in Lisbon for CARP. In his study, it is possible to deploy the proposed heuristic for both the directed and mixed cases. In the scenario, mixed cases indicate that waste generated in an urban area could be collected simultaneously on both sides of the road whereas, for directed cases, waste can only be collected on one side. Nonetheless, Otoo, D. (2012) and Abdallah, Adghim, Maraqa & Aldahab (2019) have reported essential computational results on a randomly generated date for the directed case. A similar approach is also noticeable among both studies in the scenarios concerning extended CARP benchmark problems. Across the board, generated computational results involving an estimated 400 notes for the directed problem depicted gap values. In this case, the values varied between 0.8% and 3%. For the case of the mixed problem, studies by Otoo, D. (2012) and Abdallah, Adghim, Maraqa & Aldahab (2019) established four heuristics such as extended Ulusoys, extended Path Scanning, extended Merge, and the extended Augment-Merge. However, one encouraging thing is that the authors were able to obtain encouraging feasible solution falling within the targeted gap values of 0.28% and 5.47%.
Figure 3: Arc Routing Problem
According to Li, Borenstein & Mirchandani (2008), their researchfocused on solving solid waste collection problem in Porto Alegre, Brazil. Their findings are relevant considering that Porto Alegre had a population of about 1.3 million people spread across 150 neighborhoods. Therefore, such findings can be relevant in the context of the smart city being focused on in this research. Unlike other solutions to the arc routing problem, Li, Borenstein & Mirchandani (2008) designed an efficient schedule plan for a truck with the primary aim of minimizing the fixed and operating costs. Analysis of their finding shows that for their case, the collected waste was discarded at identifiable recycling facilities as opposed to the conventional disposal facilities. Additionally, the heuristic approach used by Li, Borenstein & Mirchandani (2008) balances the undertaken number of trips within the identified recycling facilities. Based on the presented discussions, this is aimed at guaranteeing job opportunities for people living in different city areas where such recycling facilities are located. In this case, the computation results indicated that the mean number of vehicles used and the distance travelled could be reduced, thus saving about 25.25% and 27.22% respectively.
Moreover, Mourao, Nunes & Prins (2009) proposed two key two-phase heuristics for handling a sectoring arc routing problem (SARC) in the context of a municipal waste collection problem. Their study outline that in the context of SARC, it is possible to undertake partitioning of the street network into sectors. According to Mourao, Nunes & Prins (2009), such practice is purposely done to ensure that required vehicle trips are built-in consideration to each partitioned sector, therefore, minimizing total time used over for all the trips. The proposed heuristics further consider route compactness, workload balance, and contiguity. Additionally, Ogwueleka, (2009) proposes a heuristic procedure that encompasses a route and the method for solid waste management solution in Onitsha, Nigeria. The study conducts a cross-sectional analysis in such a case unlike in other scholarly studies, Ogwueleka (2009) used fewer collection vehicles and even reduced the route length by 16.31%. However, the author has attributes this to 25.25% saving in the cost of collecting waste and subsequently a 23.51% reduction in collection time. However, one consistent aspect of the study findings by Ogwueleka (2009), Mourao, Nunes & Prins (2009) and Li, Borenstein & Mirchandani (2008) is that there are cases where waste collection problems in urban areas are solved as arc and node routing problems.
Bautista, Fernández & Pereira (2008) comment : start with word when they transformed the initial arc routing into a node routing problem, have expounded such a phenomenon. Based on their discussions, this was as a result of the road constraint in the Municipality of Sant Boi de Llobregat, Barcelona. Bautista, Fernández, & Pereira (2008) maintain that their approach was based on the nearest insertion methods and the nearest neighbor. However, the generated computational results showed that the deployed methods helped in lessening total distance when compared to the current routes.
Additionally, Santos, Coutinho-Rodrigues & Current (2008) lengthy outlined a special decision support system (SDSS) and its role in the generation of vehicle routes in the context of multi-vehicle routing problem. Unlike other scholarly sources, their approach focused on vehicles along arcs and nodes of an established transportation network. According to Santos, Coutinho-Rodrigues, and Current (2008), this is a worthy consideration aimed at accommodating streets that may be very narrow to accommodate the traversing of standard-sized vehicles. As a result, Santos, Coutinho-Rodrigues & Current (2008) are convinced that the demand along such arcs and even at network nodes should be improved to help solve the waste collection problem.
2.2.2 Node Routing Problem
Unlike the arc routing problem, the location to every point in an urban area is usually known under a node routing problem when solving the issue of waste collection. Therefore, this explains why vehicles are expected to travel from one customer to another when collecting waste basing on the established sequence along the designated vehicle route. Such sequences usually involve trips made by the vehicle collecting waste to the established disposal facilities. It further accommodates instances where a vehicle may be empty or even the last visit that might be made to the depot.
Figure 4: Node Routing Problem
However, there are fundamental differences between the arc routing problems and the node routing problem in terms of the objectives, solutions, and types. Santos, Coutinho-Rodrigues & Current (2008) assert that in node routing problems, the primary objectives are usually the collection of waste within an urban area from one point to another. This is different considering that for arc routing problems, solid wastes are usually collected along the edges of an established road network in an urban area. Furthermore, Ogwueleka (2009), Mourao, Nunes & Prins (2009) and Li, Borenstein & Mirchandani (2008) concur that there is a similarity in main components used in node routing problems and arc routing problems. Based on their discussions, vehicles, depots, drivers and road networks are utilized in both cases. A similar phenomenon is observed in terms of the intended solution for node routing problems and the arc routing problems. Analysis of the findings by Ogwueleka (2009), Mourao, Nunes & Prins (2009) and Li, Borenstein & Mirchandani (2008) uphold that a set of routes is usually performed by a fleet of vehicles in both node routing problems and arc routing problems. The authors in their findings insist that each route under the identified framework of collecting wastes usually starts and ends at depots. Unlike the arc routing problem, Mourao, Nunes & Prins (2009) in their study established that multiple types can be pursued to accomplish node routing problems. In this case, the authors maintain that it can be achieved in terms of vehicle routing problem with time windows (VRPB), distance constrained vehicle routing problem (DCVRP), vehicle routing problem with pickup and delivery (VRPPD), travelling salesman problem with time windows (TSPTW), travelling salesman problem with backhauls (TSPB) and travelling salesman problem (TSP)
Comparison of Arc Routing and Node Routing
Figure 5: Comparison of Arc Routing and Node Routing
Figure 5 compares the arc routing and node routing problems by highlighting their constituent characteristics based on types, solutions and their main components. These are the necessary components to help establish the differences both in application and effectiveness when solving the routing problem.
2.3 Static Waste Collection Routing Problem
A study by Anagnostopoulos & Zaslavsky (2014) offers insight into the static waste collection routing problem by revealing that waste bins are incorporated with actuators and level sensors. Unlike other routing problems, a level sensor in a static waste routing problem aimed to measure solid waste level in a bid whereas the actuator sends signal message to a designated vehicle once a pre-determined threshold is reached. The findings by Anagnostopoulos & Zaslavsky (2014) further indicate that a waste vehicle can be scheduled at any time once the actuator message is activated. Further, the authors, in their discussions, highlight that the waste collection terrain in the context of a smart city can be partitioned into discrete city sectors for efficient waste collection process given that each sector will be assigned a corresponding vehicle.
Based on the provided information, the article by Anagnostopoulos and Zaslavsky uses level sensors is an effective strategy to determine the right time when collection should occur.
The findings of the article regarding level detection are reasonable and based on evidence.
Figure 6: Static Waste Collection Routing Problem (Anagnostopoulos & Zaslavsky, 2014)
Static routing is an effective way of compounding the routing problem observed in solid waste collection. Level sensors provide a convenient tracking mechanism for estimating the duration of collecting waste before it starts decomposing. Static routing is a much effective solution, and it will act as a key component of the suggested system for solving the problem at Alawali IoT smart city.
2.4. Dynamic Waste Collection Routing Problem
In a conducted study focusing on Nafpaktia municipality, Asimakopoulos et al. (2015) outline that a dynamic waste collection routing problem is based on fixed vehicle routes and standard time intervals. However, the authors are concerned that in such contexts, the embraced decision-making process is mostly empirical, thus leading to decision biases. Consequently, Asimakopoulos et al. (2015) assert that such scenarios have led to incidents of uncollected overfilled waste bins and even the collection of unfilled bins. Subsequent findings by Ogwueleka (2009) confirm such assertions, indicating that such protracted incidents can galvanize dissatisfaction among the local society, a phenomenon that is worsened by the increasing costs.
In their study findings, Asimakopoulos et al. (2015) maintain that such a phenomenon usually contributes to 60% of transportation, waste collection cost and disposal. In their study findings and discussions, authors maintain that the dynamic waste collection routing problem is aimed at reducing the distance between the collection points and subsequently minimizing routes taken by the vehicle. Ogwueleka (2009) in his finding asserts that taking into consideration the fill level of bins can help reduce waste collection cost by an estimated 20%. For this reason, Ogwueleka (2009) has discussed the essence of a real-time monitoring system to help in the transmission of fill levels and monitor waste bins. Ogwueleka (2009) is convinced that undertaking such measures can help make the process of collecting waste cost-effective and efficient.
Asimakopoulos et al. (2015) have further discussed various approaches that can be tapped to enhancing data harvesting during the waste collection process. For instance, Dynacargo is a notable approach that has been proposed by authors since it allows for the customization of recyclable waste. Based on the highlighted discussion, Asimakopoulos et al. (2015) state that adopting a Dynacargo architecture can easily cope with changes in cargo and the collection points. Therefore, this forms a key component under the dynamic waste collection routing problem. Unlike other approaches to the collection of waste, Dynacargo utilizes real-time data to optimize vehicle routes. It also utilizes multiple data sets to facilitate efficient transmission from the collection point.
Articles from assessed from renowned scholars on dynamic waste collection routing problems provide practical reasoning. For example, approaches proposed to enhance data harvesting such as Dyncargo’s model is effective because its evidence provides reasons to accept the model.
2.5 Smart Waste Collection Routing Problem
A series of studies have explored the routing problem in smart cities during waste collection to unravel an issue that has paralyzed urban cleaning initiatives. According to Anagnostopoulos, Zaslavsy, Medvedev, & Khoruzhnicov, (2015) cities experience delays of solid waste transportation due to traffic jams, disorganized location of collection bins and containers, leading to the collapse of efficient cleaning projects. Consequently, the authors suggest timely employment of the Internet of Things (IoT) in smart cities under the top-key query-based and scheduling model as the solution to the issue (Anagnostopoulos, Zaslavsy, Medvedev, & Khoruzhnicov, 2015). Ramos, de Morais, & Barbosa-Povoa, (2018) also investigate smart waste collection issues using the Capacitated Vehicle Routing problem to realize that improper assignment of the vehicle to the right route stands out as the leading cause of delays in solid waste collection. Experimented projects of CVRP in various regions have proved efficient if solving routing issues in conglomerated urban areas.
Smart Waste collection routing in smart cities is much efficient under the combined use of IoT supply network information. Medvedev, Fedchenkov, Zaslavsky, Anagnostopoulos, & Khoruzhnikov, (2015) offer outcomes to show that IoT avails information on schedules and targets of carrier operators. After understanding the area to tackle, drivers follow set procedures to collect and deliver waster from production points and dumpsites for treatment and storage as needed. Even after disposal, Zeng, de São Pedro Filho, Sousa, Patil-Dake, J., & Arenhardt, (2017) observe difficulties in the treatment of the waste as another global concern. Aside from polluting air and reducing land space, solid wastes make it hard to practice agricultural activities.
However, the routing challenges in smart cities should not remain a problem because IoT’s sophisticated technologies should solve the issue with ease. The article is even more informative with researched and evidenced to confirm their claim. Most of the suggested solutions such as the IoT are not effective.
Figure 7. Routing in a smart city
Chapter 3: Research Methodology
3.1 Introduction
This chapter discusses the methods to be used in developing the route optimization model to facilitate smart garbage collection for the Alawali district, Mecca City. The study adopts route optimization technological strategies to help build the shortest route network that could enhance efficiency in garbage collection. The strategy comes based on the understanding that it is not easy to perform routing effectively primarily due to the complexities of garbage conditions in major cities. As such, the use of technology can enhance the achievement of a best-fit route that can efficiently optimize the garbage collection process. Consequently, the methods to be employed in this discussion focuses on designing a static route by using software that encompasses customer-oriented features to ensure their satisfaction besides reducing the costs and time that garbage companies experience while planning (Dorneich, 2003). A less costly and efficient routing mechanism is needed for the city.
The chapter discusses various problems that need to be solved and used strategies in routing solid waste collection. The project discusses the earlier application of static routing because it plans to apply it in the design in the next chapter. The chapter further compares the technique to traveling salesman problem (TSP) and the vehicle routing problem (VRP), which would be used in developing a dynamic route optimization in the next chapter, as well as making a comparative examination of the TSP versus the VRP as used in different algorithms and the Hamilton path method. Essentially, the objective is to cross-examine such technological problems and ascertain critical issues that need to be addressed before choosing the best route to facilitate the achievement of the main objective of the project. Particularly, these problems encompass unique issues of focus through which programming machines have outlined to provide reliable technologies. This is based on the understanding that route optimization is a complex strategy that is influenced by a variety of factors, ranging from the location and number of stops along the route as well as stops that garbage collection vehicles should visit. All these factors have to be incorporated to ensure a cost-effective and dynamic route.
3.2 Route Optimization
Route optimization refers to the establishment of a routing channel that is cost-effective for sets of conventional stops. Usually, people think that the action involves simply identifying the shortest distance between two points, for example, from X to Y. Yet, this is not the case as it entails more than simply locating and mapping the shortest route. Particularly, route optimization is about minimizing of drive-in time for different stops set, while at the same time taking account for varied complexities such as vehicle capacities, customer time windows and vehicle movements, among other issues (Fitzgibbon, 2014). In the whole process, route optimization is implemented through the support of algorithms. As such, it becomes effective and efficient to easily maneuver around the complexities that encompass the optimization process unlike when a human is used to manually compute the unique parameters that entail searching for an optimal route. Besides, the use of algorithms reduces the time spent in the whole process. Consequently, the main purpose of route optimization is to find a substantial solutionto two difficult problems in computer science, namely; The Travelling Salesman Problem (TSP) and the Vehicle Routing Problem (VRP). These two problems are discussed in detail in the subsequent parts of the paper. However, the TSM problem will be applied in developing a static route optimization system while the VRP will be procured in the subsequent task to implement a dynamic route optimization system for the district. More so, of most significant are the issues that affect the outcome of route optimization. Notably, the distance and the visiting points, the visiting times, customer restrictions, driver availability and vehicle capacities are among the components that can influence the effectiveness of the route (Oliveira & Pardalos, 2011). Others include traffic jams and access to the best route. While assessing the road network system for the Alawali district, it is easy to note that the area is made of a complex set of routes that interconnects with subways through the busy town areas and some of the congested residential places in the district. The following figure is an aerial view of the district road network. From the figure, coming up with the most cost-effective route can be achieved through appropriate route optimization algorithms. However, employing traditional methods to facilitate route planning of such a setup might be time-consuming and difficult to finally attain the efficient route while taking note of inherent factors in routing.
Figure 2: Aerial view of Alawali district, Mecca City road network.Source: https://www.google.com/maps/@21.3250267,39.8970448,19770m/data=!3m1!1e3?hl=en-US
3.2.1 Travelling Salesman Problem (TSP)
The Travelling Salesman Problem (TSP) is among the widely studied optimization problems. Its basic formulation entailshaving a salesman visiting a series of cities in such a way that the total distance covered is minimized. Therefore, by definition, the TSP refers to a set of nodes or cities and the edges between them which determines the cost of travel between each point or node. A solution to a TSP is called a tour, that is made up of a combination of edges such that each node is visited sequentially (Oliveira & Pardalos, 2011). The optimal tour is the combination of edges that minimizes the total cost to the salesman. The traveling salesman problem (TSP) aims at finding the shortest Hamiltonian cycle in a graph. This problem is NP-hard and thus interesting. There are many algorithms used to find optimal tours, but none are feasible for large instances since they all grow either exponentially or factorially. To successfully employ this optimization problem, key steps will include conducting an exploratory visit of a set of cities while trying to minimize costs traveling. The cost incurred along each route is recorded while taking a keen interest in the delivery routes (Dorneich, 2003). The data collected during these exploratory activities is formulated as an integer for a programming problem. It is important to note that, the time to find optimal solution increases quickly with N. Moreover, it also requires the location of each stopping point, that is, bins or customers to be visited. Figure 4 below is an illustration of the Travelling Salesman Problem (TSP).
Figure 4: Illustration of Travel Salesperson problem pattern
Figure 4 illustrates the patterns that could help establish a less costly route while visiting all garbage collection points and returning to the initial point for the garbage trucks. A single route is used to move garbage collected across the district or production points and deposited into the depot, taking into account efficiency, timeliness and cost management. The method assumes that the costs and time spend while moving from point A to B is symmetric, that is, it is the same as moving from point B to A (Azad, 2008). Thus, various trucks can service the customers throughout the route from different directions without any extra cost or time wastage.
The problem is mathematically formulated as follows;
For a set of m locations listed as 0, 1, …., n that have to be visited and distance between each stop as i and j is indicated as cij. A decision variable yij for every (i,j) visits such that;
From the description, the objective function would be;
To minimize
……equation 1, subject to constraints, such that after salesman has visited stop i, he should visit only one location or stop next.
……equation 2, when returning, then he must have been in only one-stop, thus;
…. equation 3, further, it is critical to ensure that there are no sabotages along the route. The tour should be connected fully such that;
——equation 4, where S shows all sets of tours.
The constrains can be formulated in other forms to help eliminate sabotages such as network flow constraint and MTZ constraint, among others. However, despite being the most widely studied computational model, there has been no compact solution so far for the general case.
3.2.2 Vehicle Routing Problem (VRP)
The vehicle routing problem (VRP) is among the most challenging combinatorial
optimization problems. Since its emergence as the truck dispatching problem, the VRP has become increasingly an interesting research area due to its wide applicability and economic importance in reducing operational costs in distribution systems (Azad, 2008). The basic VRP consists of a set of trucks, customers and a depot. By definition, it is an attempt to address the logistical costs transport vehicles through establishing of a least-cost route based on the existing capacities availed from one central depot to the next set of geographically distributed customers holding positive demands. Each of these customers has to be fully serviced timely and cost-effectively once, basically by one vehicle. The route length and the aggregate demands should be equal or below the total capacity. However, the route optimization strategy seeks to ensure that deficiencies in the two components are minimized setting into account the need to sufficiently meet the demand. Along the route, the vehicle moves back and forth from the depot and customers it is assigned. Figure 5 below is an illustration of the vehicle routing problem.
Figure 5: Illustration of the Vehicle Routing Problem
When implementing VRP routes, various assumptions are made. First, the data incorporated in the implementation is randomly generated rather than using real-life data. As such, this enables in-depth analysis because it is effective to construct datasets in a way that accommodates the ability to address other issues.
The mathematical formulation of VRP is derived as an extension of TSP expression. However, the model is modified to include two vehicle indices for VRP formulations. The objective function is;
Minimize
Subject to
, whereby, the first and second constraint (in equations 6 and 7) requires that only one arc enters and leaves each stop associated with the client, accordingly. The third and fourth constraint (in equations 8 and 9) indicates that there is the same number of trucks exiting and entering the depot. The fifth constraint (in equation 10) is for the capacity required to be held by each truck. It requires a fully connected route, at the same time, the vehicle capacity should be sufficiently equivalent to demand. Lastly, the sixth constraint (11) is an integration constraint. A client set S is passed through by several arcs that such that S>= r(s), giving the least number of vehicles required to serve clients.
Similarly, the enormous majority of the real-time dynamic problems of vehicle routing presently capture all the required data to enable in-depth analysis for a particular route. Additionally, it will be assumed that a given location is distributed along with N points of the costs for traveling between locations, demand for each point and relative vehicle capacity are put into consideration. Further, there a definite number of vehicles that are known to be operating on the optimized route. Subsequently, the problem can be formulated as an integer program in several ways. While implementing VRP, it is also assumed that the time required for finding an optimal solution increases quickly for changes in N.
3.2.3 TSP versus VRP Problem
Both the TSP and VRP are some of the most common problems when it comes to the management of distribution, hence over the years, they have attracted different researchers to examine them within the combinatorial fields of study. As a result, there has been the development of important groups of algorithms, both heuristics and exacts, being applied currently. Comparing the two problems, it is ascertained that VRP is a generalization of TSP (Whitten, Bentley & Dittman, 2004). However, when formulating VRP, one requires the imposition of real constraints, for example, the total number of vehicles, vertices for each vehicle, among others. VRP entails visiting different locations while relying on a fixed number of vehicles besides minimizing the costs of traveling. Equally, the problem can be attributed to multiple numbers of traveling even though the vehicles begin from a similar location (Whitten, Bentley & Dittman, 2004). On the contrary, TSP attempts to answer how to maneuver through multiple locations using the shortest distance to visit each location or stops and return to the original location. More so, it uses only one route. Also, the problem is the simplest, unlike the VRP problem that becomes complicated due to multiple routes. In terms of similarity, both methods are highly related since they hold a condition that only one (1) truck or salesman is being used in the operation (Whitten, Bentley & Dittman, 2004). The two problems are subject to similar constraints such that capacity constraints vehicle is required to collect items at each of the identified locations while ensuring maximum capacity. Moreover, the time window for visiting each location is specified.
3.3 Choice of Algorithm
Selecting appropriate algorithms would be key in solving the routing problems besides ensuring that the project objectives are met. Considerations in making this choice would be based on algorithm qualities that would help increase efficiency either by reducing time or costs incurred for companies to operate throughout the designated routes within the Alawali district. According to Whitten, Bentley & Dittman (2004), different algorithms can be adopted in enhancing the case. Some notable examples include the genetic, anti-colony and tabu search algorithms. Briefly, the ant-colony algorithm employs the tactics of ants in solving the routing problem (Freitas, 2002). It is a probabilistic technique to facilitate a solution to computational problems, to graphically culminate to a suitable route (López-Ibáñez, Stützle, & Dorigo, 2016). Combine with tabu search, the algorithm is likely to yield a cost-effective route to enhance the distribution of vehicles and the collection of garbage. Going forward, the nearest neighbor, which is discussed below is the basic of the two algorithms where the search for the cost-effective route is randomly done until finally, the shortest route is identified.
3.3.1 Hamiltonian path
The Hamiltonian path expresses a path that is either is a constituent of a directed or undirected graph that is attached to different vertices but once. It can be described through a cycle, usually referred to as a Hamiltonian cycle. Whether the existence of a cycle or such a path is exhibited on a graph or not is called the Hamiltonian path problem, characterized an NP-complete such that it is solvable through the brute forces as well, can be simulated to find a solution to other problems through algorithms (Whitten, Bentley & Dittman, 2004). Hamiltonian cycles and paths emerged after the invention of the iconic game by William Rowan Hamilton. The technique is used in implementing a dodecahedron edge graph. Through the application of incosian calculus, Hamilton came up with a solution. Icosian calculus is characterized by similar unity routes. However, the solution to the problem is unique from the arbitrary graphs (Whitten, Bentley & Dittman, 2004). Essentially, a Hamiltonian path does not end to a point it began. It goes through every point, basically referred to as vertex. However, when the path starts and ends at some point, it is referred to as a Hamiltonian cycle. In the case of a traveling salesman problem (illustrated in figure 8 below), it can be seen that the truck is required to make several stops at client notes until it reaches delivery and back. Of critical objective in this movement is to make the journey using the shortest time and distance as possible and return to the depot. The aim is to identify the shortest route that allows the truck to visit client notes and return to depot cost-effectively. Notably, the TSP is a Hamiltonian cycle, denoting a difference between the TSP and Hamiltonian paths. Secondly, the TSP method is implemented when identifying a path with permutations along with every node. At the same time, the problem is NP-complete where the shortest path is referred to as the polynomial time.
Figure 6: Illustration of Travelling Salesman Problem with the Hamiltonian path
Equally, the Hamiltonian path solution to TSP as illustrated in figure 6 above would be formulated as shown in the flowchart in figure 7 below, which traces the cost-effective channel to help optimize garbage haulage across the district;
Figure 7: Flowchart representation of the Hamiltonian path procedure that is used to find the solution TSP problem
A truck begins at the start point after which it moves to the next node by selecting a valid edge. The choices here are whether to backtrack to the previous node, which has options of ‘yes’ or ‘no’ depending on the shortest route to reach on the node that has not yet visited. Once an optimal choice is identified, the truck proceeds to ensure that all the nodes are reached efficiently as possible while targeting to deliver the required services to the customers and return to the depot, that is, the original point.
Accordingly, the Hamiltonian path can be implemented in finding a solution to the VRP. Unlike TSP, VRP seeks to identify multiple routes that the fleet of trucks can traverse cost-effectively towards a target client node. It paints a general outlay of the TSP. As illustrated in figure 8, customers are distributed all over the region and all have to be visited. In this case, the company needs to find a solution to routing its large vehicles across the area. Usually, in such cases, zoning is used and routing implemented through the established zones instead of focusing on individual customers. However, there is a need to schedule for each customer. Hence, this is where Hamilton path problem emerges and, in most cases, it offers a good solution in determining how all these customers should be visited.
Figure 8: Illustration of the Vehicle Routing Problem with Hamiltonian path
Figure 9: Flowchart representation of the algorithm that is used to find a solution to the NP-complete problem
Once the mode of visiting all the clients is attained, managing the flow of the trucks becomes easy, courtesy of the Hamiltonian path. As illustrated in figure 9, there are paths that the trucks will not go through because they are not cost-effective. However, the ultimate goal is to visit all the nodes while taking into consideration the amount of time and transportation costs incurred in the operation.
3.3.2 Nearest Neighbor Algorithm
As the name suggests, the algorithm targets to establish the shortest distance between the depot and its nearest destination or neighboring node. The total neighbor distances are averaged to ascertain the size of the average distance concerning the averaged hypothetical random distribution. Notably, the nodes are assumed to be clustered. Particularly, the algorithm is used following some steps. This section discusses the use of the nearest neighbor algorithm to find a solution to the traveling salesman problem.
For a general overview, the first step will involve ensuring that all the vertices are initialized, assuming that they are unvisited. Then, an arbitrary vertex is selected and assigned a random letter, say T. T is marked as a visited vertex. The following activity involves finding out the shortest edge which connects the visited vertex and those that are unvisited, for instance, node W. The process draws a set of visited vertex which is then marked into the same domain and terminated if all is done. Eventually, a sequence is established, outlining visited vertices, which implies the results of the algorithm.
The algorithm is easily implemented. It is also quick in executing the program. However, it is prone to missing shorter routes hence, it is critical to compare and establish whether the first tour stages are comparable to the last few stages, the results are considered reasonable. Otherwise, large discrepancies should raise doubts. Calculations begin with identifying the nearest neighbor as follows;
Nearest neighbor = the observed distance between nodes and their respective neighbor, DO/ expected average distance from randomly given nodes, DE
The expected average distance, DE is obtained through the following formula;
—equation 12
From equation 5, n refers to the total number of nodes while A is the minimum enclosing rectangular area surrounding all nodes. The z-score for the average neighbor is computed as;
but …… equation 13
Looking at the equation, various interpretations can be made. When the mean neighbor ratio is below 1, that is, NN <1, it is an indication of clustering along the path. However, if NN>1 implies that the trend is headed to dispersion.
When applied to solve the TSP problem, the nearest neighbor algorithm can help achieve the shortest route. Stepwise, the truck begins at the depot, from where it goes to the nearest starting point. Establishing this point creates a chance to review and identify the immediate unvisited city. The process is repeated and before visiting all the cities and getting back to the destination. Mathematically, the best results can be obtained when the algorithm is repeatedly run over each vertex, for instance, n times. According to Levi, Bramel & Chen, X. (2014), the approximation can be illustrated as follows;
For all p-stops instances K of the TSP with a triangle inequality;
…. Equation 14
Additionally, for the random large values of p, there is always p-stops instances that are described as;
…equation 15
Hence, the algorithm may not be such promising when it is used in solving the TSP. It requires a modification to enhance the quality of its output. This is attained by using applying the algorithm from two endpoints instead of one. The process begins by randomly choosing a vertex on the graph and proceeding with the nearest unvisited vertex from the first one. Here, two endpoints vertices established. Then, the next vertex is added to the tour to the initially selected vertices, and update the end vertices once all the vertices are visited.
The following flow chart in figure 10 is an illustration of the solution to TSP using the nearest neighbor algorithm. As indicated by the flow chart, the first selected node is the depot, from which the next node is navigated after randomly examining the immediate neighbor from all the nodes. The distance value between the current and previous are compared simply to ascertain whether there is clustering or visiting points are dispersed. The activity proceeds once a solution is established. The process is repeated until all nodes are visited, then the truck returns to the starting point, the depot. The algorithm would also be used when it comes to finding a solution to the VRP in the second task when implementing dynamic route optimization later.
Figure 10: Flowchart representation of the nearest neighbor algorithm procedure that is used to find the solution TSP problem
Finally, it is important to note that although the nearest neighbor algorithm is effective for the estimation of simple tasks, it has limitations. First, when it comes to prediction, the algorithm gives out large data between every point and data point that is challenging for computation. It requires the whole of the data to predict the best route. Sometimes, the algorithm is likely to result in the longest route that the optimal one. To ensure that their precision, every constant along the route is multiplied by the distance measure of the optimal tour (Freitas, 2002). Hence, when making data inputs, one has to wait for some time until the algorithm outputs, which is tedious for data containing large volumes of elements. On the other hand, the algorithm is good for classifying small sets of data containing little features. More so, it is a simple tool to implement and can execute quick performances.
Chapter 4: Implementation
4.1 Introduction
This section presents how the implementation of route optimization would be made. The central focus is to address the approach that would entail the formulation of a cost-effective route by solving the above-listed problems beginning with the traveling salesman problem, TSP. As mentioned earlier, static route optimization will be a key focus in this chapter, targeting to address the movement of vehicles from the depot throughout the customer nodes to deliver the garbage collection services. The intention is to implement an efficient route that ensures investors in the garbage collection program meet their desired returns on investment while reducing costs in terms of labor, fuel and other operating expenses that emanate from a poorly planned route network. Primarily, the problem is to ensure that garbage haulers visit all the stops that are within the Alawali district. The truck begins from the depot and returns to the starting point once it has gone across all stops. Notably, the objective for the problem is establishing a path that adheres to these constraints; one, the truck visits all stops and should not leave any stop or client point unvisited. Secondly, the truck visits each stop point once, and thirdly, the distance that the truck covers while visiting each stop from the depot should be the minimum. The subsequent discussions draw an extensive overview of the implementation process, starting with an assessment of the case study mapping, procedures for collecting data and finally, the analysis of the data along the activity path.
4.2. Map of Case Study Area
The case study area is Alawali district, Mecca City in Saudi Arabia. Mecca City is a place with prime significance to the Islamic world as it is regarded as most sacred due to Holy Kaba. The city hosts pilgrimage and it is frequented by over three (3) million people from across the world for religious reasons (Imam & Cladera, 2016). As such, besides being among the oldest cities, it is highly respected by the Islam religion (Low, 2018). Geographically, the city is divided into three main regions, namely; Holy Mosque,Mina and Musdalfa & Arafat (Iman, Alhaddad, & Cladera, 2016). The focus of the study is Al Awali district, located to the south-eastern part of Mecca City within Musdalfa & Araft region. The following map shows the Mecca City and the target area of study, that is, Al Awali District;
Figure 10: Map of Mecca City
Figure 11 shows the distribution of roads within Al Awali district;
Figure 11: Al Awali District road network
Despite having a population of 1.6 million people only, the Mecca City receives over 3 million people annually, a number that has been increasing gradually. Millions of accommodation facilities exist throughout the city with hotels and camping areas spread all over. Usually, the pilgrimage arrive before Hajji commences and often stay for over a month before leaving. As a result, environmental concerns are increasingly becoming an issue especially with the increasing population, wastes keep increasing thus the growing need to ensure efficiency in garbage collection to keep the environment of the city clean. Further, there is traffic related pollutants that tend to undermine quality of air around the city and the high traffic during the pilgrimage season. This is notable due to growing residential structures in the district and across the city. Hence, there is need for an improved system of movement for companies operating in the district and by extension, the whole city.
4.3. Data Collection Processes
Based on the distribution of clients across the municipality, various process was used to collect data for analysis to find solution of the TSP model. As stated earlier, Mecca Municipality is a cosmopolitan area that has been transforming gradually from an old city to a modern setting with increase in infrastructure such as increase in roads, power systems, rails busses, accommodation and other social amenities. It is expected that by 2020, the population growth will increase by 164% and 180% by 2030 (Eckman, & Himelein, 2020). Garbage collection is done randomly by few companies that often fails to meet the increasing demands due to the growing population within the municipality. The situation has grown worse as congestion and high traffic become key hinderances to the maneuverability of garbage collectors. As such, to effectively collect data, appropriate methods are required to facilitate the process. Due to the random distribution of clients, the Hamiltonian path method was used to facilitate collection of data. First, the area was marked into a directed vertex(Levi,Bramel& Chen,2014). Secondly, to enable creation of a traceable route, each vertex was visited once and time and cost of travelling to the vertex recorded. Whenever it was clear that such a route was not eventually going to result into an optimal route, backtracking was done to retrace another route and same process repeated as a confirmation to the details recorded.
Accordingly, the process involves marking the client points using the geographical information system (GIS) to establish coordinates for both latitude and longitude. In this case, fifty-two (52) client points were selected, including the depot and their coordinates collected. The information was then collated and arranged in such a way that it is possible to estimate the distance from the source, that is, the depot and to the destination. Borrowing the idea of the ant-colony algorithm, it important to collect information on quantities and costs that are applicable to a given route. The purpose is to help eliminate routes which are short but characterized by other factors such as high traffic congestion and poor-quality road structure, which could eventually undermine the efficiency of vehicle movement. The following table is a summary of coordinates for each stopping points as collected.
| Location | Latitude | Longitude | |||
| point 1 (Depot)’ | 21.3723418000000 | 39.9048450000000 | |||
| ‘point 2’ | 21.3590931000000 | 39.9005427000000 | |||
| ‘point 3’ | 21.3588333000000 | 39.8940196000000 | |||
| ‘point 4’ | 21.3561754000000 | 39.8993625000000 | |||
| ‘point 5’ | 21.3512992000000 | 39.9008002000000 | |||
| ‘point 6’ | 21.3521785000000 | 39.9079241000000 | |||
| ‘point 7’ | 21.3580939000000 | 39.9105849000000 | |||
| ‘point 8’ | 21.3536549000000 | 39.9130954000000 | |||
| ‘point 9’ | 21.3510569000000 | 39.9115076000000 | |||
| ‘point 10’ | 21.3480991000000 | 39.9105849000000 | |||
| ‘point 11’ | 21.3459806000000 | 39.9072375000000 | |||
| ‘point 12’ | 21.3449413000000 | 39.9098982000000 | |||
| ‘point 13’ | 21.3469599000000 | 39.9119582000000 | |||
| ‘point 14’ | 21.3482190000000 | 39.9139752000000 | |||
| ‘point 15’ | 21.3461405000000 | 39.9153270000000 | |||
| ‘point 16’ | 21.3448414000000 | 39.9138679000000 | |||
| ‘point 17’ | 21.3439021000000 | 39.9162283000000 | |||
| ‘point 18’ | 21.3434624000000 | 39.9124517000000 | |||
| ‘point 19’ | 21.3428228000000 | 39.9097910000000 | |||
| ‘point 20’ | 21.3439820000000 | 39.9065294000000 | |||
| ‘point 21’ | 21.3407043000000 | 39.9051346000000 | |||
| ‘point 22’ | 21.3427029000000 | 39.9031605000000 | |||
| ‘point 23’ | 21.3450812000000 | 39.9039974000000 | |||
| ‘point 24’ | 21.3475395000000 | 39.9053492000000 | |||
| ‘point 25’ | 21.3495780000000 | 39.9039545000000 | |||
| ‘point 26’ | 21.3491383000000 | 39.9007573000000 | |||
| ‘point 27’ | 21.3511368000000 | 39.8975386000000 | |||
| ‘point 28’ | 21.3525557000000 | 39.8941483000000 | |||
| ‘point 29’ | 21.3494381000000 | 39.8925390000000 | |||
| ‘point 30’ | 21.3509769000000 | 39.8885908000000 | |||
| ‘point 31’ | 21.3552736000000 | 39.8858656000000 | |||
| ‘point 32’ | 21.3509569000000 | 39.8842563000000 | |||
| ‘point 33’ | 21.3556933000000 | 39.8811235000000 | |||
| ‘point 34’ | 21.3530154000000 | 39.8795786000000 | |||
| ‘point 35’ | 21.3520361000000 | 39.8770251000000 | |||
| ‘point 36’ | 21.3552936000000 | 39.8758878000000 | |||
| ‘point 37’ | 21.3583512000000 | 39.8744716000000 | |||
| ‘point 38’ | 21.3590706000000 | 39.8793425000000 | |||
| ‘point 39’ | 21.3588108000000 | 39.8851790000000 | |||
| ‘point 40’ | 21.3609091000000 | 39.8913374000000 | |||
| ‘point 41’ | 21.3609491000000 | 39.8968734000000 | |||
| ‘point 42’ | 21.3648658000000 | 39.8964657000000 | |||
| ‘point 43’ | 21.3667242000000 | 39.8976030000000 | |||
| ‘point 44’ | 21.3674037000000 | 39.9008216000000 | |||
| ‘point 45’ | 21.3661048000000 | 39.9049415000000 | |||
| ‘point 46’ | 21.3645600000000 | 39.9100143000000 | |||
| ‘point 47’ | 21.3635208000000 | 39.9155718000000 | |||
| ‘point 48’ | 21.3618822000000 | 39.9198634000000 | |||
| ‘point 49’ | 21.3599638000000 | 39.9174172000000 | |||
| ‘point 50’ | 21.3620221000000 | 39.9138552000000 | |||
| ‘point 51’ | 21.3632982000000 | 39.9055257000000 | |||
| ‘point 52(Deliver’) | 21.3571964000000 | 39.8535685000000 | |||
Table 2: Latitude and Longitude coordinates for study case.
Table 2 above exhibits latitude and longitudes of client points, starting from the depot point to delivery points. It is expected that the vehicle chooses one route through which it takes the shorted time to deliver the garbage collection service and back. The information in the table was obtained from the study case. Figure 12 below is a location map for all the 52 client points. The map helps reveals how each point is linked with the depot and the delivery point in terms of distance. The information was obtained through google search, after marking particular routes and collection stops across the Al Awali district;
Figure 12: Location of nodes based on coordinates by google
4.4. Data Analysis
By employing the Hamiltonian path algorithm, the movement of the truck was traced from the start point, after which it moves to the next node by selecting a valid edge. The choices here include the selection of backtrack to the previous node, which has options of ‘yes’ or ‘no,’ depending on the shortest route to reach on the node that has not yet visited. Once the optimal choice was established, the truck could proceed to the next point of the visit. Eventually, all the points were visited with the highest efficiency estimated based on the distance and time taken for the truck to move from the depot to the delivery point and then back to the original location. The data obtained from the coordinates of each node was later converted into a 52 by 52 matrix. The coordinates indicate the distance between one node to the other. Conditionally, in a static route optimization using TSP, it is assumed that once a trach moves to the next node, it should have come from only one previous node. The coordinates are then measured using google map to help establish the shortest path with improved accuracy. Figure 13 below is a summary matrix of the analysis of the optimal route using a Hamiltonian algorithm with TSP.
Figure 13: Output matrix from coordinates, distance in miles from each node and symmetric number
The asymmetric number used in the analysis for TSP refers to establishing the shortest Hamiltonian path on the finite mean graph with no loops. This case enables the effective establishment of a cost-effective way without saboteur nodes that could damage the achievement of the desired efficiency for vehicle movement. The parameters used in the analysis include the total distance measured in miles, the path direction, time in hours and minutes, the average speed for each track to move from one node to the other, and the cost of fuel in US dollars (US $). To effectively perform the simulation process, MATLAB software was used to establish the shortest path by the nearest neighbor algorithms. The objective was to find a static route optimization with TSP while applying the Hamiltonian path method to solve the traveling salesman problem, which was achieved.
Chapter 5: Preliminary Results
Following the analysis, various outputs were obtained. First, an optimal waste collection route was mapped, indicating the shortest and most efficient way for the movement of trucks from the depot point to the delivery points. The route attempts to map all the clients across the municipality, ensuring that there is only one truck moving at a given time towards a given direction while noting that all points are being visited once at a time, leaving no client behind. The mapping output is as shown in figure 14 below;
Figure 14. Diagram for 52 by 52 matrix
As shown in figure 14, all the 52 points are mapped out through the district area. This is meant to ensure that every client is serviced at minimal costs. The distance from one node to the other is estimated through the coordinates to route out the optimal path. This is clearly summarized in figure 15 below, which denotes particular coordinates for each node. The first node, 1, represents the depot, and the last node, 52, represents the delivery. This is after all clients have been visited.
Figure 15. Diagram showing latitude and longitude coordinates for each client nodes
Subsequently, a traceroute was established, which marks out the shortest path. The graph displays the shortest link from one node to the other through which vehicles run starting from the depot across the distributed network of clients in the city and culminates at the delivery points where they complete the route by disposing of the garbage. Here, the return cycle begins, tracing the same path back to the deport point. The trucks begin from the depot point, that is, node1 and ends at the delivery point, node 52. The analysis is displayed in figure 16, a graphical output analyzing the course of truck movements.
Figure 16. Graph for the result of shortest path with length distance
The above output was obtained using MATLAB software to calculate shortest distance through which the truck should move from the depot. Figure 17 below is a command window showing the input data during the analysis.
Figure 17. MATLAB command window
The results of summary information are displayed in table 3 below;
| Parameter | Number of stops | Fuel Efficiency | (Gas/fuel) price | Distance | Fuel Cost | Est. Average speed | Est.Time |
| Total | 51 | 4.4 mpg | 0.47 $/gallon | 56.38 miles | 6.02 $ | 25 miles/hr | 2 hr:15 min |
Table 3: Summary table
As shown in the table above, there are 51 stops across the district. Trucks should visit these client areas. The first point, which is the depot, is not included as it is the original point of the truck. To obtain the results as required effectively, several equations were used. The fuel cost was estimated based on the distance covered by the gas per fuel price divided by the fuel efficiency to establish the amount of fuel required over a route. The following formula was used;
…. equation 16
While time taken by each truck was estimated based on the distance covered and the average speed as shown in the formula;
The estimated average speed for each truck was 25 miles per hour and the current fuel/ gas price used is $ 0.47 per gallon in Saudi Arabia. Finally, trucks fuel efficiency was assumed to be 4.4 miles per gallon and distance estimated across the mapped area if 56.38 miles.
Chapter 6: Conclusion
Developing an efficient system for waste collection and management is a growing concern across many cities, especially with the increasing population and the need for a clean environment. Local governments are focusing on delivering quality service to the community while ensuring that costs are minimized by avoiding unnecessary wastage in the process. Planning for such an efficient system, especially in highly populated and widely distributed levels of clients across a given town setting, is tedious when left to manual planning. Hence, cities are embracing smart technology to facilitate efficient planning and improved service delivery. As established from the case study, Al Awali district growing garbage menace has precipitated to the procurement of a technologically advanced system to support waste management across its urban setting. The research undertakes to implement a static route optimization system with the traveling salesman problem, among other models such as the vehicle routing problem and dynamic TSP. The whole garbage system is reduced to the TSP problem that is eventually solved using the Hamiltonian path algorithm to establishing the shortest routing that is cost-effective and applicable to the city’s existing condition. Notably, the study concentrates on implementing and modeling the shortest path algorithm while incorporating details that facilitate the production of the district and the city map. The crucial part of the implementation process is the MATLAB graphical interface used in generating images, animations, and results of the distance and mapping of routes during the analysis.
References
Abdallah, M., Adghim, M., Maraqa, M., & Aldahab, E. (2019). Simulation and optimization of dynamic waste collection routes. Waste Management & Research, 0734242X19833152.
Anagnostopoulos, T., Zaslavsy, A., Medvedev, A., & Khoruzhnicov, S. (2015, June). Top–k Query Based Dynamic Scheduling for IoT-enabled Smart City Waste Collection. In 2015 16th IEEE International Conference on Mobile Data Management (Vol. 2, pp. 50-55). IEEE.
Azad, H. (2008). Advances in Computer Science and Engineering. Berlin: Springer-Verlag.
Bautista, J., Fernández, E., & Pereira, J. (2008). Solving an urban waste collection problem using ants’ heuristics. Computers & Operations Research, 35(9), 3020-3033.
Dorneich, M., C. (2003). Evaluation of a Dispatcher’s Route Optimization Decision Aid to Avoid Aviation Weather Hazards. Volume 212172 of NASA technical memorandum. DIANE Publishing.
Eckman, S., & Himelein, K. (2020). Methods of Geo-Spatial Sampling. Data Collection in Fragile States (pp. 103-128). Palgrave Macmillan, Cham.
Fitzgibbon, W. (2014). Modeling, simulation, and optimization for science and technology. Dordrecht: Springer.
Freitas, A. (2002). Data mining and knowledge discovery with evolutionary algorithms. Berlin-New York: Springer.
Han, H., & Ponce Cueto, E. (2015). Waste collection vehicle routing problem: a literature review. PROMET-Traffic&Transportation, 27(4), 345-358.
Hina, S. M. (2016). Graduate School (Doctoral dissertation, North Dakota State University).
Imam, A., & Roca Cladera, J. (2016). Mapping land cover changes of pilgrimage sites in Mecca using multi-temporal satellite imagery. Back to the Sense of the City: International Monograph Book (pp. 1017-1027). Centre de Política de Sòl i Valoracions.
Iman, A., Alhaddad, B., & Roca Cladera, J. (2016). Remote sensing efficiency for urban analysis of Mecca and surrounds. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences (pp. 905-910). International Society for Photogrammetry and Remote Sensing (ISPRS).
Levi, D., Bramel, J. & Chen, X. (2014). The logic of logistics: theory, algorithms, and applications for logistics and supply chain management. New York: Springer.
Li, J. Q., Borenstein, D., & Mirchandani, P. B. (2008). Truck scheduling for solid waste collection in the City of Porto Alegre, Brazil. Omega, 36(6), 1133-1149.
López-Ibáñez, M., Stützle, T., & Dorigo, M. (2016). Ant colony optimization: A component-wise overview. Handbook of Heuristics, 1-37.
Low, M. C. (2018). Mecca: Pilgrimage and the Making of the Islamic World (400–1500). In Places of Encounter, Volume 1 (pp. 127-144). Routledge.
Medvedev, A., Fedchenkov, P., Zaslavsky, A., Anagnostopoulos, T., & Khoruzhnikov, S. (2015). Waste management as an IoT-enabled service in smart cities. In the Internet of Things, Smart Spaces, and Next Generation Networks and Systems (pp. 104-115). Springer, Cham.
Mourão, M. C., Nunes, A. C., & Prins, C. (2009). Heuristic methods for the sectoring arc routing problem. European Journal of Operational Research, 196(3), 856-868.
Ogwueleka, T. (2009). Municipal solid waste characteristics and management in Nigeria. Journal of Environmental Health Science & Engineering, 6(3), 173-180.
Oliveira, C. & Pardalos, P. (2011). Mathematical aspects of network routing optimization. New York: Springer.
Otoo, D. (2012). Capacitated Arc Routing Problem: Collection of Solid Waste at Kwadaso Estate, Kumasi (Doctoral dissertation).
Ramos, T. R. P., de Morais, C. S., & Barbosa-Povoa, A. P. (2018). The smart waste collection routing problem: Alternative operational management approaches. Expert Systems with Applications, 103, 146-158.
Santos, L., Coutinho-Rodrigues, J., & Current, J. R. (2008). Implementing a multi-vehicle multi-route spatial decision support system for efficient trash collection in Portugal. Transportation Research Part A: Policy and Practice, 42(6), 922-934.
Vecchi, T. P., Surco, D. F., Constantino, A. A., Steiner, M. T., Jorge, L. M., Ravagnani, M. A., & Paraíso, P. R. (2016). A sequential approach for the optimization of truck routes for solid waste collection. Process Safety and Environmental Protection, 102, 238-250.
Whitten, J., Bentley, L. & Dittman, K. (2004). Systems analysis and design methods. Boston: McGraw-Hill Irwin.
Zeng, B., de São Pedro Filho, F., Sousa, M. V., Patil-Dake, J., & Arenhardt, V. (2017). The case of Brazil’s municipal solid waste management: Residents’ perceptions. International Journal of Environmental Sustainability, 13(3), 1-14.
Expert paper writers are just a few clicks away
Place an order in 3 easy steps. Takes less than 5 mins.