A novel methodology for determining low-cost fine particulate matter street sweeping routes

Abstract

This paper addresses the problem of low-cost PM₁₀ (particulate matter with aerodynamic diameter <10 μm) street sweeping route. In order to do so, only a subset of the streets of the urban area to be swept is selected for sweeping, based on their PM₁₀ emission factor values. Subsequently, a low-cost route that visits each street in the set is computed. Unlike related problems of waste collection where streets must be visited once (Chinese or Rural Postman Problem, respectively), in this case, the sweeping vehicle route must visit each selected street exactly as many times as its number of street sides, since the vehicle can sweep only one street side at a time. Additionally, the route must comply with traffic flow and turn constraints. A novel transformation of the original arc routing problem into a node routing problem is proposed in this paper. This is accomplished by building a graph that represents the area to sweep in such a way that the problem can be solved by applying any known solution to the Traveling Salesman Problem (TSP). As a way of illustration, the proposed method was applied to the northeast area of the Municipality of Santiago (Chile). Results show that the proposed methodology achieved up to 37% savings in kilometers traveled by the sweeping vehicle when compared to the solution obtained by solving the TSP problem with Geographic Information Systems (GIS) - aware tools.

Implications

The exposure to PM₁₀ has been shown to be harmful to human health. Street sweeping is an effective mitigating measure used to reduce the amount of PM₁₀. This paper proposes a generic method to determine a low-cost PM₁₀ sweeping route. This problem has seldom been studied in the literature, with only two previous papers focusing on solving it under very specific circumstances, which makes them not applicable to generic scenarios. By providing a generic method that solves the problem under different scenarios, it is expected to facilitate the decision-making process of environmental and other public agencies regarding the implementation of sweeping routes.

Introduction

Particulate matter (PM) air pollution is a major world concern as it causes serious health and environmental problems in densely populated urban areas (Furusjö et al., 2007). The exposure of contaminants, particularly coarse mass of PM with an aerodynamic diameter of less than 10 μm (PM₁₀), has been shown to be harmful for pregnant women, elderly, and children (Kork, 2000, Whyatt et al., 2007). Over the years, studies have confirmed the correlation between high levels of PM₁₀ and the increase of daily total mortality, and chronic cardiovascular and respiratory diseases (Cifuentes et al., 2000; Ilabaca et al., 1999; Ostro et al., 1995; Pope and Dockery, 2006; Pope et al., 2002; Schwartz et al., 1996).

Traffic on paved and unpaved roads is one of the major sources of PM₁₀ concentrations in urban areas (Fitz and Bufalino, 2002; Furusjö et al., 2007; Kuhns et al., 2003; U.S. Environmental Protection Agency, 2006; Watson et al., 2000; Yuan et al., 2003). Particles deposited and accumulated on paved roads are due to direct vehicle emissions from exhaust, tire and brake wear, and emissions from resuspended road surface material into the atmosphere due to the turbulence generated by vehicular traffic.

Several studies have stated that street sweeping is an efficient mitigating strategy employed to reduce the amount of PM₁₀ concentrations cumulated on paved streets and on resuspension state (Amato et al., 2009; Amato et al., 2010; Chang et al., 2005; Hewitt, 1981; Kuhns et al., 2003; Yuan et al., 2003). For example, Lents et al. (Lents et al., 2006) concluded that a reduction of 44% in the amount of PM mass was obtained on swept streets of the city of Santiago. This result was obtained by applying an empirical methodology to compare PM₁₀ concentrations before and after the sweeping process.

Figure 1 shows a typical sweeping vehicle equipped with a water tank and sprayers used to decrease the accumulation of PM concentrations deposited on paved streets. Note that this vehicle cleans only one side of the street as it travels.

Figure 1. Example of a typical sweeping vehicle (2011).

The street sweeping routing problem consists of determining the route traveled by a sweeping vehicle such that all street sides of the selected streets are swept following street network topology and turn restrictions, and minimizing the global cost. The cost of the sweeping process can be given by different parameters such as the length of the route, the inverse of the amount of PM₁₀ to be swept, or a mixture of both.

