How to build a custom order fulfillment decision model with MIP and Nextmv

You need something, but you don't have time to visit a local store to get it. Whether that's toothpaste, a pair of dress pants, or a present for a friend's upcoming birthday you almost forgot about — we've all been there. One solution to such a need is to visit your favorite online shop and place an order. With a simple click of a button at the checkout, peace sets in your mind, knowing that you will receive a package very soon with your order.

But how does this process work? How does your order go from button click to front door delivery? The answer: order fulfillment.

Order fulfillment describes the logistical and organizational process of fulfilling orders — from order placement to delivery confirmation. Along the way, several steps unfold: order processing, verification, quality control, and shipment. At each step, there are various decisions that need to be made.  

In this blog post, we're going to focus on two such decisions related to fulfillment center and delivery carrier selection. But before we dive into a specific example of how this could be solved with Nextmv, let's look at some of the basics for this problem. What are we deciding on? What are we optimizing? What are constraints in regard to this decision?

If you’d like to follow along with the tutorial in this post, all you need is a free Nextmv account and the code in our demo GitHub repo.

What are our order fulfillment decisions?

As mentioned above, we’re focusing on automating two decisions in our order fulfillment process with Nextmv: 

1. Which fulfillment center should orders be retrieved from?
2. Which carrier should be selected to deliver orders?

For this example, we’ll assume our retailer has tens of thousands of items available for purchase and these items are stocked at several fulfillment centers. 

Let’s consider our first decision. An order consists of a single or of multiple order lines, where each of the order lines is defined by a specific item and an ordered quantity. We’ll also assume that each center has a subset of all the items in the retailer’s catalog, but inventory, or the quantity of specific items, can also vary across each center depending on its size. 

Now, to our second decision. Each item retrieved from a fulfillment center needs a carrier to deliver it to the customer. At each fulfillment center, there might be multiple carriers to choose from, each with their own cost structure. 

What are we optimizing for?

Optimization is the process of minimizing, maximizing, or satisfying some constraints. For order fulfillment use cases, this might be minimizing the costs for an allocation of the ordered items to fulfillment centers,minimizing the time to the completion of the delivery, maximizing customer satisfaction, some other optimization goal or even a mixture of different optimization goals

We'll keep things simple with our example and seek to minimize the cost for fulfilling an order across our two decisions: fulfillment center and carrier selection.

For center selection, costs can include the labor cost for a picker to retrieve an item, the material cost for the box it's packaged into, overhead costs for maintaining the fulfillment center, and more. This list can become quite extensive, so for this example, we'll only consider a total cost.

For carrier selection, costs can vary based on how each carrier computes delivery cost based on box dimensions, box weight, box quantity, and the distance to the delivery address.

Our objective in this post is to find an allocation that minimizes the costs for handling and delivering orders. 

What are our order fulfillment constraints?

Although business rules can be very specific for each operation, there are some common constraints that we can consider in this example:

Fulfillment constraint
This constraint ensures the fulfillment of the order. We will consider this as a hard constraint, meaning our solution needs to have all items from the order assigned. This, of course, simplifies this problem as there might be situations where an order line can only be fulfilled partially or not at all. How to model this with Nextmv is reserved for a future post. 

Inventory constraint
This constraint ensures that for every assigned fulfillment center we only take out the amount of items that are available according to the given inventory. As described earlier, each fulfillment center has a specific inventory at the time of the order. Depending on the items and the business, inventory fluctuations can be dynamic. A selected assignment of the items can only use the amount at a facility that is really available. Anything above that is not possible. We assume that our input always has enough total inventory over all fulfillment centers for each item.

Carrier capacity constraint
This constraint ensures that each carrier doesn’t overcommit to more orders than it has capacity for. Each carrier has a limited capacity to transport the boxes to the customer. This limitation might be due to a contractual agreement or to an estimation of how many boxes the carrier can take on a typical day.

How to build an order fulfillment decision model

Let's create a model for our order fulfillment decisions. The Nextmv platform has two options to create such a model: We can use a mixed integer programming (MIP) modeling approach or a decision diagram approach via our store framework. In this case, let's take the MIP approach. The full model will be available in our demo repository.

