An Integrated Systems Approach to the Development of Winter Maintenance/ Management Systems

Final Report

November 2006

Principal Investigator
James S. Noble
Associate Professor, Department of Industrial and Manufacturing Systems Engineering
University of Missouri–Columbia

Co-Principal Investigators
Wooseung Jang
Associate Professor, Department of Industrial and Manufacturing Systems Engineering
University of Missouri–Columbia

Cerry M. Klein
Professor, Department of Industrial and Manufacturing Systems Engineering
University of Missouri–Columbia

Charles J. Nemmers
Director, Transportation Infrastructure Center
University of Missouri–Columbia

Research Assistants
Thomas Hutsel, Ya Zhang, and Shih-Chun Ho

Authors
James S. Noble, Wooseung Jang, Cerry M. Klein, and Charles J. Nemmers

Preparation of this report was financed in part
through funds provided by the U.S. Department of Transportation
through the Midwest Transportation Consortium, Project 2005-03.

A report from
Midwest Transportation Consortium
2711 South Loop Drive, Suite 4700
Ames, IA 50010-8664
Phone: 515-294-8103
Fax: 515-294-0467
www.ctre.iastate.edu/mtc

Table of Contents

ACKNOWLEDGEMENTS

EXECUTIVE SUMMARY

Chapter 1: Introduction

1.1       Overview of Winter Road Maintenance Operations

1.2       Optimization-Based Approach to Aid Decision Making

1.3       Opportunity for an Integrated Solution Methodology

1.4       Framework for Integrating Winter Road Maintenance Problems

1.5       Summary of the Research Objective

Chapter 2: Literature Review

2.1       Overview of Relevant Literature

2.2       Depot Location and Sector Design

2.3       Depot Location, Sector Design, and Fleet Sizing

2.4       Arc Routing Models for Directed Transportation Networks

2.5       Depot Location and Routing

2.6       Summary of Relevant Literature

Chapter 3:  Problem Formulation and Solution Methodology

3.1       Problem Formulation

3.2       Overview of the Methodology

3.3       Network Initialization Phase

3.4       Initial Solution Phase

3.4.1    Overview of Initial Solution Phase

3.4.2    Stage 1: Initial Incomplete Route Development

3.4.3    Stage 2: Integrated Depot Location, Sector Design, and Route Design

3.5       Solution Improvement Phase

3.5.1    Overview of Solution Improvement Phase

3.5.2    Stage 1: Improvement Heuristic

3.5.3    Stage 2: Manual Route Adjustment

3.5.4    Stage 3: Vehicle Scheduling and Fleet Configuration

Chapter 4: Case Study Description

4.1       Overview of Problem Characteristics

4.2       Winter Road Maintenance Operations

4.3       Service Level

4.4       Transportation Network

4.5       Depot Locations

4.6       Vehicle Routing

4.7       Fleet Configuration

4.8       Material Inventory

4.9       Operators

Chapter 5: Results and Discussion

5.1       Overview

5.2       Scenario 1: Existing Depots and Sectors

5.3.      Scenario 2: MoDOT Proposed Depots and Sectors

5.4       Scenario 3: Unconstrained Solution

5.4.1    Initial Depot Location Solution

5.4.2    Final Integrated Solution

5.5       Discussion of results

Chapter 6: Conclusions and Directions for Future Research

6.1       Summary and Conclusions

6.2       Directions for Future Research

REFERENCES

Appendix: Transportation Network

List of Figures

Figure 1. Influence diagram for winter road maintenance planning decisions

Figure 2. Problems and interactions by solution phase

Figure 3. Route first–cluster second method

Figure 4. Cluster first–route second method

Figure 5. Three-phase solution methodology

Figure 6. Influence diagram for stage 1 of the initial solution phase

Figure 7. Influence diagram for stage 2 of the initial solution phase

Figure 8. Linear program for stage 2 of the initial solution phase

Figure 9. Influence diagram for the solution improvement phase

Figure 10. Delete-and-insert algorithm example

Figure 11. Link exchange example

Figure 12. Manual route adjustment example

Figure 13. Influence diagram for stage 3 of the solution improvement phase

Figure 14. MoDOT Boone County transportation network with existing depots

Figure 15. Current solution for depot locations

Figure 16. MoDOT proposed depot locations

Figure 17. Potential depot location sites proposed for scenario 3

Figure 18. New solution: Weighted Deadhead vs. number of depots

Figure 19. Final integrated solution for the depot location problem

List of Tables

Table 1. Service hierarchy parameters

Table 2. Transportation subnetworks in Boone County, Missouri, by class

Table 3. Summary of final results for scenario 1

Table 4. Summary of final results for scenario 2

Table 5. New solution: Initial solution vs. number of depots

Table 6. Summary of final results for scenario 3

Table 7. Comparison between scenarios with respect to vehicle requirements

Table 8. Comparison between solutions with respect to weighted deadhead travel time

Acknowledgements

The research team would like to thank the Missouri Department of Transportation (MoDOT) for their assistance in data collection and for providing feedback throughout the project. We would especially like to recognize Bob Lannert and Eric Schroeter’s contributions to this project in their roles as technical advisors.

Executive Summary

Winter road maintenance operations require many complex strategic and operational planning decisions; the five primary problems include locating depots, designing sectors, routing service vehicles, scheduling vehicles, and configuring the vehicle fleet. The complexity involved in each of these decisions has resulted mainly in research that approaches each of the problems separately and sequentially, which can lead to isolated and suboptimal solutions. In addition to being integrated, a successful approach to these problems must consider the necessary practical aspects of each problem and include an explicable and easily executable solution methodology; otherwise it is unlikely to be implemented.

This research proposes a systematic, heuristic-based optimization approach which uses a route first methodology to integrate the winter road maintenance planning decisions for the five interrelated planning decisions. The planning decisions include determination of the following: 1) locations of a predetermined number of depots, 2) the corresponding sectors for each depot,
3) the routes needed to service each sector, 4) a vehicle schedule dictating the route(s) assigned to each vehicle and the order of service, and 5) the number of each type of vehicle needed at each depot. The approach presented in this work is illustrated through an example of public sector winter road maintenance planning for a rural transportation network.

The decision objective is to meet predefined guidelines for a high level of service while minimizing the required number of vehicles. The quality of the service is defined using performance measures for the frequency of service for each road segment within the network (maximum route duration constraints) and the efficiency with which the entire network receives service (total weighted deadhead travel time).

The application of the integrated solution methodology developed in this research to the winter maintenance planning problems of Boone County, Missouri, resulted in a very promising solution. The initial routing approach applied in this research reduced the number of vehicles required from 23 to 18, a fleet reduction of 20%. A subsequent unconstrained approach yielded a solution which provides for the same level of service with an additional 10% reduction in resources (one fewer depot and two fewer vehicles) and a slight reduction of weighted deadhead travel time.

The results from this real-world test problem support the relevance of a more integrated approach to winter road maintenance problems. The integrated approach allowed the initial decision on the number of depots to open to be based on insight gained from the interrelated problems of route design and sector design. The solution methodology is designed to aid winter road maintenance planners in making decisions regarding the interrelated problems studied in this research, based on the effect that these decisions have on the agency’s ability to achieve a desired level of service. The ability to solve the winter road maintenance planning problems in a more integrated manner should provide planners with the ability to make more informed, successful decisions.

While this research addresses the problems of winter maintenance, there is potential to use an integrated systems design/operation approach such as this to address other department of transportation (DOT) maintenance activities such as pavement striping, mowing, and herbicide application. The potential cost savings to the DOTs would accrue in many areas.

Chapter 1: Introduction

1.1       Overview of Winter Road Maintenance Operations

Winter road maintenance operations require many complex planning decisions; the main strategic and operational problems include defining a service-level policy, locating depots, designing sectors, routing service vehicles, configuring the vehicle fleet, and scheduling the vehicles. Since the definition of a service-level policy is a prerequisite for the rest of these planning decisions, it can be handled separately. However, the remaining activities are all interrelated, in that the effect each decision has on some or all of the other decisions impacts the agency’s ability to provide the desired level of service. Figure 1 presents an influence diagram for the complex interactions between the different winter road maintenance planning decisions.

Figure 1. Influence diagram for winter road maintenance planning decisions

The problem of locating depots entails determining the number of depots to open and where to open them. The depot location problem is often solved by choosing to open a preset number of depots from a set of candidate sites based on predefined strategic and operational objective(s). Since designing sectors involves the assignment of arcs requiring service to the depots responsible for servicing them, the sector design problem is often solved in conjunction with the depot location problem, both in practice and in existing research methods.

Winter road maintenance routing problems usually require that a set of routes is determined to optimize some performance criteria. These routes are serviced by vehicles starting and ending at their respective depots, such that all required road segments are serviced and all the operational constraints are satisfied. Routes are typically restricted either by duration or distance limitations. If a maximum duration—the time by which a route must receive further service—constrains the route length, then the number of routes and vehicles required are equivalent; this is often the case in existing research. If the maximum distance constraint dominates the duration constraint, then it may be possible for a vehicle to service multiple routes prior to reservicing any of them. If this is the case, then the vehicle scheduling problem must be solved as well.

