Introduction

Solid waste is an increasing concern to policy makers nowadays. It has been reported by the World Bank that the current global solid waste is approximately 1.3 billion tons and will approach 2.2 billion tons per year by 2025 (Hoornweg and Tata 2012). In developing countries, 80–90% of municipality budgets are reserved for collection services, while keeping lower collection frequency and efficiency (Ding et al. 2018). An important matter for municipality control is frequency of waste collection (Awasare and Sutar 2015). According to UN-Habitat, areas having high density of waste contain diarrhea six times higher than those where collection is frequent (Habitat 2010). Environmental threats such as contamination of groundwater and air pollution may happen if waste is not disposed (Bartolozzi et al. 2018). This raises an alarm of requisition of specific strategies for prevention and precaution of possible disasters that could be foreseen worldwide. Many studies that considered waste management as a strategy to minimize these effects can be seen in Han et al. (2018); Horodytska et al. (2018); and Yadav and Samadder (2018).

In order to reduce the negative effects solid waste can have on the environment, modeling and planning of solid waste collection is often performed in a computer before deploying to real cases (Das and Bhattacharyya 2015). The process of municipal solid waste (MSW) collection modeling is divided into two main phases: designing an optimization model and proposing a meta-heuristic algorithm to determine (near-) optimal collection routes of vehicles for minimization of collected time and distance. Following this strategy, many studies have been conducted. Cruz et al. (2015) designed a mixed integer optimization model for domestic solid waste collection. Yu et al. (2015) presented a bi-objective dynamic linear programming model which is lately given to a meta-heuristic algorithm to find optimal solutions. A 3D model, including conditions of driving, vehicle load, and road status, was designed to find routes having minimum fuel consumption (Tavares et al. 2009).

Buhrkal et al. (2012) proposed a mathematical formulation and a meta-heuristic algorithm to solve the waste collection routing in a time window. Das and Bhattacharyya (2015) divided the entire waste management system into three stages by formulizing collection and transportation into a mixed integer program. Heuristic solutions for waste collection were induced to identify optimal waste collection. Huang and Lin (2015) proposed a formulation with multiple trips for determining minimum routes in time constraints. Ant colony optimization was used to minimize distance traveled and time interval. Our previous works proposed a model for waste collection with particle swarm optimization in ArcGIS (Son 2014; Son and Louati 2016; Louati et al. 2018). Other relevant works can be found in Benjamin and Beasley (2010), Jiao et al. (2013), Elsayed et al. (2014), Zsigraiova et al. (2013), Khan and Samadder (2014), Malakahmad et al. (2014), Awasare and Sutar (2015), Sanjeevi and Shahabudeen (2016), Onan et al. (2015), and Cheng et al. (2017a, 2017b).

This research aims to propose a new Genetic Algorithm called SGA for determining optimal solutions for solid waste collection. The purpose of the new algorithm is to overcome drawbacks of previous works regarding the use of a local search algorithm. Specifically, that research utilized a local search algorithm associated within ArcGIS to generate an optimal path of a vehicle (Sanjeevi and Shahabudeen 2016). It should be noted that the path of a vehicle can be determined by local search (e.g., Dijkstra) but the optimal paths of many vehicles have to be found by an evolutionary algorithm (e.g., Genetic Algorithm). This clearly affirms that a fusion methodology between local search and an evolutionary algorithm should be set up for optimizing the entire systems.

Motivated by this idea, this paper proposes SGA—a new Spatial Geographic Information System (GIS)-based Genetic Algorithm for route optimizing of solid waste collection. The proposed algorithm uses a modified version of the original Dijkstra algorithm in GIS to generate optimal solutions of vehicles. Then, a pool of solutions which are optimal routes of all vehicles is encoded in Genetic Algorithm. It is iteratively evolved to a better one and finally to the optimal solution.

