prezentare licenta

5. Modelarea problemei comis-voiajorului

Date economice

Modele economice

2. Scopul si obiectivele lucrarii

Clienti actuali - 12 firme

Clienti potentiali - 30 firme

LUCRARE DE LICENTA

Fisier indexat -> Articol CLIENT

• cheie
• denumire
• localitate

Readucerea in prim plan a celui dintai domeniu de activitate: distributia si transportul cu ridicata.

Realizarea unui program unicat, presonalizat, axat pe necesitatile si cerintele tehnico-economice ale firmei S.C. Storad Exim S.R.L.

Imbunatatirea serviciului transporturi din cadrul firmei.

Punerea in practica a algoritmilor studiati la disciplina cercetari operationale.

DRUMURI - MUCHII

RESEDINTE DE JUDET - NODURI

ALGORITMI DE REZOLVARE A PROBLEMEI COMIS VOIAJORULUI CU APLICATII

HARTA ROMANIEI - GRAF

START

Absolvent: STOICESCU CRISTINA

Coordonator stiintific: conf. univ. dr. SORINA GRAMATOVICI

Concepte fundamentale din teoria grafurilor

1. Prezentarea firmei S.C. Storad Exim S.R.L.

ţ

Retele de transport

Companie infiintata in anul 1998

cu sediul in orasul Ploiesti.

3. Problema comis-voiajorului

Un comis voiajor are de vizitat un numar de localitati, urmand ca la sfarsitul voiajului sa se intoarca in localitatea de plecare.

Deplasarea dintr-o localitate in alta presupune anumite cheltuieli, distante de parcurs sau durate de mers.

Problema consta in determinarea unei ordini de vizitare a localitatilor astfel incat costul drumului sa fie minim.

4. Algoritmi de rezolvare a problemei

comis-voiajorului

1998 - 2002: obiect de activitate - distributia de geamuri si oglinzi din import

CUPRINS:

2003 - 2012: obiect de activitate - prelucrarea si fasonarea sticlei plate

Optimizarea combinatoriala

Algoritmul lui Eastman

Evaluarea timpului necesare parcurgerii distantei

Metode euristice de rezolvare aproximativa

Un camion merge in medie cu 50 km/h.

La fiecare 8 ore soferul trebuie sa

faca o pauza de 16 ore.

Algortimul Ungar

(Kuhn)

EURISTICA E1 - mergi la cel mai apropiat vecin

EURISTICA E2 - ajustare locala

ALGORITMUL LUI DIJKSTRA

(modificat)

EURISTICA E4 - metoda Cristofides

EURISTICA E3 - dublare de muchii

Algoritmul lui Prim

Algoritmul lui Kruskal

Evaluarea costului unui transport

COSTURI FIXE: costuri cu amortizarea, plata asigurarilor, plata salariului soferului, taxe de drum

COSTURI VARIABILE: costul combustibilului, plata consumabilelor, plata pieselor de schimb

1. Prezentarea firmei S.C. Storad Exim S.R.L.

2. Scopul si obiectivele lucrarii

3. Problema comis-voiajorului

4. Algoritmi de rezolvare a problemei comis-voiajorului

5. Modelarea problemei comis-voiajorului

6. Concluzii

RULAREA APLICATIEI !!!

Functia de cost pentru fiecare cluster

CLUSTER 3

Evaluarea functiei de cost

Testare validitate model

Distante peste 1000 km

H0: modelul nu este valid statistic

H1: modelul este valid statistic

Prob(F-statistic) < 0,05, deci respingem H0, acceptam H1, model valid statistic

CLUSTER 2

Distante intre 600 si 1000 km

CLUSTER 1

Testare semnificatie parametru de interceptare

Distante mai mici de 600 km

H0: parametrul nu este semnificativ statistic

H1: parametrul este semnificativ statistic

P-value=0,1070 > 0,05, deci acceptam H0, parametrul nu este semnificativ statistic

Esantion 40 observatii privind transporturi efectuate de S.C. Storad Exim S.R.L. in perioada 2010-2011

• data efectuarii transportului
• ruta (orasele vizitate)
• distanta (km parcursi)
• costul (RON)

Realizarea aplicatiei - meniu

1. Adaugarea unui client nou in baza de date a firmei

2. Stergerea unui client din baza de date a firmei

3. Listarea clientilor din cadrul firmei

4. Implementare - rezolvarea problemei comis-voiajorului

0. Iesirea din aplicatie

6. CONCLUZII:

1. afisarea in ordine a localitatilor ce trebuie vizitate, inclusiv localitatile intermediare

2. afisarea distantei ce trebuie parcurse (km)

3. afisarea timpului necesare parcurgerii distantei

4. afisarea costului total minim ce trebuie suportat de firma

Impartirea esantionului in clustere

Evaluarea distantei dintre forme: distanta Euclidiana

Evaluarea distantei dintre clustere: metoda centroidului

Prin imbinarea cercetarilor operationale cu econometria, analiza datelor si informatica s-a dezvoltat o aplicatie practica ce raspunde cerintelor tehnico-economice ale firmei S.C. Storad Exim S.R.L. si tine cont si de contextul economic actual.

Optimizarea deciziilor cu privire la planificarea transporturilor si ajustarea preturilor.

Existenta unor posibilitati multiple de extindere a aplicatiei.

outliar

STOP