Balanced Clustering Algorithms for Vehicle Routing

Balanced Clustering Algorithms for Improving Shapes on Vehicle Routing Problems

Byung-In Kim, Ph.D., Seongbae Kim, Ph.D., and Surya Sahoo, Ph.D., P.E.

Institute of Information Technology, Inc.

2204 Timberloch Place, Suite 225,

The Woodlands, TX 77380, USA

Abstract

While minimizing the number of vehicles and total travel time is the major objective of vehicle routing problems in the literature, visual attractiveness of a solution is an important criterion in many practical applications. It depends on how the stops are grouped into routes and the degree to which the routes overlap with each other. This paper examines a method by which the visual attractiveness can be measured quantitatively and be improved. A two-phase algorithm is developed and implemented, where the first phase generates the initial solution and the second improve it. For the first phase, a hybrid method of balanced clustering and an insertion algorithm is applied to enhance the visual attractiveness. For the second phase, Meta heuristic algorithms are used. It is the first phase that the visual attractiveness is mainly handled and thus is our main focus in this paper. We present a variant of k-means algorithm, a stable marriage based algorithm, and a shape improvement algorithm. Computational results show the effectiveness of the proposed approach. The algorithms are implemented in Institue of Information Technology, Inc. (IIT)’s commercial routing software, eRouteEngineTM, eRouteLogisticsTM, and MapLogisticsTM. IIT’s eRouteEngineTM has been successfully implemented in Waste Management, Inc.’s enterprise internet routing system, WasteRouteTM. Waste Management, Inc. anticipates $180 million in annual savings using WasteRouteTM.

Keywords

balanced clustering, vehicle routing problem, visual attractiveness, p-median problem, waste route

1. Introduction

Vehicle Routing Problems (VRP) refers to the problems of delivery or collection of goods between depots and customers. Toth and Vigo [10] classifies the variants of VRP as Capacitated VRP (CVRP), VRP with Time Windows (VRPTW), VRP with Backhauls (VRPB) and VRP with Pickup and Delivery (VRPPD). Typical applications of the VRP include package pickup and delivery, solid waste collection, technician dispatching, bank deliveries, school bus routing, and security patrol services. Excellent editorial works on VRP are in [1] and [10].

While minimizing the number of vehicles and total travel time is the major objective of VRP in the literature, here we focus on the visual attractiveness of a solution since it is an important criterion in many practical applications. The authors of this paper have been involved in the route optimization project for Waste Management, Inc., the largest waste collection company in the North America having 26,000 vehicles, and realized the importance of the visual attractiveness [7, 8]. The terminology “visual attractiveness” is borrowed from Poot et al. [6] and it depends on how the stops are grouped into a route. A solution in which many routes cross over each other is less visually attractive than one in which there are no overlapping routes. For measuring the visual attractiveness quantitatively, a metric is devised and presented in this research.

A two-phase algorithm is developed and implemented, where the first phase generates the initial solution and the second improves it. For the first initial route building phase, a hybrid method of balanced clustering and an insertion algorithm is applied to enhance the visual attractiveness. The second phase of the algorithm is for improving the initial solution by applying meta heuristic algorithms. In the first phase, stops are initially (roughly) routed based on their locations and time window constraints. At this stage, the routes are balanced in terms of the workload such that a single vehicle can serve each route. Then, each route is improved by a VRP algorithm or a VRPTW algorithm, depending on whether the stops in the route have time window constraints. The individual solutions for the routes are combined into a total route solution. After a feasible initial solution is obtained, the second phase of improvement scheme is applied for better solution. In this paper, our focus is on the balanced clustering algorithms and the shape improvement scheme which are important components for the first initial route building phase.

This paper is organized as follows. After we briefly discuss visual attractiveness in section 2, we present the two balanced cluster construction algorithms and one improvement algorithm in section 3. Section 4 shows the experimental results and section 5 provides our concluding remarks.

2. Visual Attractiveness

As mentioned in the previous section, the authors have been involved in the route optimization project for Waste Management, Inc. (WMI). The residential and commercial waste collection problem is a complicated VRPTW with additional constraints. These additional constraints include vehicle capacity, multiple landfill operations and drivers’ lunch breaks in addition to the standard VRPTW. In this problem, each stop has a time window, i.e., earliest and latest allowable service starting time, in addition to its pick-up amount or demand. Each vehicle has its capacity and time window, i.e., the vehicle starting time and the time at which it is due to return to the depot. Vehicles start from the depot, pick up materials from the stops until they are full, unload them at the one of unloading locations, repeat pick up and unloading, and finally return to the depot. The materials from a stop can be delivered to one of the landfill locations. The vehicle drivers are assumed to take a one-hour lunch break between 11 a.m. and 1 p.m.

