A few months ago we introduced you the collaboration agreement signed between Labdoo NGO and i2CAT. Both entities have been working together in order to break the existing digital divide and decrease the e-waste generation. After a set of meetings, the bases of the agreement were focused on two main action points i2CAT would work on. The first of them concerns extending Labdoo social network, which is the tool used by Labdoo’s collaborators to register the laptops they want to donate and/or the trips in which some of these laptops can be transported. Secondly, i2CAT would offer its infrastructures to create the “Barcelona Hub”, where the devices of this area would be stored and sanitized before their departure.
Dootrips are trips registered by the users of the social network, in which they declare to have enough space at their luggage to transport a set of laptops . Using all available dootrips of the system, we wanted to find all the existing combinations that allow to ship as many laptops as possible, using the minimum number of dootrips resources. That is, the shortest paths between the original location of the laptops and the destination ones should be found. The formal definition of the problem is the following:
- A set of laptops S sorted around the world.
- A set of destination projects T waiting to receive a defined number of laptops.
- A set of dootrips D, each of them having a capacity (in number of laptops), a departure and arrival date.
- A set of hubs H where laptops can be stored between dootrips.
The algorithm should find all paths allowing to transport the maximum number of laptops using the minimum number of dootrips. We decided to adapt an existing max-flow algorithm to resolve this problem, choosing finally the Dinitz’ Algorithm , conceived by Yefim Dinitz at 1970. It looks for the maximum flow of a network using the shortest existing paths. There ‘re some important restrictions needed to be considered:
- The flow send through an edge can’t be higher than it’s capacity.
- The set of dootrips d1-d2 can belong to a final solution only if the departure date of d2 is after the arrival date of d1, and both users can meet each other in order to deliver/receive the laptop(s).
- The set of dootrips d1-d2 can belong to a final solution if the departure date of d2 is after the arrival date of d1, both users can’t meet each other, but there’s a hub at this city where the laptops can be stored.
The original graph gets simplified twice before searching all the possible solutions. At the first phase of the transformation, the Residual Graph is constructed, which doesn’t include any edge violating the mentioned restrictions. Once the Residual Graph is built, it’s converted into the Level Graph. The BFS algorithm is executed to find the minimum distance between every node of it. Given an edge between nodes u-v, the Level Graph will include it if distance(s,v) = distance(s,u)+1. It means that the edge will be present only if it’s part of the shortest path between the initial node “s” and “v”. The objective of this transformation is to facilitate the search in every iteration by deleting unnecessary edges.
Finally, the algorithm looks for the maximum flow in the level graph, ensuring that, if it’s shipped from node “s” to node “v”, there’s no shorter path between both of them. The whole process is repeated until there ‘re no more possible solutions. Taking into account that this process was made manually by Labdoo members, the new Dootrip algorithm will improve route calculation efficiency in terms of quality, time and integrity.
Furthermore, i2CAT provides its infrastructure to store laptops if necessary, and also its members prepare them before they are sent to one of the schools Labdoo collaborates with. A hub is an entity that collaborates with Labdoo by storing and sanitizing the donated laptops .
i2CAT represents the Barcelona Hub. Users and enterprises located near Barcelona area can deliver to us their unused laptops. All of them, including the ones donated by ourselves when our devices get replaced by newer ones, are checked at Labdoo’s QGP events. Hubs all around the world get synchronized to check their available laptops hardware and to install the educational platform Edubuntu on it. All devices get tagged in order to trace it state and location during the whole laptops lifecycle. If a laptop is no longer usable, we take the working components from it and the rest of them are sent to a recycling center. In addition, we’re connected to the Labdoo QGP chat room during the QGP sessions, so every person preparing a donated laptop can receive our support immediately.
Once a laptop is assigned to one of the schools, we deliver this dooject to the user of the social network who is going to transport it from Barcelona. Nowadays, laptops that has been sanitized at i2CAT has arrived to different projects located at Ecuador, Thailand, Argentina and Cambodia, for example .
- This afternoon, i2CAT will organize the 9th QGP coordinated with the Rome hub. Our objective is to prepare ten laptops that will be added to the ones sanitized at Rome before they are sent to “La Escuelita” school, in Ecuador.
- In a few days, the module in which the algorithm is included will be integrated at Labdoo website. After the software gets tested by the Labdoo members, it will be uploaded to Drupal repository, so every organization can use it for similar purposes.
- A white paper explaining the algorithm implementation and the problem it solves will be published between June and July. Remember to have a look at it in case you want to know more about the dootrip algorithm!
Stay tuned for more news on Labdoo!
-  Labdoo Website.
-  Dinitz’ Algorithm Whitepaper. Yefim Dinitz. Ben Gurion University of the Negev, Israel.
-  Labdoo Photo Gallery, including images from dootrips, QGP and schools with the sanitazed laptops.