A hybrid genetic algorithm for waste collection problem by heterogeneous fleet of vehicles with multiple separated compartments

Abstract

In this paper, we consider the waste collection problem from customers’ location with assumptions that are closer to real life applications of the problem. The fleet of vehicles is heterogeneous and vehicles have separated compartments, namely they have different capacity for each type of waste. Also, the vehicles have different traveling time limitation and different variable and fixed cost according to their types. As well as, the multi-depot vehicle routing problem and the mixed close-open vehicle routing problem are combined together. The objective of the problem is minimizing the cost of servicing to customers with respect to customers’ demands and available constraints. A new mathematical MIP model is proposed and to deal with this problem, three meta-heuristic algorithms are investigated and the results are compared with the results of CPLEX solver. The results of experiments show that the proposed Meta-heuristic algorithms are able to produce satisfied solutions with regard to the MIP solver CPLEX.

Keywords

Waste collection multi-depot mixed close-open heterogeneous vehicles multi compartments hybrid genetic algorithm

1 Introduction

The last decades have seen an increasing attention to management of collection and distribution of goods. Generally, finding the routes that have less cost is the critical decision in strategic and tactical level of factory and distribution organizations. “The large numbers of real-world applications, both in North America and in Europe, have shown that the use of optimization procedures for the distribution process planning produces savings (generally from 5% to 20%) in the global transportation costs” [26]. The vehicle routing problem called VRP is the one of the most important and most studied problem in optimization problem. More than 50 years have elapsed since Dantzig and Ramser [5] introduced the vehicle routing problem (VRP)for the first time. The capacitated vehicle routing problem (CVRP) is often described a problem which vehicles leave the depot that are located in the area and serve customers considering the capacity of vehicle and return back to the depot. The most important variants of the vehicle routing problem can be found in [19, 26]. Gomes et al. [6] presented a neuro-fuzzy system based on competitive learning to solve multiple criteria vehicle routing optimization problem. A new mixed integer linear programming (MILP) model for the solution of a fuzzy vehicle routing problem was presented by Bjork et al. [4]. This work is inspired by a business context of timber transportation. The decisions to be made are routing decisions, truck assignment and the determination of the pickup order for a set of loads and available trucks. In this paper, the distances and times between pickup points are fuzzy.

In practice some various kinds of VRP exist such as VRP with the time windows [2, 14] and multi-depot VRP called MDVRP [11]. Single depot has attracted so much attention but this type is not suitable for companies which have several depots in different areas. Sumichrast and Markham [25] formulated MDVRP for the first time. In MDVRP the decision maker deals with three phases (grouping, routing, scheduling) to solve the problem. This classification of the problem is proposed first time by Ho et al. [11] to solve the MDVRP. Ho et al. [11] proposed a hybrid genetic algorithm for the MDVRP. Salhi and Imran [23] extended MDVRP to another application of this problem. They supposed that the fleet of vehicles is heterogeneous. They formulated this problem and implemented variable neighborhood search to solve this problem.

From the early of this century researchers take attention to new kind of problem called open VRP [24]. In this type, all of routes are open means that no vehicle comes back to the depot and all vehicles are free after servicing last customer. This type of problem corresponds with distributions companies that have not own fleet of vehicle and delegate this process to contractor. Li et al. [17] reviewed OVRP algorithms and developed a variant of their record-to-record travel algorithm for the standard vehicle routing problem to handle open routes. Fleszar et al. [8] developed a variable neighborhood search (VNS)algorithm for the OVRP. As well as, Repoussis and Tarantilis [21] had a new contribution for solving OVRP. They proposed a hybrid evolution strategy (ES) for the OVRP. Recently, another type of the problem was considered by Liu and Jiang [18]. In this type of the problem open and close routes are considered, simultaneously. The close open mixed VRP (COMVRP) can play important role in the transportation industry and companies can apply this type of the VRP in their transportation system. Liu and Jiang [18] mentioned one real case about application of COMVRP in industry. For example, in Shanghai, China most chemical companies have private fleet of vehicles carrying hazardous materials, but since sometimes the capacity of a special type of vehicle (e.g., for vitriol shipment)is not sufficient, they hire some external contractors to complete the hazardous materials shipments. The vehicles of internal return to the depot in the respect of security and maintenance after serving some customers.

According to the waste collection literature, waste collection problem is classified into three types including residential, commercial, and industry wastes collection. Residential collection involves collecting household garbage along streets. This type of problems is considered as an arc routing problems [16]. Commercial problem involves the collection of refuse from commercial locations. This is a node routing problems and each commercial location can be seen as a node in transportation network [3]. Industry wastes collection problem called rollon-rolloff problem includes the pickup, transportation, unloading, and dump of large containers typically found at construction sites or shopping centers. A hybrid Meta heuristic approach that consists of a large neighborhood search and various improvement methods is proposed to solve rollon-rolloff problem by Wy et al. [27]. Alumur and Bahar [1] proposed a new model for hazardous waste location-routing problem. Hazardous waste management includes the collection, transportation and dispose of garbages that are useless to environment and people health, so it is important to manage efficiently. The aim of the proposed model is to specify where to open disposal facility centers and with which technology and how to route different types of hazardous waste to which of the compatible treatment technology.