The process of determining fleet configuration depends on whether or not the fleet is homogeneous. Many research studies assume the fleet to be homogenous, although heterogeneous fleets are often the norm in practice. If the fleet is assumed to be homogeneous, the problem is reduced to a fleet sizing problem with the objective of determining the number of vehicles required at each depot. Otherwise, the problem is more complex and consists of determining the number of each type of vehicle that should be based at each depot. The solution to the fleet configuration problem is dictated by the vehicle routes and schedule. 

In the context of public-sector winter road maintenance, the problems of locating depots, designing sectors, routing service vehicles, and configuring the vehicle fleet are especially complex. The inherent complexity of these winter road maintenance planning problems stems from 1) the difficult-to-quantify objective of maximizing the public’s perceptions of service, 2) the urgent nature of the service requirements, 3) the varying operating conditions and constraints, and 4) the budgetary limitations on resources.

1.2       Optimization-Based Approach to Aid Decision Making

Public agencies have been performing winter road maintenance planning and operational activities since as early as 1881 (Campbell and Langevin 2000). However, surveys by Gupta (1998) and Campbell and Langevin (2000) found that most agencies do not utilize any formal methods for locating depots or designing routes, respectively. Both works suggest that most agencies still rely in large part on assessments dictated by field experiences when making depot location and vehicle routing decisions. There is considerable research which highlights the benefits of an optimization-based approach and proposes such methods designed to aid planners in making winter road maintenance decisions.

One of the most compelling reasons for the use of a formal optimization-based methodology is that changes in personnel often result in insufficient experience to make effective decisions. Additionally, changes in service-level requirements, the road network, traffic levels, budgetary constraints, or other operational constraints may increase the complexity of planning decisions and cause discontinuities between past and present operational requirements. As a result, past experience would become less relevant in the decision-making process.

Another motivation for implementing an optimization-based approach is that current winter road maintenance planning decisions would not be not restricted by previous ones. Often, public service agencies make minor annual adjustments in an attempt to improve operations, but these adjustments cause new decisions to be restricted by the efficacy of those made previously. In contrast, an optimization-based approach attempts to make decisions based on strategic objectives, operational constraints, and the topology of the road network. Therefore, new solutions are not restricted by previous practices or existing operational beliefs. This is not to say that experience is not a significant aspect of winter road maintenance planning; it is crucial that any optimization-based approach utilizes the knowledge of experienced planners to determine the objectives, constraints, and other factors. This will increase the chances of a solution being both accepted and implemented. A successful optimization-based approach to winter road maintenance will most likely be one that aims to aid planners in the decision-making process rather than dictate final solutions.

Although the benefits of an optimization-based approach to winter road maintenance planning are undeniable, this formal approach is seldom implemented because the methods are unappealing to public service agencies or seem too difficult to implement. Campbell and Langevin (2000) cited the distrust of computer-based “black box” approaches and an inability to capture the necessary operational complexities as primary reasons that neither optimization approaches nor software have been utilized in practice. To increase the chance of acceptance and implementation, a solution methodology should be explainable to planning personnel, at least to the level that the objectives and operational constraints included are clear and the desired solution can easily be achieved.

1.3       Opportunity for an Integrated Solution Methodology

The multifaceted complexity of winter road maintenance planning indicates how difficult it is to make planning decisions based solely on experience. These complexities create an opportunity for improving the planning process through the implementation of a formal optimization-based methodology. Ironically, it is the same complexities which have hindered progress in developing successful optimization-based approaches to these problems. The lack of research which attempts to integrate the chief winter road maintenance planning decisions can not be attributed to a lack of recognition of the importance of doing so; rather, it is a result of the complexity of each of the problems involved. Reinert, Miller, and Dickerson (1985) pointed out that the four problems of depot location, sector design, vehicle routing, and vehicle scheduling would “ideally be solved simultaneously” but dismissed the idea saying that it is “not practically accomplished.” Traditionally, research approaches have followed this same belief, addressing the main winter road maintenance problems separately or, in a few cases, sequentially.

The problem of sector design is usually solved in conjunction with depot location. Vehicle routing problems usually assume a predetermined depot location and corresponding sector. As a result, there are few research works that solve the combined problems of sector design, depot location, and vehicle routing, and those that do combine them invariably approach the problems sequentially.

Most of the existing research on winter road maintenance vehicle routing and combined location routing problems assumes that the number of routes is equivalent to the number of vehicles. In practice, however, the capacity constraint may dominate the time duration constraint, making it possible for a vehicle to service multiple routes prior to reservicing any of them. If this is the case, then the vehicle scheduling problem must be solved as well.

Additionally, most winter road maintenance vehicle routing problems and combined location routing problems assume a homogeneous fleet. To make the problems more realistic, a heterogeneous fleet should be assumed, and the fleet configuration and vehicle scheduling problems should be addressed in addition to the sector assignment, depot location, and vehicle route design problems.

In addition to the compelling aforementioned reasons for a systematic optimization-based approach to winter road maintenance planning, an integrated approach provides further benefits. The primary argument for an integrated approach is to provide higher-quality solutions by avoiding the suboptimization or local optimization that may occur in approaches which treat each problem individually. Suboptimization can result from treating each problem individually in succession, since the solution to each problem is restricted by the solutions to any preceding problems.

Perhaps the reason most appealing to winter road maintenance planners is the ability to assess the impact that depot location decisions have on the agency’s ability to provide a high level of service. Currently, there is little research which allows planners to assess the impact of changes in the number and locations of depots on an agency’s ability to provide a high level of service.

1.4       Framework for Integrating Winter Road Maintenance Problems

The complexities involved in each of the individual problems of depot location, sector design, vehicle routing, vehicle scheduling, and fleet configuration necessitate careful analysis to determine the significant aspects of each problem in order to unify them in an integrated approach. Recognition of a common objective or objectives is the first step in integrating these winter road maintenance planning decisions. Stricker (1970) discussed differences in the objectives of private-sector and public-sector routing operations. The author concluded that, while the former is driven by economic objectives—usually costs—the latter is motivated by a desire to improve service and instead treats cost as a budgetary constraint. The desire to provide an acceptable level of service in order to increase public safety and welfare is also the objective of the winter road maintenance operations in Boone County, Missouri, and it is the primary objective of the integrated solution methodology presented in this research.

In addition to identifying a common objective, it is necessary to determine the scope of each problem involved. The determination of an acceptable scope for the integration of the winter road maintenance planning problems ensures the inclusion of a pragmatic level of complexity for each of the included problems. It could be argued that the location of a depot should be based on the annual road maintenance performed by the facility. However, considering additional year-round operations increases the complexity of the decision-making process considerably and may not improve the desired result, because winter road maintenance operations are the most significant. Gupta (1998) found that, although other activities are important, they will “not have an impact on the location of garage or outpost, because a single activity such as snow and ice control dominates the budget.” In states where snow and ice control does not significantly dominate the budget, it can still be argued that this operation is the most important. Gupta (1998) stated that “snow removal and ice control, if not executed properly, can be the single most deterrent [factor] to the quality of service of highways, thus creating the most hazard and loss to the economy.” For this reason, winter road maintenance operations require more urgent service than any other planned maintenance activities. Therefore, depots should be in a position to increase the speed of the winter road maintenance service response. While maintenance activities such as road resurfacing and pothole filling may be required often, the locations are unpredictable. In contrast, winter road maintenance occurs on the same defined road network every year. Therefore, the consistency of the operations is another reason that it dominates the location of the depots. Finally, the objective of winter road maintenance results in depot locations which provide better service to higher priority roads than lower priority roads, which lends itself well to other operations which also aim to focus service on the roads which provide the greatest benefit to the public. Therefore, the scope of the depot location problem for this research is limited to winter road maintenance activities—a scope which does not detract from the quality of the solution and makes a feasible solution more easily attainable.

Winter road maintenance operations by themselves still present a great level of complexity. The main operations involved in winter road maintenance include pre-treating or spreading, combined spreading and plowing operations, and pure plowing. Pre-treatment usually occurs prior to a storm event, and pure plowing—often called cleanup—occurs once a storm has subsided. Though all of the operations are important, the most significant to the depot location is the plowing-and-spreading operation that occurs during a winter storm event. The combined plowing and spreading operation is the bottleneck winter road maintenance activity because it has the most urgent demand, requires the greatest service effort in terms of total time spent, and has the strictest capacity constraints. As a result, all other winter road maintenance operations can be performed more quickly and require fewer resources in terms of operators, vehicles, and material. For this reason, the scope of the winter road maintenance operations included in the integrated planning approach is limited to the combined spreading and plowing operation.

A careful analysis of the winter road maintenance operations and planning decisions has led to a logical and reasonable problem scope, which should allow for the included decisions to be handled in an integrated manner. However, the complexity of the integrated winter road maintenance planning decisions, within the defined problem scope, still prevents the realization of an optimal solution. Ideally, a fully integrated integer or mixed-integer program would be developed to include all of the individual characteristics of each of the five major problems—depot location, sector design, route design, vehicle scheduling, and fleet configuration—and the complex interactions between them. This type of solution approach would allow for the problems to be simultaneously and optimally solved. However, the complexity of the individual winter road maintenance planning decisions considered in this research and the limitations on computer processing speed make the realization of an optimal solution currently infeasible. 