The reason Genetic Algorithm (GA) was selected in this research can be demonstrated as follows. It is known that GA is an optimization method to search for good solutions for complex problems by applying genetic operations such as population representation, selection, crossover, and mutation (Hemanth et al. 2018b). The selection (reproduction) copies high-quality chromosomes in the next generation for improving the quality of the population. The next step is the crossover operator that combines two parent individuals by exchanging some parts of these chromosomes to create a new offspring. The crossover in the routing problems selects each partial route of the two solutions to produce one route. After crossover, mutation operators are utilized to preserve diversification of the population. It involves the random change of a chromosome. All genetic operations are utilized to gain better solutions in the proposed method.

In order to validate the performance of the proposal, a case study at Sfax City in Tunisia will be performed. Comparison between the proposed method and the practical route is also given. The remainder is organized as follows: the “Proposed method” section presents the hybrid method, the “Experimental evaluation” section demonstrates the case study and experiments, and the “Conclusions” section highlights the conclusions and further works of this study.

Proposed method

Problem statement

The waste collection system involves a collection of vehicles starting at the depot (D). A vehicle travels gather sites (G) or handcart (H) to collect waste until its capacity is full. Then, it goes to the landfill (L) or transfer station (TS) to unload waste and then starts a new trip. Meanwhile, another vehicle can start its own trip until the total waste of all gather sites is zero. The problem is how to plan a schedule for all vehicles that can minimize the total traveling time and distances of the vehicles to save energy and reduce environmental emission caused by the vehicles (Son and Louati 2016; Louati et al. 2018). Figure 1 illustrates the problem.

Fig. 1
figure 1

Waste collection process (Son and Louati 2016)

Full size image

Proposed framework

The flow to solve this problem consists of four main steps:

  1. 1)

    Data preparation: Use ArcGIS to calculate distances and locations of nodes and combine them with attribute data.

  2. 2)

    Local search: Use Smart routing, which is an improved Dijkstra method in GIS (Louati et al. 2018), to set up a collection of solutions, including routes of vehicles.

  3. 3)

    Evolutionary: Use GA to determine the best solution.

  4. 4)

    Route display: Use ArcGIS with Python script to display the best solution on a map.

Steps 2 and 3 are illustrated in Fig. 2. In this method, we use the local search (Smart routing) to set up a pool of solutions. GA evaluates these solutions by calculating their fitness and selects the best chromosomes for the next generation followed by the genetic operators. The iterative procedure continues until a step condition is satisfied (Table 1).

Fig. 2
figure 2

Flowchart of the proposed algorithm

Full size image
Table 1 Pseudo code of the proposed algorithm
Full size table

Smart routing

Dijkstra is used in GIS software such as ArcGIS to determine for shortest paths from a starting location to a destination (Desai et al. 2018). Nonetheless, in order to use Dijkstra within the context of real-world transportation data, it must be modified to represent user settings such as waste quantity and network constraints while minimizing a user-specified cost attribute. Recently, Louati et al. (2018) proposed a new extension of the Dijkstra algorithm in ArcGIS called Smart Routing. In what follows, we present the main steps of that algorithm (Table 2).

Table 2 The smart routing algorithm (Louati et al. 2018)
Full size table

Genetic algorithm

Solution representation

An example is illustrated in Fig. 3 where solution x is represented by one vectors P(x) containing the routes of all vehicles in a trip. It shows the order in which each vehicle must visit a set of nodes.

Fig. 3
figure 3

An example of representation

Full size image

The solution representation is: {[(no. trip, ID of vehicle): (list of nodes of trip)] [(no. trip, ID of vehicle): (list of nodes of trip)]…..}, where (no. trip) is the number of Trip and (ID of vehicle) is an identifier of a vehicle. A population consists of P chromosomes (solutions) as follows:

$$ \mathrm{P}\left(\mathrm{x}\right)=\left\{{\mathrm{p}}_1,{\mathrm{p}}_2,\dots, {\mathrm{p}}_{\mathrm{P}}\right\} $$

with pi = P(x) represented as above.

