Microsoft Solver Foundation – Distribution network optimization

Microsoft Solver Foundation – Distribution network optimization

 

Purpose: The purpose of this document is to illustrate how to use Microsoft Solver Foundation in order to resolve Distribution network optimization problem.

 

Challenge: Distribution network optimization problem is a typical problem in Supply Chain Optimization domain. This problem is especially important in Manufacturing, Distribution and Retail environments with Transportation management needs. For example, many companies procure products to distribution centers and distribute these products to retail stores or customers. A natural question is "What is the least expensive way to procure products into distribution centers with certain capacity and then distribute these products to retail stores or customers and still meet demand?" Please review some of scenarios where Distribution network optimization applies

 

Scenario 1 – Retailer/Distributor:

<![if !supportLists]>-        <![endif]>Buy products from vendors to distribution center

<![if !supportLists]>-        <![endif]>Distribute products from distribution center to stores

<![if !supportLists]>-        <![endif]>Sell products to customers from stores

 

Scenario 2 – Manufacturer/Supplier:

<![if !supportLists]>-        <![endif]>Produce parts at manufacturing facilities

<![if !supportLists]>-        <![endif]>Distribute parts from manufacturing facilities to assembly plants

<![if !supportLists]>-        <![endif]>Consume parts at assembly plants to produce finished product

 

Scenario 3 – Manufacturer/Retailer:

<![if !supportLists]>-        <![endif]>Produce finished products at manufacturing facilities

<![if !supportLists]>-        <![endif]>Distribute finished products from manufacturing facilities to stores

<![if !supportLists]>-        <![endif]>Sell finished products to customers from stores 

 

Please find more info about Supply Chain Optimization here: http://en.wikipedia.org/wiki/Supply_chain_optimization

 

Solution: The classic supply chain approach has been to try to forecast future inventory demand as accurately as possible by applying statistical techniques based on historic demand. Then, using this forecast demand, a supply chain manufacturing and distribution plan is created to manufacture and distribute products to meet this forecast demand at lowest cost (or highest profitability)

In this walkthrough we'll utilize the power of Microsoft Excel and Microsoft Solver Foundation in order to resolve Distribution network optimization problem. Speaking mathematical language our objective is to find a least cost shipping schedule that meets requirements at sources of demand and supplies at sources of supply. The mathematical model for this task will look like following:

 

 

where Cij – transportation cost per inventory unit between points i and j, Xij – volume of inventory to be distributed between points i and j, Dj – demand requirement at point j, Si – supply capacity at point i  

 

During the course of this walkthrough we'll build mathematical model to resolve the task using Microsoft Solver Foundation Add-in for Excel. And then upon resolution we'll visualize results using Bing Maps App and Power Map in Excel. I also assume that the initial data set for analysis (Supply and demand profiles) can be retrieved from Microsoft Dynamics AX 2012 using Web Services

 

Please note that for modeling using Microsoft Solver Foundation Add-in in Excel you will not need strong development skills. For mathematical modeling I'll be using very intuitive OML (Optimization Modeling Language). Please find detailed OML reference here: http://msdn.microsoft.com/en-us/library/ff524507(v=vs.93).aspx 

 

Walkthrough

 

Before we begin I will install Microsoft Solver Foundation Add-in for Excel

 

You can download it from Microsoft Solver Foundation product web site here: http://msdn.microsoft.com/en-us/devlabs/hh145003

Now let's start with formalization of the problem in Excel

 

Initial representation of the task

 

 

Thus our first matrix defines Cij - transportation costs per inventory unit between points i and j. On the left hand side (i) we have distribution centers (LA, ATL, NYC) and at the top (j) we have our regions to be covered, or in the context of our scenario it could be particular stores (EAST, MIDWEST, SOUTH, WEST)

 

For the sake of simplicity my matrix is only 3x4, but in general case obviously you may have many more distribution centers and stores (NxM)

 