As a result, this research takes a heuristic-based approach to the five integrated winter road maintenance problems. The solution approach solves the integrated problem in phases, integrating some—but not all—of the individual problems in each phase. The initial solution phase solves the integrated problems of depot location, sector design, and route design. Then the solution improvement phase attempts to improve the solution to the route design and sector design problem (based on the already-determined depot locations), and determine the solutions to the vehicle scheduling and fleet configuration problems. Figure 2 shows the problems and the interactions that are considered in the two solution phases.

Figure 2. Problems and interactions by solution phase

A successful solution methodology should be explainable to winter road maintenance planners and easily solvable by them; otherwise, it is unlikely to be accepted, much less implemented. A heuristic-based approach lends itself to the goal of an explicable and easily solvable solution methodology. A formal optimization solution methodology that can not be logically explicated is likely to be dismissed by planners, because they may not understand the motivation and methodology and therefore perceive it as a “black box” solution. Also, a formal optimization-based method is likely to be much more complex and it is most likely not able to solve problems of realistic size in a reasonable amount of computing time; on the other hand, a heuristic-based optimization approach lends itself to the goals of an explicable and easily solvable solution methodology and is capable of solving an integrated winter road maintenance problem of realistic size and scope.

The vehicle routing problem is the most complex of the winter road maintenance problems included in this research. Therefore, the solution approach for the routing problem forms the basis of the integrated solution methodology. There are two common heuristic approaches to arc routing problems: 1) a cluster first–route second approach and 2) a route first–cluster second approach. The cluster first–route second approach divides the transportation network into mutually exclusive subsets and then constructs a route for each subset. In contrast, the route first approach creates one giant route throughout the entire transportation network, and then partitions the route into smaller feasible routes. There is little research that approaches winter road maintenance problems using a route first–cluster second approach; much research in this area instead utilizes a cluster first–route second approach. Figures 3 and 4 show each of these two methods as applied to a small network.

 

Figure 3. Route first–cluster second method

 

Figure 4. Cluster first–route second method

Robinson, Ogawa, and Frickenstein (1990) compared the two approaches on a two-snowplow routing problem on a test network in Wicomico County, Maryland. The results showed that both methods resulted in the same total mileage, but the cluster first–route second method produced fewer u-turns and more balanced routes. However, the authors mentioned that the cluster first– route second approach attempted to balance the routes and reduce u-turns, while the route first–cluster second method included no mention of attempting to reduce u-turns or balance the routes. In addition, Bodin and Berman (1979) compared the two methods for a school bus routing problem and reported that the route first–cluster second approach provided better solutions than the other approach. It is difficult to determine which approach is better suited to winter road maintenance routing problems, because there is insufficient research that utilizes a route first–cluster second approach to winter maintenance or that compares the two methods.

For the winter road maintenance routing problem on a directed transportation network, the route first–cluster second approach seems the more logical approach because it factors in the direction of traffic flow, the accessibility of an arc from each of the other arcs, and the total travel time throughout the network. The contrasting cluster first–route second approach attempts to create compact clusters by dividing the network based on the distances between each of the arcs. Also, many cluster first–route second approaches to routing define clusters based on the location of the depots; that strategy is not an option for this research, since the depot locations are determined in conjunction with the routes. Therefore, a route first–cluster second routing approach is the basis for the integrated approach to the winter road maintenance problems that is proposed in this research.

1.5       Summary of the Research Objective

A systematic, heuristic-based optimization approach allows planners to deal with discontinuities between past and current operational requirements, which may result in new decision-making challenges. The utilization of a formal method prevents new winter road maintenance planning decisions from being restricted by previous decisions and traditional operational beliefs; instead it promotes decisions based on strategic objectives, operational constraints, and the topology of the road network.

This research develops a more integrated and less sequential approach to the main winter road maintenance planning decisions in an attempt to provide higher quality solutions, avoiding the suboptimization that may occur in treating each problem individually. Additionally, an integrated approach provides planners with a means for assessing the impact of depot location decisions on the agency’s ability to provide a high level of service.

The approach discussed in this research is developed with respect to Missouri Department of Transportation’s (MoDOT) winter road maintenance operations and planning for Boone County, Missouri; therefore, this study focuses on public sector winter road maintenance planning for a rural transportation network. It should be stressed that the integrated approach developed in this research is targeted towards aiding winter road maintenance planners rather than dictating a final solution to them. This research proposes a systematic, heuristic-based optimization approach to integrate the winter road maintenance planning decisions for depot location, sector design, vehicle route design, vehicle scheduling, and fleet configuration.

Chapter 2: Literature Review

2.1       Overview of Relevant Literature

This chapter discusses previous research that is relevant to the development of a systematic, heuristic-based optimization approach that integrates the winter road maintenance planning components defined within the scope of this research. Relevant literature includes research addressing the problems of depot location, sector design, arc routing on a directed network, fleet sizing, vehicle scheduling, and fleet configuration within the context of winter road maintenance, either as individual factors or in combination.

The following sections cover research combining the factors of 1) depot location and sector design, 2) depot location, sector design, and fleet sizing, 3) winter maintenance-related arc routing problems on directed networks, and 4) depot location and routing problems. For further discussion on models and solution methods which address winter road maintenance planning decisions with an analytical and optimization-based approach, see Assad and Golden (1995), Campbell and Langevin (2000), and a very thorough four-part survey by Perrier, Langevin, and Campbell (2006a, 2006b, 2007a, 2007b).

2.2       Depot Location and Sector Design

Korhonen et al. (1992) developed a decision support system for locating vehicle depots and designing sectors for winter road maintenance operations in Finland (Perrier, Langevin, and Campbell 2007a). The system allows planners to select vehicle depots and their corresponding sectors such that variable transport costs and fixed vehicle depot costs are minimized over a ten-year planning horizon. The model only considers transport costs for high-class roadways. They solved the depot location problem using a construction heuristic that opens depots sequentially until no further savings are realized. Their solution method does not include a rule for determining the order in which the depots should be opened.

Rahja and Korhonen (1994) discussed a decision support tool that assists planners in 1) locating storage facilities for abrasives used in spreading operations and 2) designating the sectors or demand zones assigned to each depot. The system was tested on the Finnish national road network, which was divided into very small, balanced geographic zones; each zone had a demand for both salt and sand. The objective of the system is to open depots and design sectors around them which minimize the demand-weighted distance between each demand zone and its assigned storage facility.

2.3       Depot Location, Sector Design, and Fleet Sizing

Hayman and Howard (1972) introduced a model that combined the vehicle depot location, material depot location, vehicle fleet sizing, and sector design decisions for the spreading operations in Wyoming. Material storage depots could be located within vehicle depots or on separate sites. The objective was to minimize the sum of the operational costs and depreciation costs. The operational costs included the cost of traveling from the vehicle depots to the material depots, the cost of delivering the material to the roadways, the cost of acquiring the material, and the depot depreciation cost. Constraints ensure that each class of roadway could be serviced prior to its deadline and that each storage depot contained the necessary amount of material to service each of its assigned roadways. The model is formulated as a mixed-integer program (MIP). The authors achieved a substantial reduction in the size of the model by eliminating any combinations of vehicle depots assigned to storage depots and storage depots assigned to roadways which required “too much” deadhead distance. The linear program (LP) relaxation of the model was solved using the simplex algorithm; the total number of vehicles required at each vehicle and material depot was rounded up to the nearest integer value. In the optimal solution, if no vehicle is assigned to a vehicle depot or a material storage depot, then that site is not opened.

The model was tested on a road network in Wyoming consisting of 15 potential vehicle depot sites, each containing a material storage depot, 6 additional storage depots, and 41 roadway segments. The solution required opening 14 of the 15 vehicle depot sites and 20 of the 21 material depot sites. The authors also developed a very similar model to represent the plowing operations on the same road network—the differences being that plowing operations had different service deadlines, required a different number of passes for each roadway, and did not require material spreading or material depots. The spreading and plowing models resulted in slightly altered vehicle depot and fleet size requirements. Several variations of the models were run to examine the effect of the costs included, and it was found that the depreciation cost had a significant impact on the solution.

Reinert, Miller, and Dickerson (1985) developed a model that combines the decisions for the location and capacity of storage depots with the assignment of pre-defined winter road maintenance routes to each depot. The model is formulated as a (MIP), with the objective of minimizing the total weighted travel distance between the median points of each route and its assigned storage depot. Constraints ensure that each route is assigned to exactly one material depot and that the maximum number of depots opened is not violated. The model allows the user to predefine some or all of the depot sites, pre-assign certain routes to depots, and to limit the capacity of some or all of the depots. The LP relaxation to the MIP was solved using IBM’s MPSX mathematical programming package; the authors noted that the program always produces integer solutions. The model was tested on the District of Columbia’s abrasive spreading operations, using the current routes and 14 potential depot sites, each with an unlimited capacity. First, the model was run using the current depot configuration. Then the model was run four additional times, and the maximum number of depots allowed was increased with each subsequent trial. Since the solution generated by this model always results in the maximum number of depots, the results show the tradeoff between the number of depots, the deadheading distance between the routes, and the assigned storage depots.