The street sweeping routing problem can be thought as a variant of the arc routing problem. This problem determines the lowest cost route that visits all arcs in a network (Chinese Postman Problem [CPP]) or visits each arc of a subset of the arcs in a network (Rural Postman Problem) (Assad and Golden, 1995). Exact and approximate solutions obtained with heuristics exist for both of these problems (Assad and Golden, 1995; Eiselt et al., 1995a; b). However, the street sweeping routing problem differs, since different streets must be traveled a different number of times (at least twice): once per side of the street. In a street without a median (Figure 2a and b), the sweeping vehicle must travel this street twice, as shown by the arrows: once to sweep the left side of the street and once to sweep the right side of the street. Depending on the traffic flow (one-way or two-way streets), the sweeping vehicle must travel the street twice in the same direction or in opposite directions. In a street with a median, the vehicle must sweep the street four times, as shown in Figure 2c. This fact is the main difficulty in determining the routing in this system and the reason why known solutions to the Chinese or Rural Postman Problem cannot be directly applied.

Figure 2. Types of streets to be swept.

An initial approach in solving the routing problem of street sweepers was discussed by Bodin and Kursh in 1978 (Bodin and Kursh, 1978). A computer-assisted method produced feasible routes for multiple street sweepers in New York City and Washington D.C. The authors concluded that even though the generated routes for New York City reduced the number of vehicles needed, they were severely overlapped. Additionally, the proposed approach was designed for a roadway network that contained many one-way streets, limiting the application to a roadway network with both one- and two-way streets.

Eglese and Murdock (1991) solved the directed CPP with vehicle capacity and available time constraints while minimizing the deadhead distance. The main objective was to determine the shortest route of street sweeping vehicles in a rural area of England. In order to sweep both sides of unidirectional streets, the proposed solution approach assumed that sweepers may travel against the traffic flow without complying with network topology. In addition, a set of routes generated with the computer program were unacceptably long for certain street network configurations.

Perrier et al. (2007) presented a survey on the solution to the vehicle routing for snow ploughing operations. Because the blade may not be sufficiently wide to plough both sides of a street at once, the vehicle might require traveling every street as many times as the number of lanes (e.g., twice or four times). Hence, the routing of a snow ploughing vehicle exhibits the same characteristics of the street sweeping routing problem studied in this paper. Since most surveyed solutions in Perrier et al. (2007) do not consider traffic flow restrictions, the authors applied the undirected Chinese Postman Problem to a modified graph with as many arcs as number of times the vehicle must travel a street (Bureau of Management Consulting, 1975; Marks and Stricker, 1971). In the case of applying the directed Chinese Postman Problem solution, the authors assumed that each street side can be ploughed by a different vehicle, which relaxes the constraint of the same vehicle visiting each street more than once (Atkins et al., 1990; Moss, 1970). A third heuristic algorithm solves the problem of traversing each street exactly twice (i.e., once per direction) (Lemieux and Campagna, 1984). However, this solution does not take one-way streets into account, in which the ploughing vehicle should visit the street twice in the same direction. No exact solutions to the snow ploughing vehicle routing problem are surveyed and none of the heuristics described address exactly the problem here studied.

This paper addresses the problem of low-cost street sweeping routing by first selecting a set of high-priority (HP) streets to be swept, and second, determining a low-cost route to visit each street in that set. In order to do so, the streets with the highest PM₁₀ emission factors of the area under study are identified and require sweeping. Next, the original arc routing problem is transformed into a node routing problem by representing the street network topology by a directed graph G, where the nodes represent the street sides to be swept. Arcs connecting nodes in graph G correspond to the shortest routes between the street sides to be swept that do not contain HP streets. Note that the resulting graph G is not necessarily a complete graph, as it typically occurs with transformations of arc routing problems to the Traveling Salesman Problem (TSP) (Laporte, 1997). This happens because the routes containing streets to be swept cannot be directly inserted in the graph, as described in the next section. The routes connecting nodes in graph G are determined in a Geographic Information Systems (GIS) environment considering traffic flow and turn restrictions.