Figure 3 presents a waste collection system of two vehicles and eight nodes (depot, transfer stations, and bins), in which node 1 is the depot (the starting node of all vehicles) and the others are gather sites containing waste. A chromosome p1 is encoded as in this figure. In this solution, three trips of vehicles 1 and 2 are executed.

  • The first trip of vehicle 1 (trip 11): vehicle 1 starts from the depot node (ID = 1) and then goes to node ID = 8 to load waste. It then moves to node ID = 6 to load waste and finally ends up at node ID = 2 (transfer station) to dump waste.

  • The second trip of vehicle 1 (trip 21): the vehicle starts from transfer station (ID = 2) and moves to gather sites IDs = 7 and 9 to collect waste and then go to the transfer station (ID = 2) again to dump waste. Finally, it arrives to the depot (ID = 1) to end its trip.

  • The first trip of vehicle 2 (trip 12): vehicle 2 also makes the similar routes (1➔5➔3➔3➔1).

  • Finally, all vehicles stop collection routes at the depot.

Here are some remarks for this representation:

  • Firstly, it is an ordered list of all nodes to be visited by vehicles in the system. Thus, changing the order of nodes will bring a new solution, but we have to ensure that the waste constraints such as the current waste quantities of vehicles must be greater than the current waste quantities of gather sites so that the vehicles can load waste.

  • Secondly, the total distance and time of vehicles can be computed by this representation.

Fitness function

The main objective is to minimize the waste collection time of all vehicles as follows:

$$ \operatorname{Min}\ \mathrm{Fitness}\ \left(\mathrm{i}\right)=\sum \limits_{k\in V}\sum \limits_{i,j\in \overline{2,{N}^{+}}}{t}_{ij}(k)\ {x}_j^i(k) $$
(1)

where tij(k) is the traveling time between nodes i and j of vehicle k and \( {X}_j^i(k) \) measures the capability of vehicle k to travel from node i to node j. \( {X}_j^i(k)=1 \), i\( {\mathrm{x}}_{\mathrm{j}}^{\mathrm{i}}\left(\mathrm{k}\right) \)f vehicle k is able to travel this arc and \( {\mathrm{x}}_{\mathrm{j}}^{\mathrm{i}}\left(\mathrm{k}\right) \) in otherwise.

Remarks

Although the objective function is to minimize the waste collection time of all vehicles, it is further induced that the function can be extended to minimize the traveling distance and other environmental emission factors. For simplicity, we use the fitness function as in Eq. (1).

Selection

In this approach, the best chromosomes are selected by the order of fitness. Firstly, fitness value of each chromosome in the actual population is computed. Afterwards, the candidate solutions are ordered by fitness in the descending order. Around 50% of chromosomes in the population with the highest fitness are selected to be reproduced in the next generation.

Crossover

We follow the crossover procedure of Murata and Ishibuchi (1994). Firstly, one-point crossover is used by selecting the starting node on the new trip as a crossover point. The permutation is copied from the first parent at it. Then, the second parent is scanned. If the nodes do not exist in the child, they will be added in the same order.

As shown in Fig. 4, we consider an example with one depot (ID = 1), one transfer station (ID = 2), and six gather sites (IDs = 3–9). A crossover point is marked on the first node of the second trip of vehicle 1. We have two parents: “parent1” and “parent2.” An offspring is created by considering the first node in the new trip of vehicle 1 as a crossover point. The first part of the child is formed by taking by the left part on the crossover point of parent1. The second part of the child is accomplished by taking from the right part on the crossover point of parent2 in the same order.

Fig. 4
figure 4

An example of crossover

Full size image

Mutation

In our approach, we use the swap mutation. We randomly select two positions of nodes and swap their values to get diversification in the population by creating a new solution (Fig. 5).

Fig. 5
figure 5

An example of mutation

Full size image

Experimental evaluation

Case study at Sfax City

Sfax is the second largest populated city and among the most polluted cities in Tunisia. The republic is located in North Africa and consists of 24 regions. Tunisia contains 10.778 million inhabitants and generates 2.423 million tons and 0.815 kg/day per capita. Tunisia has a 2.5% of MSW generation growth, and the final destination of 70% MSW is the landfill (Wilson et al. 2012). Sfax has a high pollution rate and high quantity of population with 272,801 inhabitants living in the city center (urban Sfax) which explains the high average waste quantity (0.702 h kg/hab./day).

