TWiki> OpsRes Web>NetworkOptimisation>TransportationProblem (22 Apr 2008, TWikiAdminGroup)EditAttach

The transportation problem is one of the simplest forms of network optimisation.

The network is bi-partite, i.e., it can be split into two sets of nodes with all arcs going from one set to the other. One set is called the *supply nodes* and the other set is called the *demand nodes*. The arcs are all arcs directed from a supply node to a demand node, i.e., . Any supply of goods to the network arrives at the supply nodes, denote this , and any demand for goods is realised at the demand nodes where it leaves the network, denote this . Figure 1 shows the supply and demand nodes for the Brewery Problem with node labels and the supply and demand at the nodes given. Thus , , , , , , etc.

**Figure 1** The nodes for the Brewery Problem

The arcs in the Brewery Problem carry crates of beer from the supply nodes (warehouses) to the demand nodes (bars) as shown in Figure 2. In this problem there are no restrictions of the arcs, so .

**Figure 2** The arcs carry crates of beer from the supply nodes to the demand nodes

In the transportation problem there is a cost associated with carrying goods from the supply node to the demand node along arc . In the classical transportation problem this is a unit cost per item, i.e.,

In a transportation problem we need to decide what quantity of goods to deliver along each arc to minimise the total transportation cost of delivering goods.

Transportation problem are network optimisation problems. Network optimisation problems are solved using mathematical programming. Thus, to formulate a transportation problem we use the 4 steps for formulating a mathematical programme:

- Identify the Decision Variables
- Formulate the Objective Function
- Formulate the Constraints
- Identify the Data

The decision variables in the transportation problem are the quantity of goods to carry along each arc, i.e., . Note that means that and . Usually, these variables are integer and nonegative, i.e., .

The objective in the transportation problem is to minimise the total transportation cost along the arcs, i.e.,

The constraints in the transportation are simple: 1) use all the supply of goods; 2) meet all the demand of goods. These may be expressed concisely:

The data for the transportation problem is also straightforward to determine. We need to identify the supply nodes and the demand nodes , the supply and demand amounts, i.e., , , and the cost of transportation from each supply node to each demand node .

The transportation problem we consider here must be *balanced*, i.e., , for the problem to be feasible. If a problem is not balanced then either there is an excess supply or an excess demand. These two factors can be incorporated by adjusting the relational operators on the constraints, e.g., for over supply change the supply constraint to

However, if the problem data changes, then the formulation may need to change. An easier way to deal with *unbalanced* transportation is to add *dummy* nodes to either the supply nodes (in the case of excess demand) or the demand nodes (in the case of excess supply). The supply (respectively demand) for the dummy node is simply the excess amount of demand (supply, respectively). There could also be a cost associated with goods coming from a dummy supply node, e.g., a penalty cost for buying in extra goods, or goods going to a dummy demand node, e.g., a salvage cost for unwanted items.

The arcs between the supply nodes and demand nodes may be restricted in two ways:

- there may be bounds on the amount of goods that an arc may carry;
- some arcs may not exist, i.e., there is no way to transport goods from a particular supply node to a particular demand node.

Dealing with bounds is done by adding bounds to the decision variables, i.e.,

Dealing with non-existent arcs is more complicated. One way is to price the arc out of the solution, i.e., add a big cost (often referred to as a big- cost), so the arc will not be used. Sometimes it is not easy to determine a cost that is big enough to remove the arc from the final solution, but not so big that it distorts the solution process. The easiest way is to introduce bounds with default values, e.g., 0 for the lower bounds and for the upper bounds, and then set the upper bound of the banned arcs to be 0. This way no goods will be delivered along this arc.

The transportation problem is often an integer programme as the quantity of good delivered along the arcs must be integer. However, **if the supply, demand and variable bounds** are integer, then the transportation problem will have *naturally integer* solutions. This means that any solution found using **linear** programming will have integer values. This is a property that is common to other network optimisation problems, e.g., the transshipment problem.

To see examples of transportation problems, check out some of the transportation problem case studies:

\usepackage{amsmath} Case Study: Submitted: Operations Research Topics: Application Areas: Contents Problem Description Problem Description Return ...

\usepackage{amsmath} Case Study: Submitted: Operations Research Topics: Application Areas: Contents Problem Description Problem Description Return ...

Number of topics: 2

-- MichaelOSullivan - 02 Apr 2008

Topic revision: r12 - 22 Apr 2008 - 08:47:27 - TWikiAdminGroup

Copyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding TWiki? Send feedback

Ideas, requests, problems regarding TWiki? Send feedback