This transformation of the original arc routing problem into a node routing problem is the main contribution of this paper, which obtains an optimal or near-optimal solution to the original problem by applying any known solution for the asymmetric TSP problem. Known transformations of arc routing problems into node routing problems proposed to date are not applicable to this particular case. These include the transformation of Directed/Undirected/Mixed/Windy Chinese/Rural Postman Problems and the Stacker Crane Problem into a TSP (Laporte, 1997) as well as the conversion of Capacitated Arc Routing Problems into Capacitated Vehicle Routing Problems (Baldacci and Maniezz, 2006).

The performance of this proposal was evaluated in a given area of the city of Santiago with the aim of minimizing the number of kilometers traveled by the sweeping vehicle. The solution obtained was compared to two solutions obtained by TSP ArcGIS and TSP Google solvers, respectively. Performance comparison results in this study case showed that the method proposed in this paper achieved routes up to 37% shorter than those obtained by the alternative solutions.

Proposed Solution

The flowchart of the algorithm proposed to solve the street sweeping routing problem is shown in Figure 3. This figure presents three main steps: (a) determining the set of HP street segments that must be swept; (b) transforming the original arc routing problem into a node routing problem by building a graph G, where the street segments of the HP set and the routes connecting them are represented by nodes and arcs, respectively; and (c) solving the TSP problem in the graph G. A low-cost route for the sweeping vehicle is determined with steps b and c. The following subsections describe each step of the algorithm.

Figure 3. Flowchart of the main three steps of the proposed algorithm.

Determining the set of high-priority street segments

In order to determine the street segments to be sweep in a given urban area, the level of PM₁₀ for a dry paved street s is estimated by evaluating its emission factor, E_s , in grams per vehicle kilometer traveled (VKT) using eq 1 provided by the U.S. Environmental Protection Agency (U.S. EPA) (2006). This equation is presented in this paper because it is internationally accepted and commonly employed to compute the PM₁₀ emission factor (Comisión Nacional del Medio Ambiente, 2009; Yuan et al., 2003). Note that alternative equations may be used to accommodate other local data under study.

1

where K is a dimensionless factor that depends on the diameter of the particulate matter (equal to 4.6 for PM₁₀), sL _s is the silt density of street s in g/m², W_s is the mean weight of vehicles traveling through street s in tons, and C is the emission factor yielded from tire and brake wear, and exhaust pipes from vehicles. The mean weight W_s of vehicles using street s is calculated using eq 2.

2

where W_s ⁱ is the weight of vehicle type i traveling through street s and α _s ⁱ is the fraction of vehicles type i using street s. After computing the value of E_s for all the streets in an urban area, only those with E_s values greater than 1 g/VKT are selected as HP streets to be swept according to average E_s values reported in the literature for different street types (Fitz and Bufalino, 2002). Particularly, the U.S. EPA AP-42 document presents a range between 0.08 and 0.53 g/VKT assuming default values (Fitz and Bufalino, 2002). Thus, values higher than 1 g/VKT are above average indicating streets that require sweeping.

Building graph G

The street sweeping route must meet two constraints:

•	The sweeping vehicle must visit every HP street as many times as the number of street sides.
•	The sweeping vehicle must travel following traffic flow and turn restrictions.

Considering these two constraints in the final solution, the study area is represented by a graph G. The nodes of G represent the street segment sides to sweep. Thus, every simple street segment (i.e., without a road median) is represented by two nodes in G, as shown in Figure 4a. Street segment S must be swept twice: once to sweep the left side of the street segment (S_L) and once to sweep the right side of the street segment (S_R). Therefore, nodes S_L and S_R are added to graph G. Every street segment with a median is represented by four nodes in G, as shown Figure 4b. This figure indicates that a street segment divided by a median generates two simple street segments: street segment S (upper part of figure) and street segment T (lower part of figure). In this case, four sides of the street segments must be swept: The left and right side of street segment S (S_L and S_R, respectively), and the left and right side of street segment T (T_L and T_R, respectively). Hence, four nodes (S_L, S_R, T_L, and T_R) are added to graph G.

Figure 4. Generating the nodes of graph G: (a) simple street; (b) street with median.

