A case study on collection network design, capacity planning and vehicle routing in reverse logistics

Abstract

This paper reports a case study on designing and operating a Korean municipal refuse collection system. Refuse collection, one of indispensable activities in reverse logistics, is the activity that gathers end-of-use/life products and moves them to the facilities where further recovery or disposal is done. The case problem consists of two sub-problems: (a) collection network design and capacity planning that determines the locations and capacities of collection points as well as the allocations of demand points to the opened collection points over a given planning horizon and (b) vehicle routing that determines the number and routes of vehicles in such a way that each collection point must be visited exactly once by one vehicle starting and terminating at the depot. The case problems were solved using the two tabu search (TS) algorithms, hierarchical and integrated algorithms, adopted from the previous theoretical study, and the results show that the algorithms give much better solutions than the conventional method in terms of the sum of fixed and variable costs. Also, as in the previous theoretical study, of the two TS algorithms, the integrated approach outperforms the hierarchical algorithm significantly.

Keywords::

• reverse logistics
• collection network design
• capacity planning
• vehicle routing
• case study

1. Introduction

Compared with the forward logistics from suppliers to customers, the reverse logistics is concerned with the backward logistics from customers to distributors, producers or suppliers for product recovery or disposal. Reverse logistics, the opposite direction of the conventional forward logistics, is defined as the logistics activities that end-of-use/life products or wastes no longer required by users are delivered to facilities for further product recovery or disposal (Fleischmann et al. 1997). For the characteristics, classification and comprehensive reviews on reverse logistics, see Bloemhof-Ruwaard, Fleischmann, and van Nunen (1999), Fleischmann et al. (2000), Dowlatshahi (2000), Ferguson and Browne (2001), Srivastava (2007), Lee, Kim, and Kim (2008) and Sasikumar and Kannan (2008).

Refuse collection, one of reverse logistics activities, is the one that gathers end-of-use/life products and moves them to the facilities where further recovery or disposal is done. Here, end-of-use/life products are called refuses in solid waste management. Note that refuse collection is one of the most important reverse logistics activities since end-of-use/life products must be collected before their further recovery or disposal (Lee, Kim, and Kim 2008). In general, a refuse collection system consists of collection points, recovery and disposal facilities, workers, etc. Here, the collection points, i.e. places where refuses are gathered and handled for further treatments, are important structural elements in refuse collection systems.

This study reports a case study on designing and operating a Korean municipal refuse collection system. The case problem consists of two sub-problems: (a) network design and capacity planning that determines the locations and capacities of collection points as well as the allocations of refuses at demand points to the opened collection points and (b) vehicle routing that determines the number and routes of vehicles in such a way that each collection point must be visited once by one vehicle starting and terminating at the depot while satisfying the refuse demands at collection points and the vehicle capacity. See Mansini and Speranza (1998) and Lee, Kim, and Kim (2008) for more details on other decision problems in refuse collection systems.

Most previous studies consider the network design/capacity planning and the vehicle routing problems hierarchically, and hence the resulting solutions are local optimum. Instead, the integrated approach has a substantial benefit in that it pursues the global optimum by searching enlarged solution space. See Salhi and Rand (1989) and Min et al. (1998) for the limitations of the hierarchical approach for network design and vehicle routing. In fact, we found that the Korean municipal refuse collection system considered in this case study has no concept of optimization, especially on network design, capacity planning and vehicle routing. Therefore, due to its much room for improvement, it can be expected that a significant amount of improvement can be obtained from modelling and solving the integrated problem.