Kandula and Wright (1995) described a model combining sector design, depot location, and fleet sizing for plowing and spreading operations in the La Porte district of Indiana. The model was formulated as a MIP with the objective of minimizing the sum of the distances of the shortest paths between each depot and the endpoints of the road segments assigned to that depot. The author describes the objective function as a surrogate measure for maximizing the compactness of each sector. To improve compactness, constraints are included for service hierarchy, class continuity for each vehicle with possible upgrading, contiguity of road segments in each sector, and the number of trucks (or routes) in each sector. A solution to this model designates which depot sites to open, assigns of each road segment to exactly one depot, and provides the number of trucks (or routes) assigned to each depot. The model calculates the number of trucks necessary to simultaneously service all road segments while respecting the previously mentioned constraints. Calculating the number of routes based on the kilometers of each class of roadway per depot—while accounting for a deadheading factor—provides the solution for the number of trucks required at each depot.

Since the model does not provide actual routes, it can not calculate the deadheading required. Therefore, a factor is included in the model to approximate deadheading; the quality of the solution is significantly affected by the choice of this deadheading factor. The authors tested the model using data from the La Porte, Indiana district, which included three priority classes of roadways, four depots, and a network of 63 vertices and 79 edges. The model was solved using the CPLEX Mixed Integer Optimizer. The authors also solved the LP relaxation of the model and found that the relaxation provided similar depot and roadway assignment results with fewer required vehicles. The difference in the relaxation model was that partial road segments were assigned to depots rather than being assigned in their entirety. The authors concluded from the LP relaxation that better results to the MIP may have been achieved if the road segments were further split into smaller road segments.

2.4       Arc Routing Models for Directed Transportation Networks

Marks and Stricker (1971) modeled the plow routing problem as a multiple vehicle Chinese postman problem (CPP). The problem attempts to minimize deadhead distance while respecting the multiple pass service requirements and vehicle capacity constraints. Multiple passes are handled by adding one edge for each required pass over the street it represents. Marks and Stricker state that the model is sufficient for both directed and undirected networks. For streets requiring service in both directions, the authors suggest inserting additional arcs, although no method for handling direction was included. Additionally, the authors also propose some ideas for handling service hierarchy; they suggest either weighting roads in a manner which makes the higher priority roads more attractive or partitioning the network into mutually exclusive subnetworks, with one for each class. However, service hierarchy was not included in the problem studied by the authors. Two approaches are given for solving the problem: a cluster first–route second approach and a route first–cluster second approach. The cluster first–route second approach involves partitioning the transportation network into a predetermined number of sectors and solving a separate CPP for each sector. The number of sectors is chosen based on the number of available vehicles. The route first–cluster second approach requires that first a CPP is solved for the entire network; then, the resulting tour must be partitioned such that an Eulerian tour can be found for each one without duplication of any edges. The cluster first–route second heuristic was tested on a sample network representing Cambridge, Massachusetts, with approximately 250 edges and 144 nodes. The problem was solved by hand in less than three hours. The city did not maintain any existing routes for comparison with the newly generated routes.

Liebling (1973) developed a cluster first–route second heuristic for the salt spreading operations in the city of Zurich. The first phase divides the directed transportation network into the minimum number of disjointed sectors that can be serviced while meeting capacity, time duration, and service frequency constraints. The second phase determines spreader routes for each sector by solving a directed CPP. The heuristic can be applied to snowplowing by adjusting the previously mentioned constraints. The city of Zurich successfully implemented the procedure and found that it resulted in routes more streamlined than the existing ones.

Cook and Alprin (1976) proposed a simple construction algorithm to create vehicle routes for spreading operations in Tulsa, Oklahoma. The routes are assigned dynamically using a greedy heuristic that assigns the closest unassigned street segment to each truck as it leaves the depot. Each route includes the distance of the required street segment and the deadhead distance to and from the depot. The authors define a street segment as the distance along which a street can be salted on both sides with one truckload of salt applied at the desired rate. The method for dividing the directed transportation network into street segments is not explained; it appears to be performed arbitrarily. The closest street heuristic attempts to balance the total workload while meeting the vehicle capacity and both-sides service constraints. Additionally, the procedure provides contiguous routes, a reduction in total time required to service the network, and safer deadhead travel between routes and depots over previously serviced segments. The heuristic makes no attempt to minimize deadheading. The procedure was embedded into a discrete event simulation model and used to evaluate the benefits of increasing the number of materials depots, the fleet size, and the vehicle capacity.

Lemieux and Campagna (1984) modeled a single-plow routing problem with hierarchical service constraints and u-turn restrictions. Since both sides of each street require service, the transportation network is directed. The algorithm creates a closed tour throughout the transportation network such that each arc is covered exactly once—hence no deadheading—while respecting the service hierarchy constraints and u-turn restrictions. To ensure that an Eulerian tour is feasible, the constraints are treated as soft constraints (i.e., constraints that can be relaxed to achieve feasibility). The authors propose two different rules for satisfying the service hierarchy and u-turn constraints; one rule favors the selection of higher priority streets at the expense of u-turns, while the other rule allows class upgrading to prevent u-turns when possible. The authors tested the algorithm on a sample network with 2 classes of roadways, 9 nodes, and 24 arcs. The algorithm was run one time for each of the two selection rules discussed above, and the results were compared. Both rules resulted in some Class 2 roads being serviced prior to some Class 1 roads.

In 1990, students from universities across the U.S. participated in a competition to design service routes for two snowplows in Wicomico County, Maryland. The transportation network is a strongly connected directed graph with 139 vertices and 374 arcs. The objective was to minimize the service completion time—or, equivalently, the total mileage—with a homogeneous two-plow fleet. Each team could include additional assumptions as to make the problem more realistic. The four papers described below (Atkins, Dierckman, and O’Bryant 1990; Chernak, Kustiner, and Phillips 1990; Robinson, Ogawa, and Frickenstein 1990; and Hartman, Hogenson, and Miller 1990) were chosen as the best submissions.

Atkins, Dierckman, and O’Bryant (1990) proposed a traditional cluster first–route second heuristic. First, the transportation network was divided manually into two subdistricts with approximately the same total mileage. Then an optimal Eulerian tour was manually found for each subdistrict by constructing a spanning tree for the undirected equivalent subgraph, adding the additional required edges to create a directed tree, and finally tracing a closed tour on the directed spanning tree.

Chernak, Kustiner, and Phillips (1990) added service hierarchy constraints and multiple pass requirements to the problem being studied. The proposed heuristic constructs two routes for each snowplow. An initial route, with no deadheading, services high priority roads, and a secondary route services the remaining roads. The problem was solved manually using a construction heuristic, although details for the heuristic were omitted from the paper.

Robinson, Ogawa, and Frickenstein (1990) suggested a cluster first–route second method and a route first–cluster second method for routing the two snowplows. In addition to the primary objective of minimizing total mileage, the authors included the secondary objectives of minimizing u-turns and balancing the workload. In the cluster first–route second method, roads were first manually organized into two balanced subdistricts using an “eyeball method.” The authors attempted to create subdistricts which would result in fewer u-turns and balanced workloads. However, no methods for decreasing u-turns or balancing workloads were mentioned for the route first–cluster second method. An Euler tour was manually created for each subdistrict using Trémeaux’s depth-first search algorithm. The authors also found a lower bound on the number of possible Euler tours for the network. In the route first–cluster second method, an Eulerian tour was first manually constructed using the depth-first search algorithm and then divided into two feasible subtours. The authors did not describe the method for dividing the tour, although they do mention that the solutions are very sensitive to the procedures used for bisecting the network and the tour for the cluster first and route first methods, respectively. Comparisons showed that the cluster first–route second method produced fewer u-turns and more balanced routes than the route first–cluster second method; both methods resulted in the same total mileage.

Finally, Hartman, Hogenson, and Miller (1990) developed a heuristic which simultaneously constructs two Eulerian circuits of approximately equal length. Unlike the other works entered in the contest, the authors created a computerized solution method. The solution procedure, based on Hierholzer’s algorithm, iteratively built two routes—one from each seed point—by adding one un-serviced road segment to the shorter of the two routes until all roads are serviced. This method allows for several rules to be embedded into the heuristic for adding each new segment. Once each route is finished, the heuristic checks to see if the routes are unbalanced (route lengths differed by more than five miles). If the routes are unbalanced, the program finds circuits which can be deleted from the longer route and added to the shorter route. This process was repeated until the routes were balanced or no possible exchanges existed for the Wicomico County transportation network.

