|
Objects in this document may appear out of sequence if not viewed with Internet Explorer |
|
ORMSwareTM Suite is a product of Ushar Enterprises Inc, Littleton, Colorado, USA |
|
Click to go to summaries of all examples and paths to Primer and Hands-on Tutorial |
|
A major retailer in UK wanted a system for planning minimum-cost distribution
of about 13 million cases of goods every week to 772 retail stores
from its 9 distribution centers (DCs). All costs were deemed linear, calculated on the margin (i.e. no nonlinear
or conditional fixed costs). Company had policies restricting which DCs could supply which stores.
As part of ORMSware market development effort, we built a quick near-optimal algorithm to help a software developer in UK bid on this project. He contacted us when a solution he was planning to propose could not produce results, because it was built on a strategy of choosing the best allocation from explicit consideration of all possible combinations (click here to view his algorithm and inquiry and click here for sample of the retailer's weekly distribution requirements). That a computer program of such a strategy would run on, never getting to the end, is no surprise. With a total supply of around 13 million units (see example at the link above), 9 DCs, 772 stores, and 2316 permissible supply links and other restrictions, evaluating all allowable possibilities indiscriminately would naturally take forever! For an easy way to comprehend the problem click here to see a small 4-DC-8-stores demonstration problem and click here for example data for the small problem, which is listed above retailer's actual data on the same worksheet. In the demonstration (DCs-Stores) network diagram, square nodes are DCs and circle nodes are stores. Links/arcs indicate permissible supply connections. Numbers along arcs are per-unit shipping costs. Bracketed numbers in nodes (e.g. [3]) are DC IDs and store IDs. Numbers not enclosed in brackets are supply and demand quantities. It is worth noting that an analyst would not want to take on the laborious task of drawing a diagram of the actual DC-Stores network (779 total nodes and 2316 arcs!). There is no need to do that since such a network would only be input data which can easily be expressed in a text file or an Excel worksheet.
We built a quick-and-dirty demonstration algorithm from scratch in 3 days to solve this problem. Half the effort was in making the ASCII text output easy enough to read. As usual, modeling with ORMSware involves visualizing entities traversing a [hierarchy of] logical solution network(s) expressed in terms of ORMSware objects and notation. The algorithm finds a minimum cost Initial Plan in less than 30 CPU seconds on a 1.5 GHz HP Notebook, with minor unfulfilled demands at a few stores. Fulfillment deficiencies in Initial Plan are rectified in the Make-It-Feasible phase (click MakeItFeasible tab in the solution network diagram to see the overall logic) of the optimization process. Excess supply at some DCs and deficiencies at some stores happen in the Initial Plan because total connectivity from all DCs to all stores is disallowed. However, in the Initial Plan the ORMSware algorithm ensures that there will never be a violation of any supply constraint, and that no store is oversupplied. The only infeasibility, if any, would be not meeting the whole demand at some stores. At first glance, the results may seem trivial (after the fact, as usual) but the allocation under "Store Sequence: 753" will show that this is not the case. Also, note that we could have easily used the total cost, rather than per unit cost of shipping along each link, to derive the Initial Plan. In fact, using total cost along each link would have been closer to the final objective of minimizing grand total cost of satisfying all demands. The 2nd (Make-It-Feasible) phase of the algorithm, if necessary, iteratively reallocates shipping quantities until all demands are satisfied, choosing lowest cost increases during each iteration without violating any constraint. Each store dispatches surrogates to the DCs to which it is connected, seeking satisfaction of unfulfilled demand at lowest cost. When a DC cannot fully satisfy a request, it in turn dispatches surrogates to connected stores seeking take-back of previously allocated units. During each hop cumulative net transportation costs are compared and higher cost surrogates are dropped from the search activity. This is similar to the stepping-stone algorithm for general transportation problems, but here a kind of dual of the problem is solved instead. It works backwards from infeasible optimality in the Initial Plan, giving up mostly-feasible optimality which was greedily achieved during Initial Plan, just enough during each iteration until total feasibility is achieved. The nature of the algorithm ensures that solution is always made up of integer allocations. The existing 2nd phase can be modified to produce faster results by limiting successive searches to finding feasible minimum cost exchange path from each deficient store to DCs with excess supplies in the Initial Plan. This algorithm can also be extended to cover other descriptive constraints the company might impose or be faced with in the future (e.g. maximum capacities of links, minimum shipping requirements along links, etc.).
Formulation of this problem is more easily understood through its ORMSware network diagram and its supplemental data files. Click the links below to open these files in separate windows for reference while reading the rest of this document.
VSD
file: Image of Visio network file
describing the model.
Downloads of all examples are available in Chapter 1 of the Hands-on Tutorial. However, you can also view all of the examples and their results online without downloading anything. If you wish to change
inputs and execute these models on your PC, or modify them in someway, you will
have to NETrans them and create their EXEcutables. To do that you will need to
download and install ORMSware and its support components, all of which
are available for free trial. Instructions for all of that are available at the
above link as well. |
|
Click to go to summaries of all examples and paths to Primer and Hands-on Tutorial |