Several previous studies have been done on network design in collection systems. For example, see Aras and Aksen (2008), Kim and Lee (2008, 2013a) and Kim et al. (2010) for static collection network design models, i.e. single-period models with refuse demands for a certain period of time, and Min and Ko (2008), El-Sayed, Afia, and El-Kharbotly (2010) and Kim and Lee (2013b) for dynamic models, i.e. multi-period models with dynamic refuse demands over a planning horizon. Beside these, there are some case studies on reverse logistics network design, not focusing on only the collection activity. For example, Kroon and Vrijens (1995) consider a reverse logistics network that collects and reprocesses returnable containers for reuse, and Jayaraman, Guide, and Srivastava (1999) consider the problem of determining the locations of remanufacturing and distribution facilities together with production quantities and inventory of remanufactured products. See Kara, Rugrungruang, and Kaebernick (2007), Lu and Bostel (2007) and Pati, Vrat, and Kumar (2008) for other case studies on designing various reverse logistics networks. Also, there are some case studies on vehicle routing in refuse collection systems. For example, see Tung and Pinnoi (2000), Baptisa, Oliveira, and Zúquete (2002), Teixeira, Antunes, and Sousa (2004), Kim, Choi, and Lee (2007) and Kim, Choi, and Lee (2011). For relevant literature and meta-heuristic based solution algorithms on various vehicle routing problems, see Laporte (2007, 2009) and Bräysy and Gendreau (2005a, 2005b). Finally, some case studies are reported on static network design and operation of collection systems. For example, see Mar-Ortiz, Adenso-Díaz, and González-Velarde (2011), and Manzini and Bortolini (2012).

As stated earlier, this study considers collection network design, capacity planning and vehicle routing. To the best of the authors' knowledge, there is no previous case study on the dynamic version of the integrated problem, which is the main contribution of this study. In fact, this paper is a case study version of Kim and Lee (2014) who suggest an integrated model for dynamic collection network design, capacity planning and vehicle routing. To solve the case instances, we adopted their two tabu search (TS) algorithms, hierarchical and integrated algorithms, which minimize the sum of fixed costs to open collection points and acquire vehicles as well as variable costs to transport refuses at demand points to the opened collection points and to travel the opened collection points by vehicles. To show the performances of the two tabu algorithms, computational experiments were done on the data obtained from the case and the results are reported.

The remainder of this paper is organized as follows. In the next section, we describe the refuse collection system, together with the conventional method, and the integrated problem considered in this case study. The solution algorithms and their test results, together with some managerial insights, are presented in Sections 3 and 4, respectively. Finally, Section 5 concludes the paper with a summary and discussion of some areas for further research.

2. System and problem descriptions

This section explains the refuse collection system considered in this case study, and describes the integrated problem more clearly.

2.1 System description

The material flow of the refuse collection network considered in this study is schematically described in Figure 1. As can be seen in the figure, the example has one depot, three collection points and five demand points. The refuse demand at each demand point is moved to the corresponding collection point, and the refuses gathered at collection points are transported to the depot according to pre-determined routes by collection vehicles. Here, the depot is the depository of end-of-use/life products for further recovery or disposal.

Figure 1 Material flows in the refuse collection network: schematic description.

The refuse collection system considered in this case study is shown in Figure 2, which is located at the Seongdong-gu district of Seoul, Republic of Korea. The Seongdong-gu office operates its refuse collection system in such a way that its region is divided into 20 areas, and one vehicle, together with two or three workers, is assigned to each area. In this case study, among the 20 areas of the Seongdong-gu region, we selected three adjacent areas, called Seongsu 1-ga 1-dong, Seongsu 1-ga 2-dong and Seongsu 2-ga 3-dong in Korean, due to the difficulty in gathering all the required data. The three areas currently have 47 collection points and 1 depot, where the depot is the place where the collected products or wastes are stored for further reprocessing, i.e. recovery or disposal. Also, each collection point is equipped with an identical sized bucket.

Figure 2 Locations of collection points and vehicle routes in the conventional system.

In the conventional method, network design and capacity planning are done arbitrarily without any systematic procedure. In other words, the number, locations and capacities of collection points are determined by the responsible officer's experience or intuition and fixed over time, and the refuses at demand points are allocated to the closest opened collection points. Also, the vehicle routes, which are fixed and remained the same, are determined according to the workers' experience. Note that one vehicle is assigned to each area, and hence there are three vehicles in total. Therefore, each vehicle must return to the depot whenever full while travelling from the collection points. In fact, the numbers in Figure 2 show the sequence of visits, i.e. 1–14, 15–34 and 35–47 for areas 1, 2 and 3, respectively.

2.2 Problem description

As stated earlier, the integrated problem considered in this study has two sub-problems: (a) network design and capacity planning and (b) vehicle routing. Each of the two sub-problems is explained below. Note that the integrated problem is NP-hard since it consists of two well-known NP-hard problems.

2.2.1 Network design and capacity planning sub-problem