The second matrix describes Xij – volumes of inventory to be distributed between points i and j. This is exactly what we want to calculate as the result

 

Also please note that in Excel workbook I included demand requirements (DEMAND = Dj) at stores and supply constraints (CAPACITY = Si) at distribution centers  

 

Now let's prepare the data for mathematical modeling and present it as a list

 

Simplified representation of the task

 

 

Please note that I just introduced the list underneath 2 initial matrices

 

 

In this list I added SRC and DST numeric fields to substitute SOURCE and DESTINATION literal fields respectively for convenience of math modeling

 

Now let's start building Microsoft Solver Foundation model

 

First off we'll introduce appropriate sets to represent from (i) and to (j) points 

 

Sets - SRC

 

 

Sets - DST

 

 

All is very simple: SRC = Source, DST = Destination

 

Then we'll add parameters. In particular something given to us is Cij – transportation costs between points i and j

 

Parameters - COST

 

 

This info resides in Excel workbook, that's why we'll bind math model parameter COST to appropriate cells in Excel workbook

 

Binding Editor - COST

 

 

And this is how you specify Table/Range in Binding Editor. Please note how we define Cij: i = SRC, j = DST and value field itself is COST

 

Excel workbook - COST

 

 

COST[SRC, DST] = Cost of shipment/transportation from Source to Destination per Lb., for example

 

The next step is to define the decision. For this task our goal is to calculate optimal Xij – volumes of shipments between Source and Destination. That's why we can now define SHIPMENT[SRC, DST] as below

 

Decision - SHIPMENT

 

 

Similarly we can bind SHIMPENTS[SRC, DST] to Excel workbook cells which will display the results for us

 

Binding Editor

 

 

Please note that I still use the same selection for Table/Range. This time I just mapped Value field to SHIPMENTS column

 

Excel workbook

 

 

SHIPMENT[SRC, DST] = Volume (Lbs.) of shipment from Source to Destination

 

We have mapped COST and SHIPMENTS columns by now which is enough to define the optimization criteria. In fact we want to calculate SHIPMENTS[SRC, DST] – volumes of shipments between Source and Destination in order to MINIMIZE Total Transportation Cost

For this purpose we'll define the goal as below

 

Goal - TOTALCOST

 

 

Expression – TOTALCOST

 

Sum[{i, SRC}, {j, DST}, COST[i, j]*SHIPMENTS[i,j]]

 

Please note that we calculate TOTALCOST as a sum of COST[SRC, DST] x SHIPMENTS[SRC, DST] for all pairs of Source and Destination. Essentially this can be represented with pseudo-code below

 

Pseudo-code - TOTALCOST

 

for (i = 0; i < N; i++) {     for (j=0; j < M; j++)     {         TOTALCOST += COST[i, j] x SHIPMENTS[i, j];     } }

 

As you can see OML is a very intuitive, easy to use and laconic language. You should not necessarily be a developer write OML constructs, in fact Business Analysts and Power Users in your organization may be very proficient in OML

 

Please find OML reference (SUM function) here: http://msdn.microsoft.com/en-us/library/ff818513(v=vs.93).aspx

 

The goal is to minimize the cost of shipments/transportation and satisfy demand requirements

 

To complete the model we'll need to introduce appropriate constraints

 

For the sake of simplicity first I will represent required constraints in a very straightforward manner

 

Constraints

 

 

Expression

 

SHIPMENTS[0,0]+SHIPMENTS[0,1]+SHIPMENTS[0,2]+SHIPMENTS[0,3]<=10000

SHIPMENTS[1,0]+SHIPMENTS[1,1]+SHIPMENTS[1,2]+SHIPMENTS[1,3]<=12000

SHIPMENTS[2,0]+SHIPMENTS[2,1]+SHIPMENTS[2,2]+SHIPMENTS[2,3]<=14000

SHIPMENTS[0,0]+SHIPMENTS[1,0]+SHIPMENTS[2,0]>=9000