In general, the arc between any nodes i and j in graph G corresponds to the lowest cost path between the end of the street segment represented by node i and the beginning of the street segment represented by node j. The cost of this arc can be determined according to the objective of the sweeping program. For example, if the cost of executing the sweeping program is given by the number of kilometers traveled by the sweeping vehicle, then the cost of each arc should be the length of the corresponding street. Instead, if the objective of the sweeping program is ensuring that HP streets are swept using a route that combines a balance between sweeping non-HP street segments that must be traveled to reach HP streets and traveling a short route, then the cost of the arc can be equal to the ratio between the distance of the street segment and its emission factor.

The lowest-cost path between the end of the street segment represented by node i and the beginning of the street segment represented by node j must meet the following constraints:

Figure 5. Flowchart with the description of the construction of graph G.

•

Traffic flow must be taken into account. Thus, the shortest path from i to j is not necessarily the same from j to i. As a result, the graph G is a directed graph.

•

If the lowest cost path contains certain number of HP street segments, then a direct arc between node i and j cannot be added to graph G. Instead, the lowest cost path must be broken into M + 1 sections, where M is the number of HP street segments in the shortest path from i to j. The break points of the lowest cost path are the HP street segments. By doing so, the sweeping of a vehicle through a HP street segment can be recorded by an algorithm that visits each node exactly once. Therefore, the original problem has been converted into the asymmetric version of the TSP, where the distance from node i to j is not necessarily the same as the distance from j to i. The flowchart describing the building of graph G is illustrated in Figure 5.

The left section of the upper part of Figure 6 presents an example of an urban area with four HP street segments: A, B, C, and D. The thin black arrows indicate the traffic flow direction of the streets. The right section of the upper part of the figure presents an example of the lowest cost routes from the end of street segment A to the beginning of all remaining HP street segments in the area of study. This route includes street A, as the vehicle has to traverse every street twice. Note that the shortest route from the end of street segment A to the beginning of street segment D includes street segment B. Thus, the route from A to D must be broken in two segments: a direct route from A to B and a direct route from B to D. This rupture is shown in the graph located in the lower part of Figure 6. There is a direct connection from left and right sides of the street segment A (denoted by A_L and A_R, respectively) to HP street segments B and C, respectively. Notice that the graph shown in the lower part of the figure is not complete. In order to facilitate visualization, only arcs departing from street segment A are shown. The final graph should include the arcs starting at every node.

Figure 6. Adding arcs in graph G to represent the lowest cost routes from the end of street segment A to the rest of the high-priority street segments in the area.

Solving the TSP problem in graph G

Once the graph G is built, the final route can be obtained by solving the asymmetric TSP (ATSP) or the TSP after transforming the asymmetric TSP into the TSP, as described in Jonker and Volgenant (1983). Generally, different solutions to the TSP can be classified as optimal, heuristics, and meta-heuristics. Optimal solutions for the symmetric TSP have been reported for instances of up to 85,900 nodes using Concorde (xx, xxxx), with a processing time of 136 years CPU executed in a cluster of 250 processors (Applegate et al., 2009). The heuristics proposed for the TSP may be classified as construction or improvement heuristics. Among construction heuristics, Nearest Neighbor, Greedy, Clarke-Wright, and Christofides present the best performance (Johnson and McGeoch, 1997). In terms of their distance to the Held-Karp lower bound, Christofides achieves solutions adding about 10% on average more than the lower bound in the examples studied by Johnson and McGeoch (1997), as opposed to 26% in the case of the Nearest Neighbor heuristic. However, Christofides exhibits the highest computational complexity, O (N ³), with N denoting the number of nodes to visit. Alternatively, Nearest Neighbor has a computational complexity of O(N ²). Among the improvement heuristics, 2-Opt and 3-Opt are highlighted because of its good performance. Johnson and McGeoch (1997) presented results that show solutions found by 3-Opt with starting tours generated by the Greedy algorithm are just 3% away from the Held-Karp lower bound, significantly improving the performance of construction heuristics. This improvement comes at expense of higher computational complexity. For the 2-Opt case, the authors report that some instances and starting tours might require O(2 ^N/2) moves before stopping (Johnson and McGeoch, 1997). Finally, several meta-heuristics such as ant colony, genetic algorithms, tabu search, and simulated annealing have been proposed to solve the TSP. However, according to Johnson and McGeoch (1997), none of them seem to outperform the results obtained by 3-Opt.