The network design and capacity planning sub-problem is a restricted dynamic version in that it determines the static locations and capacities of collection points and the dynamic allocations of refuses at demand points to the opened collection points over a planning horizon with discrete time periods while satisfying the capacity and the maximum allowable collection distance constraints at each collection point. Here, the collection points are selected among the potential sites. The objective is to minimize the sum of fixed costs to open collection points and variable costs to move refuses at demand points to the opened collection points. The fixed costs may be different at different collection points and capacity levels, and the variable costs are assumed to be directly proportional to the corresponding distance and refuse amount. More formally, the two cost terms can be represented as

where the notations can be defined as follows.

	=	fixed cost to open a collection point with capacity level q ∈ Q at potential site j ∈ N (normally incurred by system administrators), where N and Q represent the set of potential sites and the set of capacity levels available at each potential site, respectively
cij	=	variable cost to move a unit of refuse per unit distance from demand point i to collection point located at potential site j (normally incurred by customers)
wit	=	amount of refuse at demand point (potential site) i in period t
dij	=	distance between potential sites i and j
	=	= 1 if a collection point with capacity level q is opened at potential site j, and 0 otherwise (decision variable)
xijt	=	= 1 if the refuse at demand point i is allocated to the collection point opened at potential site j at period t and 0 otherwise (decision variable)

In this study, a restricted dynamic problem is considered in order to consider the fluctuating refuse demands explicitly. According to Kim and Lee (2013b), the restricted dynamic problem is worth to be considered because it is highly unlikely to change collection points due to their large fixed costs incurred by frequent changes in the locations of collection points. In addition, the capacity of each collection point is determined by selecting one among the set of predetermined capacity levels.

The first sub-problem has two main constraints: capacity and maximum allowable collection distance. The capacity constraint implies that there is an upper limit on the amount of refuses at demand points when they are allocated to the collection point. Note that the capacity level at each collection point is one of decision variables. Also, the maximum allowable collection distance at each collection point implies that no demand points beyond its distance limit can be allocated to the collection point. This constraint is considered additionally due to the fact that a physical distance/time limit exists between collection and demand points.

The basic assumptions made for the first sub-problem are as follows: (a) potential sites are given in advance and do not change over the planning horizon, where a potential site, used as a synonym of a demand point, is defined as the one that the collection point can be located; (b) only one collection point is opened at each potential site; (c) each demand point is allocated to exactly one collection point, i.e. no demand splitting; (d) the amount of refuse at each demand point is deterministic and given in advance; (e) the set of capacity levels at each potential site is given in advance; (f) the maximum allowable distance at each potential site is deterministic and given in advance and (g) symmetric rectilinear distance is used between two points in the network.

2.3 Vehicle routing sub-problem

The vehicle routing sub-problem considered in this study is the capacitated vehicle routing problem (CVRP). More specifically, the sub-problem is to determine the number and routes of vehicles to serve the opened collection points while satisfying their refuse demands and the available vehicle capacity in each period of the planning horizon. In this sub-problem, the collection points are given from the solution of the network design and capacity-planning sub-problem. Since we consider a multi-period problem, it is needed to solve T problems, where T denotes the number of periods in the planning horizon. The objective is to minimize the sum of fixed costs to acquire vehicles and the variable costs to travel from opened collection points. Here, the fixed cost is additionally considered in this study since it is one of major tactical decisions in designing and operating collection systems, and the purchase or rental cost occupies a large part of the total logistics cost. More formally, the cost terms can be represented as

where the notations can be defined as follows.

N′	=	set of opened collection points
fv	=	fixed cost to acquire a vehicle
K	=	number of vehicle routes
vij	=	vehicle travelling cost between collection points i and j
	=	= 1 if vehicle (route) k travels from collection points i to j, and 0 otherwise.

The basic assumptions made for the vehicle routing sub-problem are as follows: (a) all vehicles start and end at the depot, (b) every collection point is visited exactly once by exactly one vehicle, (c) cost values are deterministic, time-invariant and given in advance and (d) variable travelling costs are symmetric and satisfy the triangular inequality.