SHIPMENTS[0,1]+SHIPMENTS[1,1]+SHIPMENTS[2,1]>=6000

SHIPMENTS[0,2]+SHIPMENTS[1,2]+SHIPMENTS[2,2]>=6000

SHIPMENTS[0,3]+SHIPMENTS[1,3]+SHIPMENTS[2,3]>=13000

 

As you can see I defined number of constraints one by one with hard-coded values on the right hand side. First 3 constraints represent Distribution centers capacity constraints, and the last 4 – Stores demand requirements

 

Let's leave these constraints as they are for now and review the entire model

 

Model

 

 

OML

 

Model[   Parameters[     Sets[Any],     SRC,     DST   ],   Parameters[     Reals[-Infinity, Infinity],     COST[SRC, DST]   ],   Decisions[     Reals[0, Infinity],     SHIPMENTS[SRC, DST]   ],   Constraints[     Constraint1 -> SHIPMENTS[0,0]+SHIPMENTS[0,1]+SHIPMENTS[0,2]+SHIPMENTS[0,3]<=10000,     Constraint2 -> SHIPMENTS[1,0]+SHIPMENTS[1,1]+SHIPMENTS[1,2]+SHIPMENTS[1,3]<=12000,     Constraint3 -> SHIPMENTS[2,0]+SHIPMENTS[2,1]+SHIPMENTS[2,2]+SHIPMENTS[2,3]<=14000,     Constraint4 -> SHIPMENTS[0,0]+SHIPMENTS[1,0]+SHIPMENTS[2,0]>=9000,     Constraint5 -> SHIPMENTS[0,1]+SHIPMENTS[1,1]+SHIPMENTS[2,1]>=6000,     Constraint6 -> SHIPMENTS[0,2]+SHIPMENTS[1,2]+SHIPMENTS[2,2]>=6000,     Constraint7 -> SHIPMENTS[0,3]+SHIPMENTS[1,3]+SHIPMENTS[2,3]>=13000   ],   Goals[     Minimize[       TOTALCOST -> Annotation[Sum[{i, SRC}, {j, DST}, COST[i, j]*SHIPMENTS[i,j]], "order", 0]     ]   ] ]

 

Essentially this model is all you need to resolve Distribution network optimization problem we initially formulated. And this is exactly what we are going to do right now

 

Log

 

 

Log

 

[11/9/2013 12:12:14 AM] Solve started... [11/9/2013 12:12:14 AM] Excel: 00:00:00.0796462 [11/9/2013 12:12:15 AM] ===Solver Foundation Service Report=== Date: 11/9/2013 12:12:15 AM Version: Microsoft Solver Foundation 3.0.2.10889 Express Edition Model Name: DefaultModel Capabilities Applied: LP Solve Time (ms): 119 Total Time (ms): 254 Solve Completion Status: Optimal Solver Selected: Microsoft.SolverFoundation.Solvers.SimplexSolver Algorithm: Primal Arithmetic: Hybrid Variables: 12 -> 12 + 8 Rows: 8 -> 8 Nonzeros: 36 Eliminated Slack Variables: 0 Pricing (exact): SteepestEdge Pricing (double): SteepestEdge Basis: Slack Pivot Count: 7 Phase 1 Pivots: 6 + 0 Phase 2 Pivots: 1 + 0 Factorings: 5 + 1 Degenerate Pivots: 1 (14.29 %) Branches: 0 ===Solution Details=== Goals: TOTALCOST: 86800   [11/9/2013 12:12:15 AM] Solve Complete

 

When you solve the model you will see the outcome as shown above

 

Please note that the system provides the solution and details of the algorithm which has been chosen to resolve the task. On the Solver Foundation Results tab you can now see optimal values of SHIPMENTS[SRC, DST]

 

Result

 

 

