Smart Cities in Europe and the ALMA Logistics Project

Abstract ：In this paper， a brief survey of smart citiy projects in Europe is presented. This survey shows the extent of transport and logistics in smart cities. We concentrate on a smart city project we have been working on that is related to A Logistic Mobile Application （ALMA）. The application is based on Internet of Things and combines a communication infrastructure and a High Performance Computing infrastructure in order to deliver mobile logistic services with high quality of service and adaptation to the dynamic nature of logistic operations.

Keywords：smart cities; Internet of Things; logistics; combinatorial optimization; high performance computing

1 Introduction

The growth of cities has been particularly noticeable in the twentieth century and has raised many issues related to pollution， health， water distribution， logistics， and transport. The concept of smart cities has emerged recently as a way of addressing these issues using technology and social information. The European Union has promoted several smart cities projects with the goal of sustainable development. One of these projects is SmartSantander， a city?scale facility for experimental research on smart?city applications and services that are scalable， flexible， and open. The project involves the deployment of 20，000 sensors in several European cities， including Belgrade， Guildford， Lübeck， and Santander. IoT technologies and user acceptability will be the subjects of experimental research and testing.

Logistics and transport is of primary importance in a smart city. For logistics operators who deliver goods to customers， optimizing quality of service， e.g.， ensuring on?time delivery for reasonable cost， is of major concern. This necessitates the optimization of truck loading and vehicle routing. The nature of logistics is dynamic―orders or cancellations may be made at any time， and transportation difficulties may arise at any time. These vicissitudes may be due to vehicle faults， traffic jams， or weather conditions.

In this paper， we concentrate on smart cities in Europe and present “A Logistic Mobile Application” （ALMA） project， which proposes a mobile， real?time， IoT?based approach to solving dynamic logistic problems and optimizing quality of service in logistics. Mobile devices like smart phones are used to report good delivery occurrences and incidents like an engine fault or a traffic jam; they are also used in order to launch computations related to the solution of a resulting routing problem on computing infrastructures in order to cope with incidents in real time. The ALMA project relies on a new high?performance computing （HPC） infrastructure that makes use of clusters， grids and volunteer computing， e.g.， peer?to?peer networks via a broker that takes into account computational need and machines availability. The peer?to?peer concept has seen great developments with file sharing applications like Gnutella or FreeNet. Recent advances in microprocessors architectures， e.g.， multicore processors and advances in high bandwidth networks permit one to consider high performance volunteer computing as an economic and attractive solution. The ALMA project relies also on new optimization algorithms for the solution of combined truck loading and vehicle routing problems.

In section 2， we present a brief overview of smart city projects in Europe. Section 3 deals with logistics issues. We present ALMA architecture in section 4; in particular， we detail the communication infrastructure and the HPC infrastructure. Some preliminary computational results are presented in section 5. Finally， conclusions and future work are introduced in section 6.

2 Smart Cities

From the time “smart cities” was first coined in 2000 [1]， there have been numerous definitions of what a smart city is [2]-[6]. In [1]， a smart city is “the urban center of the future， made safe， secure environmentally green， and efficient because all structures―whether for power， water， transportation， etc. are designed， constructed， and maintained making use of advanced， integrated materials， sensors， electronics， and networks which are interfaced with computerized systems comprised of databases， tracking， and decision?making algorithms.” In this very first definition， the technological part is emphasized but the citizen are forgotten which is corrected in this later definition from [4]： “Smarter Cities are urban areas that exploit operational data， such as that arising from traffic congestion， power consumption statistics， and public safety events， to optimize the operation of city services. The foundational concepts are instrumented， interconnected， and intelligent. This approach enables the adaptation of city services to the behavior of the inhabitants， which permits the optimal use of the available physical infrastructure and resources.”

The turning point in Europe for the definition of smart cities is a report of the Centre of Regional Science at Vienna University of Technology [3]， which identifies six main axes defining a smart city. These axes are： smart governance （participation）， smart mobility （transport and information and communication technologies， ICT）， smart environment （natural resources）， smart people （social and human capital）， smart living （quality of life） and a smart economy （competitiveness）. The smart city is also defined as “A city well performing in a forward?looking way in economy， people， governance， mobility， environment， and living， built on the smart combination of endowments and activities of self?decisive， independent and aware citizens.”