In the previous section, we defined domain specific objects like fulfillment centers, carriers and order lines, what the objective function should look like and what kind of constraints we need in our model. Now this needs to be transferred into code. With the Nextmv SDK, this is straightforward.

Step 1: Initialize a decision template

Let's start with initializing the ^mip-knapsack template. (Note: You’ll need to have Nextmv installed. Get started with a free account in minutes.) For this, we open the terminal and use Nextmv's CLI to initialize the template.

nextmv sdk init -t mip-knapsack

This template gives us a good starting point for our order fulfillment model. It shows you how to create decision variables for our model as well as constraints and the objective function — all the building blocks we need to customize this template to our use case. 

Step 2: Customize the decision template

We're going to look at this decision problem as a set partitioning problem, meaning that we take the items of the order and partition them into smaller subsets. Each subset defines a tuple of item, fulfillment center, and carrier. The solution will tell us which of these subsets should be selected in order to fulfill the order, while still considering all of the constraints.

Based on this modeling approach, we need to modify or add the following items:

• We need something that generates the set of assignments from which the solver should select a solution. The size of this set will determine the runtime of the solver as it directly affects the number of decision variables to consider. In this blog post, the assignment generation will look at all possible combinations for order line, fulfillment center and carriers.
• We need to create a boolean (or binary) decision variable for each of these possible assignments. This variable tells us whether an assignment is selected or not. If it is selected, it will also be used to check the constraints and to compute the objective function.
• We need to adjust the objective function to make use of the newly created decision variables. We also need to determine the handling cost term and the delivery cost term.
• We need to add the three constraints that we discussed earlier (fulfillment, inventory, carrier capacity)

Let's dive into the code. We can keep the general structure of the ^main.go file. 

Step 3: Modify the input and output schema

Next, we're going to modify the input schema. Go ahead and change the input struct to this one:

type input struct {
  Items               []item                         `json:"items"`
  WeightCapacity      int                            `json:"weightCapacity"`
  FulfillmentCenters  []fulfillmentCenter            `json:"fulfillmentCenters"`
  CarrierCapacities   map[string]map[string]float64  `json:"carrierCapacities"`
  DeliveryCosts       map[string]map[string]float64  `json:"deliveryCosts"`
  BoxVolume           float64                        `json:"boxVolume"`
}

Furthermore, we create a new struct called ^assignment. This will hold the information of a single assignment that can be selected by the solver. Let's add this to the model just underneath the input struct:

type assignment struct{
    Item		item				`json:"item"`
    FulfillmentCenter	fulfillmentCenter		`json:"fulfillmentCenter"`
    Carrier		string				`json:"carrier"`
    Quantity		int				`json:"quantity"`
}

Finally, as the output will also look different from the knapsack problem, we can replace the output struct with the following code:

type Output struct {
    Status		string			`json:"status,omitempty"`
    Runtime		string			`json:"runtime,omitempty"`
    Items		[]item			`json:"items,omitempty"`
    Value		float64			`json:"value,omitempty"`
    Assignments		[]assignment		`json:"assignments"`
    Boxes		map[string]float64	`json:"boxes"`
}

You can also see that we’re using a couple of other objects like ^{fulfillmentCenter} and ^item. Let’s define those structs as well and we will also add a couple of ^ID functions, which we require for some of the constructs of our MIP framework.

type item struct {
	ItemID    	string 		`json:"itemId"`
	Quantity	float64		`json:"quantity"`
	Volume   	float64   	`json:"volume"`
}

func (i item) ID() string {
    return i.ItemID
}

type fulfillmentCenter struct{
	FulfillmentCenterId	string 		`json:"fulfillmentCenterId"`
	Inventory		map[string]int	`json:"inventory"`
	HandlingCost		float64		`json:"handlingCost"`
}

func (i fulfillmentCenter) ID() string {
    return i.FulfillmentCenterId
}

type carrier struct{
	FulfillmentCenter	fulfillmentCenter		`json:"fulfillmentCenter"`
	Carrier			string    			`json:"carrier"`
}

func (i carrier) ID() string{
    return i.FulfillmentCenter.FulfillmentCenterId + "-" + i.Carrier
}

Step 4: Define the assignment generator

