Developing an applied algorithm for multi-trip vehicle routing problem with time windows in urban waste collection: A case study

Abstract

This paper studies a multi-trip vehicle routing problem with time windows specifically related to urban waste collection. Urban waste collection is one of the municipal activities with large costs and has many practical difficulties. In other words, waste collection and disposal is a costly task due to high operating expenses (fuel, maintenance, recycling, manpower, etc.) and small improvements in this field can result in tremendous savings on municipal expenditure. In the raised problem, the goal is to minimize total cost including traversing cost, vehicle employment cost, and exit penalty from permissible time windows. In this problem, the waste is deposited at the points indicating the demand nodes, in which each demand shows the volume of generated waste. Considering multiple trips for vehicles and time windows are the most critical features of the problem, so that the priorities of serving some specific places such as hospitals can be observed. Since vehicle routing problems (VRP) belongs to NP-hard problems, an efficient simulated annealing (SA) is proposed to solve the problem. The computational results show that our proposed algorithm has a great performance in a short computational time in comparison with the CPLEX solver. Finally, in order to demonstrate the applicability of the model, a case study is analyzed in Iran, and the optimal policies are presented.

Keywords

Vehicle routing problem multiple trips urban waste collection simulated annealing time windows CPLEX solver

Introduction

The world population has grown dramatically in the last 10 years, with annual growth rates of 1.1%. In particular, the total number of living human beings on Earth has risen from 6 billion in 1999 to 7 billion now (US Census Bureau¹). This dramatic growth was mainly due to the advances in medicine and agriculture. If the population is able to keep growing at this rate, it is estimated that the world’s population will reach about 9 billion by 2040 (US Census Bureau²). These factors illustrate why the management of waste has been one of the world’s greatest concerns over the past few decades. Urban areas produce the highest amount of waste, so they need an efficient system for waste collection and disposal. Maintenance of a proper waste management system is very difficult and costly.

Today, the production of various solid wastes and the occurrence of a variety of social, economic and environmental inconveniences associated with them, has caused urban service management problems with collection, transportation, processing, and disposal of such waste. Since between 60% and 80% of solid waste management costs are related to waste collection and transportation, evaluation and optimization of this system will have a significant role in solving and reducing problems in urban services management (Tirkolaee et al., 2018a). Therefore, the problem of urban waste collection can be formulated in various versions of the vehicle routing problem (VRP). VRP has been studied to be modeled in a wide range of common problems such as transportation, supply chain management, production planning, and communications (Karadimas et al., 2007; Mirmohammadi et al., 2017; Tirkolaee et al., 2017).

Currently, interest in waste management is growing. Considering the major threats to human health and its impact on the environment, management of hazardous waste requires much more attention. However, in the literature, there is a lack of specific techniques to optimize such critical activities, which are characterized by more precise limitations for waste management in the urban community. To fill this gap, we provide an approach to address routing problems and scheduling of vehicles for collecting and disposing of hazardous waste (De Bruecker et al., 2018).

The vehicle routing problem with time windows (VRPTW) is a generalized problem of the VPR with capacity constraints in which each customer must be serviced at a particular time interval (this interval is known as a time window) (Tirkolaee et al., 2017). Since this problem emphasizes on time in its approach, it is more applicable in practice and has therefore attracted more attention in scientific circles. Known examples of VRPTW include the distribution of cash to bank branches, urban and industrial waste collection, fuel delivery to gas stations, school services, and so on. By considering time windows, the priorities of service are defined according to the waste types including household waste, wastes of electric and electronic equipment (WEEE), chemical waste, hospital waste, etc. With respect to the harmfulness level of the waste, the priorities of service are defined through hard (strict) or soft (light) time windows. The priority of services to some special places such as hospitals and health centers that produce more hazardous waste than household waste can be easily considered by defining time windows. Furthermore, WEEE is also categorized as a hazardous waste due to its utilization of dangerous substances which leads to difficult challenges during the disposal and recovery processes (Gamberini et al., 2008). WEE is currently regarded as being one of the quickest developing waste streams in the European Union – with an annual increase rate of 3–5% it needs to treated using an efficient collection system.

In the following, we will examine the literature related to the problem, especially in the context of the waste collection and developed solution methods.