In this report， a definition of the smart city within Europe emerged [7]： a smart city “is a city seeking to address public issues via ICT?based solutions on the basis of a multi?stakeholder， municipally based partnership”. This definition is still contested but is generally accepted as the official definition.

To be classified as a smart city， a city must contain at least one initiative that addresses one or more of the following characteristics： smart governance， smart people， smart living， smart mobility， smart economy， and smart environment. ICT initiatives based on these characteristics aim to connect existing and improved infrastructure to enhance the services available to stakeholders （citizens， businesses， communities） in a city.

2.1 Development of Smart Cities in Europe

If this latter definition is used， it is possible to evaluate the status of smart city within the EU， counting only its 28 member states. Ninety percent of cities with a population of more than 500，000 have implemented or are in the process of implementing smart cities initiatives. This percentage drops to 51% for cities with a population of more than 100，000. This means that the concept of smart city is well?known in EU. The champions are the UK， Spain， Italy， Austria， Denmark， Norway， Sweden， Estonia and Slovenia.

2.2 State of the Art

Smart Urban Spaces （SUS） [8] is a project funded by EU in 2009. The aim of this project was to deploy innovative mobile services in real conditions using a network of European cities. Different applications have been developed like ticketing service but the most interesting application is a museum quest a quiz installed at the Caen museum. This application uses near?field communication （NFC） tags to ask questions about the item displayed.

The main concern at EU level for a smart city is energy efficiency. Many different EU projects have been funded to study how to enhance energy usage in future cities. Building Energy Decision Support Systems for Smart Cities （BESOS） [9] integrates diverse and heterogeneous energy?management systems into a single platform， enabling higher?level applications to take care of data and services from multiple sources. Better energy efficiency in buildings is also the objective of the Control and Optimisation for Energy Positive Neighbourhoods （COOPERATE） [10] project， which has the same idea of offering a single interface for many different sensors and data. Decision Support Advisor for Innovative Business Models and Use Engagement for Smart Energy Efficient Districts （DAREED） offers approximatively the same service but at a wider range. It also puts the citizen at the center of the system， providing information and action that can be taken to reduce energy consumption. Within the same scope one can cite District of the Future （DoF） [11] and Energy Efficiency in the Supply Chain through Collaboration， Advanced Decision Support and Automatic Sensing （e?SAVE）.

Other projects， such as Energy Forecasting （NRG4CAST）， focus on efficient energy distribution in urban and rural communities through real?time management， analytics and forecasting. The Energy Positive Neighbourhoods Infrastructure Middleware based on Energy?Hub Concept （EPIC?HUB） project developed a middleware to ease this task.

Finally， keeping the ease of use in mind the Environmental Services Infrastructure with Ontologies （ENVISION） project aims to help non?ICT specialists discover and combine environmental services.

In the smart governance item， the flagship is Helsinki with the Infoshare project [12]. Infoshare gives free access to various urban statistics which can be used by businesses， academia and research institutes， governmental institutes or citizens. These data are covering many different aspects of Smart governance like living conditions， employment， transport， economics and so on.

3 Logistics

Logistic applications involve difficult problems， most of which are NP?complete problems [13]-[17]. The ALMA logistic application considers combined truck loading and vehicle routing problems. Treatment of vehicle routing problems in conjunction with truck loading is very attractive in just?in?time distribution context. Indeed the stock can be close to zero. This technique is used more and more in car manufacturing and mass?market retailing. Despite the advantages of just?in?time distribution， in particular， cost reduction， this technique may create weaknesses in the logistic chain in case of failures. Therefore， it is necessary to treat dynamically and as quickly as possible the events that may perturb the correct working of the logistic chains.

Treatment of vehicle routing problems in conjunction with truck loading has been discussed in the literature [13]-[16]. The ALMA logistic application concentrates on dynamic logistic problems whereby dynamism results from new orders， cancellations， as well as traffic incidents that may occur at any time. This leads to extremely difficult problems. Our approach is based on the approximate solution of truck loading problems via strip generation and beam search [17]-[19]. Vehicle?routing problems are solved via Ant Colony Optimization （ACO） [20]. This approach relies on parallel and distributed computing systems because those optimization problems are difficult to solve. We consider clusters， volunteer computing and peer?to?peer infrastructures.

