Project 1 for COSC 6367 (Dr. Eick) in Spring 2001
USING EC FOR 5x6 BALANCED TRANSPORTATION PROBLEMS

due date: March 6, 2001
last updated: January 15, 7:11p

Write a system that is capable of solving 5 source / 6 destination real-valued balanced transportantion problems with respect to four given cost functions. Write an interactive EC-style system that
  • reads the amount available at the five sources
  • read the amount to be delived to the six final destinations
  • asks the user to select one four possible cost functions (see below) and finds a "good" solution for the transportation problem, and allows to rerun the system for the same or another cost-functions.

    For example, let us assume that the following source and destination capacities are given:

    sourse[1]=5;source[2]=5;source[3]=20; source[4]=15; source[5]=15
    destination[1]=destination[2]=destination[3]=destination[4]=destination[5]=8; destination[6]=20

    Moreover, four different cost functions f1, f2, f3, and f4 will be used for the project: 

    Let 
i the source index (i=1,...,5)
j be the destination index(j=1,...,6)
u the number of units to be transported (>=0)

f1(i,j,u):= (|i-4|+1)*(|i-j|+1)*u "linear transportation problem"
f2(i,j,u):= (|i-4|+1)*(|i-j|+1)*u*u "quadratic transportation problem"
f3(i,j,u):= |i*j-13|*sqrt(u) + sqrt(u) "general transportation problem1"
f4(i,j,u):= (|i-j|+1)*u*u + u*u*u*u "general transportation problem2"

Assuming this framework, a solution found by your program could be:

     8    8    8   8    8    20

5    5    0    0   0    0     0
5    3    2    0   0    0     0
20   0    6    8   6    0     0
15   0    0    0   2    8     5
15   0    0    0   0    0    15


    The transportation cost of the above solution matrix, assuming that function f1 is used, would be: 
    f1(1,1,5) + f1(2,1,3) +  f1(2,2,2) + f1(3,2,6) + f1(3,3,8) +
f1(3,4,6) + f1(4,4,2) +  f1(4,5,8) + f1(4,6,5) + f1(5,6,15)
    In general, the elements of the solution matrix are floating point numbers; however, if you print the elements of the matrix, round those to two numbers after the decimal point(e.g. 27.14334344343434 is printed as 27.14 and 3.45500111232332 is printed as 3.46).

    Write a program that displays the inputs, the evolution process, and the final results obtained by a program run in a nice and understandable form. Test and enhance your program assuming for the 4 classes of supported cost-functions. Be prepared to demo your program!

    Write a report (approx. 9 to 13 single spaced pages) that describes the evolution of the project, gives a clear description of the explored and employed search strategies, and summarizes the results of running your program using the four cost functions for: source[1]=5;source[2]=5;source[3]=20; source[4]=15; source[5}=15 destination[1]=destination[2]=destination[3]=destination[4]=destination[5]=8; destination[6]=20 and for source[1]=12;source[2]=12;source[3]=12; source[4]=12; source[5}=12 destination[1]=destination[2]=destination[3]=destination[4]=destination[5]= destination[6]=10; and reports the best found solutions for each cost function. Finally, the report should interpret the empirical results and summarize the important findings and accomplishments of the project.