In this paper, we tackle a special type of the problem in which the combination of close-open mixed vehicle routing problem (COMVRP) and multi-depot vehicle routing problem (MDVRP) are considered simultaneously. Therefore, this type of problem can be seen as an extension of COMVRP and MDVRP. Also, the vehicles are heterogeneous means that they are different in capacity for each type of waste (i.e., Vehicles have multi separated compartments for each type of waste.) and maximum route length. In this case, some vehicles should not return to the starting depot but the rest ones should come back to the depot which they have departed from. In addition, one disposal facility is available for each type of waste and each type of waste should be disposed in a compatible disposal center with respect to technological limitations. We assume that each customer generates all types of wastes, so when a vehicle moves to disposal centers has all types of wastes. It should be noted that each type of waste should be disposed in compatible disposal center, and since vehicles have all types of wastes in their load, so vehicles should track all disposal facilities after collection of wastes from customers’ location. The problem considered in this paper has significant application in the real world. For example, in the companies that have their own vehicles but this number of vehicles is limited and can not meet the customers’ demand and some parts of servicing are performed by external fleets. In addition, this paper considers companies which have several depots.

Vehicle routing problems is classified as the NP-Hard problems [26]; hence finding exact solution for this problem is very difficult or impossible in many medium and large scale cases, so heuristic and meta-heuristic approaches can support us to solve these problems. It is obvious that less gap between exact solution and approximated solution in small and medium scale problems is better and can help us to make a best decision in different situations. In this paper, we try to create real world situations and prepare good algorithms to solve this problem. CPLEX solver and genetic algorithm (GA) are used to solve the problem. In addition, a new hybrid algorithm (i.e., hybrid genetic algorithm with analytic hierarchy process called AHP technic) is proposed in this paper and the results obtained with this algorithm are compared with the result of GA and CPLEX solver. A new mathematical model for the problem is presented and this model is validated with GAMS software.

The rest of the paper is organized as follows: In Section 2, we propose a mathematical model. In Section 3, proposed algorithms is presented. The numerical experiments are reported in Section 4. Finally, conclusions and future work are presented in Section 5.

2 Problem description

Waste collection problem is one of the most important issues in the human life. In this research, we consider waste collection problem in which the wastes are left at specific sites and customers request for waste collection. Because of easement in recycling the wastes, these centers separate their wastes into different types including plastics, bottle, glass, papers, foods and etc. Vehicles leave depots to serve customers and collect their wastes. It is assumed that fleet of vehicles consists of internal and external fleets (i.e., corporation has decided to assign some services to contractors in order to fulfill costumers demand). Number of internal vehicles is limited and number of external vehicles is unlimited. It is assumed that internal fleet has variant cost only, but external one has hiring fixed cost in addition. After servicing customers, internal vehicles should return to depots starting their routes, while external vehicles will be free after servicing the costumers.

Each vehicle consists of multiple compartments and each compartment belongs to one type of waste. Vehicle starts from depot and moves to customers’ locations. Wastes are collected from customers’ location and each type of waste is poured in specific compartment that is belonged to. Heterogeneous fleet of vehicles is considered, means that each vehicle has the maximum allowable operating time and maximum allowable capacity. Vehicles collect waste regarding to their constraint of time and capacity and after last servicing move to disposal facilities. Each customer generates all types of wastes and each type of waste has its own compatible disposal facility, hence vehicles should visit all disposal facilities and empty each type of waste in its compatible disposal facility. In this problem, we have several depots that vehicles start their routes from there (multi-depot problem). We have several disposal facilities corresponding each type of waste. Objective of the problem is to determine routes that minimize the travelling cost which is dependent on travelling time and number of required vehicles to serve all given customers’ demand. So a combination of multi depot vehicle routing program (MDVRP) with close-open mixed vehicle routing problem (COMVRP) and heterogeneous vehicles with multiple compartment are considered in this paper. We call this type of the problem close-open multi depot vehicle routing problem (COMDVRP). Two types of trip are shown in Fig. 1. Route1 is close and route2 is open and each route starts from depot and goes through all disposal facilities.

2.1 Mathematical formulation

Assumptions:

Customers’ demand and travelling time between nodes are deterministic and known.

Each type of waste has one compatible disposal facility.

Vehicles are heterogeneous.

Vehicles have multiple separated compartment for each type of waste.

Number of internal vehicles are limited and number of external ones are unlimited.