Haslam and Wright (1991) developed a decision support system for planners to develop snowplow routes for the Indiana Department of Transportation (INDOT). The interactive procedure aids in the creation of routes with the primary objective of minimize deadheading miles and the secondary objective of minimizing the number of required vehicles. The authors discussed many of the practical considerations of snowplowing operations and included many of them in the problem studied. These constraints included service hierarchy, class continuity with possible upgrading, and maximum route length. INDOT is responsible for servicing interstates, highways, and state roads, but some county roads could be traversed in the process. The transportation network is represented as a directed graph in which not all of the roads required service. The procedure includes a method for calculating a lower bound on the number of required routes (equivalently, the number of vehicles), a route generation heuristic, and two improvement heuristics. First, the lower bound for the number of routes needed to service each class is calculated by dividing the total number of lane miles in the class by the maximum distance a plow may travel when servicing that class. The route generation method requires the user to input seed nodes such that the number of nodes is greater than or equal to the lower bound for the number of routes. The procedure generates the routes from the depot to the seed node and back such that each route only services one class and does not exceed the maximum route length. Remaining unassigned roads of the same class are then added to each route, and finally, roads of different classes can be added such that classes are upgraded; both modifications must respect the maximum route length constraint. A drawback to this heuristic is that not all roads requiring service were assigned to routes.

The authors also suggested using the current routes as the initial route solution. Once routes are established, they are improved using elimination and swap heuristics. The elimination heuristic attempts to reduce the number of routes by breaking up some of the routes and distributing their arcs to other existing routes. This procedure must be performed by a knowledgeable decision maker. The swap heuristic attempts to reduce deadheading by swapping arcs between existing routes. The entire procedure was tested on a subnetwork of the Fowler subdistrict with 21 nodes, 54 arcs, and 3 classes of roads. Unfortunately, the solution did not include all of the arcs requiring service. The interactive improvement procedures were also tested on the entire district of Fowler, which contained 99 nodes, 362 arcs, and 3 classes of roads. The swap and elimination heuristics successfully aided in the creation of routes which required fewer vehicles and less deadheading mileage than the existing routes.

Wang and Wright (1994) developed an interactive decision support system, called CASPER (Computer Aided System for Planning Efficient Routes), to assist planners from INDOT in the design of winter road maintenance routes. The system can handle spreader and plow routing problems with service time windows, class continuity, and class upgrading; these constraints are included in a weighted multiple objective penalty function, which minimizes deadhead distance, service time window violations, and total distance of class upgraded road segments. CASPER includes a route generation heuristic and an interactive tabu search-based improvement heuristic. If desired, the user can specify the initial routes to be improved. The route generation procedure starts by estimating the number of routes required to service each class of roadway in the given sector. The number of routes for each class is calculated by dividing the total workload (in kilometers) by the total kilometers which can be serviced within the time constraint, then adding in a deadheading factor that estimates the impact of deadheading on the required number of routes. Routes are constructed one at a time, for each class, by adding segments which are adjacent to the maximum number of nonserviced segments within the same class, such that the route does not exceed the maximum allowable duration. The remaining required arcs are then sequentially inserted into established routes using four insertion rules, which attempt to minimize the penalty function while relaxing either one or both of the class continuity and route duration constraints. Since the routes are generated using a penalty function, the initial solution may be infeasible. Once the initial routes are established, they are input into the tabu-based interactive improvement heuristic. The improvement algorithm uses the previously described penalty function. The weights for the penalty function, the number of iterations, class upgrading allowances, and the routes available for improvement are input by the user. The improvement solution defines a neighborhood and attempts to reduce the objective function by removing an arc or pair of arcs from a route and adding them to another route. Once the possible moves within the neighborhood are exhausted, a new neighborhood is selected. The heuristic continues until the maximum number of iterations is reached. The heuristic successfully reduced deadhead distance, the number of routes, and violations of the service time windows in several test districts in Indiana.

Kandula and Wright (1997) developed an interactive bounds-based heuristic for winter road maintenance routing in the state of Indiana. The heuristic attempts to minimize deadhead distance while taking into account class continuity, maximum route duration for each class, and both-sides service. The authors noted that the heuristic does not penalize short routes. The procedure identifies a set of seed nodes which correspond to the number of routes required to service the network within the time limit. Next, the maximum number of routes that can be constructed from each seed node is calculated, and a lower bound on the amount of required deadheading is found using a modified version of a procedure developed by Assad, Pearn, and Golden (1987) for the capacitated Chinese postman problem (CPP). Routes are constructed one at a time from each seed node, based on a greedy method which chooses the nearest nonserviced edge that is farthest away from the depot and will not violate the previously mentioned constraints. If no such edge can be found, then the partially constructed route is extended to the depot using the shortest path of deadhead edges. Once an initial solution is found, an interactive improvement procedure is applied which attempts to improve the feasibility and quality of that solution. The improvement procedure involves manually swapping edges among the routes or deleting an edge from one route and adding it to another. The heuristic was compared with the previously discussed tabu search algorithm developed by Wang and Wright (1994). Both methods were tested on five networks from Indiana, and the results showed that the interactive bounds-based procedure performed better than the tabu search-based method for a predefined number of iterations.

Campbell and Langevin (2000) discussed the commercially available interactive decision support system GeoRoute for designing vehicle routes for postal delivery, winter maintenance, meter reading, street cleaning, and waste collection problems. GeoRoute can develop routes for plowing, spreading, and snow blowing operations. The objective function is a weighted additive multi-criteria function defined by the user which includes optional constraints for service time windows, service frequency, vehicle capacities, spreading rates, turn restrictions, street segment dependencies, and both-sides service. Since GeoRoute is a proprietary software package, the algorithms used to develop vehicle routes are not publicly available. The authors describe the method as a two-phase cluster first–route second method, which constructs one route at a time. Clusters are determined by allocating segments to predetermined seed nodes. Then routes within each cluster are developed using a composite routing procedure. Campbell and Langevin (2000) report that the software has been implemented in several cities and counties in Canada and England for winter road maintenance operations.

Haghani and Qiao (2001) proposed a heuristic for routing spreader trucks in Calvert County, Maryland. The problem considers a single-depot, homogeneous-fleet, capacitated arc routing problem on a directed transportation network. Although both sides of each two-lane highway can be serviced once from either direction, the direction is arbitrarily fixed prior to the application of the solution method. Therefore, the problem is a directed capacitated arc routing problem. The authors suggest that the solution method could be modified for plow routing. (The transportation network and the capacity constraints would be different for a snowplow routing problem.)

The authors proposed a four-stage solution procedure. An initial solution is found in the first stage, and then the heuristic attempts to minimize the total deadhead distance by means of three successive improvement stages. Two methods for determining an initial routing solution are proposed in the paper. The first and simpler procedure creates one route for every road segment that requires service. Each route consists of 1) the shortest path from the depot to the beginning of the road segment, 2) the road segment, and 3) the shortest path from the end of the road segment to the depot. The second method begins with the furthest road segment from the depot and sequentially adds the nearest required segments to the route as long as the vehicle capacity constraint permits; finally, the shortest paths from the depot to the route and from the route to the depot are included. This procedure is continued until all required road segments are included for service in exactly one route.

The augment algorithm determines whether a larger route can service another smaller route. If so, the smaller route is discarded and its required road segments are included in the larger route. The merge procedure also attempts to join two routes by combining them at the common node, which results in the best improvement and meets the required constraints. Both the augment and merge algorithms are modifications of algorithms developed by Golden and Wong (1981) for the undirected case. The delete-and-insert algorithm deletes a required arc from a route, redefines that route such that all of the remaining arcs are serviced in the best order, and inserts previously deleted arc into another route at the point which provides the greatest improvement. The link exchange algorithm is similar to the delete-and-insert algorithm, except that two required arcs are exchanged between the two routes, such that the greatest improvement is achieved.

The second stage—the first improvement stage—applies the augment, merge, and delete-and-insert algorithms in succession. The third stage improves upon the output from the second stage by applying augment, merge, delete-and-insert, and link exchange algorithms in that order. Finally, the fourth stage takes the output from the third stage and iteratively applies the delete-and-insert, and link exchange algorithms until no further improvements can be made. The authors tested the four-stage heuristic on three subdistricts in Calvert County, Maryland, with up to 42 nodes and 104 edges. The solution was obtained very quickly—in less than two minutes—and resulted in a reduction in both deadhead distance and the number of vehicles required, when compared to the existing route and fleet configuration.

Salim et al. (2002) developed an artificial intelligence-based decision support system called SRAM (Snow Removal Asset Management) for making asset management and routing decisions related to winter road maintenance operations. (Sugumaran et al. 2005 embedded this approach in a Web-based GIS environment.) The system develops routes for plowing and spreading operations and assigns those routes to the vehicles available in Black Hawk County, Iowa. The routing procedure aims to minimize total service time while ensuring that strict service hierarchy constraints and maximum route time constraints are not violated. First, the procedure estimates the number of vehicles assigned to service each priority level by dividing the total estimated plowing time by the maximum allowable plowing time for one vehicle. Then, routes are constructed one at a time for each vehicle using a simple greedy heuristic which starts with a seed node and continues to add the nearest segment to the route until the maximum allowable plowing time is reached. The system continues until all required segments are assigned to exactly one route. Routes are created separately for each class of roads, ensuring class continuity. The system includes detailed operational information gained from interviews with winter maintenance planners and embedded into the GIS system, which allows for accurate estimates of required service times. In addition, the routes vary depending on the forecasted intensity of the storm. Once routes are established, the available vehicles are assigned to those routes—for each class of roads—using one of two methods, depending on the user’s preference. If the user specifies that a vehicle can be assigned to exactly one route and that each route can be assigned exactly one vehicle, then an assignment problem is solved using the Hungarian algorithm. Otherwise, if a vehicle can be assigned to more than one route and a route can be assigned to more than one vehicle, then the vehicle scheduling problem is solved as a transportation problem using the stepping stone solution technique.