Beltrami and Bodin (1974) introduced one of the first problems of waste collection and the routing problem in the form of a classic VRP for New York City and Washington Municipalities, along with a variety of vehicles (trucks, tugs, towing vessels, and mechanical sweepers). They improved Clarke and Wright’s (1964) innovative algorithm for finding optimal routes. The result of their work was applied to the municipalities and created significant benefits. Tung and Pinnoi (2000) developed the innovative algorithm proposed by Solomon (1987) to solve the VRPTW problem and applied it to the waste collection problem in Hanoi, Vietnam. In addition to taking into account the classical assumptions of VRPTW, they considered a practical site for the disposal of collected waste. They implemented 2-Opt and Or-Opt algorithms to improve the quality of the applied algorithm’s solutions.

Kim et al. (2006) also studied a VRPTW for waste collection considering lunch and rest periods for drivers. Their goal was to minimize the number of vehicles and the total trip time. They also implemented an algorithm based on clustering of areas to solve their problem and used it in the waste management for some North American municipalities. Buhrkal et al. (2012) studied a VRPTW associated with the urban waste collection. They tried to find an expedient way to calculate the cost of the optimal route for the waste collecting vehicles’ transit from the start of their route at the base to the discharge at the disposal site.

A recycling process of WEEE was analyzed efficiently by Gamberini et al. (2008) considering the three levels of: return points; collecting points; and recycling plants. They designed a mixed-integer linear programming (MILP) model to maximize the efficiency of the collection system through minimizing unsatisfied calls coming from the first two levels. Finally, they could demonstrate the applicability of the proposed model by conducting a case study in the Italian region of Emilia Romagna. Gamberini et al. (2010) designed a WEEE transportation-optimization network model associated with both technical decisions such as optimal routing and scheduling of vehicles and environmental performance. Mar-Ortiz et al. (2013) introduced a greedy randomized adaptive searching procedure algorithm to solve a multi-trip multi-period vehicle routing and scheduling problem for the collection of WEEE.

Angelelli and Speranza (2002) presented a periodic vehicle routing problem with intermediate facilities. When a vehicle reaches a middle facility, its capacity becomes zero again. They developed a Tabu search algorithm to solve their problem. Teixeira et al. (2004) developed an innovative method for solving the periodic vehicle routing problem suited for three types of waste (plastics/metal, glass, and paper). Their proposed solution consisted of three phases: (1) defining an area for each vehicle; (2) defining the type of waste to be collected per day; and (3) selecting the order of the points to cover the demands.

Erfani et al. (2017) presented a novel approach to determine optimal bin location and collection routes using a geographic information system. They surveyed a case study in Iran by their proposed method and could demonstrate that the current collection system is not optimal due to its incompatibility with the urban structure and population distribution.

Babaee Tirkolaee et al. (2016) also developed a robust mathematical model for solving the capacitated arc routing problem (CARP) particular to the urban waste collection in uncertain conditions. They solved the problem by developing a hybrid simulated annealing (SA) and were able to prove the effectiveness of their proposed algorithm in comparison with the CPLEX solver. Tirkolaee et al. (2018a) developed a MILP model for the multi-trip CARP in order to minimize total cost in the scope of the urban waste collection. They considered separate places for depots and disposal facilities specific to the urban waste collection. They proposed an Improved Max–Min Ant System to solve well-known test problems and large-sized instances.

Therefore, the innovations of this research are described below:

Developing a novel waste collection model for the real-world applications by considering a maximum available time for vehicles in addition to the possibility of having multiple trips – hard and soft time windows for covering all demand nodes according to the priorities of service, and separate locations for the disposal site and the depot.

Proposing a constructive efficient method for generating initial solutions, and subsequently applying an efficient SA to improve them.

Investigating a case study in order to demonstrate the applicability of the proposed model and to determine the optimal policy.

In the following: the proposed mathematical model is presented in the second section; in the third section, the proposed solution method is introduced; in the fourth section, the numerical results from the implementation of the algorithm are presented; and finally, the conclusions and suggestions for future works are given in the fifth section.

Problem description and modeling

This problem involves obtaining the optimal number of used vehicles and the optimal routes of each vehicle in order to minimize the total cost, which includes the usage cost of vehicles, traversing cost through network edges, and violating penalty cost from the permissible time windows of services. The vehicles are located at the depot (node number 1) and start their trip toward the demand nodes (the nodes with waste), and after filling to their capacity, they should go to the disposal site (node n) in order to unload the collected waste, get their capacity back, and start their next trip from the disposal site toward the remaining demand nodes if possible. Finally, they will go back to the depot in order to complete their service tour. In addition to capacity constraints, the maximum allowable usage time of each vehicle is also important; when the vehicles are close to this maximum available time, they have to return to the disposal site and eventually return to the depot after being unloaded. It is also important to consider time windows for each demand node to uphold optimal urban waste collection policies. The assumptions of this problem are as follows:

