Proposta de beca i PFC de la Fundació i2CAT

El dootrips permeten registrar els viatges que un fa independentment de Labdoo i l'espai lliure que un té a l'equipatge per transportar portàtils entre usuaris, els quals inclou usuaris que tenen portàtils que ja no fan servir, usuaris que tenen espai extra per emmagatzemar portàtils temporalment, usuaris que testegen portàtils i hi instal·len un nou sistema operatiu, els nous usuaris dels portàtils, i empreses de reciclatge electrònic. D'aquesta manera es poden transportar portàtils sense cap cost de transport. Per exemple, un usuari de Labdoo de Nova York (NYC) va recollir 5 laptops d'un altre usuari de NYC, els va testejar, els hi va re-instal·lar un nou sistema operatiu, i els va donar a una usuària que normalment viatge de NYC a Boston, la qual els va portar a Boston en un dels seus viatges i els va donar a un altre usuari que pertany als Enginyers Sense Fronteres de Massachussets (EWB WMAS) que regularment viatge de Northampton a Boston, el qual els va portar a la seu dels EWB WMAS a Northampton, i EWB WMAS—en un dels seus viatges a Kenya—els va portar finalment a l'escola de Matete, Kenya perquè els seus alumnes puguin connectar-se a Internet. Aquests i d'altres exemples arreu del planeta es poden seguir a traves de l'inventari global www.labdoo.org/map.
 

El projecte Labdoo dootrips serà tutelat per a que pugui ser presentat com a PFC. Aquest projecte es centrarà en dissenyar i implementar un mòdul que (i) quan sigui necessari seleccioni un conjunt de dootrips que permetin transportar un conjunt de portàtils—l'estat operacional dels quals hagi canviat recentment—entre usuaris de Labdoo, i (ii) contacti als usuaris pertinents amb els detalls logistics adequats per dur a terme el dootrip. Aquests desenvolupaments es desplegaran sobre la plataforma actual de Labdoo, i les tasques a realitzar són les següents: 

1. Formalitzar i estudiar la complexitat de (*)
   1. el problema general de
      donat
      a. un conjunt de portàtils P={p1, p2, ..., pn}, on cada portàtil pi pesa wi kg, està en una adreça concreta, i està en un nou estat operacional si ϵ S={S0, S1, ..., Sk} (k constant);
      b. un conjunt d'usuaris U={u1, u2, ..., um}, on cada usuari ui està disposat a rebre xi portàtils que estiguin en el subconjunt d'estats operacionals Si ≤S; i
      c. un conjunt de dootrips D={d1, d2, ...., dp}, on cada dootrip està especificat per un origen, destinació, data, i espai extra (en kg);
      trobar un conjunt de dootrips factibles per transportar cada portàtil a l'usuari pertinent en el mínim temps possible.
   2. una solució basada en un algorisme conegut (e.g, un algorisme heurístic o greedy) aplicat a un problema específic basat en simplificar, si és possible i pertinent, el problema general 1.1 (e.g., ∀i wi =w i/o n=1).
2. Implementar iterativament i seguint una metodologia de desenvolupament de software Àgil
   1. l'algorisme per decidir quan és necessari calcular dootrips basat en l'estat operacional dels portàtils
   2. l'algorisme 1.2 per seleccionar els dootrips
   3. els mòduls de comunicació de la xarxa social associada als dootrips dins d'un mòdul Drupal, publicat amb llicència open-source, i integrant-ho amb l'aplicació Labdoo fent servir tecnologies de comunicació de xarxa social (e.g., SMS, tweet, email), PHP, Javascript, i SQL.
3. Escriure un white paper (en anglès).

(*) El problema general segurament sigui NP-hard (possiblament es pugui demostrar reduint algun problema NP-hard com el Knapsack Problem, o el Bin Packing Problem).