Internal fleet has only variable cost, but external fleet has hiring fixed cost in addition

Each customer generates all types of wastes.

Indices:

D = {1, 2, . . . , d}

Set of indexes for depots

K = {1, 2, . . . , k}

Set of indexes for vehicles

F = {1, 2, . . . , f}

Set of indexes for disposal facilities

C = {1, 2, . . . , c}

Set of indexes for customers

W = {1, 2, . . . , w}

Set of indexes for types of wastes

S = {1, 2, . . . , s}

Set of indexes for internal/external fleet

Parameters:

d _iw

demand of customer i for collection of waste w

Q _wk

capacity of vehicle k for waste type w

Tr _k

maximum allowable traveling time for vehicle k

maximum internal vehicle

t _ij

traveling time between node i and node j

p _iwsk

loading/unloading time for waste type w by means of vehicle k of fleet s in node i

F _k

fixed cost of using vehicle k

V _k

variable cost of using vehicle k

great number

Decision variables:

x _ijsk

if vehicle k belonged to fleet type s travels directly from node i to node j, x_ijsk = 1; otherwise=0.

o _isk

if vehicle k of fleet type s departs from depot i, O_isk = 1; otherwise=0.

y _isk

if vehicle k of fleet s is allocated to customer i,y_isk = 1; otherwise=0.

U _iskw

continuous variable that represents the load of compartment w of vehicle k and type s just after leaving the customer i.

T _isk

continuous variable that represents the traveling time of vehicle k of fleet s from depot to the customer i when it arrives at customer i’s location

Objective function:

$\begin{matrix} Min \sum_{k \in K} f_{k} \sum_{i \in D} o_{i 1 k} \\ + \sum_{k \in K} V_{k} \sum_{s \in S} \sum_{i \in D ⋃ F ⋃ C} \sum_{j \in D ⋃ F ⋃ C} t_{ij} x_{ijsk} \\ - \sum_{k \in K} V_{k} \sum_{i \in F} \sum_{j \in D} t_{ij} x_{ij 1 k} \\ + \sum_{k \in K} V_{k} \sum_{s \in S} \sum_{i \in D ⋃ C} \sum_{j \in C ⋃ F} \sum_{w \in W} p_{iwsk} x_{ijsk} \end{matrix}$ (1)

Constraints: $\sum_{s \in S} \sum_{k \in K} \sum_{i \in D ⋃ C} x_{ijsk} = 1 \forall j \in C$ (2) $\sum_{s \in S} \sum_{k \in K} \sum_{i \in C ⋃ F} x_{jisk} = 1 \forall j \in C$ (3) $\sum_{i \in D ⋃ C} x_{ijsk} = \sum_{i \in C ⋃ F} x_{jisk} \forall j \in C, s \in S, k \in K$ (4) $\sum_{i \in F ⋃ C} x_{ijsk} = \sum_{i \in C ⋃ F} x_{jisk} \forall j \in F, s \in S, k \in K$ (5) $\sum_{i \in F} x_{ij 0 k} = \sum_{i \in C} x_{ji 0 k} \forall j \in D, s \in S, k \in K$ (6) $\sum_{i \in D} \sum_{j \in D} x_{ijsk} = 0 \forall s \in S, k \in K$ (7) $T_{isk} = 0 \forall i \in D, s \in S, k \in K$ (8)

$\begin{matrix} T_{isk} + t_{ij} + \sum_{w \in W} p_{jwsk} x_{ijsk} - M (1 - x_{ijsk}) \leq T_{jsk} \\ \forall i, j \in C ⋃ F, k \in K, s \in S \end{matrix}$ (9)

$\begin{matrix} T_{i 0 k} + t_{ij} - M (1 - x_{ij 0 k}) \leq {Tr}_{k} \\ \forall j \in D, i \in F, k \in K \end{matrix}$ (10)

$\begin{matrix} T_{i 1 k} + t_{ij} + \sum_{w \in W} p_{jw 1 k} x_{ij 1 k} - M (1 - x_{ij 1 k}) \leq {Tr}_{k} \\ \forall i, j \in C ⋃ F, k \in K \end{matrix}$ (11) $0 \leq T_{isk} \leq \sum_{j \in D ⋃ C} x_{jisk} {Tr}_{k} \forall i \in C, s \in S, k \in K$ (12) $0 \leq T_{isk} \leq \sum_{j \in F ⋃ C} x_{jisk} {Tr}_{k} \forall i \in F, s \in S, k \in K$ (13) $\sum_{k \in K} \sum_{i \in D} \sum_{j \in C} x_{i, j, 0, k} \leq I$ (14) $\sum_{j \in C ⋃ D} x_{jisk} = y_{isk} \forall s \in S, k \in K$ (15) $\sum_{i \in C} d_{iw} y_{isk} \leq Q_{wk} \forall w \in W, s \in S, k \in K$ (16) $U_{iskw} = 0 \forall i \in D, s \in S, k \in K, w \in W$ (17)