The municipality solid waste sources at Sfax are called the gather sites. The current real scenario of Sfax, especially at borough “elboustène,” includes a depot (the starting place of vehicles), many gather sites, and many collection centers (or transfer stations). The vehicles collect waste to transfer stations. An agricultural tractor can carry up to 1.6 t of waste. A dumper truck can transport 2.3 t of waste and a compactor vehicle can carry 7.4 t of waste. Drivers start the first trip from the depot at the same time. After loading waste, and total load reaches the vehicle’s capacity, each vehicle unloads it at a collection center and starts a new route. Inhomogeneous vehicles are used. The case study contains one depot, two transfer stations, and four vehicles, including two agricultural tractors, one dumper truck, and one compactor vehicle (Table 3).

Table 3 Vehicles and bins of MSW scenario at Sfax
Full size table

The vehicles start at 06:00 am from the depot and finish the trip at the depot again but they must go to transfer station 1 or transfer station 2 before coming back the depot before 1:00 pm. The collecting waste process has two steps. In the first step, the vehicles start at the depot, collect waste at the gather sites, and then unload it at a transfer station. In the second step, the vehicles start at the transfer station and come back the depot. We have three types of vehicles, namely, agricultural tractor, dumper truck, and compactor vehicle, that have capacities of 3528, 5071, and 16,315 kg, respectively. There are 39 gather sites and three nodes being the depot, transfer station 1 and transfer station 2. The optimization model for solid waste collection in Sfax is given in Tables 4 and 5.

Table 4 Notations of the model
Full size table
Table 5 The optimization model
Full size table

Waste collection is modeled by (N+, Z, V, Q), where N+ is a collection of nodes; Z and Q change dynamically by time. When vehicles in V move to gather sites to load waste and dump them at a transfer station, waste quantities of those nodes decrease. Partial loads are not allowed, which means that a vehicle should load the total waste quantity in a gather site without exceeding the capacity of the vehicle (consider 100% of vehicle capacity). The objective of the waste collection problem is to minimize the traveling (operational) time which indirectly implies the minimum of total traveling distances of vehicles.

Results

In this section, we compare the proposed SGA method with the practical routes (Wilson et al. 2012) and the ArcGIS Desktop 10.1 with the original Dijkstra function (Karadimas et al. 2007) on the model in Tables 4 and 5 of Sfax City. All algorithms are implemented in Python using a computer with configuration of Intel Core 1.9-GHz PC with 4 GB of memory. Vehicle Routing is solved by using the ArcGIS solver (Desai et al. 2018). Genetic Algorithm is run for 10 iterations and with 30 solutions for each population. The best solutions are reported.

The criteria for evaluation are traveling distances (km), operational time (h), fuel consumption (L), and average truck release (g/km) of all vehicles after finishing the waste collection.

The “Comparative results” section, firstly, presents the comparative results in tables. “Interpretation on maps” section shows the route maps of all methods. “Sensitivity analysis” section performs the sensitivity analysis.

Comparative results

Table 6 demonstrates the comparative results on each type of vehicle. It has been shown that the total traveling time of the proposed method is better than those of the practical route and the ArcGIS.

Table 6 The traveling time for each type of vehicles (h) where bold values indicate the best
Full size table

In what follows, we compare all methods by the total traveling distances (km), operational time (h), fuel consumption (L), and average truck release (g/km) of all vehicles. In order to compute the average fuel consumption of vehicles, we refer to the benchmark indices in Hickman et al. (1999) and Kholod et al. (2016). That is to say, the fuel consumptions are 53 L/100 km for dumper truck and agricultural tractors and 39 L/100 km for compactor vehicle. Analogously, the emission gas for calculating average truck release of all vehicles is shown in Table 7.

Table 7 The average truck release coefficients (Hokkanen and Salminen 1997)
Full size table