4 Global Alma Architecture

The ALMA logistic application relies on two infrastructures： a communication infrastructure and an HPC infrastructure. Fig. 1 displays the infrastructures of the mobile application ALMA [21].

4.1 The Communication Infrastructure

Goods to be delivered are identified by tags. When a good is delivered， the transporter scans the tag and transmits the information in real time to the logistics centre with a smart phone connected to the Internet 3G. The mobile application is based on the existing telecommunication infrastructure. Similarly， the transporter informs the center in real time of traffic incidents， like road closed and traffic jam. In case of problems， e.g. traffic incidents， the proposed initial route may not be valid. Thus the transporter uses also the mobile application to ask for a new route. The request for a new route is transmitted to the broker of the HPC infrastructure.

4.2 The HPC Infrastructure

4.2.1 The Broker

The broker is designed in order to select a convenient HPC infrastructure from several available parallel or distributed computing systems. These systems may be clusters or peer?to?peer networks. For a given vehicle?routing problem and method， the broker selects a convenient topology and number of machines. This represents an evolution from the approach in [22]. The main goal of the broker is to select a computing infrastructure that satisfies the real?time constraints of the application. The requests of vehicle routing solution are associated with a deadline for result reception in order to limit important vehicle immobilization and blocking of the logistics application. The selection of unsuitable infrastructure leads to a suboptimal solution.

Two main phases are considered for brokering： first， the supervision of available resources， e.g. clusters or peer?to?peer networks. Secondly， the prediction of computation time for the considered problem and selected method. We note that these steps can be iterated several times in order to improve prediction. Reference is made to [23] to [25] for previous work on performance prediction of HPC applications on distributed computing infrastructures.

4.2.2 The Environment for Computing

The environment for computing is an extension of peer?to?peer distributed computing （P2PDC） [22]. P2PDC is a decentralized environment for peer?to?peer high?performance computing. P2PDC is a multinetwork environment that supports Infiniband， Myrinet and Ethernet networks. P2PDC is particularly used to task parallel applications. It is intended for scientists who want to solve difficult optimization problems or numerical simulation problems via distributed iterative methods that lead to frequent direct data exchanges between peers. References [26] and [27] provide more details and extensions of P2PDC. P2PDC relies on the use of the P2PSAP self?adaptive communication protocol [28] （Fig. 2） and a reduced set of communication operations， i.e.， P2Psend， P2Preceive and P2Pwait in order to facilitate programming. The programmer cares only about the choice of distributed iterative scheme of computation， e.g.， synchronous or asynchronous， that needs to be implemented and does not care about the communication mode between any two nodes. The programmer can also select a hybrid iterative scheme of computation， whereby computations are locally synchronous and asynchronous at the global level.

P2PSAP dynamically chooses the most appropriate communication mode between any two peers according to a decision taken at application level， such as scheme of computation and elements of context like network topology at transport level. In the hybrid case， the communication mode between peers in a group of nodes that are close and that present the same characteristics is synchronous， and the communication mode between peers in different groups is asynchronous. The decentralized environment of P2PDC is based on a hybrid topology manager and a hierarchical task?allocation mechanism which make P2PDC scalable. P2PSAP communication protocol was designed first as an extension of the CTP transport protocol [29] based on the CACTUS framework， which uses microprotocols [30].

The CTP protocol includes a wide range of micro?protocols including a small set of basic micro?protocols like Transport Driver， Fixed Size or Resize and Checksum that are needed in every configuration and a set of micro?protocols implementing various transport properties like acknowledgements， retransmissions， error correction and congestion control. The P2PSAP communication protocol takes into account Ethernet， Infiniband and Myrinet clusters. Reference is also made to [31] for details on peer?to?peer computing.

5 Experimental Results

Here， we consider loading problems and present preliminary experimental results obtained for a 2D cutting stock problem solved using a two?stage， two?dimensional method based on strip generation and beam search via the decentralized environment P2PDC on the Grid 5000 testbed. For details on the two?stage two?dimensional method based on strip generation and beam search see [32] and [33].