A solution for the CVRP considered in this study can be represented as a set of routes R₁, R₂, … , R_K, where R_k = (0, i_k1, i_k2, … , 0). Note that i_kl denotes the index for the lth collection point to be visited. Overall, the vehicle routing solution can be obtained from two distinct decisions, i.e. allocation and routing. The allocation decision is to assign collection points to vehicles while the routing decision is to order the collection points assigned to each vehicle. Also, the constraint is that the total demand of any route should not exceed the vehicle capacity. Note that the CVRP is NP-hard since its special case is the well-known travelling salesman problem.

3. Solution algorithms

This section explains the two types of TS algorithms, hierarchical and integrated algorithms. The hierarchical algorithm solves the two sub-problems sequentially, while the integrated algorithm solves the two sub-problems at the same time. The solution algorithms are explained briefly since they are adopted from Kim and Lee (2014).

3.1 Hierarchical tabu search algorithm

In the hierarchical tabu search (H-TS) algorithm, the network design and capacity planning sub-problem is solved using a TS algorithm, and then the vehicle routing sub-problems are solved using the cluster-first route-second algorithm of Fisher and Jaikumar (1981) with the 2-opt/3-opt improvement method. Each of the algorithms is explained below.

3.1.1 Network design and capacity planning algorithm

This section explains the TS algorithm to solve the network design and capacity planning sub-problem. The algorithm is explained with the methods to represent solutions, to obtain an initial solution, to generate neighbourhood solutions, to define tabu moves and to terminate the algorithm.

Solution representation. A solution is represented using the three vectors, Y = (y₁, y₂, … , y_n), Q = (q₁, q₂, … , q_n) and X_t = (x_1t, x_2t, … , x_nt), where Y, Q and X_t represent the static locations of collection points, their capacities and the allocations of demand points in period t, respectively. (n denotes the number of potential sites, i.e. |N| = n.) More formally, y_i = 1 if potential site i is selected as a static collection point, and 0 otherwise. Also, q_i and x_it denote the indices of the capacity level of the collection point opened at potential site i and the collection point is assigned to demand point i in period t, respectively.

Obtaining an initial solution. The initial solution is obtained using a simple greedy heuristic in which the static collection points are selected one-by-one in the non-decreasing order of their fixed costs until a feasible allocation is obtained over the planning horizon. In the initial solution, the fixed cost is determined after selecting the capacity level randomly and each demand point is allocated to the closest collection point. Here, a feasible allocation implies that all demand points can be allocated without violating the corresponding maximum allowable collection distance. After a feasible allocation is obtained, the capacity of each collection point is set to the feasible capacity level nearest to the sum of the demands allocated to the corresponding collection point. If no feasible capacity level can be set to a collection point, the demand point with the maximum demand among those allocated the collection point is reallocated to the second closest collection point. This is done until a feasible solution is obtained.

Generating neighbourhood solutions. The neighbourhood solutions are generated using the method to change locations, capacities and allocations sequentially. First, the location is changed by removing an existing collection point and adding a new point, i.e. swapping two collection points. After setting the capacity level of the new collection point to that of the removed point, the allocation is done as in the first method. Then, the best one is selected that gives the minimum cost after evaluating all possible candidates for swapping collection points. Second, for the best solution obtained at the first step, the capacity levels are changed for all alternatives of two collection points, and the best one is selected after allocating demand points as in the first step. Finally, for the current best solution obtained at the second step, the allocation is changed in each period of the planning horizon by selecting two demand points and interchanging their collection points while satisfying the capacities and the maximum allowable collection distances, and the best one is selected as the final neighbourhood solution.

Defining tabu moves. Tabu moves are maintained by storing the solutions that have been visited, i.e. three lists for location, allocation and capacity are maintained and checked for tabu moves. As an exceptional case, a tabu move can be allowed to be chosen if it generates a solution better than the incumbent solution, i.e. the best objective value obtained so far.

Termination condition. The algorithm was terminated if no improvements have been made for a certain number of consecutive iterations.

3.1.2 Vehicle routing algorithm

In the H-TS algorithm, the vehicle routing sub-problem is solved by a two-phase heuristic in which an initial solution is obtained using the cluster-first route-second algorithm of Fisher and Jaikumar (1981), and then it is improved using the 2-opt/3-opt algorithm.