Both the assignment problem and the transportation problem have the objective of minimizing the total cost of operations, which consists of an operating cost per unit of time for each vehicle and the operating time required by each route. Since the cost for each vehicle is independent of the route it services, it appears that all vehicles are located at the same depot, but require different operating costs. The procedure also determines the required quantities of material required by each route for spreading operations. The system was found to be very user friendly and successful in generating routes which required less total service time than those previously in use. In addition, the system proved useful in analyzing the impact of changes in the available number of vehicles, the storm intensity, the road segments requiring service, and other parameters on the total service time and total operating costs.

2.5       Depot Location and Routing

Lotan et al. (1996) discussed a systematic location and routing problem for spreading operations in Antwerp, Belgium. The methodology aims to locate both vehicle and storage depots and create vehicle routes, while achieving the multiple and conflicting objectives of minimizing total mileage, minimizing the number of depots, and minimizing the number of routes (or, equivalently, the number of vehicles required). The problem includes capacity constraints for a homogeneous vehicle fleet and two levels of service hierarchy, with a service completion deadline for each class. Additionally, high priority roads require one pass in each direction, while low priority roads can be serviced with one pass in either direction.

The authors solve the combined location and routing problem in two stages. The first stage integrates the vehicle depot locations and the construction of feasible routes for the high-priority network. Initially, an upper bound is determined on the number of depots required to service the high-priority roads with no deadhead mileage. Then, the methodology iteratively solves the location routing problem for the high-priority network, each time with a decreasing number of depots below the upper bound. The results show the tradeoff between the number of depots and deadhead mileage; an acceptable solution to the number and location of vehicle depots and the corresponding vehicle routes is then decided by a qualified decision maker based on this tradeoff. The first stage was tested on the province of Antwerp, Belgium. The number of nodes and road segments in the high-priority network were not specified.

The second stage allocates the low-priority roads to the previously established depots, establishes feasible routes for each depot, and locates secondary storage depots, with the objective of minimizing total distance. The methodology includes a districting procedure which allocates the roads to the nearest depot, with the secondary objective of creating Eulerian subgraphs for each district. Once districts are established, the routing problem is modeled as a single-depot capacitated arc routing problem (CARP), with one subproblem for each depot. The objective of the CARP is to minimize total travel distance, while minimizing the number of vehicle routes by increasing the capacity of some tours through the introduction of storage depots. The problem is formulated with the following features: routes must begin and end in the depot from which they originate; routes can only service their assigned district; routes may include refill at a secondary storage facility, which doubles the route’s capacity; and roads can be serviced once in either direction, resulting in a mixed network. The CARP is then solved for each depot using the augment-insert construction algorithm for the CARP on sparse networks with large arc demands, described in Pearn (1991). Finally, a secondary storage depot is added to improve the previously constructed routes. The author did not include any rules for determining the location of the silo. The second stage was tested on the network of Brecht, Belgium that includes 33 nodes and 43 road segments.

In 1997, Kandula and Wright described a modified version of the combined sector design, depot location, and fleet sizing model previously described (Kandula and Wright 1995). The new model was formulated as a mixed-integer programming (MIP) model with the multiple objectives of minimizing 1) the sum of the distances of the shortest paths between each depot and the endpoints of the road segments assigned to it, 2) the total deadheading time, 3) the total number of time units of all the commodities on each arc, and 4) the total number of vehicles used. The model includes additional flow constraints designed to provide a better estimate of the amount of deadheading by improving the estimate of the number of routes required. For a predefined number of depots to open, the model determines which depot sites to open, the assignment of each road segment to exactly one depot, and the number of trucks (or routes) assigned to each depot. To improve compactness, the model still includes constraints for contiguity of road segments in each sector and for the sector size. However, the model no longer considers service hierarchy. The model was solved using the CPLEX Mixed Integer Optimizer for five different districts in Indiana, each with up to 3 depots, 62 nodes, and 73 edges. The newly designed sector, depot, and fleet configurations were tested using two routing procedures: CASPER and a lower bound-based procedure (Wang and Wright 1994). The results showed more compact sectors in all cases, but only reduced deadheading and the required number of vehicles about half of the time when compared with the earlier model described by Kandula and Wright (1995). Since the new model had different constraints and the results were similar to the previous model, the authors concluded that it is a good alternative to the existing model, but not necessarily an improvement.

Gupta (1998) developed a decision support system which aids planners in estimating the economical impacts of the following four scenarios: closing an existing facility, opening a new facility, simultaneously closing an existing facility and opening a new facility, or maintaining the current facility configuration. The model allows planners to compare any two of the four scenarios. Gupta’s model included estimates for the annualized cost of winter road maintenance activities, capital costs of vehicles, annualized cost of facility infrastructure associated with the opening of a new facility, and a one-time cost of environmental treatment required to close an existing facility. Since the annualized cost of winter road maintenance depends on the total distance of the vehicle routes, a solution to the snowplow routing problem must be established first. The snowplow routing problem is solved using the Snowmaster software (Evans and Weant 1990). Snowmaster models the routing problem as a multiple-depot, multiple-vehicle Chinese postman problem (CPP) with vehicle capacities and route duration constraints. The software offers the user a choice of the five route generation rules which attempt to minimize total distance. The rules are as follows: shortest available road segment first, longest available road segment first, node closest to the depot first, node farthest from depot first, and node farthest when going out and closest when returning. Once all of the costs described above are estimated, the model can be solved for any of the two scenarios in question to determine the better scenario. The model was tested using data from Hamilton County, Ohio, with a transportation network that included 360 nodes and 855 arcs.

2.6       Summary of Relevant Literature

The review of existing research shows an opportunity for improving winter road maintenance planning by approaching the problems of depot location, sector design, route design, and fleet configuration in a systematic, integrated manner. There is little research that addresses the problems in combination, and a review of those that have reveals an opportunity for a method which approaches them in a more integrated and less sequential manner. Research which has addressed the main winter road maintenance problems of depot location, sector design, route design, and fleet sizing in combination includes solution methods that are very computationally demanding; this prevents the determination of multiple depot locations or only allows unrealistically small problems to be considered.

Additionally, the existing research has assumed homogeneous fleets—an assumption which results in the number of routes being equivalent to the number of required vehicles. In practice, however, service agencies often utilize heterogeneous fleets. The introduction of a more realistic, heterogeneous fleet presents the additional challenge of determining the fleet configuration.

Vehicle scheduling is required when a vehicle can service additional routes prior to providing further service to any of the routes it has previously serviced; this occurs when a vehicle’s routes are constrained by capacity rather than time limits. The only research effort described in this chapter which included the vehicle scheduling problem is the research performed by Salim et al. (2002); in this case, the authors solved the problem as a transportation problem where the routes represent the demand and the vehicles represent the supply.

The existing research on winter road maintenance routing described in this chapter assumes that one predefined depot location and sector exists, around which routes are designed. To integrate the decisions for vehicle route design, depot location, and sector design, it is necessary to include a routing solution method that can handle multiple depots and consider adjustments to the sector design to possibly improve the overall solution.

An integrated approach to winter road maintenance planning can be built upon many of the existing research methods and concepts discussed in this chapter. However, modifications of previous methods and new ideas are also required. The integrated solution approach developed in this research builds upon the route first–cluster second approach suggested by Marks and Stricker (1971), the depot location solution method proposed by Reinert, Miller, and Dickerson (1985), and the vehicle routing methodology proposed in Haghani and Qiao (2001). The methods are adapted to integrate the decisions involved and to handle the problem characteristics defined within the scope of this research effort. In addition to integrating the decisions, the method also incorporates the aspects of multiple-depot vehicle routing, fleet configuration, and vehicle scheduling.

Chapter 3:  Problem Formulation and Solution Methodology

3.1       Problem Formulation

When dealing with such complex problems as winter road maintenance, it is often advantageous to formulate the problem or a relaxed version of the problem to help in the development of solution methodologies. The basic underlying problems, which are discussed in the previous section, can be formulated mathematically. However, each of these basic problems are nonpolynomial (NP)-complete or NP-hard problems. This means they are not computationally tractable, and either very sophisticated techniques must be used—which require a great deal of solution time—or heuristic approaches must be employed.

Due to the difficulty in formulating and solving the integrated model, it was decided to formulate aspects of the overall problem that could be used in possible solution methodologies. These smaller, relaxed integrated problems can then be used to generate initial solutions and to form a basis from which it would be possible to add constraints—through column generation—to approach the solution to the integrated problem. Through this brief discussion of the formulation of smaller problems, an appreciation of the task of formulating and solving the overall integrated problem can be had.

The most basic underlying problem is that of arc routing, meaning that it is necessary to ensure that every road segment to be maintained is visited by a vehicle. This classic problem goes by several names, but is generally called the Chinese postman problem (CPP). A variant of that problem related to snow removal can be formulated as follows based on the work presented in Perrier, Langevin, and Campbell (2006a).