– Each demand node is only serviced by one vehicle.

– There is one depot and one disposal site.

– The vehicles will start from the depot, go to the disposal site when filled, and start again if there is time.

– The vehicles are heterogeneous and the grid is asymmetric.

– The vehicles will return to the depot at the end of their trip.

– Each vehicle has the maximum time of service.

– Each vehicle may have multiple trips, first one from the depot to the disposal site, and their other trips will start from the disposal site and again, end at the disposal site.

– The time and cost of a route is the same for all vehicles.

– Each demand node has a hard and soft time window of service, which means that exit from a soft time window will have a penalty, and exit from a hard time window is not possible.

Figure 1 depicts the schematic problem. Index $r$ is used to define vehicles’ multiple trips. If r is 1, it represents the first trip, starting from the depot to the disposal site. If r is 2 or greater, the vehicle begins the trip at the disposal site and ends at the disposal site. This is shown clearly in Figure 1.

Figure 1.

Multiple trips in a vehicle tour.

In Figure 1, the bold lines demonstrate the first trip, and the dashed lines show the second trip of the vehicle, which ends at the disposal site and eventually returns to the depot after completing the tour. Linear Programming (LP) models have the ideal possibility of being solved using commercial software such as GAMS and LINGO (Mohammadi et al., 2017; Tirkolaee et al., 2017). In the following, the proposed novel MILP model is presented.

Indices and sets

NC	Set of nodes with demand (demand node)
NT	Set of total nodes
K	Set of vehicles
R	Set of vehicle trips
S	Any optional subset of the demand node set
i,j	Demand node index
k	Vehicle index
r	Trip index

Parameters

c_ij	Cost of the traversing edge (i , j)
Pe	Early service cost per demand node
Pl	Late service cost per demand node
e_i,l_i	Hard time window of demand node i
ee_i,ll_i	Soft time window of demand node i
W_k	Vehicle capacity
d_j	Demand of node j
T_max	Maximum available time for each vehicle
M	Optional large number
n	The node indicating the disposal site and the number of total nodes in the network with the first node being the depot
ul	Unit of loading time for vehicles at demand nodes
uu	Unit of discharging time for vehicles at the disposal site
t_ij	Time for traversing edge (i,j)
$θ$	Converter coefficient of distance to cost (Iranian rial/km)

Variables

tt_i	Arrival time at demand node i
$L T_{k}^{r}$	Total loading time of vehicle K in trip r
$U T_{k}^{r}$	Total unloading time of vehicle K in trip r
Ye_ki	Amount of early service of the demand node i by vehicle k
Yl_ki	Amount of late service of the of the demand node i by vehicle k

