Arc Routing vs. Node Routing: Why Snow Plowing Is a Different Problem Than Delivery
Delivery trucks visit stops. Snow plows traverse roads. That distinction — node routing versus arc routing — changes everything about how you optimize. Most fleet software gets this wrong.
Greg Dogum · 2026-02-01
When a municipality decides to modernize its snow plow routing, the first instinct is often to reach for the tools that work well for other fleet operations. Delivery companies have spent billions on route optimization. UPS famously reduced miles driven by avoiding left turns. Amazon's logistics engine is a marvel of node-sequencing efficiency. Surely some of that technology transfers to snow plowing?
It doesn't. Not because snow plowing is low-tech or unimportant, but because it's a fundamentally different mathematical problem. The distinction is subtle but consequential, and understanding it explains why snow plow routes are so much harder to optimize — and why most fleet management software produces marginal improvements at best when applied to plowing operations.
The distinction is between node routing and arc routing.
Node routing: the delivery problem
In a delivery operation, you have a set of locations — customers, warehouses, stops — represented as nodes (points) on a map. The routing problem is: which stops does each vehicle visit, and in what order, to minimize total distance or time?
This is the domain of the Traveling Salesman Problem (TSP) and its multi-vehicle extension, the Vehicle Routing Problem (VRP). The vehicle doesn't need to drive down every street in the city. It just needs to reach specific addresses. The roads between stops are incidental — they're the cost of getting from node A to node B, but they're not the work itself.
A delivery driver's route might look like this: leave the warehouse, drive to stop 1, deliver, drive to stop 2, deliver, and so on until the truck is empty, then return to the warehouse. The work happens at the nodes. The travel between nodes is overhead to be minimized. Some stops can be skipped or rescheduled. The driver can choose which streets to take between stops.
This is a well-understood problem class. Exact algorithms can solve small instances optimally. Heuristics and metaheuristics handle large instances efficiently. Commercial platforms like Google OR-Tools, Route4Me, and OptimoRoute solve VRP variants millions of times per day. The industry is mature, competitive, and very good at what it does.
Arc routing: the plowing problem
Now consider a snow plow. The truck doesn't have a list of addresses to visit. It has a network of roads — every road in its service zone — and it must drive down each one with the blade lowered. The work happens on the edges (road segments), not at points. The plow doesn't "visit" an intersection; it traverses the road connecting two intersections.
This changes the problem entirely:
There's nothing to skip. In delivery routing, you can defer low-priority stops, batch nearby deliveries, or drop stops that don't fit the route. In snow plowing, every road must be cleared. The entire network is the assignment. The workload isn't a subset of locations — it's the complete graph of streets.
Direction matters differently. A delivery truck arriving at a customer's address from the north or south doesn't change the service. A snow plow driving a two-lane road must plow both directions — or, more commonly, must plow with traffic, loop around, and plow the return direction. On divided highways, each direction may require separate passes. Researchers have formalized this as the Windy Postman Problem, where traversal costs differ by direction — a variant directly applicable to plowing, as Dussault, Golden, Groër, and Wasil (2013) explored in their work on the Downhill Plowing Problem.
The "overhead" is different. In delivery routing, the time between stops is wasted travel. In arc routing, the analogous waste is deadheading — driving with the blade up between service passes. But deadheading isn't just about choosing the shortest path between two points (which GPS handles trivially). It's about sequencing the edges themselves so that when you finish one road, the next road you need to service is adjacent, minimizing the blade-up transition.
Capacity creates a different structure. A delivery truck runs out of packages. A snow plow runs out of salt. Both must return to the depot to reload. But the optimization implications are different. For a delivery truck, the depot return happens when the stop list is exhausted — it's a clean break between sets of nodes. For a plow, salt depletion happens mid-route through a continuous network of edges. The solver must plan reloading at a point where the truck is near a depot and where resuming service after reloading doesn't create excessive deadhead. This creates a tightly coupled geometric problem that VRP solvers don't model.
Why the computational difference matters
Here's what makes the node-vs-edge distinction so consequential: the base versions of these problems have dramatically different computational complexity.
The Chinese Postman Problem — the simplest arc-routing problem, finding the shortest walk that covers every edge — is solvable in polynomial time for undirected and directed graphs. You can find the optimal solution efficiently. It reduces to minimum-weight perfect matching on odd-degree nodes, as shown by Edmonds and Johnson (1973). The problem was first posed by Guan Meigu in 1960.
The Traveling Salesman Problem — the simplest node-routing problem, finding the shortest tour through all nodes — is NP-hard. No polynomial-time algorithm is known, and most researchers believe none exists.
This is one of the few cases in combinatorial optimization where the arc version is strictly easier than the node version. Euler solved the arc-routing foundation (the Königsberg Bridge Problem) in 1736. The node-routing equivalent remains one of the great open problems in mathematics.
But the moment you add real-world constraints — vehicle capacity, multiple vehicles, priority classes, time windows — the arc problem becomes NP-hard too. The Capacitated Arc Routing Problem (CARP), introduced by Golden and Wong in 1981, is NP-hard. And crucially, it's NP-hard in a different way than VRP, meaning the heuristics, solution structures, and algorithmic toolkits that have been built for decades of node routing research don't transfer. You can't take a VRP solver, feed it edge data reformulated as node visits, and expect good results.
Some researchers have tried transforming CARP instances into VRP instances (by converting each required edge into a "virtual node" at its midpoint). Longo, de Aragão, and Uchoa (2006) showed this is technically possible, but these transformations lose geometric information, inflate the problem size, and produce inferior solutions compared to native arc-routing solvers. The most comprehensive review of CARP solution methods — Corberán et al. (2021) — confirms that purpose-built arc routing algorithms consistently outperform node-routing transformations.
What this looks like in practice
The difference isn't theoretical. It shows up in PlowPath's data every time we compare approaches on a real city.
On Brattleboro, Vermont's road network (1,398 road segments, 2 trucks), a greedy nearest-neighbor heuristic — conceptually similar to what a repurposed delivery router would produce — generates a deadhead ratio of 55.5%. That means more than half of all driving is blade-up repositioning. A proper CARP solver on the same network drops that to 17.6%, and since it drives less overall too, blade-up driving falls from 396 km to 68 km: 83% less wasted driving.
The difference shows up on the map. A naively routed plow produces a GPS trace full of zigzags — the truck crisscrosses its zone, repeatedly driving past unplowed roads to reach a distant one. An optimized route produces a trace that looks almost like a systematic sweep, where consecutive service passes are adjacent and blade-up transitions are short. You can see this visually in PlowPath's gallery, where every city shows both the greedy baseline and the CARP-optimized routes side by side.
The Pittsburgh results from Kinable, van Hoeve, and Smith (2021) make the point even more starkly. Their purpose-built CARP solver — using constraint programming on the city's actual road network — found routes 3–156% shorter than what Pittsburgh was generating with commercial fleet software. That commercial software was almost certainly a VRP-based tool applied to an arc-routing problem.
What this means for municipal software choices
This isn't an academic distinction. It has direct consequences for cities evaluating technology for snow operations.
General-purpose fleet management platforms — Samsara, Verizon Connect, Fleet Complete — provide excellent GPS tracking, driver behavior monitoring, and compliance dashboards. They tell you where your trucks are and what they've done. They don't solve the arc-routing problem. They don't generate optimized edge traversal sequences.
Delivery-focused route optimization platforms — Route4Me, Upper, OptimoRoute — solve VRP variants. They're optimized for "visit these 50 stops in the best order." Some market themselves for snow plowing, but the underlying solver is node-based. When applied to plowing, they treat road segments as stops to visit rather than edges to traverse. This can produce passable results for simple networks but breaks down on complex topologies where sequencing, direction, and continuity matter.
True arc-routing solvers are rarer. Academic implementations exist for CARP — the research literature is extensive — but commercial products that solve CARP on real road networks with full operational constraints are uncommon. Routeware offers optimization as part of its enterprise platform. Research groups at CMU, Iowa State, and elsewhere have published working implementations. PlowPath runs on freely available OpenStreetMap data — but the broader market gap is real. There are far more VRP solvers than CARP solvers available to municipalities.
Where the fields are converging
The good news is that the wall between node routing and arc routing is getting more permeable. Some recent advances are relevant to municipalities:
Hybrid formulations combine arc and node elements. A fleet that does snow plowing and spot-salting intersections has both edge traversal and node visitation in the same problem. Salazar-Aguilar, Langevin, and Laporte (2012) introduced the Synchronized Arc Routing Problem for tandem plowing of multi-lane roads, and newer formulations handle mixed arc-and-node constraints in a single solver.
Learning-based solvers are emerging. A 2024 arXiv paper demonstrated a learning-based CARP solver competitive with traditional metaheuristics — a sign that the deep learning revolution in node routing (which has produced strong TSP and VRP solvers) is beginning to reach arc routing too.
Open data — particularly OpenStreetMap — has made real road networks available as graph data at no cost. This removes the data acquisition barrier that historically made arc routing a specialist domain. Any city's road network can be downloaded, classified by road type, and fed into a CARP solver. PlowPath uses OSM as its sole network data source across every city in the gallery.
Cloud compute has made it practical to run metaheuristic solvers — which benefit from large populations and many iterations — on real-world CARP instances. Problems that would have taken hours on a 2010-era workstation solve in minutes on modern hardware. PlowPath's NSGA-II multi-objective solver, which explores the Pareto frontier of tradeoffs between deadhead distance and workload balance, has mapped that frontier for four of the towns in the gallery so far.
The convergence of open data, cheap compute, and growing awareness of the node/arc distinction is creating an opening for municipalities to adopt real arc-routing optimization — not as a replacement for their fleet management platforms, but as a complementary layer that answers the question those platforms don't: which truck should drive which road, in what order.
PlowPath is a CARP solver built for real road networks. It downloads geometry from OpenStreetMap, classifies edges by priority tier, and produces optimized routes that minimize deadheading. See the results →
References
[1] Golden, B.L. & Wong, R.T. (1981). "Capacitated Arc Routing Problems." Networks 11(3):305–315. DOI: 10.1002/net.3230110308
[2] Edmonds, J. & Johnson, E.L. (1973). "Matching, Euler tours and the Chinese postman." Mathematical Programming 5:88–124. DOI: 10.1007/BF01580113
[3] Guan, M. (1962). "Graphic programming using odd or even points." Chinese Mathematics 1:273–277.
[4] Kinable, J., van Hoeve, W.J., & Smith, S.F. (2021). "Snow Plow Route Optimization: A Constraint Programming Approach." IISE Transactions 53(6):685–703. DOI: 10.1080/24725854.2020.1831713
[5] Corberán, Á., Eglese, R., Hasle, G., Plana, I., & Sanchis, J.M. (2021). "Arc Routing Problems: A Review of the Past, Present and Future." Networks 77(1):88–115. DOI: 10.1002/net.21965
[6] Dussault, B., Golden, B., Groër, C., & Wasil, E. (2013). "The downhill plow problem with multiple plows." Journal of the Operational Research Society 64:1084–1092. DOI: 10.1057/jors.2013.83
[7] Salazar-Aguilar, M.A., Langevin, A., & Laporte, G. (2012). "Synchronized arc routing for snow plowing operations." Computers & Operations Research 39(7):1432–1440. DOI: 10.1016/j.cor.2011.08.014
[8] Longo, H., de Aragão, M.P., & Uchoa, E. (2006). "Solving capacitated arc routing problems using a transformation to the CVRP." Computers & Operations Research 33(6):1823–1837. DOI: 10.1016/j.cor.2004.11.008
[9] Eiselt, H.A., Gendreau, M., & Laporte, G. (1995). "Arc Routing Problems, Part I: The Chinese Postman Problem." Operations Research 43(2):231–242. DOI: 10.1287/opre.43.2.231
[10] Iowa DOT Office of Maintenance. "Snowplow Optimization." InTrans Project 17-626, Iowa State University. rosap.ntl.bts.gov