Let G = (V, E) be an undirected graph where V is the vertex set and E is the edge set, and let K be the set of vehicles. For each node v_i Î V, let E(v_i) = {v_j Î V: (v_i, v_j) Î E} be the set of nodes adjacent to node v_i , which can be reached directly by traversing one arc. Let every edge (v_i, v_j) Î E have a nonnegative length c_ij. For each vehicle k Î K, define b_k as the maximum distance vehicle k can service, based on its capacity. For each edge (v_i, v_j) Î E and for each vehicle k Î K, let x_ijk be a binary variable equal to 1 if and only if edge (v_i, v_j) is serviced from v_i to v_j by truck k. The problem is then formulated as a linear 0-1 integer program as follows:

Minimize               

Subject to

                                                                                                     

                                                                                                    

                                                                                    

                                                                                                                

                                                                                                                

                                                                                                      

The objective in this formulation is to minimize the total distance traveled. The constraints guarantee that 1) each road segment is serviced at least once, 2) there is a limit on the distance each vehicle can travel, 3) there is flow conservation at every node, 4) each vehicle starts and ends its route at a depot, and 5) all x_ijk variables are binary. Note that this model can be solved by commercial software, even though it may be time consuming.

This formulation is only concerned with the routing of vehicles. If both the routing of the vehicles and the location of the depots is considered, the problem becomes more difficult. The following formulation models this integration of concepts. This formulation is based on the work presented by Daskin (1995).

Let I = the set of nodes (where each node represents a road segment needing service), let J = the set of candidate depot locations, let N =I È J = the set of all nodes, and let K = set vehicles. Additionally, let h_i = service time required by the road segment represented by node i, let f_j = fixed cost of locating a facility at candidate site j, let c_ijk = the cost of servicing node i from location j using vehicle k, let g_k = fixed cost of using vehicle k, and let u_k = capacity of vehicle k. The decision variables for the problem are as follows:

           

                      

           

The problem is then formulated as

Minimize                

Subject to

                                                                                                           

                                                                                         

                                                                               

                                                                                                 

                                                                                                 

                                                                                                      

                                                                                                            

                                                                                      

                                                                                                                        

                                                                                                    

                                                                                                 

The objective function minimizes the sum of the fixed facility location costs, the distance-related routing costs, and the fixed costs associated with using the vehicles. The constraints restrict each road segment to one route so that each segment is serviced by one vehicle and flow conservation is maintained. Additionally, the constraints involving Ω are subtour elimination constraints. This is done by requiring that for any subset (Ω) of segments, the total number of connections between pairs of nodes in the subset must be less than or equal to the cardinality of the subset minus 1. 

Lastly, it is possible to formulate one more integrated subproblem of the overall problem. The formulation presented below is for the sector design, depot location, and fleet sizing problem as presented in Kandula and Wright (1995) and Perrier, Langevin, and Campbell (2007a).

Let g = (V,E) be a connected undirected graph where V = {v₁, v₂, …,v_n} is the vertex set and E = {(v_i, v_j) : v_i,v_j Î V and i ¹ j} is the edge set. A nonnegative length c_ij and a positive number of circulation lanes l_ij are associated with every edge (v_i, v_j). Let sc_ij be the length of the shortest chain linking vertex v_i to vertex v_j in G. Let D Ì V be a set of potential depot sites. For every depot v_d ÎD, define dhf_d as the deadhead factor used for road segments associated with depot v_d (dhf_d ³ 1 for all v_d Î D), define cap_d as the maximum number of kilometers assigned to depot v_d, and define sumsc_d as the limit on the sum of the lengths of the shortest chains from depot v_d. For every edge (v_i, v_j) Î E, and for every potential depot site v_d Î D, let x_ijd be a binary variable equal to 1, if and only if edge (v_i. v_j) is assigned to depot v_d, if it is opened.

Let P_K = {E₁, E₂, …, E_K} be a partition of E, with E₁ È E₂ È…È E_K = E_K = E and E_i Ç E_j = Æ for all i, j Î{1,2,…,K}, i ¹j. For every depot v_d Î D and every class E_k Í P_K, let n_kd be a nonnegative integer variable representing the number of vehicles based at depot v_d to service edges of class E_k assigned to depot v_d. For every depot v_d ÎD and every class E_k Í P_K, define cl_kd as the maximum number of class k kilometers assigned to depot v_d. For every class E_k Í P_K, define f_k as the frequency of service in hours that must be provided to road segments of class k. The vehicle speed, expressed as kilometers per hour, is denoted by s.

Finally, define numv as the maximum number of vehicles to be used, numd as the maximum number of depots to be operative, and sumsc as the limit on the sum of the lengths of the shortest chains from operative depots to both ends of road segments that are assigned to these depots. The modified version of the Kandula and Wright (1995) formulation given by Perrier, Langevin, and Campbell (2007a) is

Minimize                                                                                            

Subject to                                                                                                                                

                                                                             

                                                                                 

                                                                                                    

                                                                                                          

                                                                                        

                                                                                                 

                                 

                                                                                      

                                                       

                                                        

                                                                                               

                                                                                                  

                                                                                   

                                                                                         

                                                                                         

                                                                         

                                                                            

                                                                                 

                                                                                    

                                                                             

A formulation of the integrated model presented in this work would require the combination of the above models with additional factors and coupling variables and constraints. The resulting model would be intractable, and any solution methodology would be dependent on the appropriate solution of these relaxed subproblems. Therefore, an overall integrated model was not developed. 

Likewise, the complexity of the problems and their formulations require heuristic approaches to be employed in the solution of the problem. The presented formulations, though, help in the development of the heuristics and bring to light the tradeoffs between the heuristic approach and exact methods. The formulations also give a framework for building an integrated solution and for possibly determining bounds on the solution. The heuristic procedure is presented in the next section.

3.2       Overview of the Methodology

The solution methodology consists of three phases: a network initialization phase, an initial solution phase, and finally, a solution improvement phase. The network initialization phase prepares the network for input into the initial solution phase. The first step is to check whether the transportation network is set up correctly by verifying that the network is strongly connected. Then the shortest paths from each node to every other node in the network are determined. The first two steps are achieved simultaneously using an algorithm for the directed Chinese postman problem (CPP). Finally, four strongly connected subnetworks—one for each hierarchical class of roadway—are created from the original transportation subnetwork.

The initial solution phase simultaneously determines the location of the depots as well as the initial solutions for the sector design, vehicle routes. (It should be noted that the solutions to the fleet configuration and vehicle scheduling problems could be solved in this phase as well; however, they would need to be solved again in the solution improvement phase, if the routes and sectors are improved in that phase.) First, a Chinese postman tour (CPT) is found for each of the four subnetworks created in the network initialization phase. The CPT serves as the basis for the initial routes, which are created in this phase.

Once the CPT is determined for a subnetwork, it is then partitioned into routes according to the maximum route duration and service distance constraints; at this point the initial routes are incomplete, because they do not begin and end at a depot. The algorithm for dividing the CPT into feasible routes attempts to meet but not exceed the maximum service distance and duration constraints which, consequently, minimizes the number of routes created. Minimizing the number of routes attempts to satisfy the objective of providing the desired service level with a minimum number of required vehicles. There are many possible outcomes for partitioning the CPT into feasible tours; therefore, the objective of minimizing the deadhead travel between the routes and their assigned depots is considered in this step. The algorithm determines each of the possible outcomes for dividing the CPT into routes. Then it chooses the one that results in the least total deadheading between all routes and all depots.

Next, the completed initial routes, sectors, and depot location are simultaneously determined. The depot location problem involves the selection of a predetermined number of depot sites to be opened out of a larger set of candidate depot sites, based on the objective of minimizing the weighted deadhead travel time between each route and its assigned depot. The sector design is achieved through the assignment of the required routes to opened depots, with the same objective of minimizing deadhead travel time. The initial routes are completed by extending each of the previously determined routes to and from the depot to which it is assigned. The initial solutions developed in this stage are also analyzed to determine the number of depots to open.

The third phase, the solution improvement phase, attempts to improve the quality of the initial solutions to the sector design and plow and spreader route design problems, based on the determined depot locations. The improvement heuristic attempts to enhance the quality of the sector and route designs by making two different types of moves: 1) removing an arc from one route, then inserting it into another route and 2) exchanging arcs between two routes. The heuristic only allows moves which satisfy the operational constraints and improve the objective of minimizing total deadhead travel time. Moves between two routes in the same sector improve the route design, while moves between two routes in different sectors improve both the route design and the sector design. The improvement heuristic is applied separately to all four subnetworks. Then, once the routes are designed, the third phase concludes by determining the fleet configuration and vehicle schedules necessary to service the routes. The following diagram outlines the three-phase solution methodology.

Figure 5. Three-phase solution methodology

3.3       Network Initialization Phase

The network initialization phase determines the inputs necessary for the initial solution phase. The first step in the phase is to create one tour throughout the entire transportation network; this step achieves two purposes: 1) verification that the network is strongly connected and 2) calculation of the shortest paths between every node and their corresponding costs. While there are many algorithms for solving the CPP, this research uses the algorithm for the closed CPP presented in Thimblebly (2003). Thimblebly’s algorithm was chosen for several reasons: the readily available Java code provides an executable solution method rather than just a description of the algorithm; the program is very user friendly; and finally, the program is quick and efficient. The author states that the solution to the CPP requires the solution to an integer linear program, and until a quicker method for solving an integer program becomes available, no significantly faster algorithm for solving the CPP is attainable (Thimblebly 2003). The program is very user friendly, requiring the transportation network (a directed multi-graph) to be represented as a collection of arcs, where each arc from vertex i to vertex j is labeled and assigned a cost.