In the cluster-first route-second algorithm, the collection points are clustered by solving the generalized assignment problem, and then the vehicle route in each cluster is determined by solving the corresponding travelling salesman problem. Here, the number of clusters (vehicles) is determined by dividing the total demand by the vehicle capacity, i.e. ⌈Σd_I/C⌉, where d_i and C denote the refuse demand at collection point i and vehicle capacity, respectively. (⌈·⌉ denotes the smallest integer that is greater than or equal to.) Note that the generalized assignment problem has the vehicle capacity constraint and hence the collection points are clustered in such a way that the total demand of each cluster does not exceed the vehicle capacity. In our application, the generalized assignment problem is solved using the MTHG algorithm of Martello and Toth (1990), and for each cluster determined by solving the generalized assignment problem, the travelling salesman problem is solved using the constraint relaxation-based algorithm of Miliotis (1976) to form the vehicle route.

After the initial solution is obtained using the cluster-first route-second algorithm described earlier, it is improved by applying the 2-opt and the 3-opt algorithms sequentially to each route, i.e. the 3-opt algorithm is used if there is no improvement after the 2-opt algorithm is used. Here, the 2(3)-opt algorithm improves the solution by removing all possible two (three) connections in a route and then reconnecting the separated routes in all possible ways.

3.2 Integrated tabu search algorithm

Unlike the H-TS algorithm, the integrated tabu search (I-TS) algorithm solves the two sub-problems at the same time. In other words, the network design and capacity planning sub-problem is solved using the TS algorithm explained earlier, and for each alternative of network design and capacity planning, the vehicle routing sub-problems are solved using another TS algorithm.

In the TS algorithm for vehicle routing, the initial solution is obtained using the saving algorithm of Clarke and Wright (1964) while considering the vehicle capacity. (The detailed procedure of the saving algorithm is omitted here.) Also, the neighbourhood solutions are generated by applying the 2-opt and the 3-opt algorithms sequentially to each vehicle route, where the 3-opt algorithm is used if there is no improvement using the 2-opt algorithm for a certain number of iterations. (In our case study, the number of iterations was set to 100.)

4. Test results

This section reports the test results on the case study. First, we report the amount of improvement that the two TS algorithms gave over the conventional method. Second, the two TS algorithms are compared with each other to show the efficiency of the integrated approach. The two algorithms were coded in C and the test was performed on a workstation with an Intel Xeon processor operating at 3.20 GHz clock speed.

To gather the required data, we visited the Seongdong-gu office several times. Since it was not enough to gather the required data during the office visits, we visited some collection points and discussed with the workers on the data. As can be seen in Figure 2, there are 47 collection points currently in total, i.e. 14, 13 and 20 at areas 1, 2 and 3, respectively. After the visits and discussions, we summarized the case data as follows.

• The total number of demand points (potential sites) was set to 1313, i.e., 452, 462 and 399 at areas 1, 2 and 3, respectively. (These points were determined according to the locations of the major buildings located within the three areas.)

• The planning horizon was set to 3 days and the distances were obtained directly from the map. Recall that the rectilinear distances were used in this case study.

• The refuse demands at demand points in each period were generated from DU(1, 35), where DU(a, b) denotes the discrete uniform distribution with range [a, b], since we could obtain the demand data only at the collection point level, not the demand point level. Note that the demand data were generated in such a way that the sum of the refuse demands assigned to a collection point in each period is equal to the corresponding demand at the collection point. (Table 1 shows the refuse demands at each collection point over the planning horizon, which were set according to the data obtained from the district office.)

  Table 1 Refuse demands over the planning horizon: case data.

  Collection points	Day 1 (kg)	Day 2 (kg)	Day 3 (kg)	Average (kg)
  1	600	612	588	600
  2	882	900	918	900
  3	600	600	600	600
  4	1009	988	1003	1000
  5	600	597	603	600
  6	1304	1200	1096	1200
  7	689	700	711	700
  8	1119	1200	1281	1200
  9	600	600	600	600
  10	900	909	891	900
  11	2500	2500	2500	2500
  12	2419	2581	2500	2500
  13	1489	1500	1511	1500
  14	2500	2328	2672	2500
  15	1020	1020	1020	1020
  16	840	835	845	840
  17	999	1080	1161	1080
  18	1000	1000	1000	1000
  19	992	1288	1140	1140
  20	480	480	480	480
  21	800	796	804	800
  22	1000	1000	1000	1000
  23	916	960	1004	960
  24	1000	1000	1000	1000
  25	420	420	420	420
  26	600	599	601	600
  27	988	1052	1020	1020
  28	830	827	833	830
  29	1258	1400	1542	1400
  30	600	572	628	600
  31	420	428	412	420
  32	300	320	280	300
  33	780	780	780	780
  34	780	780	780	780
  35	1040	1040	1040	1040
  36	1105	1186	1267	1186
  37	771	775	765	771
  38	891	920	949	920
  39	1260	1260	1260	1260
  40	862	852	872	862
  41	1280	1280	1280	1280
  42	720	716	724	720
  43	760	760	760	760
  44	1110	1140	1170	1140
  45	1120	1120	1120	1120
  46	800	821	1043	888
  47	841	840	839	840

