DYNAMIC PROGRAMING CASE STUDY

PREPARED BY 

MADUKA ANTHONY .N.

CASE STUDY

Ooshaynaz is a company that produces and sells cement majorly. After production, they have trucks and trailers that would be used to transport this goods to their numerous customers. for this to be done, they need to evaluate cost spent on transportation so as not to incur losses. ooshaynaz is located in the western part of Nigeria and want to transport their product to the Northern part of the country, this part has various routes and some are farther than the others and as such will take more time and cost in terms of petroleum used and parts of vehicle used. Also, time spent in delivery which is valuable to the company in terms of production .

            Lets consider a situation where a truck carrying goods produced by OOSHAYNAZ is to be moved from lagos to Kano state, the truck has some choices of path to take as it enters some stages of coaches . the truck needs the safest possible route so as to reduce cost.

Although the starting points and end destinations are fixed, they had considerable choice as to which states and route to take. The distances and cost that would be incurred as a result of taking certain route are analysed in this study

There are two methods in dynamic programming, the BELLMAN FORD ALGORITHM and MATRIX PRODUCT ALGORITHM. For the purpose of this work, emphasis is laid on the Bellmans ford method. To get the shortest path, it is assumed that there is no negative weight cycle (else the shortest path can wrap around such a cycle infinitely often and has length negative infinity) 

Ooshaynaz moved through the following distances which are datas collected and coded in alphabets to represent the names of towns that lead to the predefined state and distances in kilometers

Table 1 DISTANCE IN KM FROM LAGOS TO KANO

TO / FROM	B	C	D
A	5	4	2

TO / FROM	E	F	G
B	7	4	6
C	3	2	4
D	6	3	5

TO / FROM	H	I
E	3	4
F	6	2
G	5	3

TO / FROM	J
H	6
I	5

  

A

 

                        5                                  4                                  2

B

C

D

 

                        6                                                                      6         

                                                                                                            3                      5

                                                3          2                      4         

7                      4

E

F

G

 

3                                  4                      6          2                      5          3

H

I

J

 

THIS IS HEREBY SOLVED BY THE FOLLOWING ALGORITHM

NODES                      COMPUTATIONS                                                    LABELS

A                     U_A = 0                                                                          (0,-)

B                      U_B =U_A + D_AB     ;     0 + 5 = 5                                     (5,A)

C                     U_C  = U_A + D_AC  ;     0+ 4 = 4                                      (4,A)

D                     U_D = U_A + D_AD ;      0 + 2 = 2                                      (2,A)

E                      U_E  = U_B +D_BE ;   U_C + D_CE ;  U_D + D_DE

                                    5+7= 12  ; 4+5= 9 ;    2+6= 8                          (8,D)

F                      U_F = U_B + d_BF   ; U_C + d_{CF     ;} U_D +d_DF

                                    5+4= 9 ;    4+2= 6 ;    2+3= 5                          (5,D)

G                     U_G = U_B + U_BG   ; U_C + d_CG    ; U_D + d_DG

                                    5+6= 11 ;    4+4= 8 ;   2+5= 7                         (7,D)

H                     U_H = U_E + d_EH ;   U_F + d_GH ;   U_G + d_GH

                                    8+3= 11 ; 5+6= 11 ; 7+5= 12                          (11,E or F)

I                       U_I = U_E +d_EI ; U_F + d_FI ; U_G + d_GI

                                    8+4= 12 ;  5+2= 7 ;   7+3= 10                         (7,F)

J                       U_J = U_H + d_HJ ;       U_I + d_IJ

                                    11+6= 17 ;    7+5= 12                                     (12,I)

RESULT

The shortest possible route that can be taken by the drivers is enumerated below

A

 

D

F

J

I

            2km     2km                 3km                             2km                 5km                                                    

The total distance covered by taking this path is 12km

i.e 2 + 3 + 2 + 5 =12 km

  CONCLUSION

            It can be concluded that the use of dynamic programming in the analysis of the path that a driver can take given the available routes to a defined destination can be solved . This study and results obtained using the aforementioned methods in this report can be applied to any path or roads to a certain place once the distances and places are known.

  RECOMMENDATION

                        Having analysed the activities involved in delivery of products, by ooshaynaz industries, it can be recommended to use the algorithm to solve any transportation problems for any industry that has route issues.

Therefore, subsequent development can make use of motorized hydraulic or pneumatic systems as this will help save a lot of energy and reduce work time.

 For the diagram of the case study, pls leave your mail and it will be sent to you..... the alphabeths are the products of the case study.