The algorithm determines an optimal CPT and the associated cost of the tour. If possible, the algorithm determines an Eulerian tour; otherwise an optimal tour with some required deadheading is determined. The algorithm creates an initial solution using a greedy heuristic and then iteratively improves the solution using a cycle canceling algorithm, until no further improvement is possible. Additionally, the algorithm verifies that the network is strongly connected and provides both the shortest paths between every node and corresponding costs. Checking to see that the network is strongly connected—that every node can be reached from every other node—is necessary to verify that the transportation network was input correctly. The algorithm determines the shortest path from each node to every other node in the transportation network using the Floyd-Warshall algorithm and stores the corresponding costs in a matrix where they can be easily called upon for use in the algorithm (Skiena 1998). The shortest paths are an integral part of the solution methodology presented in this paper and will be used frequently.

Since the service for the roadways must be provided according to priority rather than geography, the initial routing is performed separately for each class of roadway. The second step makes this possible by creating four subnetworks, one for each class, from the existing transportation network. The four subnetworks included in this research—A₁, A₂, A₃, and A₄—are comprised of Class 1 highways, Class 1 non-highway roadways, Class 2 roadways, and Class 3 roadways, respectively. In order to determine a CPT throughout each of the subnetworks, they must all be strongly connected. Since it may be necessary to travel on a Class 1 highway in the subnetwork A₁ in order to reach a Class 2 roadway that requires service in subnetwork A₂, it may be necessary to add additional arcs from the other classes to each subnetwork for connectivity purposes. The original arcs in any subnetwork are treated as service arcs for the purpose of routing, while any arcs added for connectivity are considered deadhead arcs in the routing stage for that subnetwork. To connect the remaining subnetworks, the following greedy procedure is applied for each subnetwork:

1)      Randomly choose an isolated arc that is part of the disconnected subnetwork.

2)   Using the shortest paths, determine the nearest node of the same class.

3)   Add all of the arcs that make up the shortest path between the two nodes in the subnetwork.

4)   Repeat this procedure until the entire subnetwork is strongly connected.

3.4       Initial Solution Phase

3.4.1    Overview of Initial Solution Phase

The initial solution phase determines the location of the depots as well as the initial solutions for the sector design and vehicle routes. The first stage of the initial solution phase creates the initial routes for the combined spreading and plowing operations; the routes determined in this step are still incomplete because they do not begin and end at a depot. In the second stage, the initial solutions for the sector designs, depot locations, and completed initial routes are derived simultaneously.    

3.4.2    Stage 1: Initial Incomplete Route Development

The initial incomplete routes for each class of roadway are determined using a method based on the route first–cluster second method suggested by Marks and Stricker (1971) that includes additional constraints. The route design problem includes vehicle capacity and service frequency constraints. The vehicle capacity constraints are expressed as a maximum distance which can be serviced by one route, which depends on the type of vehicle. Subnetwork A₁ is serviced using vehicles which can service 100 lane miles. Subnetworks A₂, A₃, and A₄ are serviced by vehicles with a maximum service distance of 75 lane miles. As previously discussed, any higher class roadways added to a subnetwork for connectivity are considered deadhead arcs and therefore are not included the total service distance. The service frequency constraints are expressed as maximum time duration constraints, which depend on the class of roadway being serviced. The maximum route durations for A₁, A₂, A₃, and A₄ are 2, 2, 6, and 12 hours, respectively.

The route first–cluster second approach involves first solving a CPP for the transportation network, then partitioning the resulting tour into routes based on the defined objective(s) and operational constraint(s). For each transportation subnetwork A₁, A₂, A₃, and A₄, a CPT is found using Thimblebly’s (2003) algorithm for the closed CPP. If the CPT includes more than one pass over a service arc, the additional passes are considered deadheading. The CPT creates the foundation for the initial routes, based on the objective of minimizing the deadhead travel needed to service all of the required arcs within the subnetwork.

The CPT must then be divided into feasible routes, based on the operational constraints for maximum service distance and maximum duration. The algorithm for dividing the CPT into feasible routes attempts to meet but not exceed the maximum service distance and duration constraints and, consequently, minimizes the number of routes created. Minimizing the number of routes attempts to satisfy the objective of providing the desired level of service with a minimum number of required vehicles. Since the depot locations are still undetermined, the duration of a route is calculated using the service time and an approximation of deadhead travel time between each route and its assigned depot. The heuristic approximates deadhead travel time between the depots and routes by calculating average deadhead travel times on the shortest paths between the endpoints of each route and the ten nearest depot candidate sites.

There are many possible outcomes for partitioning the CPT into feasible tours. Since the CPT begins and ends at the same point, a tour containing n arcs can be divided into n possible combinations of routes with one route starting at each arc. It is possible that a better partitioning of the CPT into feasible routes will lead to a solution requiring less deadheading between the routes and depots as well as a fewer number of required routes. Therefore, the objective of minimizing the deadhead travel between the routes and their assigned depots is considered in this step. The algorithm determines each of the possible outcomes for dividing the CPT into routes, then chooses the one that results in the least total deadheading between all routes and all depots. Since the depot locations have yet to be determined, the algorithm uses the total deadheading between depots and all routes to evaluate the quality of the solution to the problem of partitioning the CPT into the initial incomplete routes. The following diagram shows the relationship between the depot location problem and the route design problem established in this stage.

Figure 6. Influence diagram for stage 1 of the initial solution phase

The following heuristic is used to determine the initial incomplete vehicle routes based on the objectives of providing the desired level of service frequency, minimizing deadhead travel, and minimizing the number of routes, the topology of the transportation network, the potential depot locations, and the operational constraints:

Stage 1 Heuristic

(0)   Initialize

a.   Initialize variables setting i = 1, j = 1, k = 1, and m = 1.

b.   Define total distance as sum of the distances of all the serviced arcs included in the current route and a_j.

c.       Define total duration as the sum of 1) the travel time on all of the arcs included in the current route (either serviced or deadheaded depending on the arc), 2) the travel time on arc a_j, 3) the average deadhead travel times of the shortest paths from the ten nearest depots to the beginning of the current route, and 4) the average deadhead travel times of the shortest paths from of the end of arc a_j to the ten nearest depots.

d.   Define n as the number of subnetworks (A₁…A_n).

e.   Define the total deadhead travel time as the sum of the deadhead travel time from each depot to the beginning of each route and the deadhead travel time from the end of each route to each of the depots.

(1)   For subnetwork A_i, choose a seed node v₀ and create a closed Chinese postman tour (CPT) that begins at the seed node and includes all arcs (v_i,v_j) Î A_i, using the program presented in Thimblebly (2003). Set P = the number of arcs in the CPT.

(2)   Partition the initial CPT into routes (R₁, R₂…R_K) that satisfy the limits on the maximum route distance d_i and maximum allowable duration t_i by executing the following:

a.   Rank and label the arcs in the CPT from 1 to P, starting with the arc a_m and ending with the arc just prior to arc a_m. Define a_j as the arc in the j^th position of the CPT, where j = 1…P.

b.   Choose a_j and determine whether the arc is deadheaded or serviced. If the arc is serviced, add a_j to the current route and update j = j + 1. If j ≤ P, proceed to step 2c, otherwise proceed to step 2f. If the arc is deadheaded, then update j = j + 1. If j ≤ P, repeat step 2b; otherwise proceed to step 2f.

c.   Choose the next arc a_j in the tour that is not assigned to a route, and determine whether the arc is deadheaded or serviced. If a_j is deadheaded, move on to step 2d. If a_j is serviced, determine whether the total distance exceeds d_i. If the total distance is less than or equal to d_i, go to step 2d. If the total distance exceeds d_i, then go to step 2e.

d.   Determine whether the total duration exceeds t_i. If the total duration is less than t_i, then add a_j to the current route and set j = j + 1. If j ≤ P, return to step 2c; otherwise proceed to step 2f. If the total duration exceeds t_i, then proceed to step 2e.

e.   Complete the current route R_k, set k = k + 1, and return to step 2b.

f.    Complete the current route R_k, and then proceed to step 2g.

g.   Check to see if any routes end with a deadheaded arc. If so, remove the arc and repeat step 2g. Otherwise, proceed to step 3.

h.   Save the set of routes as S_m. If m < P, set m = m + 1, set j = 1, set k = 1, and return to step 2a; otherwise proceed to step 3.

(3)   Choose the best partitioning of the CPT, the set of routes S_m with the least total deadhead time.

a.   Calculate the total deadhead travel time for each set of routes S_m.

b.   Choose the set of routes S_m with the minimum total deadhead travel time, and set S_m equal to S_i. If i < n, update i = i + 1, set j = 1, set k = 1, set m = 1, and return to step 1; otherwise terminate.

3.4.3    Stage 2: Integrated Depot Location, Sector