• The collection system uses the identical collection vehicles with the capacity of 2.5 ton. In our case study, we consider other vehicle types, i.e. 4.5 and 5.8 ton. Note that one vehicle type is used for each test instance, i.e. homogeneous CVRP is considered in this case study. Also, the fixed costs of 2.5, 4.5 and 5.8 ton vehicles were set to 3,000,000, 4,000,000 and 5,000,000 Won, which were estimated from their purchase costs and useful lives.

• The capacity levels of collection points are determined according to the available bucket sizes, i.e. 1, 2.5, 4.5 and 5.8 ton. In the conventional system, the 2.5 ton bucket is being used at each collection point.

• The maximum allowable collection distance for each collection point was set to 0.2 km according to the workers' opinion.

• The fixed costs to open collection points were calculated using the land cost, i.e. collection point size × unit land cost. (Note that the collection point size is about 5 m².) Also, the bucket costs, i.e. 80,000, 120,000, 150,000, 280,000 Won for 1, 2.5, 4.5 and 5.8 ton buckets, were added to the fixed cost in order to consider the capacity level-based fixed costs. (1 US$ ≅ 1100 Korean Won.)

• The unit transportation cost from a demand point to a collection point was set to 100 Won/kg, which was estimated from the purchase cost of one standard plastic garbage bag. Also, the unit transportation cost among collection points was set to 200 Won/km, which was estimated from the vehicle fuel cost.

The first test is on the amount of improvement that the two TS algorithms give over the conventional method, where the conventional method is not a systematic solution algorithm, but an experience based algorithm. As explained earlier, the number, locations and capacities of collection points are determined by the responsible officer's experience or intuition and fixed over time, and the refuses at demand points are allocated to the closest opened collection points. Also, the vehicle routes, which are fixed and remained the same, are determined according to the workers' experience. See Figure 2 for the visit sequence over the 47 collection points. Recall that one 2.5 ton vehicle is assigned to each of the three areas, and hence each vehicle must return to the depot whenever full while travelling from the collection points.

In the test, two cases were considered. The first one is the case that the number of identical vehicles (2.5 ton) was fixed to three. In this case, each vehicle must return to the depot whenever full while the vehicle travels from the collection points according to the predetermined routes. The second one is the case that the number of identical vehicles was not fixed, where one vehicle is assigned to each route. In this case, three vehicle types, i.e. 2.5, 4.5 and 5.8 ton vehicles, are considered. As explained earlier, the homogeneous CVRP is considered in this study. Also, the capacity levels of collection points were set according to the available bucket sizes, i.e. 1 and 2.5 ton buckets for 2.5 ton vehicles, 1, 2.5 and 4.5 ton buckets for 4.5 ton vehicles and 1, 2.5, 4.5 and 5.8 ton buckets for 5.8 ton vehicles. Note that the bucket sizes were obtained from the real data. Also, to find the appropriate parameter values of the two tabu algorithms, a preliminary experiment was done on some test instances. More specifically, several values of the tabu list size and the termination condition were tested, and they were set to 200 and 5000, respectively.