It has been shown from Table 8 that the proposed method achieves better values than the other algorithms. Specifically, the SGA method collects waste in 10.914 h and optimizes the traveling time by saving 4.28 h less than that of the practical routes. This is 5 min less than that of the optimized route of ArcGIS on the proposed model. The traveling time of the optimized route of ArcGIS on the proposed model is smaller than that of the practical routes by 4.21 h. Nevertheless, the total traveling times of both methods are still larger than that of the proposed one.

Table 8 The comparative results (bold values refer to the best)
Full size table

The proposed method has the smallest total collected traveling distance among all. According to Table 8, the traveling distance of SGA is 13 km shorter than that of the practical routes, and 1.5 km shorter than that of the ArcGIS. The same results have been found with the fuel consumption and average truck release. It is, indeed, evidence to show the efficiency of the proposed SGA method.

Interpretation on maps

Figures 6, 7, and 8 show the maps of the practical scenario, ArcGIS and SGA. The process for mapping routes on the map of Sfax is as follows.

Fig. 6
figure 6

Routes map from the practical scenario

Full size image
Fig. 7
figure 7

Route map from the ArcGIS

Full size image
Fig. 8
figure 8

Route maps from the proposed SGA method

Full size image

Firstly, data is collected from the municipality of Sfax, including locations of nodes (depot, transfer stations, and gather site), road network, the base maps of Sfax, and borough “Elboustene.” Secondly, the network database is created with many layers being identified such as a line layer for the road, a point layer for nodes, and a gather site layer. Lastly, optimal routes of all vehicles generated from Python code are displayed on the map through Arcpy library in ArcGIS (Desai et al. 2018).

Figure 6 shows the nodes located, the gather sites, and the route of each vehicle. Herein, all vehicles start from the depot, collect garbage from the gather sites, and unload waste at transfer stations. A tour consists of one trip or many trips for a vehicle. For instance, dumper truck in the first trip loads waste from five gather sites (IDs = 15, 14, 11, 5, 29, and 41). It then goes to transfer station 1 to unload waste. In the second trip, the dumper truck loads waste from gather sites (IDs = 22, 23, 24, 28, 27, and 26) and unloads waste in the transfer station. After finishing trip 2, it returns to the depot and finishes its tour.

Figure 7 shows the result of ArcGIS in which all vehicles start from the depot, collect garbage from the gather sites, and unload it at transfer station 2. Agricultural tractor 1 visits four gather sites like agricultural tractor 2. Dumper truck visits five gather sites, and compactor vehicle visits 18 gather sites. There are eight gather sites (IDs = 32, 36, 37, 38, 39, 34, 33, 35) that are not visited because of the capacity constraints. Thus, there is a need of the second trip visited by dumper truck and agricultural tractor 1.

Figure 8 shows the result from the proposed SGA method. All vehicles start from the depot. The compactor vehicle loads waste from gather sites (IDs = 18, 17, 20, 21, 16, 4, 25, 41, 40, 29, 42, 38, 39, 35, 34, 33, 31, 30) and goes to the transfer station 2 to unload waste. Then, it starts the second trip from transfer station 2 and visit nodes (IDs = 24, 28, 27, 26, 32, 36, 37, and 22). Finally, it unloads waste again in the transfer station and goes to the depot. The dumper truck starts its trip from the depot, loads waste from gather sites (IDs = 19, 15, 14, 11), and goes to transfer station 2 to unload waste and finishes trip in the depot. Agricultural tractor 1 visits nodes (IDs = 5, 12, 7, and 9) and returns to the depot. Finally, agricultural tractor 2 loads waste from nodes (IDs = 8, 6, 23, 13) and goes to transfer station to unload and finishes its tour in the depot.

Sensitivity analysis

In order to verify efficiency of the proposed method, we perform the sensitivity analysis in this section regarding bin capacity, vehicle capacity, and the number of vehicles.

Sensitivity analysis regarding bin capacity

