Algoritmi de rutare

Introducere

Deoarece problemele lumii reale devin extrem de complicate este necesar să se facă o abstractizare și o simplificare a realității într-un model. Să considerăm de exemplu problema construirii unei clădiri. Este necesară o durată îndelungată pentru culegerea de informații privind locul unde se amplasează, caracteristicile fizice ale clădirii, studiul detaliat al condițiilor climatice și de sol, influența asupra costurilor, sursele de finanțare și costurile. Decidentul poate hotărî să considere în mod deosebit și în detaliu toate celelalte potențiale folosite în această perioadă și în perioadele viitoare. Dacă decidentul adoptă strategia colectării tuturor informațiilor înainte de a acționa, atunci nici o acțiune nu va avea loc. Mintea umană nu poate considera toate aspectele empirice ale problemei. Anumite atribute ale problemei trebuie ignorate ca să se poată lua o decizie. Decidentul trebuie să identifice factorii cei mai relevanți pentru problemă. Abstracția și simplificarea sunt pași necesari în rezolvarea oricărei probleme umane.

După ce decidentul a identificat factorii critici ai problemei concrete pe care o are de rezolvat, aceștia trebuie combinați în mod logic formând astfel modelul. Un model este reprezentarea simplificată a problemei reale. Prin modelare, fenomenului natural complex i se reproduce comportarea esențială cu mai puține variabile și care sunt legate între ele mai simplu. Avantajele unui model simplu sunt:

1) economia de timp de concepere

2) poate fi înțeleasă realitatea de către decident

3) dacă este necesar, modelul poate fi modificat repede și eficient.

Optimizarea poate fi definită ca știința determinării - celei mai bune- soluții la anumite probleme definite matematic, care sunt adesea modele ale realității fizice. Ea implică studiul criteriilor de optimalitate pentru probleme, determinarea soluției cu metode algoritmice, studiul structurii acestor metode și experimentarea pe calculator a metodelor cu date experimentale și cu date reale.

Metodele de optimizare au o largă aplicabilitate în aproape orice activitate în care sunt prelucrate informațiile numerice: știință, inginerie, matematică, economie, comerț etc. O selecție a domeniilor în care apar probleme de optimizare ar cuprinde: proiectarea reactoarelor chimice, a aparatelor aerospațiale, a clădirilor, a podurilor, în comerț în probleme de alocarea resurselor, planificarea producției, a stocurilor, în diferite ramuri ale analizei numerice, în ajustarea datelor, principii variaționale.

Problemele integrate de amplasare-rutare combină trei componente ale proiectării canalului logistic:

a) amplasarea depozitelor;

b) alocarea clienților la depozite;

c) rutarea vehiculului.

Funcția obiectiv pentru problema integrată de amplasare-rutare, minimizează suma costurilor fixe de amplasare a depozitelor, costuri de expediere de la fabrici la depozite, costurile de tranzit variabile prin depozite și costurile de rutare la clienți:

unde I este mulțimea punctelor de amplasare a clienților, indexate după i;

J - mulțimea amplasamentelor posibile pentru depozite, indexate după j;

P - setul de puncte IJ;

S - mulțimea punctelor de aprovizionare (furnizori) indexate după s;

fj - costul fix al amplasării unui depozit în poziția jJ;

csj - costul unitar al expedierii de la furnizorul sS la potențialul amplasament jJ al depozitului;

wsj - cantitatea expediată de la sursa de aprovizionare sS la depozitul j J;

vj - costul variabil pe unitate procesată de un depozit din poziția jJ;

hi - cererea la clientul situat în punctul i;

Yij - fracțiunea cererii clientului situat în punctul i care este servită de un depozit situat în punctul j;

k - costul pe unitate de distanță pentru livrarea pe ruta kK;

dij - distanța între nodul iP și nodul jP;