Fig. 3 shows the number of active processors during the solution of a cutting stock problem in function of the time. A maximum of twenty processors were allocated to this particular problem. The number of active processors varies according to the evolution of the algorithm， i.e.， the need of computing resources to treat the problem in parallel. In the beginning， the solution requires few computing resources because the number of nodes to explore is small. The number of processors increases with time because more and more nodes to explore are created until the limit is met， i.e.， the maximum number of twenty processors that were allocated to the solution of this problem. At the end of this solution， the number of active processors decreases because the number of nodes to explore decreases.

Obtaining a good approximation of the best solution at a given processor and communicating it to other processors means that the need for computing resources can sometimes be significantly decreased. This is what we observe when the number of processors decreases suddenly from twenty to fifteen. Nevertheless， we observe that the number of computing resources required may increase for a while before finally tending to zero at the end of the computation.

Fig. 4 displays solution times for several instances of cutting stock problems according to the maximum number of allocated processors.

Three cases are considered： a case with a maximum number of six computing nodes （diamonds）， a case with maximum number of ten nodes （squares）， and a case with twenty nodes （triangles）. In general， the more processors that are allocated， the smaller the solution time. This shows that our approach is scalable in terms of the number of computing resources， i.e.， the number of processors in the computing system. The design of the architecture of the HPC infrastructure also makes our approach scalable when the complexity of the problem increases， i.e.， when the number of goods and vehicles increases or the size of the city/conurbation increases due to the dedicated brokering system and large number of computing resources available via cluster or volunteer computing systems.

References [34] and [35] give details on peer?to?peer distributed algorithms for 2D Cutting stock problems. Reference [36] describes distributed branch and bound on peer?to?peer networks.

6 Conclusions

In this paper， we have presented an overview of smart city projects in Europe. We have shown that transport and logistics projects are prominent in smart cities. We have detailed the logistics mobile application ALMA that is based on the Internet of Things. ALMA addresses dynamic logistics problems whereby new orders or cancellations or traffic incidents may occur at any time. The ALMA application permits one to communicate in real time the information regarding delivery of goods.

The logistics application ALMA combines a communication infrastructure and a parallel/distributed computing infrastructure in order to obtain rapidly new routes for transporters that deliver goods to customers in case of incidents like traffic jam. The HPC infrastructure makes use of a broker to select the convenient parallel/distributed computing system as well as the number of computing nodes to perform computations according to a fixed deadline. Clusters or peer?to?peer infrastructures can be selected from a pool of available parallel/distributed computing systems. The computing infrastructure makes use of the high?performance computing decentralized environment P2PDC.

The mobile application ALMA also addresses combined truck loading and vehicle routing problems that lead to very complex optimization problems. Preliminary computational results for cutting stock problems solved on Grid 5000 have been presented and analyzed in the paper. This permits us to illustrate the interest of the proposed approach.

We are presently extending the P2PSAP communication protocol and P2PDC decentralized environment to multiple network context， i.e.， Infiniband， Myrinet and Ethernet networks， and heterogeneous architectures combining multicore CPUs and GPUs. The self?organizing strategies are also studied for deployment and efficiency purposes or for insuring everlastingness of applications in hazardous situations or in the presence of faults.

Acknowledgment

The authors wish to thank Agence Nationale de la Recherche （ANR） for support through several contracts. Experiments presented in this paper were carried out using the Grid’5000 experimental testbed being developed under the INRIA ALADDIN development action with support from CNRS， RENATER and several Universities as well as other funding bodies.

References

[1] B. Bowerman， J. Braverman， J. Taylor， H. Todosow， and U. Von Wimmersperg， “The vision of a smart city，” In 2nd International Life Extension Technology Workshop， Paris， France， Sept. 2000.

[2] A. Caragliu， C. Del Bo， and P. Nijkamp， “Smart cities in Europe，” Journal of Urban Technology， vol. 18， no. 2， pp. 65-82， 2011.

[3] R. Giffinger， C. Fertner， H. Kramar， et al.， “Smart cities?ranking of European medium?sized cities，” Vienna University of Technology， Vienna， Austria， Tech. rep.， 2007.