$\begin{matrix} U_{iskw} + d_{jw} - M (1 - x_{ijsk}) \leq U_{jskw} \\ \forall i, j \in C, s \in S, k \in K, w \in W \end{matrix}$ (18)

$\begin{matrix} d_{iw} \leq \sum_{s \in S} \sum_{k \in K} U_{iskw} \leq \sum_{s \in S} \sum_{k \in K} \sum_{j \in D ⋃ C} x_{jisk} Q_{wk} \\ \forall i \in C, w \in W \end{matrix}$ (19) $\sum_{s \in S} \sum_{k \in K} \sum_{j \in D} \sum_{i \in C} x_{ijsk} = 0$ (20) $\sum_{s \in S} \sum_{k \in K} \sum_{j \in F} \sum_{i \in D} x_{ijsk} = 0$ (21)

$\begin{matrix} \sum_{s \in S} \sum_{k \in K} \sum_{j \in C} \sum_{i \in D} x_{ijsk} = \sum_{s \in S} \sum_{k \in K} \sum_{i \in C ⋃ F} x_{ihsk} \\ \forall h \in F \end{matrix}$ (22) $\sum_{i \in C ⋃ F} x_{ijsk} = 1 \forall j \in F, s \in S, k \in K$ (23) $\sum_{j \in F ⋃ D} x_{ijsk} = 1 \forall i \in F, s \in S, k \in K$ (24) $\sum_{j \in C} x_{ijsk} = o_{isk} \forall i \in D, s \in S, k \in K$ (25) $x_{ijsk} = {0, 1} \forall i, j \in D ⋃ C ⋃ F, s \in S, k \in K$ (26) $o_{isk} = {0, 1} \forall i \in D, s \in S, k \in K$ (27) $y_{isk} = {0, 1} \forall i \in C, s \in S, k \in K$ (28) $U_{iskw} \geq 0 \forall i \in D ⋃ C, s \in S, k \in K, w \in W$ (29) $T_{isk} \geq 0 \forall i \in D ⋃ C ⋃ F, s \in S, k \in K$ (30)

Objective function (1) minimizes the total cost of waste collection with respect to customers’ locations. In the first term of the objective function only external vehicles are considered, because only external vehicles have fixed cost. While in terms 2 and 3 we consider variable cost but we have to lessen cost of returning external vehicles which we take into account in term2. In the last term, the loading/unloading cost in customers or disposal facilities locations is added to the objective function, since these activities are time consuming.

Equations (2) and (3) represent that each customer is assigned to a single route. Equation (4) represents that each vehicle enters a customer’s node, should go out as well. The same constraint for disposal facilities is shown in Equation (5). All of internal vehicles that leave the depots should come back to depot. This restriction is shown in Equation (6). Constraints in Equation (7) ban moving vehicles between depots. Each vehicle has specific time limitation means that traveling time of the route must not trespass from this limitation. Equations (8)–(13) satisfy this time restriction. Number of internal vehicles is limited. Equation (14) justifies this limitation. Equation (15) defines the new decision variable and specifies relationship between two variables. Equation (16) ensures that collected wastes in each route do not exceed from allowable capacity. As mentioned in the introduction vehicles are multi compartments and each compartment has specific capacity and each waste type is carried in each route should not exceed from capacity of corresponding compartment. The next three sets of constraints (17)–(19) are lifted Miller-Tucker-Zemlin (MTZ) sub tour elimination constraints for classical VRP, which are first proposed by Desrochers and Laporte [7], and are revised by Kara et al. [15]. In our problem these constraints ensure the sub tour elimination. Equation (20) ensures that vehicles do not move directly from depots to disposal facilities and Equation (21) guarantees that vehicles do not move directly from customers to depots and they must empty their loads at disposal facilities. Equation (22) guarantees that all vehicles left depots must visit all disposal facilities. Equations (23) and (24) represent that all vehicles enter the each disposal facility only once and exit from there. Equation (25) represents new decision variable and specifies relationship between two variables. Constraints (26–30) specify the ranges of variables.

3 Methodology

Genetic algorithm (GA) developed by John Holland [13], is one of the meta-heuristic algorithms to solve the problems which are hard to find exact solution. Basic idea of genetic algorithm is creation of initial population and improve this population by searching in a solution area by means of genetic operators called mutation and crossover. GA had successful results in wide variety of optimization problems such as Traveling sales man problem (TSP) and vehicle routing problem (VRP) [9, 10]; however, GA has been applied good results in different problems, but has a simple approach and using of this algorithm is easy and has a flexibility to use in different problems; Hence, we use GA in this paper and we hybrid it by heuristic methods.