x_{i j k}^{r} = {\begin{cases} 1 If vehicle k moves from node i to node \\ j in trip r without serving node j, \\ 0 Otherwise . \end{cases}

(1)

y_{i j k}^{r} = {\begin{cases} 1 If vehicle k serve node j in trip r \\ through traversing edge (i, j), \\ 0 Otherwise . \end{cases}

(2)

u_{k} = {\begin{cases} 1 I f v e h i c l e k i s u s e d, \\ 0 O t h e r w i s e . \end{cases}

(3)

Mathematical equations including objective function and constraints are as follows:

\begin{array}{l} M i n i m i z e Z = θ (\sum_{i = 1}^{N T} \sum_{j = 1}^{N T} \sum_{k = 1}^{K} \sum_{r = 1}^{R} c_{i j} x_{i j k}^{r}) \\ + \sum_{k = 1}^{K} \sum_{i = 1}^{N C} (P e Y e_{k i} + P l Y l_{k i}) + \sum_{k = 1}^{K} c v_{k} u_{k} \end{array}

(4)

subject to

\sum_{j \in N T} x_{i j k}^{r} = \sum_{j \in N T} x_{j i k}^{r} \forall i \in N T \ {1, n}, \forall k \in K, \forall r \in R,

(5)

\sum_{i = 1}^{N T} \sum_{k = 1}^{K} \sum_{r = 1}^{R} y_{i j k}^{r} = 1 \forall j \in N C,

(6)

\sum_{j = 1}^{N T} \sum_{i = 1}^{N T} d_{j} y_{i j k}^{r} \leq W_{k} \forall k \in K, \forall r \in R,

(7)

y_{i j k}^{r} \leq x_{i j k}^{r} \forall i, j \in N T, \forall k \in K, \forall r \in R,

(8)

\sum_{i = 1}^{N T} \sum_{j = 1}^{N T} \sum_{r = 1}^{R} x_{i j k}^{r} \leq M u_{k} \forall k \in K,

(9)

L T_{k}^{r} = u l \sum_{j = 1}^{N T} \sum_{i = 1}^{N T} d_{j} y_{i j k}^{r} \forall k \in K, \forall r \in R,

(10)

U T_{k}^{r} = u u \sum_{j = 1}^{N T} \sum_{i = 1}^{N T} d_{j} y_{i j k}^{r} \forall k \in K, \forall r \in R,

(11)

\sum_{r = 1}^{R} L T_{k}^{r} + \sum_{r = 1}^{R} U T_{k}^{r} + \sum_{i = 1}^{N T} \sum_{j = 1}^{N T} \sum_{r = 1}^{R} t_{i j} x_{i j k}^{r} \leq T_{m a x} \forall k \in K,

(12)

\sum_{i \in S} \sum_{\begin{array}{l} j \in S \\ i \neq j \end{array}} \sum_{k = 1}^{K} x_{i j k}^{1} \leq | S | - 1 \forall S \in N T \ {1, n}, S \neq \emptyset,

(13)

\sum_{j \in N T} x_{1 j k}^{1} \geq \sum_{j \in N T} x_{n j k}^{2} \forall k \in K,

(14)

\sum_{j \in N T} x_{n j k}^{r} \geq \sum_{j \in N T} x_{n j k}^{r + 1} \forall r \in {2, 3, \dots, R - 1}, \forall k \in K,

(15)

t t_{j} = \sum_{i = 1}^{N T} \sum_{k = 1}^{K} \sum_{r = 1}^{R} (t t_{i} + t_{i j}) y_{i j k}^{r} \forall j \in N C,

(16)

t t_{i} = 0 \forall i = 1,

(17)

e_{i} \leq t t_{i} \leq l_{i} \forall i \in N C,

(18)

Y e_{k i} \geq e e_{i} - t t_{i} \forall k \in K, \forall i \in N C,

(19)

Y l_{k i} \geq t t_{i} - l l_{i} \forall k \in K, \forall i \in N C,

(20)

\sum_{j \in N C} x_{1 j k}^{1} = u_{k} \forall k \in K,

(21)

\sum_{j \in N C} x_{i j k}^{1} = u_{k} \forall k \in K,

(22)

\sum_{i \in N C} x_{i n k}^{r} \leq M (1 - u_{k}) + 1 \forall r \in {2, 3, \dots, R}, \forall k \in K,

(23)

\sum_{j \in N C} x_{n j k}^{r} \leq M (1 - u_{k}) + 1 \forall r \in {2, 3, \dots, R}, \forall k \in K,

(24)

\begin{array}{l} x_{i j k}^{r}, y_{i j k}^{r}, u_{k} \in {0, 1}, Y e_{k i}, Y l_{k i}, t t_{i}, L T_{k}^{r}, U T_{k}^{r} \geq 0 \\ \forall i, j \in N T, \forall k \in K, \forall r \in R . \end{array}

(25)

Equation (4) defines the objective function of the problem for minimizing the total cost including the usage costs of vehicles, traversing costs, and the penalty costs for violating from permissible time windows (soft time window). Equation (5) denotes the flow balance for each vehicle. When a vehicle arrives at a specific node, it should leave from that specific node. Equation (6) ensures that each demand node is only serviced by one vehicle. Equation (7) indicates vehicle capacity constraints. Equation (8) indicates that the demand node is served by the vehicle which has already arrived at it. In other words, a vehicle may cross a node but not serve it. Equation (9) indicates that the vehicle is used when its cost is paid. Equations (10) and (11) respectively represent the total loading and unloading time for each vehicle per trip. Equation (12) indicates the usage time limitation for each vehicle. Equation (13) eliminates sub-tours. Equations (14) and (15) ensure that the order of vehicle trips’ number is from $r$ to $r + 1$ in succession. Equations (16) and (17) calculate the arrival time of vehicles at demand node. Equation (18) defines the hard time window of service for each demand node. Equations (19) and (20) respectively calculate the amount of early or late service for violating soft time windows. Equations (21) and (22) ensure that the vehicle’s first trip begins at the depot and ends at the disposal site. Equations (23) and (24) indicate that, on the second, third, and subsequent trips, vehicles will begin their trip from the disposal site and return to the disposal site. Other trips will start from the disposal site. Equation (25) specifies the types of the variables.

Linearization of Equation (16)

t t_{j} = \sum_{i = 1}^{N T} \sum_{k = 1}^{K} \sum_{r = 1}^{R} (t t_{i} + t_{i j}) y_{i j k}^{r} \forall j \in N C,

(17)

f_{i j k}^{r} \leq t t_{i} \forall i, j \in N T, \forall k \in K, \forall r \in R,

(26)

f_{i j k}^{r} \leq M y_{i j k}^{r} \forall i, j \in N T, \forall k \in K, \forall r \in R,

(27)

f_{i j k}^{r} \geq t t_{i} - M (1 - y_{i j k}^{r}) \forall i, j \in N T, \forall k \in K, \forall r \in R,

(28)

t t_{j} = \sum_{i = 1}^{N T} \sum_{k = 1}^{K} \sum_{r = 1}^{R} f_{i j k}^{r} + t_{i j} y_{i j k}^{r} \forall j \in N C,

(29)

f_{i j k}^{r} \geq 0 \forall i, j \in N T, \forall k \in K, \forall r \in R .

(30)

Proposed solution

Due to the complexity of the problem, it is not efficient to solve it with precise methods (Solomon, 1987). Therefore, an innovative algorithm for generating an initial solution and a SA is proposed to solve the problem. Many studies have been carried out on using this algorithm to solve optimization problems with various purposes, which indicates the high efficiency of SA for solving routing problems (Tirkolaee et al., 2018a, 2018b, 2018c).

The following sub-sections describe the mechanism of SA and the innovative algorithm to generate the appropriate initial solutions.

Innovative algorithm to generate initial solutions

An innovative random generator algorithm is developed to generate the initial solutions; the steps to implement this method are as follows:

Step 1: Choose a vehicle randomly. The first trip starts from the depot.

Step 2: Choose v nodes according to the time window, priority (eligible) and the least distance to the depot among the remaining demand nodes, choose one on random and then go to step 3.

Step 3: If there are still any remaining demand nodes eligible to be services and added to the vehicle’s trip, go to step 4, otherwise, go to step 5.

Step 4: The capacity and usage time limitation of the vehicle allowing them to be chosen, select one of them randomly and then go to step 3. If there are no eligible demand nodes, go to step 5 (the last considered node is eligible to be served only if the vehicle has enough time and capacity to serve it and then move back to the disposal site).

Step 5: Go to the disposal site and then go to step 6.

Step 6: If all demand nodes are covered, go to step 7, otherwise, update vehicle’s capacity constraint. If the vehicle’s time limit allows for at least a trip from the disposal site to a demand node, go to step 3, otherwise, choose the next vehicle and go to step 2.

Step 7: Stop the algorithm.

The number of the generated initial solutions is set to 500, and the best solution is reported after implementing the proposed SA. The flowchart of the proposed algorithm to generate the initial solutions is shown in Figure 2.

Figure 2.

Flowchart of the innovative algorithm for generating the initial solutions.

SA

The proposed SA is applied to improve the solutions and all the initial solutions are individually improved with this algorithm. SA is a local search algorithm that has the ability to escape from local optimums. This algorithm is very efficient at solving non-convex or discrete optimization problems. As the same way, SA is employed to solve integer programming problems (Glover and Kochenberger, 2006).

Moreover, the simplicity of the implementation, the convergence properties, as well as the hill climbing movements to escape the local optimum trap have led to the improvement of the initial solutions generated in each iteration. The general framework of the algorithm is that it starts with an initial solution – the initial parameters of the algorithm include the number of the algorithmic iteration at each temperature ( $M$ ), the initial temperature ( $T_{0}$ ), the temperature decrease rate ( $α$ ), the final temperature ( $T_{e n d}$ ), and the Boltzmann constant ( $K$ ) that are initialized before the start of the search, then a neighborhood is considered for the initial solution. If the value of the generated neighboring objective function is better than the current objective function, the neighboring objective function is substituted as the solution and otherwise, a random number in the range of [0, 1] is compared with the algorithm value – if the random number is less than the value of the algorithm, the solution is accepted. At each temperature, there are a number of iterations, and then the temperature decreases. The stop condition is to reach the final temperature. Ultimately, the values of the parameters are determined using the trial and error method, which are shown as follows:

M = 5, α = 0.98, T_{0} = 200, T_{e n d} = 1, K = 0.8

(31)

Local search

The local search methods for constructing neighborhoods in the algorithm are as follows:

(A) Displacement: In this method, the location of one of the nodes in the constructive route string (from the depot to the disposal site and then from the disposal site to the disposal site) changes (see Figure 3).

(B) Replacement: In this method, the locations of two nodes in the constructive route string are replaced (see Figure 4).

(C) 2-Opt: In this method, the location of a primary node and a final node on the path edges are replaced (see Figure 5.

(D) Or-opt: In this method, the position of the two nodes is changed simultaneously in the constructive route string (see Figure 6).

Figure 3.

Displacement.

Figure 4.

Replacement.

Figure 5.

2-Opt.

Figure 6.

Or-Opt.

The implementation of the algorithm is shown by presenting the pseudo-code in Figure 7.

Figure 7.

Simulated annealing pseudo-code.

Computational results

In order to evaluate the efficiency of the proposed algorithm, eight problems with small and medium dimensions, and seven large dimension problems are solved and the quality of the solutions is analyzed. Table 1 provides information about the randomly generated samples.

Table 1.

Randomly generated samples.

Problem number	Total number of nodes	Number of vehicles available in each problem
P1	7	2
P2	12	3
P3	15	3
P4	18	4
P5	22	4
P6	25	5
P7	28	5
P8	32	6
P9	40	6
P10	45	6
P11	60	7
P12	70	7
P13	80	8
P14	90	8
P15	100	9

To solve the problem, a computer with a Core i7-4720HQ CPU @ 2.60GHz processor and 8.00GB of RAM is used, the proposed algorithm is coded in MATLAB software, and the proposed mathematical model is coded and run in GAMS software (CPLEX solver) as the suggested exact method. The obtained results are presented in Table 2. The average values reported for the objective function and run time of SA is determined after running 10 times. Comparing the best solution from the algorithm with the best solution so far and calculating the percentage of gap, it is found that the proposed algorithm generates suitable results in a short computational time.

Table 2.

Computational results.

Problem	Number of used vehicles	CPLEX objective value	CPLEX run time (seconds)	Simulated annealing (SA) mean objective value	SA mean run time (seconds)	SA best objective value	Gap (%)
P1	1	2862	20.15	2891.5	2.67	2873	0.38
P2	1	3023	79.64	3115.1	4.52	3046	0.76
P3	2	3716	218.25	3783.2	7.9	3751	0.93
P4	2	4232	361.14	4338.6	11.29	4322	2.08
P5	2	4571	1001.54	4664.3	13.82	4613	0.91
P6	3	5408	1825.8	5492.4	17.18	5478	1.28
P7	4	5644	2438.71	5703.02	23.14	5694	0.88
P8	4	6469	3714.92	6534.48	28.22	6517	0.74
P9	5	–	–	7288.68	32.86	7260	–
P10	5	–	–	7404.16	37.04	7392	–
P11	6	–	–	8179.12	44.15	8165	–
P12	7	–	–	9376.83	56.73	9328	–
P13	7	–	–	9613.21	61.28	9582	–
P14	8	–	–	10328.9	69.19	10240	–
P15	8	–	–	10864.57	76.84	10816	–

As it is clear, for the eight examples above, the error rate in SA relative to the exact method is, on average, approximately equal to 1%, which indicates the ability of the algorithm to find the appropriate solutions. CPLEX is not able to solve the P9–P15 within applying time limitation of 3600 seconds.

In terms of run time, the average time required to solve a problem in small dimensions for the exact method is about 1205 seconds and for the proposed algorithm is about 13.5 seconds. This information represents the high speed of the proposed SA. Figure 8 shows this run time comparison.

Figure 8.

Run time comparison.

Case study

To study the applicability of the proposed mathematical model, a case study is conducted in a district of the Sanandaj city using the proposed algorithm of the research. Primarily, by reviewing the information in this district, including the procedure of waste collection, routing, and the number of required vehicles, the current status of the waste collection system is carefully examined. This occurs after the required information, such as the usage cost of the vehicles (i.e., the wages of drivers and their crew, and fuel cost), distance between network nodes, vehicle capacity, demand values of nodes and the time windows given for specific nodes such as hospitals and clinics, has been provided by the municipality’s experts.

It should be noted that the district has two clinics that need to be considered as the priority for the service. It also has a 5-ton vehicle for waste collection. The value of θ is also assumed to be 10 units. The demand for each normal node is also estimated at between 100 and 200 kilograms.

Figure 9 shows the district’s aerial map. The district has an area of 330 square kilometers and a vehicle parking as the depot, and has 43 nodes of demand. Numbers 23 and 43 indicate the nodes of the clinics, which are estimated at 10 and 20 kilograms of waste, respectively. These demand nodes and vehicle parking are specified in Figure 9. Moreover, the network graph associated with this map is shown in Figure 10.

Figure 9.

Aerial map of the district.

Figure 10.

Graph network specifying the access routes for demand nodes.

Due to the availability of information, the district begins the waste collection service from 7:00 pm to 12:00 pm and all of the waste in the area is collected by a 5-ton dump truck. The routing of this vehicle in the current situation is in accordance with the order of demand numbers where the vehicle moves from parking to the demand node 1, and then to the demand node 2, and so on. There is no attention to the priority of serving the clinical nodes in order to prevent hazardous contamination. In this research, we implement our proposed algorithm considering the priorities and the other input parameters.

After solving the problem, the result is given in Figure 11 characterized by its prioritization and routing schedule.

Figure 11.

Optimal routing for the case study problem.

The priorities of the optimal routing, the objective function, and the run time of the case study are provided in Table 3. As it is obvious, the truck can cover all the demands with two trips.

Table 3.

The optimal solution obtained from the case study.

Optimalrouting	Parking – 11-21-31-32-39-40-42-41-43-38-33-30-22-20-23-19-12-10-4-2-1-3- Disposal site – 5-6-9-8 -13-14-18-24-29-34-37-35-28-27-25-36-26-16-17-15-7- Disposal site – parking
Objective value (Iranian rial)	55,050,000
Run time (seconds)	43.525

As shown in Table 3, nodes 43 and 23 are respectively the ninth and fifteenth priorities of the service.

To compare the obtained results with the current state, Table 4 is presented.

Table 4.

The comparing status of the current and optimal policies.

Values	Current status	Optimal status
Priority of node 23	23	15
Priority of node 43	43	9
Objective value (Iranian rial)	63,500,000	55,050,000

As shown in Table 4, after obtaining the optimal solution of the case study, the objective function has dropped 8,450,000 Iranian rial, which is equivalent to a 13.3% decrease in the total cost. It should be noted that such savings are obtained while the priority of the clinics is regarded. It is obvious that the savings would certainly be greater without these priorities.

Conclusions and future suggestions

Optimal routing and vehicle allocating are one of the important decisions of organizations such as municipalities in the urban waste collection, since optimal vehicles’ allocation and their optimal routing can lead to a significant percentage reduction of related costs. In this paper, a MILP model is proposed for heterogeneous multi-trip vehicle routing problem with time windows specific to the urban waste collection, which aims to determine the optimal service routes and the optimal number of the used vehicles. In order to solve the problem, a SA algorithm is developed based on the considered assumptions in the problem. The results obtained by solving the problem in small and medium sizes indicate that this algorithm offers near-optimal solutions in comparison with the CPLEX solver. Finally, a case study is investigated in order to evaluate the applicability of the proposed model in the real world. After analyzing the case study, it has been demonstrated that the proposed model can improve the current status by generating a 13.3% decrease in the total cost.

For future work suggestions, the demand parameter can be considered uncertain in the model and the other metaheuristics such as ant colony optimization and genetic algorithm can be tested to solve the problem as a rival for SA.

Footnotes

Declaration of conflicting interests

The authors declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The authors received no financial support for the research, authorship, and/or publication of this article.

Notes

ORCID iDs

Erfan Babaee Tirkolaee

Seyed Ali Ghaffarian

References

Angelelli

Speranza

(2002) The periodic vehicle routing problem with intermediate facilities. European Journal of Operational Research 137: 233–247.

Babaee Tirkolaee

Alinaghian

Bakhshi Sasi

et al . (2016) Solving a robust capacitated arc routing problem using a hybrid simulated annealing algorithm: A waste collection application. Journal of Industrial Engineering and Management Studies 3: 61–76.

Beltrami

Bodin

(1974) Networks and vehicle routing for municipal waste collection. Networks 4: 65–94.

Buhrkal

Larsen

Ropke

(2012) The waste collection vehicle routing problem with time windows in a city logistics context. Procedia – Social and Behavioral Sciences 39: 241–254.

Clarke

Wright

(1964) Scheduling of vehicles from a central depot to a number of delivery points. Operations research 12: 568–581.

De Bruecker

Beliën

De Boeck

et al . (2018) A model enhancement approach for optimizing the integrated shift scheduling and vehicle routing problem in waste collection. European Journal of Operational Research 266: 278–290.

Erfani

SMH

Danesh

Karrabi

et al . (2017) A novel approach to find and optimize bin locations and collection routes using a geographic information system. Waste Management & Research 35: 776–785.

Gamberini

Gebennini. Grassi

et al . (2008) An innovative model for WEEE recovery network management in accordance with the EU directives. International Journal of Environmental Technology and Management 8: 348–368.

Gamberini

Gebennini

Manzini

et al . (2010) On the integration of planning and environmental impact assessment for a WEEE transportation network – A case study. Resources, Conservation and Recycling 54: 937–951.

10.

Glover

Kochenberger

(eds) (2006) Handbook of Metaheuristics. Berlin, Germany: Springer Science and Business Media.

11.

Karadimas

Papatzelou

Loumos

(2007) Optimal solid waste collection routes identified by the ant colony system algorithm. Waste Management & Research 25: 139–147.

12.

Kim

Sahoo

(2006) Waste collection vehicle routing problem with time windows. Computers & Operations Research 33: 3624–3642.

13.

Mar-Ortiz

González-Velarde

Adenso-Díaz

(2013) Designing routes for WEEE collection: The vehicle routing problem with split loads and date windows. Journal of Heuristics 19: 103–127.

14.

Mirmohammadi

Babaee Tirkolaee

Goli

et al . (2017) The periodic green vehicle routing problem with considering of the time-dependent urban traffic and time windows. International Journal of Optimization in Civil Engineering 7: 143–156.

15.

Mohammadi

Limaei

Shahraji

(2017) Linear programming approach for optimal forest plantation. Journal of Forestry Research 28: 299–307.

16.

Solomon

(1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research 35: 254–265.

17.

Teixeira

Antunes

de Sousa

(2004) Recyclable waste collection planning-a case study. European Journal of Operational Research 158: 543–554.

18.

Tirkolaee

Goli

Bakhsi

et al . (2017) A robust multi-trip vehicle routing problem of perishable products with intermediate depots and time windows. Numerical Algebra, Control and Optimization 7: 417–433.

19.

Tirkolaee

Alinaghian

Hosseinabadi

AAR

et al . (2018a) An improved ant colony optimization for the multi-trip Capacitated Arc Routing Problem. Computers & Electrical Engineering. E-publication before print, 13 February 2018. DOI.org/10.1016/j.compeleceng.2018.01.040.

20.

Tirkolaee

Hosseinabadi

AAR

Soltani

et al . (2018b) A hybrid genetic algorithm for multi-trip green capacitated arc routing problem in the scope of urban services. Sustainability 10: 1366. E-Publication before print. DOI.org/10.3390/su10051366.

21.

Tirkolaee

Mahdavi

Esfahani

MMS

(2018c) A robust periodic capacitated arc routing problem for urban waste collection considering drivers and crew’s working time. Waste Management 76: 138–146.

22.

Tung

Pinnoi

(2000) Vehicle routing–scheduling for waste collection in Hanoi. European Journal of Operational Research 125: 449–468.

Problem number	Total number of nodes	Number of vehicles available in each problem
P1	7	2
P2	12	3
P3	15	3
P4	18	4
P5	22	4
P6	25	5
P7	28	5
P8	32	6
P9	40	6
P10	45	6
P11	60	7
P12	70	7
P13	80	8
P14	90	8
P15	100	9

Problem number	Total number of nodes	Number of vehicles available in each problem
P1	7	2
P2	12	3
P3	15	3
P4	18	4
P5	22	4
P6	25	5
P7	28	5
P8	32	6
P9	40	6
P10	45	6
P11	60	7
P12	70	7
P13	80	8
P14	90	8
P15	100	9

Problem number	Total number of nodes	Number of vehicles available in each problem
P1	7	2
P2	12	3
P3	15	3
P4	18	4
P5	22	4
P6	25	5
P7	28	5
P8	32	6
P9	40	6
P10	45	6
P11	60	7
P12	70	7
P13	80	8
P14	90	8
P15	100	9