An important aspect for a waste collection scenario is the waste capacity of gather sites (or bin capacity) denoted by \( {Z}_4,..,{Z}_{N^{+}} \) in Table 4. In Table 8, we compare all methods by the same bin capacity of 0.4 t of 39 gather sites (see Table 3 for these values). Here, we examine two other cases such as case 2 (35 gather sites—GS with 0.4 t and 4 GS with 0.7 t) and case 3 (35 GS with 0.4 t, 3 GS with 0.3 t, and 1 GS with 0.7 t). It can be seen from Table 9 that the total traveling time of SGA is smaller than that of ArcGIS in all cases. This shows the efficiency of SGA even by variation of the bin capacity.

Table 9 The comparative results by bin capacity
Full size table

Sensitivity analysis by vehicle types

In our real-life case, we have four vehicles: agricultural tractor (denoted as T), dumper truck (D), and compactor vehicle (C). To evaluate the impact of different vehicle types, we consider two cases: the first case has one compactor vehicle, one dumper truck, and two agricultural tractors with the total capacity of 12.9 t; the second case has four agricultural tractors. The number of gather sites (bins) and their capacities are kept intact as in Table 3 (39 and 0.4, respectively).

Table 10 shows in the first case that the distance of SGA is 154.6 km and the traveling time is 10.83 h. In the second case, the distance is 246.4 km and the traveling time is 11.55 h. The distance and traveling time of SGA with different types of vehicles increases because the number of trips also increase, meaning that waste collection takes more time to process. However, they are still better than those of ArcGIS.

Table 10 The comparative results by vehicle types
Full size table

Sensitivity analysis by both the number of vehicles and bin capacity

Here, we change the number of vehicles and the capacity of bins in Table 11. Firstly, consider two compactors with total capacity of 14.8 t and bin capacity of 0.6 t. SGA has a distance of 114.0 km and traveling time of 10.51 h. Secondly, three types of vehicles are considered with the total capacity of 11.3 t and bin capacity of 0.4 t. The results show that the distance and traveling time of SGA are 123.6 km and 10.59 h. Thirdly, one compactor vehicle and one dumper truck with bin capacity of 0.4 t are considered. The results show that the distance and traveling time of SGA are 92.6 km and 10.34 h.

Table 11 The comparative results by number of vehicles and bin capacity
Full size table

From Table 11, it can be seen that using a large capacity and small number of vehicles is better than using a large number of vehicles with small capacity because it minimizes the number of trips as well as the total traveling time and distances of the vehicles. In general, SGA with a fixed number of gather sites has better results than ArcGIS.

Sensitivity analysis by the number of bins

Here, we consider variations for the number of bins. Table 12 shows the results by different numbers of bins. The bin capacity and vehicles’ capacity are also changed to measure their impact to the performance of methods. For the SGA algorithm, the traveling time and distance almost increase when the number of bins increases. SGA gets better results than the ArcGIS algorithm.

Table 12 The comparative results by the number of bins
Full size table

Conclusions

In this paper, we proposed a new Spatial Geographic Information System (GIS)-based Genetic Algorithm called SGA for the route optimization of municipal solid waste collection. SGA uses a modified version of the original Dijkstra algorithm in GIS to generate optimal solutions of vehicles which are then evolved by Genetic Algorithm to choose an optimal solution with respect to the traveling time and distances of vehicles in the waste collection system. The best solution was shown on the map interface using ArcGIS software.

The proposed approach was extensively validated on the real dataset of Sfax City, Tunisia. It has been shown that adopting meta-heuristic approaches in which capacity routing decisions are simultaneously evaluated has a great potential impact with respect to the current scenario of waste collection routes. The proposed method obtains a better total traveling time than the practical routes currently applied in Sfax as well as the Network Analysis ArcGIS with our model result. The time saved showed the efficiency of the proposed method. Sensitivity analysis also suggested the efficiency by parameter changing.

Further works of this study will investigate another improvement of vehicle routing algorithms to get better planning results of the waste collection scenario as well as to resource allocation by evolutionary approaches (Hemanth et al. 2018a, b; Son et al. 2018; Singh et al. 2018; Tam et al. 2018; Thong and Son 2016), neural networks (Giap et al. 2018), and information systems (Ali et al. 2018).