You remember that we initially represented our constraints explicitly one by one and using hard-coded values. As the next step let's explore the power of OML further by simplifying our model and rewriting constraints in a more generic way. Specifically we'll rewrite our constraints doing data aggregation in OML. So this time we'll represent our constraints implicitly reducing the size of OML model

 

Excel workbook

 

 

As you can see I added 2 more tables in a right bottom corner of Excel workbook. These tables represent capacity constraints at Distribution centers and demand requirements at Stores correspondingly

 

Now I can also define capacity constraints at Distribution centers and demand requirements at Stores as Parameters in my model as below

 

Parameters - CAPACITY

 

 

Binding Editor - CAPACITY

 

 

Excel workbook - CAPACITY

 

 

Please note that I define CAPACITY as Parameter the same way as I defined COST initially. Next I will repeat the same exercise for DEMAND Parameter

 

Parameters - DEMAND

 

 

Binding Editor - DEMAND

 

 

Excel workbook - DEMAND

 

 

We have now defined CAPACITY and DEMAND Parameters which can be used in Constraints definition. This time we will shrink number of constraints to 2 and make then generic

Our first constraint will represent capacity constraints at Distribution centers as shown below

 

Constraints - SENTCAPACITY

 

 

Expression - SENTCAPACITY

 

Foreach[{x,SRC},Sum[{z, DST}, SHIPMENTS[x,z]]<=CAPACITY[x]]

 

Here I use Foreach clause to iterate through the list of Sources and check that we don't exceed appropriate capacity. Please find OML reference (Foreach) here: http://msdn.microsoft.com/en-us/library/ff818500(v=vs.93).aspx

 

Then I also need to define demand requirements constraint for Stores not to exceed declared demand there

 

Constraints - RECEIVEDDEMAND

 

 

Expression - RECEIVEDDEMAND

 

Foreach[{y,DST},Sum[{z, SRC}, SHIPMENTS[z,y]]>=DEMAND[y]]

 

And again I use OML Foreach clause to iterate through the list of Stores making sure that we don't exceed declared demand. Please find OML reference (Foreach) here: http://msdn.microsoft.com/en-us/library/ff818500(v=vs.93).aspx

 

Now our enhanced model will look like this

 

Model

 

 

Expression

 

Model[   Parameters[     Sets[Any],    DST,     SRC   ],   Parameters[     Reals[-Infinity, Infinity],     DEMAND[DST],     COST[SRC, DST],     CAPACITY[SRC]   ],   Decisions[     Reals[0, Infinity],     SHIPMENTS[SRC, DST]   ],   Constraints[     SENTCAPACITY -> Foreach[{x,SRC},Sum[{z, DST}, SHIPMENTS[x,z]]<=CAPACITY[x]],     RECEIVEDDEMAND -> Foreach[{y,DST},Sum[{z, SRC}, SHIPMENTS[z,y]]>=DEMAND[y]]   ],   Goals[     Minimize[       TOTALCOST -> Annotation[Sum[{i, SRC}, {j, DST}, COST[i, j]*SHIPMENTS[i,j]], "order", 0]     ]   ] ]

 

I highlighted changed we introduced with Yellow and now you can notice that our model became even more laconic and universal (meta-data driven)

 

When I solve the model I will get absolutely the same result

 

Log

 

 

Log

 

[11/9/2013 1:05:03 AM] Check started... [11/9/2013 1:05:03 AM] Excel: 00:00:00.0836686 [11/9/2013 1:05:03 AM] Model syntax passed [11/9/2013 1:05:03 AM] Model Check Complete [11/9/2013 1:05:25 AM] Solve started... [11/9/2013 1:05:25 AM] Excel: 00:00:00.2225209 [11/9/2013 1:05:26 AM] ===Solver Foundation Service Report=== Date: 11/9/2013 1:05:26 AM Version: Microsoft Solver Foundation 3.0.2.10889 Express Edition Model Name: DefaultModel Capabilities Applied: LP Solve Time (ms): 0 Total Time (ms): 0 Solve Completion Status: Optimal Solver Selected: Microsoft.SolverFoundation.Solvers.SimplexSolver Algorithm: Primal Arithmetic: Hybrid Variables: 12 -> 12 + 8 Rows: 8 -> 8 Nonzeros: 36 Eliminated Slack Variables: 0 Pricing (exact): SteepestEdge Pricing (double): SteepestEdge Basis: Slack Pivot Count: 7 Phase 1 Pivots: 6 + 0 Phase 2 Pivots: 1 + 0 Factorings: 5 + 1 Degenerate Pivots: 1 (14.29 %) Branches: 0 ===Solution Details=== Goals: TOTALCOST: 86800   [11/9/2013 1:05:26 AM] Solve Complete

 

