ALMA : A Logistic Mobile peer-to-peer computing Application

Algen organized a mission in October 2013 with Dr. Didier El Baz and for the ALMA project. The mission was to meet academic partners (Tsinghua,…) and joint research centers in China (LIAMA) in order to build a ANR-NSFC joint funded project.

Dr. El Baz (right) and Alexandre HEUZÉ (left) in Tsinghua, October 2013

Here below is a description of the ALMA project for reference :

1.   Scope of the project

ALMA project is a research project aimed at proposing an innovative infrastructure of communication and computing for real-time mobile logistic applications. This project extends in some sense the research work of the previous ANR project CIP, ANR-07-CIS-7-011 (a French research project), that started in 2008 and ended in 2011 (see http://projects.laas.fr/CIS-CIP/ ).

The ANR project CIP aimed at developing a prediction tool and a decentralized environment for high performance peer-to-peer distributed computing applications that require direct and frequent communications between peers. The applications considered in this project were task parallel applications like combinatorial optimization problems and numerical simulation problems that are usually solved via recursive methods or iterative methods. In particular, project CIP has considered 2D cutting stock problems, finance problems and process engineering problems.

The ALMA project proposes a mobile solution for logistic applications based on peer-to-peer computing and cluster computing. This proposal considers logistic problems that result from a combination of vehicle routing problem and loading problem which occur frequently in the delivery of items by logistic companies. Typically, operators have to deliver items to customers in due time while minimizing the transportation cost. Logistic companies nevertheless have to face many incidents, like engine faults, mechanical problems, roads closed or delays due to traffic. Thus, it is more efficient to take decision online when new order arrives or incident occurs. The transporter enters data in the system online as soon as an item is delivered to a customer; it also sends a query for a new solution as soon as he faces an incident, e.g., he asks for a new road to deliver items when some traffic jam occurs. Nevertheless, we note that vehicle routing problems are difficult to solve since they are NP-Complete problems. Thus, some high performance computing platform is needed in order to compute solutions online for transporter. The aspects related to the Internet of Things and intelligent treatment of data are particularly important in this project since they contribute to trace online items that are delivered, e.g. mobile phones can be used to process online the delivery of items.

The ALMA project concerns the infrastructure for future services. It deals both with mobile applications and innovative numerical services furnished to logistic operators that rely on high performance computing since the considered problems are difficult to solve.

The ALMA project proposes several innovative concepts to cope with the different aspects of mobile logistic applications:

–          It deals with an eco-intelligent, low throughput, low consumption communication architecture for online data and query processing related to logistic applications;

–          It proposes a new computing infrastructure that represents the advantage of large scale distributed computing systems and virtualization and that is based on a broker and a decentralized environment for high performance computing designed as an extension of the P2PDC environment developed in the framework of project ANR CIP. It uses also technologies that tend to increase the computation power per Watt ratio by combining, for example, peer-to-peer computing and GPU computing;

–          It proposes innovative mobile technologies for logistic applications that furnish solutions which improve quality of service and tend to minimize gas consumption of trucks;

–          Finally, it proposes new distributed algorithms to solve a combined vehicle routing problem and loading problem / cutting stock problem.

In short, the ALMA project aims at providing answers to the following questions:

• What kind of Communication infrastructures for next-generation logistics solutions?
• What kind of computing infrastructure for next-generation logistics solutions?
• How IoT (Internet of Things) could be used in improving logistics solutions ?

This project is part of Green ICT, because it aims at reducing energy consumption in logistics, in communications infrastructure and in computing infrastructure.

2.   Problems faced in logistics:

Logistics (delivering goods from a location to a destination) is e very challenging business because it offers very complex problems :

• How to load a truck/container optimally ?
• How to choose the optimal road?
• How to respond to changes ?

a.   How to optimally load a truck/container

Research has already been done on the best way to load a container with packages of different sizes, but there is still room for improvement and basic research on algorithm :

• Improve current algorithms with 3D loading (previous study are mainly for 2D)
• Improve current algorithm to take operation time into consideration
• Improve current algorithm to take “fragile” packages into consideration
• How to regroup items which are the same
• How to manage the expiration date of items
• Improve current algorithm to take unloading into consideration
• Improve current algorithm with the use of IoT

The calculation of the optimum can be very challenging for a computer. In order to have a response from the system in a short time, new methods of parallel-computing must be developed to answer these questions.

Furthermore, the system may have to re-calculate the optimum considering real-time changes : an order has been canceled, road is blocked or other real-time constraints.

b.   How to choose the optimal road

There is already research done on calculating the optimal road, but the challenge here is to have the system calculate new optimal routes very quickly. The typical scenario is a truck driver who is confronted with a problem on the road: he has to change his previous routing plan. The driver must receive the new routing plan quickly and this can be a challenging request for the computing services.

There is also a challenge when considering the loading/unloading issue with the optimal road. There could be a cost associated in changing the order of deliveries. The calculations involved in solving these issues are very challenging and a new approach to parallel computing needs to be considered. It is not only a problem of software and algorithm, it is also a problem of infrastructure.

c.   Global Architecture of the project

 

d.   Peer to peer calculation

ALMA project aims at doing basic research on infrastructure for intensive calculation. Based on previous research done by the team, ALMA aims at further investigating peer to peer distributed/parallel calculation solutions. These solutions could also provide an answer to the optimal use of calculation resources. We know that companies have a lot of CPUs and computers, but most of the time, these resources are not used. ALMA proposes an innovative approach to distribute and use calculation power available on any networked device in order to solve complex calculation problems without having to invest in big infrastructures:

How would it be possible to use already installed infrastructures (PCs, etc) and tap into their calculation power in order to solve complex problems?

3.   ALMA Project objectives

ALMA would like to be an international research cooperation project between China and France on the following issues :

• Computing power issues
• Communication (low powered networked devices) power issues
• Parallel computing
• Optimization (filling a container, optimal route, …)
• Logistics operations issues

4.   French members of the project

a.   LAAS-CNRS

Web-site : http://www.laas.fr

LAAS-CNRS is one of the first and top research institution in France. This project involves the Asynchronous and Distributed Calculation laboratory with Mr. Didier El BAZ.

b.   FEMTO-ST

Web-Site: http://www.femto-st.fr

The FEMTO-ST laboratory is a very important research center in France. The Software and Complex Systems laboratory with Mr. Julien BOURGEOIS is involved in the ALMA project.

c.   EPROAD

Web-Site: http://www.u-picardie.fr/jsp/fiche_pagelibre.jsp?STNAV=&RUBNAV=&CODE=14366568&LANGUE=0

EPROAD is a research unit which is part of the Picardie University. It is famous in optimization and decision support and involves Mr. Toufik SAADI.