[4] C. Harrison， B. Eckman， R. Hamilton， et al.， “Foundations for smarter cities，” IBM Journal of Research and Development， vol. 54， no. 4， pp. 1-16， Jul. 2010.

[5] T. Nam and T. A. Pardo， “Conceptualizing smart city with dimensions of technology， people， and institutions，” in Proc. 12th Annual International Digital Government Research Conference： Digital Government Innovation in Challenging Times， New York， USA， Jun. 2011， pp. 282-291.

[6] K. Su， J. Li， and H. Fu， “Smart city and the applications，” in International Conference on Electronics， Communications and Control， Ningbo， China， Sept. 2011， pp. 1028-1031. doi： 10.1109/ICECC.2011.6066743.

[7] C. Manville， G. Cochrane， J. Cave， et al.， “Mapping smart cities in the EU，” European Parliament， Brussel， Belgium， Rep. IP/A/ITRE/ST/2013?02 PE 507.480， 2014.

[8] S. Chaumette and J. Ouoba， “A multilevel platform for secure communications in a fleet of mobile phones，” in 6th International Conference on Mobile Computing， Applications and Services， Austin， USA， Nov. 2014， pp. 173-174.

[9] W. Apolinarski， “Establishing secure intelligent environments，” in Workshop Proc. 11th International Conference on Intelligent Environments， Prague， Czech Republic， Jul. 2015， pp. 43-45.

[10] T. Greifenberg， M. Look， and B. Rumpe， “Integrating heterogeneous building and periphery data models at the district level： the NIM approach，” in Proc. 10th ECPPM eWork and eBusiness in Architecture， Engineering and Construction， Vienna， Austria， Sept. 2014， pp. 821-828.

[11] District of Future. （2015， Feb. 25-26）. “Europe： A better place to live and work，” Sabadell Smart Congress 2015 [Online]. Available： http：//www.districtoffuture.eu/index.php/mod.eventos/mem.detalle/id.22/relcategoria.104

[12] Helsinki Region Infoshare [Online]. Available： http：//www.hri.fi/en

[13] M. Iori， J. J. Salazar Gonzalez， and D. Vigo， “An exact approach for the symmetric capacited vehicule routing problem with two dimensional loading constraints，” DEIS， University of Bologna， Bologna， Italy， Tech. Rep. OR/03/04， 2003.

[14] M. Gendreau， M. Iori， G. Laporte， and S. Martello， “A Tabu search heuristic for the vehicle routing problem with two?dimensional loading constraint，” Management Science， vol. 40， no. 10， pp. 1276-1290， 1994.

[15] E. Choi and D. W. Tcha， “A column generation approach to the heterogeneous fleet vehicle routing problem，” Computers and Operations Research， vol. 34， no. 7， pp. 2080-2095， Jul. 2007.

[16] K. Ganesh and T. T. Narendran， “CLOVES： a cluster?and?search heuristic to solve the vehicle routing problem with delivery and pick?up，” European Journal of Operational Research， vol. 178， no. 3， pp. 699-717， May 2007.

[17] M. Hifi， R. M’Hallah and T. Saadi， “Approximate and exact algorithms for the double?constrained two?dimensional guillotine cutting stock problem，” Computational Optimization and Applications， vol. 42， no. 2， pp. 303-326， Mar. 2009. doi： 10.1007/s10589?007?9081?5.

[18] M. Hifi， R. MHallah， and T. Saadi， “Algorithms for the constrained two?staged two?dimensional cutting problem，” INFORMS Journal on Computing， vol.20， no. 2， pp. 212-221， 2008. doi： 10.1287/ijoc.1070.0233.

[19] M. Hifi and T. Saadi， “A cooperative algorithm for constrained two?staged two?dimensional cutting problems，” International Journal of Operational Research， vol. 9， no.1， pp. 104-124， 2010.

[20] M. Dorigo， “Optimization， learning and natural algorithms”， PhD thesis， Politecnico di Milano， Italy， 1992.

[21] D. El Baz， J. Bourgeois， T. Saadi， and A. Bassi， “ALMA， a logistic mobile application based on the internet of things，” in 2013 IEEE International Conference on Internet of Things， Beijing， China， Aug. 2013， pp. 355-358. doi： 10.1109/GreenCom?iThings?CPSCom.2013.78.