Result

 

 

Finally let's make the model even more user friendly by using literals instead of numeric IDs for the shipments matrix. For this purpose I've introduced SOURCE and DESTINATION columns to substitute SRC and DST columns 

 

Binding editor

 

 

Once we completely defined our model it is time to get back to human readable/friendly descriptions of Source and Destination. Please note that now I can manipulate with literal values of Source and Destination just like I used to do this with numeric values of SRC and DST

 

Excel workbook

 

 

Result

 

 

Now after we solved the model and got the result we can visualize the result on Bing Maps. This is truly the most exciting part! J 

 

Visualization

 

Our task will be to visually compare volumes and distribution of shipments to different regions (Stores)

 

For this purpose you can install Bing Maps App from the list of Apps for Office, so you will have it available on INSERT tab as shown below. As you can see I also did install Microsoft Power Map product (currently in Preview) for even cooler 3D visualization!

 

Excel – INSERT Tab

 

 

Once you install Bing Maps App for Excel you can visualize the results with single click

I simply highlighted the part of Excel workbook and clicked on the Pin in Bing Maps App

 

Bing Maps App

 

 

As the result the system showed me shipments volumes we optimized on 2D map

In case you want to visualize your results in 3D you can launch Power Map as shown below

 

PowerMap

 

 

Of course, when you select particular pie chart on the map the appropriate info about distributions will show up, etc. In this document I highlighted only several options of how you can visualize your results in Excel but you are very welcome to use your visualization means too!  

 

Summary: In this document I illustrated how to use Microsoft Solver Foundation in order to resolve Distribution network optimization problem. In particular in order to resolve this problem I used Microsoft Solver Foundation and Microsoft Excel providing robust platform for solving complex mathematical problems and rich visualization means to analyze the results of optimization. Please note that the data for initial analysis can be extracted from Microsoft Dynamics AX 2012 by means of Web Services, and optimization results can be pushed back to Microsoft Dynamics AX 2012 the same way. For example, input data about Supply and Demand profile can come in form of Sales orders and Purchase orders for Stores and Distribution centers correspondingly, and optimization results can be imported back to Microsoft Dynamics AX 2012 in form of Transfer orders between Distribution centers and Stores. For communication with Microsoft Dynamics AX 2012 you may use standard Microsoft Dynamics AX 2012 Excel Add-in or custom Excel Add-ins supported by Web Services. It is also very important to mention that using Microsoft Solver Foundation Add-in for Excel doesn't require strong development skills, thus Business Analysts and Power Users may be very proficient in doing various optimizations using familiar Excel user interface. Please find more info about Modeling in Excel here: http://msdn.microsoft.com/en-us/library/ff524510(v=vs.93).aspx

      

Note: This document is intended for information purposes only, presented as it is with no warranties from the author. This document may be updated with more content to better outline the concepts and describe the examples.

 

Tags: Dynamics ERP, Dynamics AX 2012, Distribution Network Optimization, Supply Chain Optimization, Solver Foundation, Excel, Excel Add-in, Bing Maps, Power Map, Web Services, Manufacturing, Distribution, Retail, Transportation Management, Purchase order, Sales order, Transfer order

 

Author: Alex Anikiev, PhD, MCP