Öncan et al. (2009) present exact formulations of the ATSP. Hahsler and Hornik (2007) and Lodi and Punne (2010) list available TSP solvers. Among the TSP solvers, different variants exist depending on the specific constraints of the problem. For example, if the capacity of the sweeping vehicle is limited, then a solution to the Capacitated Vehicle Routing Problem must be used. If the sweeping must be carried out at specific periods, then one of the known solutions to the TSP with time windows may be employed to address this problem (Liong et al., 2008).

Case Study

The Municipality of Santiago has an area of 22.4 km² and 200,000 inhabitants, representing the 4.3% of the total population of the city of Santiago. This municipality concentrates major political, administrative, and financial activities of the city, thus, there is a population of 1.8 million daily commuters, and over 70% of these individuals travel in vehicles. PM₁₀ emissions originated from paved roads in this area may reach high levels values, especially during the winter months (Jorquera, 2002; Koutrakis et al., 2005). Therefore, the use of a sweeping program will be highly beneficial. In this case study, it is assumed that the cost of the sweeping system is determined by the amount of distance that a sweeping vehicle travels in kilometers.

As a way of illustration, the methodology proposed in this paper was applied to the northeast area of the Municipality of Santiago. Figure 7 shows this study area, which contains 9 one-way and 2 two-way paved streets. Note that each street consists of several segments. Street segments were classified in types I, II, and III depending on the average vehicle weight and traffic flow (a more detailed characterization of the streets is described below). This is a small instance of the sweeping routing problem; however, this real-world example was selected due to the availability of field measurements regarding the average vehicle weight and traffic flow of the streets.

Figure 7. Area of study within the Municipality of Santiago.

In the present study, the sweeper vehicle follows street network topology and turn restrictions. Therefore, no traffic regulations are violated. In addition, the simplest form of the TSP problem is considered, in order to facilitate the illustration of the proposed methodology. Two simplifying assumptions are made. First, the shift work period between 11 p.m. and 6 a.m. is suffice for sweeping the entire study zone and parking regulations do not restrain the vehicle from sweeping certain streets at certain times. Second, the vehicle capacity is sufficient to sweep all streets in the study area without needing to empty at the depot.

Implementation of the proposed solution

In the following subsections, each of the three main steps of the proposed algorithm is described for this case study.

Determining the HP set

Equation 1, which is widely employed in Chile (Comisión Nacional del Medio Ambiente, 2009), was applied to evaluate the emission factor of street segments in the zone shown in Figure 7. Type I segments (represented by thick solid arrows in Figure 7) belong to two-lane streets with average traffic volume greater than 500 vehicals (veh)/day and less than 5000 veh/day, whereas type II segments (depicted by solid arrows in Figure 7) are two-lane streets with traffic volumes between 5000 veh/day and 10,000 veh/day. Type III segments (shown by dashed arrows) are dead-end streets, where only few vehicles travel and, hence, near zero PM₁₀ concentration values are emitted. The average weight on type I streets was calculated considering that approximately 60%, 10%, and 30% of the traffic are 2.7-ton small vehicles, 3.85-ton medium vehicles, and 20.8-ton heavy vehicles, respectively (xx, 2008). The mean weight of small, light vehicles that travel through streets type II is 2.7 ton (xx, 2008). Values of 4.6 g/VKT and 0.1317 g/VKT for K and C factors were employed for PM₁₀ (U.S. Environmental Protection Agency, 2006). The amount of silt loading (sL) in g/m² was obtained from a study performed by DICTUC (2006) given the traffic flow F for the area of study. Table 1 presents the emission factor computed for street types I and II in the area of study. This table shows that type I street segments has an emission factor E_s greater than the threshold of 1 g/VKT, and that these streets have a significantly higher emission factor than type II streets. Therefore, type I and II segments are classified as high- and non-high-priority segments, respectively. The set of HP street segments in this study consists of 17 type I street segments, as shown in Figure 7.

Table 1. Particulate emission factor for street blocks in the area of study

Block Type	Ws (ton)	K (g/VKT)	C (g/VKT)	F (veh/day)	sL s (g/m^2)	Es (g/VKT)
I	8.2	4.6	0.1317	>500 and ≤5000	0.31	6.11
II	2.7	4.6	0.1317	>5000 and ≤10,000	0.15	0.60

