Network Flow problems: a clever approach with sql server

By: Christopher Waldeck

Fair Warning: This article assumes a working knowledge of Linear Programming and SQL

Maybe you're just jumping into the business world, and you've found that no one in your organization has heard of GAMS or LINDO. Maybe you're finding that Excel can't handle the matrices you're trying to build, or that a custom-made approach to building your matrices will be a large project that won't scale well to different applications.

An entry-level approach to building transportation networks involves plugging distances between supply, demand, and transshipment nodes into a matrix, the costs of traveling those arcs into an objective function, and then some constraint equations that restrict the values of certain variables.

Generally, the better you are at formulating these problems, the simpler the constraints can be, and the easier they are to solve. However, a few textbook examples show how, even in simple cases, the matrices grow as the networks' complexity increases. Scaling that up to, say, an enterprise-grade logistics network with tens of thousands of supply, transshipment, and demand nodes, it is clear that even setting up the distance matrix could become an insurmountable task.

If you try to offload spatial problems onto an analysis platform like R or Python, you'll likely find that all the tools you want to use were created in different packages or libraries. Keeping spatial data usable and comparable across different packages can mean building translations to different map projections, data structures (e.g. spatial data frames), and more to utilize the functions you want to apply.

However, a little celebrity appearance by SQL Server can take a huge bite out of the work that often proves most tedious when deploying this kind of work on an enterprise scale.

the sql server solution​

As I've said before, I love SQL Server because it has a flavor for every budget, including free. SQL Server's unique distance functions offer an easy way to dynamically fill out the distance matrix. Replacing the tedious process of having data entry interns estimating distances and filling out huge matrices (or, the more common approach: Just not solving the problem at all) with this automated implementation is a classic case of making  computers work for your organization rather than the other way around.

step one: Finding Lat-Longs

Google Places API makes it very easy to tag locations with lat-long coordinates​. Obviously, the API can be used with traditional languages, and the API is flexible enough to accommodate a few use scenarios (searching by address, searching by place name, etc.). R users should check out this post to implement it. Consider running this tagging for your data set in chunks each night to get around the API's 2500 query limit.

R Example: Google API via ggmap

Step two: sql server geography

​Once you've gotten lat-longs from Google, use the T-SQL below to convert them to Geography datatypes and calculate distances between all the points.

TSQL: Set up geography column & Retrieve point-to-point distances

​Note that I divided by a decimal when converting my distances from meters to miles. It is good SQL practice to always multiply and divide by a decimal, even if it's [Some Number].0, to avoid an accidental integer casting. This is especially dangerous since it can mess with calculations and will not throw an error or warning.

The results are saved to #temp and referenced below. 

step three: Select the Solution

At this point, you have a couple of options. You can pivot the solution to create a traditional matrix, or you can just directly apply your constraints and costs to the results above, aggregate them, and order the answers to give you the lowest-cost options. This should almost always be the easiest solution, since all the metadata is still attached to the nodes.

If you're after a traditional matrix, I suggest the following approach, which borrows the dynamic SQL code you can find here. 

Dynamic Matrix Selection

wrap up

There you have it! A quick way to populate the distance matrix that can easily be incorporated with the rest of many network problems for a direct solution.

With just a few extensions (and some heuristics), it's an easy task to take the weight of setting up and formulating your problems off of your shoulders and put it on SQL Server's Query Optimizer!