For this, we create a new function that returns a list of assignment structs, describing tuples of order line, fulfillment center, and carrier. You can add this function right above the solver function:

func computeAssignments(input input) []assignment{
    assignments := []assignment{}
    for _, it := range input.Items{
   	 for _, fc := range input.FulfillmentCenters{
   		 for c := range input.CarrierCapacities[fc.FulfillmentCenterId]{
   			 for q := 0; q < int(it.Quantity); q++{
   				 newAssignment := assignment{
   					 Item: it,
   					 FulfillmentCenter: fc,
   					 Carrier: c,
   					 Quantity: q+1,
   				 }
   				 assignments = append(assignments, newAssignment)
   			 }
   		 }
   	 }
    }
    return assignments
}

Let's call this function from the solver function to get a list of assignments.

assignments := getAssignments(input)

Now let's look at the decision variables. They are defined with a multimap data structure just like you can see in the template. We’re creating two types of variables for our model:

• ^x will be used to determine whether an assignment is selected for the solution
• ^boxes will be used to compute the number of boxes used for each fulfillment center - carrier combination

x := model.NewMultiMap(
	func(...assignment) mip.Bool{
		return m.NewBool()
   	 }, assignments)

boxes := model.NewMultiMap(
   	 func(...carrier) mip.Float{
   		 return m.NewFloat(0.0, 1000.0)
   	 }, fulfillmentCenterCarrierCombinations)

^{fulfillmentCenterCarrierCombinations} refers to a data structure that we use to store all the available combinations of fulfillment center and carrier. You can access the full code of this example in our demo repository. There you will also see how we created this and other helpful data structures for this model.

Directly below these multimaps comes the definition of the sense of the objective function. In the knapsack template this is maximize, as you want to maximize the value of the items in your knapsack. Here, in our order fulfillment model, we want to minimize the costs. So let's switch that:

m.Objective().SetMinimize()

Step 5: Codify the constraints

Next let's start defining the constraints. First the fulfillment constraint. Our input data contains the items that have been ordered and that need to be considered for this. This constraint should state that when you look at all selected assignments, the total selected quantity of an item should be equal to the ordered quantity of this item. That means we create this constraint for every item in the order:

for _, i := range input.Items{
	fulfillment := m.NewConstraint(
		mip.Equal,
		i.Quantity,
	)
	for _, a := range itemToAssignments[i.ItemID]{
		fulfillment.NewTerm(float64(a.Quantity), x.Get(a))
	}
}

The next constraint is the inventory constraint. Here, we're looking at each fulfillment center and the inventory of the ordered items. The total quantity of an item at a fulfillment center, given by the selected assignments, should not be higher than the available inventory.

for _, i := range input.Items{
	for _, fc := range input.FulfillmentCenters{
 		inventory := m.NewConstraint(
 			mip.LessThanOrEqual,
			float64(fc.Inventory[i.ItemID]),
		)
 		for _, a := range itemToAssignments[i.ItemID]{
  			if a.FulfillmentCenter.FulfillmentCenterId == fc.FulfillmentCenterId{
   				inventory.NewTerm(float64(a.Quantity), x.Get(a))
   			}
   		}
  	}
}

The next constraint for this model should be the carrier capacity constraint. With this we want to make sure that we don't exceed the capacity of the carrier that is selected at a fulfillment center:

for fcId, v := range fulfillmentCenterToCarrierToAssignments{
    for cId, list := range v{
   	 carrier := m.NewConstraint(
   		 mip.LessThanOrEqual,
   		 input.CarrierCapacities[fcId][cId],
   	 )
   	 for _, as := range list{
   		 carrier.NewTerm(as.Item.Volume * as.Item.Quantity, x.Get(as))
   	 }
    }
}

Step 6: Codify the objective function

The last part of the model is now the objective function, which consists of a term for the handling costs and a term for the delivery costs for every assignment. These costs are based on the number of boxes necessary to package up the assigned items at a fulfillment center. Before we define the objective function, we define another constraint to compute the number of boxes:

