This page presents several corrected exercises on automated planning and scheduling problems, more particularly on transport problems and the associated algorithms: stepping stone.

**Exercise 1**

**Exercise 1**

A business needs to transport supplies from factories to construction sites. The three factories have a supply capacity of 300, 300, 100 respectively. And the three yards require 200, 200, 300 respectively.

Shipping costs are shown in the following chart:

Figure out how to distribute supplies.

## Solution

Solve the following planning problem with the Stepping Stone algorithm.

**Exercise 2**

**Exercise 2**

Wheat is harvested in the Midwest and stored in grain elevators in three different cities: Kansas City, Omaha and Des Moines. These grain elevators supply three flour mills located in Chicago, St. Louis and Cincinnati. Grain is shipped to the mills in railroad cars, each car holding a ton of wheat. Each grain elevator is able to supply the following number of tons (i.e. railroad cars) of wheat to the mills on a monthly basis.

Each mill demands the following number of tons of wheat per month.

The cost of transporting a ton of wheat from each grain elevator (source) to each mill (destination) differs depending on the distance and the rail system. These costs are shown in the following table. For example, the cost to ship a ton of wheat from the grain elevator in Omaha to the mill in Chicago is 7 $.

The problem is to determine the number of tons of wheat to be transported from each grain elevator to each mill on a monthly basis in order to minimize the total transport cost. Is there an alternative solution? If yes which ?

## Solution

**Exercise 3**

**Exercise 3**

From the linear program below, formulate the transport problem and solve it.

Is there an alternative solution? If yes which ?

## Solution

Same solution as exercise 2.

**Exercise 4**

**Exercise 4**

Take the same problem as Exercise 2. Change the demand in Cincinnati to 350 tons. Solve.

## Solution

**Exercise 5**

**Exercise 5**

Solve the following LP problem:

## Solution

We introduce a dummy variable for j because supply(45+60+35)-demand(50+60)=30:

**Exercise 6**

**Exercise 6**

The Atlantic Coast Conference is hosting four basketball games on a particular night. The conference office wants to assign four teams of officials to the four games in order to minimize the total distance covered by the officials. The distances in miles of each team of officials at each match venue are shown in the table below:

## Solution

Each supply and each request is equal to 1. Solve it as a transportation problem.