In order to solve the routing problems of WMI, we extended the well-known Solomon’s insertion algorithm [9] considering multiple landfill trips, lunch breaks, and other constraints [4]. Figure 1-a shows a routing solution instance of the original extended insertion algorithm without considering the visual attractiveness. Although this solution approach could reduce the number of vehicles from the current practice, it is not practical to have routes having lots of overlapping in real world application. To handle this problem, we developed the two-phase approach in which visual attractiveness is handled by a hybrid method of balanced clustering algorithm and improvement scheme in the first phase of the algorithm. Figure 1-b shows a solution instance of our two-phase algorithm.

Figure 1. Solution results for a problem set

Even though the visual attractiveness of the solutions can be easily compared by the figures (figure 1-a vs. figure 1-b), a shape metric is devised as equation (1) in order to quantitatively measure it. Stopc is the stop that is closest to the centroid of each Routej. Note that the Dist(Stopk, Stopc) can be one of any distance metrics: street distance on a Geographic Information System, Euclidean distance, or Manhattan distance. Street distance is used in our application. A solution with smaller shape metric is better than a solution with larger shape metric in terms of visual attractiveness. While the solution of figure 1-a results in a 3,296,504 feet shape metric, figure 1-b computes to only 1,203,289 feet. Note that the problem set of figure 1 has 1,599 stops.

There are several business rules to enforce while building routes. Each vehicle can visit a maximum number of stops and can treat a maximum volume and weight. These constraints form the capacity of the vehicle. Routing time is also considered as another capacity constraint. In order to minimize the number of routes, the routes must be balanced, in terms of routing time and other criteria. At the same time, the geometric locations of stops should be considered to get visually attractive clusters. To cope with these requirements, three balanced clustering algorithms are developed and they are discussed in the next section.

3. Balanced Clustering Algorithms

In this section, two balanced cluster construction algorithms and one improvement algorithm are presented.

3-1. K-means Variant Balanced Clustering Algorithm

The k-means variant clustering algorithm works as follows. As in the k-means algorithm, an initial centroid seed stop for each route (cluster) is selected randomly as the first step and the remaining stops are assigned to their nearest route. Then, a new centroid is calculated for each route. The stops are clustered by considering the distances between the stops and the centroids, in order words; a stop is assigned to the route whose centroid is the closest to the stop. When a stop is assigned to a route, the capacity of the route is considered. The capacity of the route is defined by the maximum number of stops that the vehicle is allowed to visit, the volume or weight that the vehicle is allowed to handle, and the allowable routing time. Routing time for each route is estimated each time a stop is added in the route by using a fast TSP heuristic algorithm. When a route whose centroid is the nearest to the stop being processed has already reached its capacity, the stop is assigned to the next closest route whose capacity is not full.

One other factor that can be included in assigning a stop to a route is the time window for the stop. When considering whether to add a stop to a route, if the stop’s time window conflicts with other stops already assigned to the route, then the stop should be assigned to a different route. For example, if stop A has time window [10:30am, 10:40am] and 5-minute service time, stop B has time window [10:50am, 11:20am] and 5-minute service time, and the travel time between the two is 20 minutes, the two stops cannot be assigned to the same route because the two cannot be served within their time windows using the same vehicle.

3-2. Stable Marriage Based Balanced Clustering Algorithm

The stable marriage based balancing algorithm is motivated by the polygamous stable marriage (poly-stable) algorithm of [2]. Step 0 of the algorithm is an initialization step in which centroids for routes are generated using a simplified version of the k-means variant balanced clustering algorithm, in which only the number of stops is considered as the route’s capacity constraint.

In step 1, each route proposes to its closest stops that have not been assigned to the route with consideration of all capacity constraints. In step 2, each of the stops that received one or more proposals accepts the best proposal by determining which proposal comes from the closest route. If a stop is already assigned to a route, it will accept a proposal from a closer route if it has any. Then, any rejected stops are removed from their current routes in step 3. With the updated stop-route assignment information, the centroids of the routes are updated in step 4. If all the stops are assigned, the algorithm stops. Otherwise, the algorithm attempts to insert unassigned stops to their nearest route. At step 6, if the capacity of a stop’s nearest route is full the stop cannot be assigned to the route. In step 8, the algorithm attempts to move stops from a route that would require more capacity to include nearby stops, to neighborhood routes whose capacity is not full in order to make room for the closer stops. Steps 1 through 8 are iterated until either: 1) there is no change in stop-route relationship, or 2) all the stops are assigned, or 3) the maximum iteration number is reached. In step 10, if there are unassigned stops remaining, the algorithm tries to insert those stops to their nearest possible route, which is not necessarily the nearest route. If the nearest route is full, the next nearest route would be checked and so on. Steps 6, 7, 8 and 10 is analogous to a matchmaker’s role.

Step 0. Generate centroids for routes using a simplified k-means variant balanced clustering algorithm.