[22] T. T. Nguyen， D. El Baz， P. Spiteri， J. Jourjon， and M. Chau， “High performance peer?to?peer distributed computing with application to obstacle problem，” in Proc. 24th IEEE IPDPSW， Atlanta， USA， May 2010， pp. 1453-1461. doi： 10.1109/IPDPS.2010.5470930.

[23] B. Cornea， J. Bourgeois， T. T. Nguyen， and D. El Baz， “Performance prediction in a decentralized environment for peer to peer computing，” in Proc. 25th IEEE IPDPSW， Anchorage， USA， May 2011， pp. 1613-1621. doi： 10.1109/IPDPS.2011.321.

[24] B. Cornea and J. Bourgeois， “Performance prediction of distributed applications using block benchmarking methods，” in Proc. 19th Conference on Parallel， Distributed and Networked?Based Processing， Ayia， Napa Cyprus， Feb. 2011， pp. 183-190.

[25] B. Cornea and J. Bourgeois， “A framework for efficient performance prediction of distributed applications in heterogeneous systems，” The Journal on Supercomputing， vol. 62， no. 3， pp. 1609-1634， Dec. 2012. doi： 10.1007/s11227?012?0823?5.

[26] B. Cornea， J. Bourgeois， T. T. Nguyen， and D. El Baz， “Scalable performance predictions of distributed peer?to?peer application，” in Proc. 14th IEEE International Conference on High Performance Computing and Communication， Liverpool， UK， 2012， pp. 193-201. doi： 10.1109/HPCC.2012.34.

[27] T. Garcia， M. Chau， T. T. Nguyen， D. El Baz， and P. Spiteri， “Asynchronous peer?to?peer distributed computing for financial applications，” in Proc. 25th IEEE IPDPSW， Anchorage， USA， May 2011， pp. 1453-1461. doi： 10.1109/IPDPS.2011.292.

[28] D. El Baz and T. T. Nguyen， “A self?adaptive communication protocol with application to high performance peer?to?peer distributed computing，” in Proc. 18th Conference on Parallel， Distributed and Networked?Based Processing， Pisa， Italy， Feb. 2010， pp. 327-333.

[29] G. T. Wong， M. A. Hiltunen， and R. D. Schlichting， “A configurable and extensible transport protocol，” in Proc. IEEE INFOCOM’01， Anchorage， USA， 2001， pp. 319-328. doi： 10.1109/INFCOM.2001.916714.

[30] M. A. Hiltunen， “The Cactus approach to building configurable middleware services，” in Proc. DSMGC2000， Nuremberg， Germany， 2000.

[31] D. El Baz and G. Jourjon， “Some solutions for Peer to Peer Global Computing，” in Proc. 13th Conference on Parallel， Distributed and Networked?Based Processing， Lugano， Switzerland， Feb. 2005， pp. 49-58.

[32] M. Hifi and R. M’Hallah， “An exact algorithm for constrained two?dimensional two?staged cutting stock problems，” Operations Research， vol. 53， no. 1， pp. 140-150， 2005.

[33] M. Hifi and T. Saadi， “A parallel algorithm for constrained two?staged two?dimensional cutting problems，” Computers and Industrial Engineering， Vol. 62， No. 1， pp. 177-189， 2012.

[34] M. Hifi， T. Saadi， AND N. Haddadou， “High performance peer?to?peer distributed computing with application to constrained two?dimensional guillotine cutting problem，” in Proc. 19th Conference on Parallel， Distributed and Networked?Based Processing， Ayia， Napa Cyprus， Feb. 2011， pp. 552-559.

[35] D. El Baz， M. Hifi， and T. Saadi， “Peer?to?peer solution of 2D?cutting stock problems，” in Proc. 11th Cologne?Twente Workshop on Graphs and Combinatorial Optimization， Munich， Germany， May 2012， pp. 116-120.

[36] M. Djama?， B. Derbel， and N. Melab， “Distributed B&B： a pure peer?to?peer approach”， in Proc. 25th IEEE IPDPSW， Anchorage， USA， May 2011， pp. 1788-1797. doi： 10.1109/IPDPS.2011.337.

Manuscript received： 2015?08?10