Building the graph G

The resulting graph G contains 34 nodes with 2 nodes for each HP street segment. Environmental Systems Research Institute (ESRI) ArcGIS 9.2 and its extension Network Analyst were used to determine shortest routes between every pair of nodes in graph G with the execution of Dijkstra algorithm. In this way, network topology and turn restrictions were taken into account. From the total number of 1122 routes, 906 routes had to be broken in segments, as they contained one or more HP segments. Thus, the corresponding pairs of nodes in the graph G were not directly connected. The remaining 216 routes between pairs of HP streets did not contain other HP street segments. These did not require to be broken in segments and were represented by only one arc in graph G.

Solving the TSP problem

In this example, the low-cost route in terms of distance traveled was obtained by using the nearest neighbor heuristic algorithm with an asymptotic complexity equal to O(N ²), where N is the number of nodes in the graph. This heuristic is computationally simple, easily applicable to larger instances of the problem, and has one with the best performance (Hashler and Hornik, 2007; Johnson and McGeoch, 1997). Table 2 shows its pseudo-code.

Table 2. Pseudo-code of the nearest neighbor heuristic

Step	Description
1	randomly selected from the set of nodes in graph G → start node
2	start node → current node
3	route=route ∪ current node
4	nearest (current node) → next node
5	If next node = φ, end. Else, next node → current node
6	Go to step 3

The heuristic performs as follows. First (step 1), a node is selected randomly to start the sweeping route. Consequently, the route is constructed by selecting the nearest node as the next node to visit (steps 2–5). The function nearest (A) returns the identification of the nearest node to A, which has not yet been included in the route. If this function does not return the identification of a node (i.e., the last node visited does not contain an arc to an unvisited node), then the algorithm ends (left part of step 5). In order to improve the performance of the heuristic, the procedure described in Table 2 is repeated N times, once for each possible start node. The route with the lowest cost is selected as the final solution.

Depending of the topology of graph G, it may occur that after executing the nearest neighbor heuristic, some nodes are left unvisited. In that case, an insertion heuristic is executed to include such nodes in the final sweeping route. Table 3 shows the pseudo-code of this heuristic.

Table 3. Pseudo-code of the insertion heuristic

Step	Description
1	Number of nodes belonging to the route from 1 (start node) to M (M: number of nodes in the sweeping route)
2	Select an unconnected node. Denote it by u.
3	Evaluate the cost of sweeping route ri = {0, 1, 2,..., i, u, i+1,..., M} ∀ i = 1,..., M
4	Select the sweeping route ri with the lowest cost, ∀ i = 1,..., M, as the new sweeping route
5	M = M+1
6	If M = N, end the algorithm. Else, go to step 1.

The insertion heuristic evaluates the cost of every possible position of the unconnected node in the sweeping route. The position with the lowest cost is selected. Note that to evaluate the cost of a new sweeping route (step 3), the cost of the arc from node i to I + 1 in the route must be subtracted and the cost of arcs I → u and u → i must be added to the cost of the sweeping route. Once the lowest cost route has been identified, the sweeping route is updated (by adding the node u and increasing the length of the route by one, step 5). The heuristic terminates when there are no more unconnected nodes.

Results

The sweeping route obtained from applying the heuristics described above is illustrated in Figure 8. The route is 7.5 km long. Each street segment has an identification number (e.g., 40,046) given by the GIS software. The solid lines represent the HP segments. The dashed lines represent segments that do not require sweeping, but that are used to access HP segments. The black and gray lines represent the first and second times that the sweeping vehicle travels through a street segments, respectively.

Figure 8. Final sweeping route obtained after applying the proposed methodology.

To evaluate the quality of the solution obtained with the method proposed in this paper, a comparative study was carried out. To do so, low-cost sweeping routes were also obtained using two GIS-aware TSP solvers: TSP solver of ArcGIS 9.2 and TSP solver of Google Maps ("http://gebweb.net/optimap/"). Both TSP solvers yield a tour or a route that visits each location exactly once while minimizing the total travel distance. However, each TSP solver employs different meta-heuristic algorithms. The TSP solver of ArcGIS 9.2 uses a tabu-search-based algorithm to find the best sequence of visiting the stops, whereas the TSP solver of Google Maps applies a combination of Greedy heuristic and Ant Colony Optimization, or Ant Colony Optimization and k2-opting heuristic algorithms, depending on the number of nodes to visit. None of these solvers allow the route to pass the same segment twice. To achieve this, different solution strategies were applied to the TSP solvers. These are explained as follows.