Obtain Max_Iteration from the user.

Set iteration counter N = 1.

Set the status of all stops as unassigned.

Step 1. Proposal: Each of the routes proposes to the stops nearest to them, which are not yet included in the current route, up to its capacity.

Step 2.Disposal: Each of the proposed stops accepts the best proposal.

Step 3.Removal: Remove the rejected stops from the routes.

Step 4.Update the centroids of the routes.

Step 5.If there are unassigned stops, go to step 6.

Else, go to step 11.

Step 6.Add unassigned stops to their closest route if possible.

Step 7. If there are unassigned stops, go to step 8.

Else, go to step 11.

Step 8.Move assigned stops from routes requiring more capacity to handle nearby stops to neighborhood routes if possible.

Step 9.If there is no change in the stop–route relationship in steps 1 through 8 or if N = Max_Iteration, go to step 11.

Else, update N = N +1. Go to step 1.

Step 10.If there are unassigned strops, add unassigned stops to their possible nearest route.

If a stop cannot be assigned to any route, it is infeasible, go to step 11.

Step 11.Stop.

3-3. An Improvement Algorithm

Since the previous algorithms are heuristic, there are ways to improve the solution. In this subsection we discuss a simple move improvement algorithm. The basic idea of the improvement is very simple: if a stop’s current route is not the same as the stop’s nearest route, move the stop to the nearest route when its move does not violate the routes’ capacity constraints and when its move improves the overall route quality. In addition to the shape metric that was presented in section 2, another measure ‘num_in_hulls’ is devised and the weighted sum w1*shape metric + w2*num_in_hulls is used to measure the routing quality. Each route forms a convex hull as presented in figure 2. The measure num_in_hulls counts the number of stops that belong to more than one convex hull of routes. While num_in_hulls of figure 2-a is 2, num_in_hulls of figure 2-b is 0. Obviously, figure 2-b route is better than figure 2-a in terms of visual attractiveness.

Figure 2. Convex hulls and measure num_in_hulls

4. Experimental Results

In order to evaluate the algorithms presented in the previous section, we use the capacitated clustering problem (CCP) or capacitated p-median problem data set of Osman and Christofides [5], which is downloadable from OR-Library, [3]. Osman and Christofides [5] defined CCP as “the problem in which a given set of weighted objects is to be partitioned into clusters so that the total weight of objects in each cluster is less than a given value (cluster ‘capacity’).” The objective of CCP is to minimize the total scatter of objects from the centroid of the cluster to which they have been allocated. Euclidean distances are used for exact comparison, for Osman and Chistofides used Euclidean distance in their paper. Although our clustering problem is not exactly the same as the p-median problem, the problem set can be used for benchmarking because it has known solution values and the two problems are similar. Table 1 summarizes the results.

Data sets 1 through 10 in table 1 have 50 stops and require 5 clusters while data sets of 11 through 20 have 100 stops and require 10 clusters. The second column ‘OC-best’ shows the best result value of [5]. The third column headed ‘k-means’ shows the result of the k-means variant balanced clustering algorithm and ‘(i) k-means’ column presents the result of the k-means variant with the improvement algorithm. The next two columns show the results for the stable marriage based algorithm and the one with the improvement. It is interesting that there is no improvement in the k-means variant. Most of the cases, the k-means variant algorithm successfully assigns stops to their nearest clusters so that there is no need to move stops between clusters to improve the cluster quality. Note that this statement is for only our improvement scheme and we are not claiming that the results are optimal. In the actual problems of WMI, however, there is much improvement in many cases like as figure 3. Square and circle shapes represent different routes in figure 3. While two routes overlap in figure 3-(a), the routes are clearly separated in figure 3-(b). The k-means variant algorithm generates better routes for 7 problems and the stable marriage based algorithm improves the clustering quality for 6 problems of the data set compared with the OC-best.

Table 1. Results for p-median problem sets

Figure 3. Visual attractiveness improvement

5. Conclusions

This paper presents balanced clustering algorithms for vehicle routing problems. Computational experiments with p-median problem sets show the effectiveness of the proposed algorithms. The algorithms have been implemented in C language and the k-menas variant balanced clustering algorithm with the improvement scheme have been used in Institue of Information Technology, Inc. (IIT)’s commercial routing software, eRouteEngineTM, eRouteLogisticsTM, and MapLogisticsTM. IIT’s eRouteEngineTM has been successfully implemented in Waste Management, Inc.’s enterprise internet routing system, WasteRouteTM. Waste Management, Inc. anticipates $180 million in annual savings using WasteRouteTM[11].

References

1. Ball, M. O., Magnanti, T. L., Monma, C. L. and Nemhauser, G. L., (eds,), 1995, Handbooks in Operations Research and Management Science Volume 8: Network Routing, Elsevier Science B.