The test results are summarized in Table 2(a) and (b). Table 2(a) shows the test results for the case that the number of identical 2.5 ton vehicles was fixed to three. As can be seen in the table, the two algorithms give much better solutions over the conventional method with respect to the total cost, i.e. 47.7% and 49.4% for the H-TS and the I-TS algorithms, respectively. Also, there were significant amount of improvement in both the number of collection points and the travel distance. The results show that the municipal refuse collection system considered in this case study has much room for improvement. Table 2(b) shows the test results for the case that the number of identical vehicles was not fixed. As in the first case, the two algorithms outperform the conventional method significantly, i.e. up to 55.3% and 59.6% improvement in the total cost for the H-TS and the I-TS algorithms, respectively. This is because there is much reduction in the number of collection points and the vehicle travel distances. In fact, the number of opened collection points was reduced up to 57.5% and 63.8% and the vehicle travel distances were reduced up to 48.5% and 53.1% for the H-TS and the I-TS algorithms, respectively. However, the number of vehicles increased to 20, 14 and 12 for 2.5, 4.5 and 5.8 ton vehicles since one vehicle is assigned to each vehicle route. Finally, as in Kim and Lee (2014), the I-TS algorithm (integrated approach) was better than the H-TS algorithm (hierarchical approach).

Table 2 Test results: improvement over the conventional method.

(a) Case that the number of vehicles is fixed
		Methods
		2.5 ton vehicles
Parameters	Conventional method		H-TS			I-TS
Objective value (Korean Won)	330,591,300		173,046,510 (47.7)^a			167,254,500 (49.4)
Number of collection points	47		33 (29.8)			29 (38.3)
Vehicle travel distance (km)	75,621		72,718 (3.8)			67,218 (11.1)
Number of vehicles	3		3			3
(b) Case that the number of vehicles is not fixed
		Methods
		2.5 ton vehicles		4.5 ton vehicles		5.8 ton vehicles
Parameters	Conventional method	H-TS	I-TS	H-TS	I-TS	I-TS	I-TS
Objective value (Korean Won)	330,591,300	222,702,310 (32.6)^a	216,566,500 (34.5)	178,781,300 (45.9)	158,894,300 (51.9)	147,769,100 (55.3)	133,510,100 (59.6)
Number of collection points	47	33 (29.8)	29 (38.3)	23 (51.1)	19 (59.6)	20 (57.5)	17 (63.8)
Vehicle travel distance (km)	75,621	64,278 (15.0)	60,497 (20.0)	44,821 (40.7)	39,636 (47.6)	38,965 (48.5)	35,465 (53.1)
Number of vehicles	3	20	20	14	14	12	12

a The values in parentheses show the amount of improvement over the conventional method (%).

The second test is to compare the performances of the two types of tau search algorithms. For this purpose, we generated 300 instances randomly based on the case data, i.e. 10 instances for each of 30 combinations of three levels of the number of periods (10, 15 and 20) and 10 levels of the number of potential sites (10, 20, 30, 40, 50, 100, 200, 300, 400 and 500). The locations of potential sites were randomly generated within the case areas. The amount of refuse at each demand point in each period was generated from DU(28, 41). The unit land prices to calculate the fixed cost to open collection points were generated from DU(580,000, 1,000,000). Also, we considered one vehicle type, i.e. 5.8 ton vehicle whose fixed cost is set to 5,000,000 Won. Note that 5.8 ton vehicle represents the maximum vehicle capacity of the refuse collection system considered in this case study. Finally, the other cost values were set to the corresponding case data.

Since we could not obtain the optimal solutions, the two tau search algorithms were compared with relative performance ratios, where the relative performance ratio of algorithm a for an instance is defined as

where Z_a is the objective function value obtained from algorithm a and Z_best is the better one of the objective values obtained from the two algorithms. As in the first test, the tabu list size was set to 200 and the algorithm was terminated if no improvements have been made for 5000 consecutive iterations.

The test results are summarized in Table 3 that shows the average relative performance ratios and the average CPU seconds. As in the case result, the I-TS algorithm gave better solutions than the H-TS algorithm while requiring longer CPU seconds. This is the same result as in Kim and Lee (2014), which can be easily expected since the integrated type algorithm is designed to search larger solution space than the hierarchical type algorithm. Recall that the I-TS type algorithms solve the vehicle routing sub-problems for each alternative of network design and capacity planning sub-problem. Therefore, we can conclude that the integrated approach is more efficient for collection network design and operation.

Table 3 Test results: comparing the two TS algorithms.