for _, fc := range fulfillmentCenterCarrierCombinations{
    boxConstr := m.NewConstraint(
   	 mip.Equal,
   	 0.0,
    )
    boxConstr.NewTerm(-1, boxes.Get(fc))
    for _, a := range assignments{
   	 if a.FulfillmentCenter.FulfillmentCenterId  == 
		fc.FulfillmentCenter.FulfillmentCenterId && 
		a.Carrier == fc.Carrier{
   		 boxConstr.NewTerm(a.Item.Volume * float64(a.Quantity) * 
			1/input.BoxVolume, x.Get(a))
   	 }
    }
}

Now we can add the objective function:

for _, combination := range fulfillmentCenterCarrierCombinations{
	// delivery costs    
	m.Objective().NewTerm(
		input.DeliveryCosts[combination.FulfillmentCenter.FulfillmentCenterId]
    		[combination.Carrier], 
		boxes.Get(combination)
	)   	 

	// handling costs
    	m.Objective().NewTerm(
		combination.FulfillmentCenter.HandlingCost, 
		boxes.Get(combination)
	)
}

Finally, let's replace the output format function so that we now can read our order fulfillment result when we solve this model.

func format(
    solution mip.Solution,
    input input,
    x model.MultiMap[mip.Bool, assignment],
    assignments []assignment,
    carriers []carrier,
    boxes model.MultiMap[mip.Float, carrier],
) (output Output, err error) {
    output.Status = "infeasible"
    output.Runtime = solution.RunTime().String()

    if solution != nil && solution.HasValues() {
   	 if solution.IsOptimal() {
   		 output.Status = "optimal"
   	 } else {
   		 output.Status = "suboptimal"
   	 }

   	 output.Value = solution.ObjectiveValue()

   	 assignmentList := make([]assignment,0)
   	 for _, assignment := range assignments {
   		 if solution.Value(x.Get(assignment)) > 0.5{
   			 assignmentList = append(assignmentList, assignment)
   		 }
   	 }

   	 output.Assignments = assignmentList

   	 output.Boxes = make(map[string]float64)
   	 for _, c := range carriers{
   	 output.Boxes[c.FulfillmentCenter.FulfillmentCenterId+"-"+c.Carrier] 
       	 = solution.Value(boxes.Get(c))
   	 }
    } else {
   	 return output, errors.New("no solution found")
    }

    return output, nil
}

Let’s solve an order fulfillment example

Now that we have defined our model, we can take a look at an example. You will also find this example in our demo repository if you want to test this on your own. 

The example consists of a small purchase order of five items: books, sneakers, hydrating gel, a pressure cooker, and a mattress. Each of these items has a specific quantity ordered as well as a specific volume. Furthermore, we have two fulfillment centers: fc1 and fc2. For both, we know the inventory and we also know the cost for handling one box at that facility. Finally, our input contains carrier related information like the available capacity (in volume) as well as the delivery cost for a single box. 

With the model we defined before, we can now solve this example and determine which fulfillment center we should use as well as which carrier we should use to fulfill this purchase order. Thanks to our output definition we will find this information in the output file. 

The first thing you will notice in the output file are the run statistics: This example was solved to optimality in a matter of milliseconds. We also get the objective value of this solution, which tells us the cost associated with the assignments in our solution. After this, we come to two sections that describe our solution in more detail: ^assignments and ^boxes.

The section ^assignments contains all the assignments that have been selected by the solver for the solution of this example. For each of these assignments, you can see which item it relates to as well as the selected fulfillment center, the selected carrier and the assigned amount of the item to this fulfillment center. As it might be the case that we have to split items over multiple fulfillment centers to get to the total ordered quantity, we also need to figure out how much of each item should be handled at each assigned fulfillment center.

The section ^boxes contains an overview of the number of required boxes for each fulfillment center - carrier combination. As we’re only considering one type of box (defined by its volume), we might get a fractional value in this section for the number of boxes required. Ways on how this is handled in an actual operation are numerous and each one would require a more customized model than what we show here in this demo. 

Try it out yourself

Everything I’ve demonstrated in this blog post is something you can do with Nextmv for free on your local machine. Simply create a free Nextmv account, follow the quick installation steps, and reference the code in our public GitHub repo.  

If you’re new to this space or just want to talk with folks who have solved these kinds of problems, feel free to reach out to us to talk.