ArcGIS TPS solver

Route 1 was obtained by applying the TSP solver of ArcGIS 9.2. The HP segments were entered randomly in the application. The TSP solver yielded a low-cost route that traveled once through all the HP street segments following street network topology and turn restrictions, as shown in Figure 9a. To sweep both sides of the streets, the TSP problem was solved once again by selecting the end of the previous route as the start point. This time, the TSP solver was forced to traverse two-way streets in the opposite direction of the first route, in order to comply with traffic flow constraints (See Figure 9b). The final solution is obtained by merging both routes obtaining a total distance of 9.5 km. Additionally, a low-cost tour (denoted as Route 2) was also computed using this TSP solver. This tour traveled each HP street segment once. By traveling this tour twice (i.e., one per street side), a lower bound to the problem is obtained. The resulting route, shown in Figure 10a, visits each HP segments once and is 4.4 km long. Hence, the sweeping vehicle must travel a total distance of 8.8 km to visit each HP segments twice if this tour were to be used. Notice that this tour is presented just as a lower bound, as flow traffic constraints might not be followed in two-way streets.

Figure 9. Schematic of Route 1 obtained with the ArcGIS TSP solver: (a) first time sweeping route; (b) second time and return sweeping route.

Figure 10. Schematic of resulting routes: (a) Route 2 with ArcGIS TSP solver; (b) Route 3 with Google Maps TSP solver.

Google TSP solver

This TSP solver does not offer the functionality employed to calculate Route 1. That is, it is not possible to force the TSP solver to traverse two-way streets in the opposite direction of the first route. Thus, only the lower bound could be obtained. In this case, using the Web platform provided by Google Maps, the segments to visit were entered randomly. The resulting lower bound route (denoted as Route 3) is 11.8 km long, as shown in Figure 10b.

Table 4 summarizes the routes obtained by the method proposed in this paper (Route 0 in the table), and the TSP solvers of ArcGIS 9.2 and Google Maps; the distance that the sweeping vehicle must travel in each case, and the percentage of savings in kilometers obtained with the proposed method with respect to each of the remaining routes. Notice that Route 0 is 21%, 14%, and 37% shorter than solutions shown in Routes 1, 2, and 3, respectively.

Table 4. Summary of sweeping routes obtained with different solution methods

	Sweeping Route
	Route 0	Route 1	Route 2	Route 3
Route calculation method	Proposed method	TSP solver ArcGIS	TSP solver ArcGIS	TSP solver Google
Distance traveled by	7.5	9.5	8.8	11.8
sweeping vehicle (km)
Saving of Route 0	—	21%	14%	37%

Conclusions

The methodology proposed in this paper presents a novel transformation of the original arc routing problem into a node routing problem, in order to obtain an optimal or near-optimal solution to the original problem by applying any known solution for the asymmetric TSP problem. This methodology was applied to the northeast area of the Municipality of Santiago, Chile. The resulting route was compared with routes computed with two different GIS TSP solvers provided by Google Map and ArcGIS 9.2. A route was obtained using TSP solver of ArcGIS 9.2 that traverses each HP segment once, and then travels a second time in the opposite direction starting from the end point of the first route. In addition, a lower bound route was obtained for both TSP solvers, where the sweeping vehicle follows the resulting route twice. The comparison results indicate that the proposed methodology reduces up to 37% of the total distance traveled. This emphasizes the importance of considering the constraint of visiting each segment at least twice (i.e., once per side of the street) in the design of the solution method. It is expected that this methodology will help environmental agencies to plan the routing of sweeping vehicles in an efficient way.

Acknowledgments

Financial support from Anillo Project ACT-88 (Conicyt-Chile), USM Project 23.11.40, and Chilean National Fund for Scientific and Technological Development (FONDECYT 1070386) is acknowledged. Anonymous revision of this paper is also gratefully thanked.