In this paper, the problem is solved with the simple and the hybrid genetic algorithms. The GA developed in this paper is improved with several heuristics to obtain the better solutions. In the first algorithm, initial population is made randomly, and the algorithm searches in the solution area by means of crossover and mutation operators, but HGA1 and HGA2 algorithms use heuristic methods to create an initial solution and these solutions are improved by improvement method ISP (iterated swap procedure). Basic structure of construction method for generating initial solutions is that in the first step, the vehicles and customers order are specified. Since, vehicles like customers are different, we should schedule the vehicles in order to determine priority of vehicles for servicing customers. In the second step vehicles are assigned to customers with regard to capacity of vehicles. We consider routes time limitation with adding penalty to the objective function for violation from this constraint; therefore, the routes are made in the second step. Third step specifies that each route starts from which depot; in the other words, depots are assigned to routes in this step. Steps are different in GA and hybrid GAs (HGAs). These steps are shown in Fig. 2 for the simple GA and HGAs methods.

3.1 Initialization

In the genetic algorithm and hybrid genetic algorithms, we should create an initial population. As mentioned, in the GA all of steps are performed randomly, but in HGAs we used heuristic methods to achieve better solution. Steps of construction algorithm are as follows:

Step 1. Customers are scheduled randomly for the both GA and HGA1. For this reason, we generate random real numbers in the range of [0-1] for all customers. For example, in customers ordering, each random real number corresponds to one customer. We can specify the order of customers by sorting of corresponding real numbers. Nearest neighborhood heuristic (NNH) is used for the HGA2 means that the first customer is selected randomly. The second position in customers order is allocated to nearest customer to the first customer and the third position is allocated to the nearest customer to the second customer among unscheduled customers and so on. In addition, order of vehicles should be determined. In GA, vehicles are scheduled randomly, but in HGAs we use the analytic hierarchy process (AHP) to specify priority of vehicles to serve the customers.

Step 2. In the second step, the vehicles are assigned to customers with respect to the customers’ demand and capacity of vehicles. It should be noted that sum of the customers’ demand in each route must not exceed from capacity of vehicle servicing to these customers. We start with the first rank vehicle in vehicles order and assign the first rank customer to the first vehicle. We keep on with the second customer. If adding this customer to route does not exceed the capacity of corresponding vehicle, we add this customer to current route; otherwise, we refer to the next customer in customers order. This manner will be continue until adding another unassigned customer in customers order to current route causes trespass from capacity of vehicle. At this point, we stop assigning customers to current route and current vehicle, and we will continue with the next vehicle in the vehicles order. It should be noted that open or close routes are specified in this step. If the assigned vehicle to the route was internal, the route would be close, and if the assigned vehicle to the route was external, the route would be open.

Step 3. In this step, depots are assigned to the routes. In GA algorithm this performed randomly with respect to the number of internal fleet limitation, but in HGA1 and HG2 we assigned nearest unfilled depot to the first customers in the service scheduling.

Nearest neighborhood heuristic is used to choose the depot assigned to the routes in both HGA1 and HGA2, also AHP which is the technique to make a decision is used in both HGA1 and HGA2. The disposal facilities are scheduled with the nearest neighborhood heuristic(NNH). The difference of HGA1 and HGA2 is that we use NNH to schedule customers in HGA2 while in HGA1 customers are scheduled randomly. In HGA2, the first customer is chosen randomly but the second customer is the nearest customer to the first one and third customers is the nearest customer to the second one. This manner keeps on till all customers are scheduled.

3.1.1 AHP technique to specify vehicles order

Analytic hierarchy process (AHP) is one of the techniques to make a decision. It is structured technique for organizing and analyzing complex decision with regard to the criteria and alternatives. This technique is proposed for the first time by Thomas Saaty [22]. In the current paper, heterogeneous fleets of vehicles are considered and they are different with each other in capacity, maximum allowable traveling time, fixed and variable cost. In the first step of the methodology to solve the problem, we must specify vehicles order to serve customers. It is obvious that we want to choose vehicles that have a maximum capacity, maximum time limitation, and minimum variable and fixed cost sooner than other vehicles. Since there is no vehicle that has all criteria in the best state simultaneously, we want to rank vehicles with regard to priority of criteria. We use the AHP technique to solve this problem. According to the problem, we have four criteria and have some alternatives (vehicles). We use the AHP technique and sort vehicles in order of their earned score in AHP technique.

