In arc routing problems, the goal is to determine an optimal path, or set of paths, that traverse a required subset of arcs on a graph with respect to a set of constraints and objective function. The Chinese Postman Problem (CPP) forms the basis for many arc routing problems. Let graph G =(V,A), where V is a set of vertices and A = {(i,j) | i,j in V} is a set of arcs that each connect exactly two vertices, each with its own cost of traversal c_ij. The objective of the CPP is to construct a least cost path that traverses each arc in A at least once.

There are many practical applications for variants of the CPP, including winter street maintenance, and street sweeping that incorporate:

[Rural Instances] Rural Postman Problems (RPP) stipulate that only a subset $A_R \subset A$ require traversal, allowing for non-servicing traversal on the rest of the graph. In the context of street sweeping, a street sweeper isn't responsible for sweeping all the streets.

[Windy Graphs] In the CPP, the cost of traversal of an arc is the same, regardless of the direction of traversal. In the Windy Postman Problem (WPP), the cost of traversal is asymmetric. That is, it is possible for c_ij not equal c_ji. In the context of snow plowing, it is harder to plow uphill than downhill.

[Multi-Vehicle] Instead of a single vehicle with a single tour, multiple tours are found for multiple vehicles. This is often accompanied with an objective function that seeks to minimize the cost of the largest cost route. This is motivated by practical applications, which seek to balance the cost of each route. In the case where route cost is measured in time, route balancing minimizes, for example, paid overtime.

[Turn Penalties] UPS reported that it saved three million gallons of gasoline annually by avoiding unnecessary left-hand turns, which take longer to perform than going straight or turning right. Instances with turn penalties incorporate costs of turning, in addition to costs of traversal.

The Windy Postman Problem (WPP) incorporates windy graphs and the Rural Postman Problem (RPP) incorporates rural instances. The RPP can be extended to include turn penalties (RPPTP). The Windy Rural Postman Problem (WRPP) incorporates instances that are both windy and rural. The WRPP can be extended to the MM k-WRPP which adds k plows. In this dissertation, we extend these variants to new problems with new problem attributes that are practically motivated. Our new attributes are listed below.

[Multi-Period] The CPP solves for a single route, which can be interpreted to be traversed in a single day. It is possible that the set of required arcs is too long to service in a single day and therefore must be split among multiple days. In this case, we need to decide which day to assign service to each arc, before routing can take place.

[Downhill Instances] In street snow plowing, it is faster to deadhead (traverse without servicing) a street rather than plowing it. In this case, there are different costs for deadheading and plowing a street. Moreover, it takes longer to plow uphill, resulting in four costs: plowing uphill, plowing downhill, deadheading uphill, and deadheading downhill.

[Precedence] When considering downhill instances, the snow may be so deep that it is impossible for a snowplow to deadhead a street before the street is plowed.

In this dissertation we present a variety of heuristics to solve these problems, all adaptations of the concept of cycle permutation based on Euclidean cycle decomposition. To our knowledge, the use of moving or permuting sub-cycles as a way to change and improve a Eulerian cycle is novel and we show that it is very robust at improving solutions.