Wayfair Tech Blog

Utilizing Piecewise Linear Approximations – With a Twist – to Make Supply Chain Decisions

Global Network Optimization allows Wayfair to make strategic decisions about the company's supply chain.

The annual conference for the Institute for Operations Research and the Management Sciences (INFORMS) brings together professionals and experts from the industry and academia. At INFORMS 2022, I will be giving a presentation on Global Network Optimization (GNO), which is an ongoing project carried out by Wayfair’s operations research team.

GNO allows Wayfair to make timely and strategic decisions related to our transportation network. To give just one example, Wayfair utilizes GNO to make an informed decision on the optimal location for a new facility by considering factors like the total network cost and impact on shipping times.

We also utilize GNO to determine the most optimal shipping route to get a product from the supplier to the end customer. Historically, every supplier within Wayfair was assigned to a middle mile facility called the “pool point.” Products are then sent from the supplier to pool points, from where they are dispatched to cross docks. This stage marks the transition to last mile facilities called home delivery operation (HDO) centers, from where they are delivered to customer residences.

Wayfair has over 30 million customers – and the number is growing. As we add more transportation centers to meet this increasing demand, we need to quickly optimize the pairings between suppliers and middle mile facilities, as a decision made to assign a supplier to a particular center might get out of date very quickly. The GNO tool solves this problem by allowing Wayfair to look at the entire network holistically and make decisions related to the transportation network in near-real-time. What’s particularly interesting about GNO is the sophisticated optimization model that is driving the engine.

Multi-commodity flows – with a twist.

Broadly speaking, GNO utilizes the multi-commodity flow model. At their essence, multi-commodity flow models are used to solve optimization problems where the network has defined capacities for every edge (in our case this would refer to available routes and associated costs) along with a distinct set of commodities (products) that must be transported through the network – which is what makes it a “flow model”. The goal of the multi-commodity flow model is to solve for a feasible flow considering all capacity constraints.

The optimization solver we use to solve this problem utilizes an approach called mixed integer linear programming, which is widely used in operations research. From a mathematical perspective, mixed integer linear solvers operate over real numbers (fractions and integers), and equations used to solve problems are restricted to linear equalities and inequalities.

Imagine that you have to send a certain number of items between two cities. We have to now decide how we want to best ship items between different nodes in the network. Each route is associated with a particular set of costs. For a traditional multicommodity flow model, the costs would be directly proportional to the number of items that are being shipped.

However, a solver that utilizes a linear relationship between shipping and number of items shipped wouldn’t be apt for Wayfair’s use case. Consider having to move 50 items versus 200 items between two cities. In the latter case, having a greater number of items means that we could run more trucks along that route, effectively leading to a reduction in the shipping time.

We experimented with a variety of approaches to solve this problem that is essentially non-linear at its core. We utilized simple nonlinear functions such as quadratic to capture non-linear relationships between variables. These approaches didn’t yield the accuracy and solve times we wanted.

We ultimately found success by utilizing piecewise linear approximations to fit a nonlinear objective function. As the name suggests, piecewise linear approximations approximate a complicated function to multiple simpler ones. This effectively means that every continuous piece of the model needs to be aligned – however you are allowed to have multiple discrete pieces that aren’t connected to each other. The piecewise linear approximation approach has delivered accurate results in terms of capturing the inverse relationship between variables such as shipping volume and speed.

The GNO tool is proving to be effective in helping us design and adapt our transportation network to help get products to customers in both a timely and cost-effective manner. Given the complexity and scale of our operations, making complicated decisions related to supply chain optimization could take as long as 24 hours previously. With GNO, we can make those same decisions in less than thirty minutes.

On a personal level, this project has been particularly meaningful to me. I was always drawn to Math even at school – particularly the practical aspects that allowed people to make the best decisions given all the available information. I am grateful that I now have the opportunity to solve problems utilizing this mental model at Wayfair, and make a real-world impact on the lives of millions of people around the world.