For each pair of criteria, the decision maker is required to specify which one of these criteria is more important. Rating the relative priority of these criteria is done by assigning a weight. Then, for each criterion we make the table like Table 1. weights are proportional to their amount in the problem; then, the weights are normalized and then are averaged in order to obtain an average weight for each criterion. For each criterion we generate table such as Table 1. We compare each pair of vehicles to fill cell of the table. Where $w_{ij}^{t}$ determines cell (i, j) of table related to criterion t where i and j belong to set of vehicles and t belongs to set of criteria. $w_{ij}^{t} = {\begin{matrix} \frac{c_{i}^{t}}{c_{j}^{t}}, & If t is the positive criterion; \\ \frac{c_{j}^{t}}{c_{i}^{t}}, & If t is the negative criterion . \end{matrix}$

Where $c_{i}^{t}$ is the amount of parameter related to criterion t and vehicle i. We sum all cells of each column and all cells of each column are divided into resulting number. This action called normalization of table. Then, we sum all number of each row and the resulted number is the score of corresponding alternative in this criterion. We do these actions for all criteria and calculate each alternative score in all criteria. After doing these actions, we compare pairs of criterion by composing table like Table 1. Thus we calculate each criterion’s weight called W_t. Therefore, we can calculate score of each alternative as following: $p_{i} = \sum_{t} w_{i}^{t} \times W_{t}$

We calculate each vehicle score in this manner and sort them in descending order of scores.

3.2 Improvement

2-Opt heuristic method is generally used to improve initial generated solutions. In this method all two swaps are examined and if a new solution generated by this method is better than parents, this solution will be replaced and becomes new parent. This method increases computational time because of all two swaps are checked. In this paper, we use iterative swap procedure (ISP) proposed by Ho and Ji [12] to improve initial solutions. The principle of the ISP is similar to the 2-opt local search heuristic, except that some swaps are examined. The procedure of ISP is shown in Fig. (4) and procedure of the ISP is as follows:

In each chromosome (i.e., vehicles order or customers order), two genes are selected randomly.

Two selected genes are exchanged.

The neighbors of the two selected genes are swapped to form four new offsprings.

The offsprings are evaluated and the solutions are compared with parent. If new solution is better than parent the offspring will be exchanged with parent.

3.3 Crossover operator

There are many crossover operators in the literature. Order crossover (OX) [20] operator is chosen in this paper according to the nature of defined chromosomes. In the first step, two parents must be chosen to perform crossover operation. Roulette wheel method is very applicable to choose parents. In this method which parents that have a better objective function have more chance to be selected. After selection of parents, crossover operator is applied and it helps us to move toward optimized solution. In this stage, one integer number is generated between 1–3 randomly to specify the crossover operator deformed customers order chromosome or vehicles order chromosome or both of them. OX method selects two genes inparents’ chromosome randomly. OX constructs the child chromosomes from parents as shown in Fig. 4.

3.4 Mutation operator

In this stage, some parents are chosen from population to apply mutation operation. After selection of parents, one random integer number is generated between 1–3 to determine which mutation operator is selected to perform operation. Three types of mutation operators are addressed in this paper namely, swap, insertion, and reverse. After specifying of mutation operator, the chromosomes (i.e., customers order, vehicles order or both of them) are selected to perform mutation operator.

After doing crossover and mutation operations and creation a new population, the initial population is merged with the new population. Then, population is sorted according to individuals’ objective function. Better solutions stay in a new population and others are omitted.

4 Parameters tuning

GA has several parameters that tuning of these parameters correctly can help us to achieve better solution or reach to solution in less time. HGAs parameters including number of solution in the initial population (n_pop), crossover parameters (p_c), mutation parameters (p_m) and roulettewheel method parameters to select solutions (β). Taguchi method is applied to design of the experiment. Three levels are considered for each factor and Minitab software is used to design experiments and analyzing its result. For tuning parameters, we solve the medium-size problem according to the design of Taguchi method. We can understand which amount of parameters are suitable and has a better result from analysis diagrams. Abstract of diagrams and results are summarized in Table 2.

5 Numerical results

5.1 Model validation

In this section, for validation of the proposed mathematical model, the model is solved by GAMS software in small size example including 10 nodes, 2 depots, 2 disposal facilities, 6 customers, 2 types of waste, and 4 types of vehicle including internal and external ones. In this problem two types of waste are available. In the customers’ location vehicles must collect all of waste types. All parameters about this example are uploaded at link: <a href=“https://www.dropbox.com/s/8vyamwske4nl8i6/example.xlsx?dl=0”> < /a>.

Nodes number 1 and 2 represent depots, nodes 3 and 4 represent disposal facilities and nodes 5–10 represent customers. Model presented in this paper is solved by GAMS software and the results are represented in Table 3. Global Optimum value for objective function is earned 94 units. Table 3 represents relations between nodes in the optimal solution. Number in each cell specifies which vehicle crosses from the route between two nodes. If no vehicle crosses between two node, the cell will be left blank. Each vehicle is shown by two characters. First character shows that this vehicle is internal or external. Second character shows vehicle type. As shown in Table 3, the optimum solution consists of two routes. One route starts from depot 1 with vehicle type 1. This vehicle moves to customer 10 and collects its wastes. Then, this vehicle moves to disposal facilities 3 and 4, respectively and returns to depot 1. Also, another route is 2-9-6-8-7-5-4-3-2 which is done by vehicle 3.

5.2 Comparison of methods

As mentioned in previous sections, GA, HGA1, and HGA2 methods are proposed for solving the problem. In addition, for small size and medium size problems the CPLEX solver solution is available. We can compare these methods solution with each other and with CPLEX solver. Parameters are set with Taguchi design and these tuned parameters are used to achieve better solution and less cost. In order to evaluate the effectiveness of the hybrid GAs for solving the investigated problem, 15 random instances (10 small/medium-sized + 5 large-sized) have been generated randomly and have been solved with these proposed algorithms and CPLEX solver. Traveling time between nodes and loading/unloading time in each location of customer and disposal facility iscreated randomly according to the uniform distribution in the range of [1 –8]. As well, demand matrix for each type of waste is created randomly in the range of [1 –10] by uniform distribution. Attributes of vehicles are randomly generated and almost they are same by their attributes in small-size problem. All test problems have been solved by GA and the HGAs. These algorithms have been coded in MATLAB^® R2013a and implemented on an Intel Core i5 2.27 GHz personal computer with 4 GB RAM. In order to verify the performance of the considered metaheuristics, for the small/medium-size problems, the results of GA and HGAs are compared to the solutions obtained by GAMS 23.6. Numerical results for small/medium sized problem are shown in Tables 4–6. All examples run 5 times for each method and minimum, maximum and average results are recorded. In these tables problem information parts indicates number of nodes, number of depots, number of vehicle types, number of customers and number of disposal facilities (waste types) by n, d, k, c and f, respectively. In Tables 4 to 6, the results of methods are compared with GAMS and for average of solutions and best solution, gap is calculated and shown in gap^mean and gap^best. We use the percentage of gap which is the deviation of the objective function’s values obtained by the metaheuristics (HGAs and GA) from values obtained by GAMS.

According to the Tables 4–6, as the problem becomes bigger, GAMS software loses its efficiency to solve the problem and becomes unable to solve and objective functions have large gap with lower bound value, so in Tables 7–9 the results of all algorithms are compared with each other. Also all algorithms achieve reasonable solution, but we can conclude from numerical results that HGAs have better solution than classical GA. In small and medium size problems, HGA1 achieves better solution than HGA2, but in large scale problem HGA2 starts with better initial solution and has effective construction algorithm and finally achieves to better final solution than HGA1. Both HGA1 and HGA2 have better solution than classical GA and they can improve the results. For two test problems (one medium scale and one large scale), the GA and HGA1 and HGA2 are compared graphically and the obtained results for two test problems are shown in Figs. 7 and 8.

6 Discussion and conclusion

In this work, a new mathematical model for a waste collection problem which is the application of vehicle routing problem was addressed. Multi depots and mixed close and open routes was considered in this paper. It is supposed that a fleet of vehicles is heterogeneous. This means that the vehicles are different in fixed and variable cost, capacity and servicing time limitation. Also, several types of wastes was considered and these wastes should be disposed in compatible disposal facility. CPLEX solver was used for validation of proposed mathematical model, but according to the NP-Hard nature of the problem this solver was unable to solve large scale problems. For this reason, three metaheuristic algorithms including GA, HGA1, and HGA2 was applied for solving a large scale problems. An order based representation for coding a solutions was implemented. In this manner, order of customers and vehicles is specified and all solutions are considered as feasible solutions. A penalty was considered for trespassing from traveling time limitations of routes. In this kind of representation, applying of some operators such as crossover and mutation would be easy and executable. In order to show the effectiveness of proposed algorithms several test instances were conducted and the results were compared with each other.

According to the numerical results in the previous section, we can understand that GA and HGAs have good results and the hybrid genetic algorithms gain better solution than classical GA, since we usedheuristic algorithms to improve our hybrid algorithms. We used nearest neighborhood heuristic (NNH) and analytic hierarchy process (AHP) and improvement method (ISP) to hybrid classical GA. The difference between HGA1 and HGA2 is that NNH was used to schedule customers in HGA2 in addition to heuristics used in HGA1. This action causes that HGA2 constructs good initial solutions. As seen in Fig. 7 in medium size problem, HGA1 achieved better solution than HGA2 but both of them operated better than classical GA. The reason can be explained that adding more heuristics and more hybridizing increase the probability of trapping in local optimum. As seen in two Figs. 7 and 8, HGA2 started with the better solution than other algorithms and in large-scale instance achieved better solution. According to the Table 8, HGA2 improved objective function from 17% up to 24% proportional to classical GA in the large scale problems. Also, according to the Table 7 HGA1 improved objective function from 7% up to 16% in large scale problems. Numerical results shows all algorithms efficiency and we understood that HGAs proposed in this paper had a better efficiency in large and medium-scale problems. Also, in small size instances the gap between obtained objective function by HGA1 and CPLEX solver is less than 2% and for HGA2 this gap is less than 4% . Computational time for GA is less than HGAs, but this bigger computational time is reasonable, because HGAs can reach to good quality solutions rather than GA.

References

Alumur

and Kara

B.Y.

, A new model for the hazardous waste location-routing problem, Computers & Operations Research 34(5) (2007), 1406–1423.

Azi

, Gendreau

and Potvin

J.-Y.

, An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles, European Journal of Operational Research 202(3) (2010), 756–763.

Benjamin

and Beasley

, Metaheuristics for the waste collection vehicle routing problem with time windows, driver rest period and multiple disposal facilities, Computers & Operations Research 37(12) (2010), 2270–2280.

Björk

K.-M.

and Mezei

, A fuzzy milp-model for the optimization of vehicle routing problem, Journal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology 26(3) (2014), 1349–1361.

Dantzig

G.B.

and Ramser

J.H.

, The truck dispatching problem, Management science 6(1) (1959), 80–91.

de CT Gomes

and Von Zuben

F.J.

, Multiple criteria optimization based on unsupervised learning and fuzzy inference applied to the vehicle routing problem, Journal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology 13(2-4) (2002), 143–154.

Desrochers

and Laporte

, Improvements and extensions to the miller-tucker-zemlin subtour elimination constraints, Operations Research Letters 10(1) (1991), 27–36.

Fleszar

, Osman

I.H.

and Hindi

K.S.

, A variable neighbourhood search algorithm for the open vehicle routing problem, European Journal of Operational Research 195(3) (2009), 803–809.

Gen

and Syarif

, Hybrid genetic algorithm for multi-time period production/distribution planning, Computers & Industrial Engineering 48(4) (2005), 799–809.

10.

Goldberg

D.E.

and Holland

J.H.

, Genetic algorithms and machine learning, Machine Learning 3(2) (1988), 95–99.

11.

, Ho

G.T.

, Ji

and Lau

H.C.

, A hybrid genetic algorithm for the multi-depot vehicle routing problem, Engineering Applications of Artificial Intelligence 21(4) (2008), 548–557.

12.

and Ji

, Component scheduling for chip shooter machines: A hybrid genetic algorithm approach, Computers & Operations Research 30(14) (2003), 2175–2189.

13.

Holland

J.H.

, Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence, U Michigan Press, 1975.

14.

Homberger

and Gehring

, A two-phase hybrid metaheuristic for the vehicle routing problem with time windows, European Journal of Operational Research 162(1) (2005), 220–238.

15.

Kara

, Laporte

and Bektas

, A note on the lifted miller–tucker–zemlin subtour elimination constraints for the capacitated vehicle routing problem, European Journal of Operational Research 158(3) (2004), 793–795.

16.

Lacomme

, Prins

and Ramdane-Cherif

, Evolutionary algorithms for periodic arc routing problems, European Journal of Operational Research 165(2) (2005), 535–553.

17.

, Golden

and Wasil

, The open vehicle routing problem: Algorithms, large-scale test problems, and computational results, Computers & Operations Research 34(10) (2007), 2918–2930.

18.

Liu

and Jiang

, The close–open mixed vehicle routing problem, European Journal of Operational Research 220(2) (2012), 349–360.

19.

Marinakis

and Marinaki

, A hybrid genetic–particle swarm optimization algorithm for the vehicle routing problem, Expert Systems with Applications 37(2) (2010), 1446–1455.

20.

Oliver

, Smith

and Holland

J.R.

, Study of permutation crossover operators on the traveling salesman problem. In Genetic algorithms and their applications: Proceedings of the second International Conference on Genetic Algorithms: July 28-31, 1987 at the Massachusetts Institute of Technology, Cambridge, MA, 1987.

21.

Repoussis

P.P.

, Tarantilis

C.D.

, Bräysy

and Ioannou

, A hybrid evolution strategy for the open vehicle routing problem, Computers & Operations Research 37(3) (2010), 443–455.

22.

Saaty

T.L.

, How to make a decision: The analytic hierarchy process, European Journal of Operational Research 48(1) (1990), 9–26.

23.

Salhi

, Imran

and Wassan

N.A.

, The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation, Computers & Operations Research (2013).

24.

Sariklis

and Powell

, A heuristic method for the open vehicle routing problem, Journal of the Operational Research Society (2000), 564–573.

25.

Sumichras

R.T.

and Markham

I.S.

, A heuristic and lower bound for a multi-depot routing problem, Computers & Operations Research 22(10) (1995), 1047–1056.

26.

Toth

and Vigo

, The vehicle routing problem, Siam, 2001.

27.

and Kim

B.-I.

, A hybrid metaheuristic approach for the rollon–rolloff vehicle routing problem, Computers & Operations Research 40(8) (2013), 1947–1952.