Labdoo project and design of optimal routes to distribute laptops

Labdoo is a NGO with the objective to delete the digital divide and decrease the e-waste. In the world, millions of computers are replaced every year, most of these computers still work fine but are changed for devices due to new technological innovations. In contrast, it exists an important group of people that cannot connect to the Internet and enjoy the last educational advantages which Internet offers. Labdoo wants to create a platform to redistribute these laptops in the different communities that have not enough economical resources to afford them. Ladbdoo is distributed around the world and takes advantadge of the web 2.0 technology and social networks to provide these resources without operational costs.

In addition, Labdoo and i2CAT are interested in collaborating on supporting Labdoo’s mission and goals, toward the shared objective of bridging the global digital divide. The general objective of the understanding is to seek ways to collaboration between the two parties. A specific area of collaboration will consist of supporting Labdoo on disseminating the Labdoo’s concept in the Catalan TIC sector and establishing the bases for a future donation to Labdoo (to be agreed at the patronate level of i2CAT), of the old i2CAT’s laptops to be recycled. Furthermore, Labdoo and i2CAT will participate on defining new proposals for improving the Labdoo platform and its social networking service.

To achieve Labdoo’s objectives, Labdoo develops a set of online tools to register the available user resources: laptops, trips to transport devices, time or places to store computers.

Consequently, there are four main resources which Labdoo has to manage:

  • Laptops. They will have to be registered in the Labdoo web (a registered laptop is “tagged”).

  • Places. These laptops have to be stored in different places before they can be transported to the target communities (Labdoo defines these places as “hubs”) or places to recycle a laptop if it can not be repaired.

  • Trips. It is defined as “dootrip”. It is a trip which defines a possible route to transport a laptop. Furthermore, Labdoo registers all these available “dootrips” and its capacity to transport laptops.

  • Demand kicks in schools, towns, etc… Needy communities which can get profit from these laptops.


 

Problem

The Labdoo challenge is the design of an algorithm to handle all these resources in order to define the most optimal route to transport a set of tagged laptops to the destination places. For example, a Labdoo user in New York can get five laptops from different users which he will repair and reinstall an Edubuntu S.O (System Operative). After that, he will give them to another user which will do a business trip to Boston. In Boston, these laptops can be sent to Kenya in a girl’s baggage that travels every year with EWB (Engineers Without Borders)

This design problem needs a formal representation which it is represented as knapsack problem. It is a combinatorial optimization problem:

 

Knapsack problem definition

Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

The formal representation is:

  • Laptops L = {l1, l2, ,l3, …, ld}. It includes size, location and laptop state (it is defined as S={ S0, S1, S2, …, SK})

  • Users U={u1, u2, u3, …, um}. Users which it will be able to receive Xi laptops.

  • Dootrips D = {d1, d2, d3,….., dp} . It includes: source, target, departure data and size to move laptops

Solution

Now, the solution is an open issue, and Labdoo is working to design the necessary and better algorithm. The idea is to use a Greedy algorithm to implement the most optimal route. Finally, this study will be explained in a white paper which will explain the conclusions and the most interesting results.

Links:

Labdoo – http://www.labdoo.org

Edubuntu – http://www.edubuntu.org

Greedy algorithm – http://en.wikipedia.org/wiki/Greedy_algorithm

Knapsack problem – http://en.wikipedia.org/wiki/Knapsack_problem

 

This entry was posted in Research and tagged . Bookmark the permalink.