Number of potential sites	Number of periods	H-TS	I-TS
10	10	0.0 ( < 1.0)^a	0.0 ( < 1.0)
	15	0.2 ( < 1.0)	0.0 ( < 1.0)
	20	0.0 ( < 1.0)	0.0 ( < 1.0)
20	10	1.5 ( < 1.0)	0.0 ( < 1.0)
	15	1.7 ( < 1.0)	0.0 (1.2)
	20	0.0 ( < 1.0)	0.0 (2.6)
30	10	1.0 ( < 1.0)	0.0 (1.7)
	15	1.9 (2.3)	0.0 (4.1)
	20	2.4 (3.6)	1.2 (4.9)
40	10	1.1 (3.2)	0.2 (4.8)
	15	0.0 (6.9)	0.6 (16.3)
	20	4.5 (9.9)	2.4 (27.7)
50	10	2.5 (8.6)	0.0 (18.2)
	15	3.5 (19.2)	0.0 (27.5)
	20	5.0 (38.5)	0.0 (58.6)
100	10	2.6 (28.7)	0.0 (44.4)
	15	3.8 (42.1)	0.0 (87.5)
	20	4.7 (65.3)	1.7 (155.6)
200	10	0.0 (95.8)	0.2 (223.8)
	15	0.3 (129.6)	0.3 (256.9)
	20	5.6 (190.0)	0.0 (437.2)
300	10	2.6 (211.5)	0.4 (515.5)
	15	3.5 (256.3)	1.2 (638.7)
	20	6.3 (303.8)	1.8 (665.3)
400	10	3.5 (369.9)	0.0 (712.3)
	15	7.1 (401.5)	0.0 (798.9)
	20	10.2 (465.1)	0.0 (812.0)
500	10	2.9 (478.6)	0.1 (820.1)
	15	4.2 (501.7)	0.0 (888.2)
	20	9.1 (612.9)	0.0 (928.8)
Average		3.1	0.3

a Average relative performance ratio (average CPU seconds in parentheses) out of 10 test instances.

5. Concluding remarks

In this paper, we reported a case study on collection network design, capacity planning and vehicle routing in a real-life refuse collection system. The problem has two types of decisions: (a) restricted dynamic network design and capacity planning that determines the static locations and capacities of collection points and the dynamic allocations of refuses at demand points to the opened collection points over a planning horizon and (b) vehicle routing that determines the number and routes of vehicles. To solve the problem, we adopted two types of TS algorithms, H-TS and I-TS, for the objective of minimizing the sum of fixed costs to open collection points and acquire vehicles as well as variable costs to transport refuses at demand points to the opened collection points and to travel from the opened collection points by vehicles. Computational experiments were done on the case data, and the results showed a significant amount of improvement over the conventional method. Also, as in the previous study, we showed that the integrated approach outperforms the hierarchical approach.

The managerial insights obtained from modelling and solving the case instances can be summarized as follows. First, we observed that the network design, capacity planning and vehicle routing in refuse collection systems affect the system performances significantly. In other words, much improvement could be obtained over the conventional method by applying an appropriate optimization technique. This implies that the current refuse collection systems have much room for improvement. Second, as in the previous study, the integrated approach gave additional improvement over the hierarchical approach, which shows the importance of integrating the network design, capacity planning and vehicle routing problems. Third, although there is an improvement in total cost, the number of vehicles increases due to the characteristics of the vehicle routing problem that determines the vehicle routes at the same time. Nevertheless, the actual number of vehicles can be decreased since the operation system can be designed in such a way that one vehicle may travel two or more routes sequentially. In this case, the time limitation must be additionally considered. Note that the conventional operation system assigns one vehicle to each area, which leads to the increases in working hours, physical and mental fatigues, rapid vehicle worn outs, etc.

This study can be extended in several directions. First, it is needed to enlarge the system scope, i.e. from the three areas to the entire region. To do this, more efforts are required to gather the data. Second, other types of vehicle routing problems, such as period vehicle routing, vehicle routing with pickup and delivery, and so on, can be considered. Finally, the integrated model can be used as a building block for designing and operating the entire reverse logistics networks.

Funding

This work was supported by Jungseok Logistics Foundation Grant. This is gratefully acknowledged.