Feed on
Posts
Comments

Routing optimization in a humanitarian context

Routing optimization generally solves the Vehicle Routing Problem (a simple example being the more widely known Traveling Salesman Problem). A more complex example would be the distribution of goods by a fleet of multiple vehicles to dozens of locations, where each vehicle has certain time windows in which it can operate and each delivery location has certain time windows in which it can be served (e.g. opening times of a supermarket).

In this Jupyter example we’ll look at atypical humanitarian scenario of distributing medical goods during disaster response following one of the worst tropical cyclones ever been recorded in Africa: Cyclone Idai.

In this scenario, a humanitarian organization shipped much needed medical goods to Beira, Mozambique, which were then dispatched to local vehicles to be delivered across the region. The supplies included vaccinations and medications for water-borne diseases such as Malaria and Cholera, so distribution efficiency was critical to contain disastrous epidemics.

We’ll solve this complex problem with OpenRouteService new route optimization service.

The logistics setup

In total 20 sites were identified in need of the medical supplies, while 3 vehicles were scheduled for delivery. Let’s assume there was only one type of goods, e.g. standard moving boxes full of one medication. (In reality there were dozens of different good types, which can be modelled with the same workflow, but that’d unnecessarily bloat this example).

The vehicles were all located in the port of Beira and had the same following constraints:

  • operation time windows from 8:00 to 20:00
  • loading capacity of 300 [arbitrary unit]
You will find a Jupyter example with code solving the scenario  at https://openrouteservice.org/disaster-optimization/

For this example we’re using the FOSS library of Vroom, which has recently seen support for OpenRouteService and is available through our APIs.

To properly describe the vehicle routing problem in algorithmic terms, we have to provide the following information:

  • vehicles start/end address: vehicle depot in Beira’s port
  • vehicle capacity: 300
  • vehicle operational times: 08:00 - 20:00
  • service location: delivery location
  • service time windows: individual delivery location’s time window
  • service amount: individual delivery location’s needs

Then we have to only wrap this information into our code and send a request to OpenRouteService optimization service at https://api.openrouteservice.org/optimization.

For all the details of the example see: https://openrouteservice.org/disaster-optimization/

We cordially invite everybody interested to our next open GIScience colloquium talk!

The speaker is Dr. René Westerholt from the Centre for Interdisciplinary Methodologies, University of Warwick, UK.

When: Monday 29.07.2019, 2:15 pm

Where: INF 348, room 015 (Institute of Geography, Heidelberg University)

Place in GIScience - A human geographic overview of the components to be formalised

The term “place” describes geographical entities that are important for individuals or groups of people. While abstract, geometric space, as it is mostly used in GIScience, is based on coordinates, places are represented and expressed verbally and on the level of experience. Therefore, it has been difficult in GIScience to grasp this inherently complex concept in order to make it available for formal treatments, reasoning, and modelling. This talk argues that many attempts to use place suffer from a lack of coherent theoretical underpinning and conceptual accuracy. Most GIScience papers refer to authors such as Yi-Fu Tuan, Edward Relph, and Doreen Massey. Too often, however, this happens in an almost anecdotal manner that does not take into account the philosophical depth of the concepts mentioned. In this talk, I will give a synopsis of the human geographical concepts of place and their constituent components that are likely to be required in a sufficiently comprehensive GIScience characterisation of places. These components include landscape (the visual component of place), locale (the physical conditions under which social interaction takes place), and sense-of-place (the way people relate themselves to places). These concepts are complex, and it is argued that it is precisely the great challenge of place-based GIScience research to combine them into a unified formal construct.

Last week, GIScience Heidelberg successfully held two collaborative workshops about OpenStreetMap (OSM) at the Department of Earth Observation in Jena. Dr. Chistian Thiel and his team from the University of Jena kindly organized the event. Three members of the GIScience Research Group and the Heidelberg Institute for Geoinformation Technology (HeiGIT), Dr. Michael Schultz, Benjamin Herfort and Janek Voß, took the opportunity to present our work.

In the context of building and maintaining an active network among academic institutions, we were able to introduce our research, share ideas, initiate future cooperation, impart knowledge and gather important data together. Both workshops were realized with the help of around 60 participants, who are future geography teachers from the University of Jena. We announced and outlined the event beforehand, via a 30 min Skype Video Conference. Last week, our primary objective was to empower the participants to work with OpenStreetMap (OSM) data at school in the future.

During the first workshop, held by Dr. Schulz and Janek Voß, students learned to combine theoretical knowledge about OSM with hands-on exercises, recognizing both potential and challenges of this datasource, as well as being able to obtain and use it. Also, data collected by participants will be used to validate our product osmlanduse.org in the future. The second workshop highlighted the potential of OpenStreetMap for disaster management and humanitarian aid. Together we mapped buildings and roads in Tanzania to support the work of the local communities there to fight FGM (Female Genital Mutilation).

We would like to thank participants and our colleagues in Jena for making this event a successful one and we are hoping to continue our collaboration in the near future.

Mitmach-Exponate geben auf der MS Wissenschaft in Heidelberg vom 28. August bis 1. September Einblicke in die Entwicklung und Anwendung Künstlicher Intelligenz (KI). Mit auf dem zu einer schwimmenden Ausstellung umgebauten ehemalige Kohlefrachter ist auch ein Exponat des Heidelberg Institute for Geoinformation Technology (HeiGIT) an der Universität Heidelberg, gefördert von der Klaus Tschira Stiftung. Das Institut unterstützt den Wissens- und Technologietransfer aus der Geoinformatik-Grundlagenforschung in die Praxis, vor allem in den Bereichen Humanitäre Hilfe, Smart Mobility und Big Spatial Data Analytics.

Mensch und Maschine – Forschung im Team
Für die Ausstellung hat das HeiGIT daher gemeinsam mit dem Alfred-Wegener-Institut für Polar- und Meeresforschung in Potsdam ein Exponat für die Ausstellung entwickelt, an dem die Gäste Satellitenbilder interpretieren können. Es stehen zwei Aufgaben zur Auswahl: Die Kartierung von Gebäuden oder das Erkennen von arktischen Frostmusterböden. Die Bildauswertung erfolgt in kleinen, einfachen Aufgaben (sogenannten „Mirco-Tasks“). Diese können an den beiden Touchscreens von den Besucherinnen und Besucher auf der MS Wissenschaft in wenigen Sekunden gelöst werden.

Die gesammelten Informationen dienen als Datengrundlage für das „Training“ eines KI-Algorithmus, um Objekte wie Häuser automatisch zu erfassen. So wird die menschliche Fähigkeit, Satellitenbilder zu interpretieren, mit dem Vorteil der KI, große Datenmengen automatisch zu verarbeiten, vereint. Die gewonnenen Geoinformationen sind unter anderem nützlich für gesellschaftsrelevante Anwendungsfelder. Zum Beispiel um nach Naturkatastrophen zerstörte Gebäude zu kartiert oder Veränderungen des empfindlichen arktischen Ökosystems im Kontext des Klimawandels zu erkennen.

Das Exponat selbst ist keine KI, stellt aber eine Methode dar, wie Datensätze erhoben werden können, um KI-Modelle zu trainieren. Denn die rasant wachsende Zahl an verfügbaren Satellitenbildern ermöglicht es uns aus einer einzigartigen Perspektive ein besseres Verständnis unserer Erde zu erlangen. Automatisierte Verfahren stoßen bei der Interpretation dieser Aufnahmen aus dem All jedoch an ihre Grenzen. Aus diesem Grund wird erforscht, wie das Zusammenspiel zwischen Mensch und KI zu einer verbesserten Bildauswertung führen kann.

Quelle:
https://www.heidelberg.de/hd/HD/Arbeiten+in+Heidelberg/16_07_2019+exponat+aus+heidelberg+bietet+training+fuer+ki-algorithmen+auf+der+ms+wissenschaft.html

Weiterführende Information zum „Micro-Mapping” + KI:

Porto de Albuquerque, J., B. Herfort, M. Eckle (2016): The Tasks of the Crowd: A Typology of Tasks in Geographic Information Crowdsourcing and a Case Study in Humanitarian Mapping. Remote Sensing. 2016, 8(10), 859; doi:10.3390/rs8100859.

Herfort, B., Höfle, B. & Klonner, C. (2018): 3D micro-mapping: Towards assessing the quality of crowdsourcing to support 3D point cloud analysis. ISPRS Journal of Photogrammetry and Remote Sensing. Vol. 137, pp. 73 -83.

Chen, J., Y. Zhou, A. Zipf and H. Fan (2018): Deep Learning from Multiple Crowds: A Case Study of Humanitarian Mapping. IEEE Transactions on Geoscience and Remote Sensing (TGRS). 1-10. https://doi.org/10.1109/TGRS.2018.2868748

A pilot study for the Waterproofing Data project took place in Brazil (Rio Branco and São Paulo) last month. Carolin Klonner from the GIScience team and researchers from the UK and Brazil focused on testing the developed methods in the specific setting of the study areas and on exploring the flood mitigation measures taken by local authorities and flood-affected citizens. Students of local schools as well as people living in the area took part in the workshops with several different tasks. Students learned how to digitally map their surrounding area, and local citizens shared their experiences of flood events in memory stories, interviews as well as participatory mapping activities. During walks through the flood prone areas, the researchers were able to identify flood protection measures of the people living in these areas. Moreover, the difficult living conditions for these people became apparent. Overall, it was a very successful trip during which a lot of valuable feedback for adapting the methods was gained, and future steps of the project were discussed among the interdisciplinary and international research team.

Where is the next shaded bench to escape the burning heat? Where can I play soccer within the city and later on have a barbecue with my friends? All of these questions require information about features of urban green spaces. Although it is easy to find the right place within your own neighbourhood, it is usually more difficult if you are in an unfamiliar area. Together with our partners of the meinGrün project we are developing an app which will help you find and navigate to the best green space for your needs, no matter where you are.

But wait, first we need to gather the data before we can make recommendations. Our partner cities Heidelberg and Dresden have already provided us with a lot of valuable information about public urban green spaces. But still, these data sets don’t provide all the necessary information about green spaces that we need e.g. there is no official data set of benches in Heidelberg. To fill these data gaps we are exploring what kinds of urban green space features we can extract from OpenStreetMap (OSM) and at what quality to complement the municipal data. As a preliminary analysis we queried the number of benches across the cities Heidelberg and Dresden using the ohsome API by HeiGIT.


Looking at the map for Heidelberg, we can see that the distribution is quite heterogeneous, with parks generally showing higher numbers of benches. In Heidelberg for example, the number of mapped benches in the old town and at the Neckarwiese (popular public green area) seems rather high, while the campus Im Neuenheimer Feld shows only one hotspot for benches at the botanical garden. To draw conclusions regarding the mapping completeness just from looking at these distributions is risky, since some areas, e.g. especially industrial areas, may not even contain benches. Therefore, we are looking at ways to better quantify mapping completeness and OSM data quality indicators.

An initial approach is to find correlations in the data: are there many active OSM editors in an area where there are no benches? How many benches can usually be expected in areas with e.g. landuse=park? Are for example waste bins usually associated with benches?

Below maps show the number of contributing OSM editors for both Heidelberg and Dresden, as well as the number of mapped waste baskets for these locations.



Generally, by visually inspecting the maps, we can see that there are usually a higher number of trash cans associated with areas containing benches. In the example from above of the botanical garden, we see that trash cans are barely mapped, while there are quite a few editors active in that area. It would be one area to investigate, whether there are indeed trash cans, just waiting to be mapped in OSM! Regarding the campus area, where neither benches nor trash cans are mapped in in larger numbers, we also see only a marginal amount of OSM users. Does this indicate missing data in OSM? We’re working hard on exploring some indicators to discover missing data in OSM!

In order to fill some of those data gaps, we would also like to encourage more people in Heidelberg and Dresden to share their local knowledge of urban green spaces by contributing to OSM. Therefore, we joined the roadto_ festival last Saturday, July 6th 2019, organized by the DAI in Heidelberg.

People were very interested in the project and excited to be able to contribute their perception on local green spaces and route quality. Our map of Heidelberg quickly filled up with green spots, where people denoted their favourite activity in their special green space, as well as blue routes that they prefer for biking through the city. Pink routes and spots indicated problematic routes with e.g. lots of traffic, short traffic light signals etc.

Change analysis of rock glaciers is crucial to analyzing the adaptation of surface and subsurface processes to changing environmental conditions at different timescales because rock glaciers are considered as potentially unstable slopes and solid water reservoirs. To quantify surface change in complex surface topographies with varying surface orientation and roughness, a full three‐dimensional (3D) change analysis is required. This study therefore proposes a novel approach for accurate 3D point cloud‐based quantification and analysis of geomorphological activity on rock glaciers. It is applied to the lower tongue area of the Äußeres Hochebenkar rock glacier, Ötztal Alps, Austria. Multi‐temporal and multi‐source topographic LiDAR data are used to quantify surface changes and to reveal their spatial and temporal characteristics at different timescales within the period 2006–2018. LiDAR‐based examinations are complemented with subsurface characteristics obtained from electrical resistivity tomography.

This combined approach reveals active and variable spatial and temporal surface dynamics in the investigated area, with minimum detectable change between 0.09 and 0.65 m at 95% confidence. Given that this approach overcomes current uncertainties in established methods of differentiating complex rock glacier surfaces, we consider it a valuable addition that can be applied to objects of similar properties such as landslides or glaciers.

Find all details in the full paper:

Zahs, V., Hämmerle, M., Anders, K., Hecht, S., Rutzinger, M., Sailer, R., Williams, J.G., Höfle, B. (2019): Multi-temporal 3D point cloud-based quantification and analysis of geomorphological activity at an alpine rock glacier using airborne and terrestrial LiDAR. Permafrost and Periglac Process. 2019;1-17. DOI: https://doi.org/10.1002/ppp.2004.

Research is continued…

Research at the active rock glacier Äußeres Hochebenkar is continued within the frame of two current research projects (AHK-4D, Geomorph4D) of the 3DGeo group.

  • AHK-4D focuses on the development of a methodology to quantify the magnitudes and frequencies of individual surface change processes of a rock glacier over several years. We do this by analyzing three dimensional (3D) surface change based on high-resolution, high-frequency (bi-weekly) and multisource LiDAR data. Follow our updates on Twitter.
  • Geomorph4D aims at exploring the importance of rockfalls and talus accumulation at the headwall of rock glaciers, and to examine this within the context of changing climate conditions, and therefore stresses, within paraglacial environments.

If you are interested in using LiDAR data acquired at the AHK rock glacier for your own research, you can find multi-temporal terrestrial laser scanning datasets openly provided on PANGAEA:

Pfeiffer, J., Höfle, B., Hämmerle, M., Zahs, V., Rutzinger, M., Scaioni, M., Lindenbergh, R., Oude Elberink, S., Pirotti, F., Bremer, M., Wujanz, D. & Zieher, T. (2019): Terrestrial laser scanning data of the Äußeres Hochebenkar rock glacier close to Obergurgl, Austria acquired during the Innsbruck Summer School of Alpine Research. PANGAEA. DOI: https://doi.pangaea.de/10.1594/PANGAEA.902042 .

Members of the GIScience research group, Dr. Tessio Novack, Dr. Michael Schultz, Dr. Yair Grinberger, Prof. Dr. Alexander Zipf, along with Dr. Peter Mooney of Maynooth University, Ireland, organized a pre-conference workshop as part of the AGILE 2019 conference in Limassol. The workshop titled “Geographical and Cultural Aspects of Geoinformation: Issues and Solutions (geoCultGIS)” aimed at developing a discussion around the constraints geo-cultural contexts put on the generalizability and transferability of geoinformatic methods and geographical data, while also considering the approaches for handling these.

The workshop included a mix of research talks with an open discussion around the themes of the workshop and attracted multiple participants from diverse research and cultural backgrounds such as Dr. Andrea Ballatore (Birkbeck, University of London), Prof. Catherine Jones (University of Luxemburg), Prof. Toshihiro Osaragi (Tokyo Institute of Technology), Dr. Stefan Steiniger (Pontificia Universidad Catolica de Chile), and Mr. Yoav Zohar (Israeli Police). The research talks included an introductory talk by Dr. Novack, a study of the institutional contexts of OpenStreetMap data by Dr. Grinberger, a presentation about the spatial signatures of places by Mr. Rui Zhu of UC Santa Barbara, and an inquiry into the representation of urban green spaces in OpenStreetMap across different regions by Ms. Christina Ludwig of Heidelberg’s GIScience team.

These presentations stimulated a World Cafe-style workshop during the afternoon, led by Dr. Schultz, in which the group discussed the issues, open questions, and approaches related to geo-cultural contexts relevant to each of the participants’ research projects. The discussion targeted the identification of geo-cultural elements resilient to context and therefore transferable, using the metaphor of the Glass Bead Game as inspiration. Disaster response was identified as particularly suitable vehicle of thought to communicate geo-cultural aspects. Essential spatial parameters that were understood as linked to geo-cultural aspects included security, social, emotional, technological and economic contextual aspects.

The outputs of the workshop will soon be published in the form of online proceedings with their own DOI. This will be followed by a Call for Papers for a special issue of Transactions in GIS focusing on the themes of the workshop. For more information, see the workshop’s website.

Das meinGrün Team ist morgen beim roadto_ Festival des DAI Heidelberg dabei. Unter dem Motto “Do-it-yourself together” gibt es heute und morgen viele verschiedene Workshops zum mitmachen und ausprobieren sowie Filme, Theater und Konzerte. Wir vom meinGrün Team werden während des Festivals über unser Projekt informieren und mal in die Runde fragen, wo man in Heidelberg denn gut Zeit im Grünen verbringen kann. Da OpenStreetMap in unserem Projekt eine entscheidende Rolle für die Extraktion von Informationen bezüglich städtischer Grünflächen spielt, werden wir den Teilnehmenden im Workshop auch zeigen, wie man OpenStreetMap Daten nutzen und zum Projekt beitragen kann.

(Grüne Route Bsp. Mannheim)

Welcome back to another ohsome blog post. Today, we will present the results of a recent analysis performed by our student assistant Jascha, who took a look at the distribution and development of farm shops (in German: Hofläden) at different scales in OpenStreetMap (OSM). This analysis is based on previous work within the global climate protection map. It allows its users to find relevant information about the topics energy supply, mobility, as well as nutrition and consumption. You can read more about it in this blog post.

Back on track, let’s take a look at the analysis and its results. The following gif shows the distribution of farm shops from 2009 to 2019 of Germany in a hexagonal grid. Whilst at the beginning of 2009 only about 20 hexagons had features with the OSM tag shop=farm, almost the whole of Germany was covered ten years later.

klick the picture to see the animated gif

If you are also interested in creating such a gif, you should read the blog How to become ohsome part 1. As usually, if you want to take a look at the exact request parameters and curl commands, we’ve prepared a snippet for you. The next visualization shows a diagram covering the development of farm shops in Baden-Württemberg in the same time frame of ten years, measured on a monthly basis. You can see a constant increase over the whole time period, similar to the gif of Germany showed above.

This pattern does not always apply though, which we see when we take a closer look down to city level (in this example the city of Heidelberg). Here, we’ve compared the mapped farm shops in OSM with official values from the city of Heidelberg in the given time frame. For getting the temporal aspect into that data set, we’ve contacted each farm shop and asked about their start/end dates, hence the visible temporal differences in the values. The following diagram shows these two measures:

The first mapped farm shop of Heidelberg in OSM was in June 2012. Interesting side-note: In this month, all nine new mapped farm shops in whole Baden-Württemberg where mapped in Heidelberg. When taking a closer look at the diagram, both data sets had the same number for roughly half of 2017. At any other time period, they were different. This could be, for example due to different tags being used for the OSM features, like amenity=marketplace, which also appears nine to ten times in Heidelberg from the first of July 2012 onwards.

To wrap it up, this small analysis shows that the attention for regional shopping and products is also reflected within OSM. On a regional and country-level scale, the data is still increasing, whereas on some city levels, like Heidelberg, it already seems to be quite complete. Further analysis looking deeper into the OSM data set would be necessary to precisely measure the (attributive) completeness of specific feature categories, for which the ohsome API http://api.ohsome.org/ can deliver the necessary functionalities. The next ohsome blog post will cover a new feature of the API, which should make your requests simpler. As always, you can reach us via info@heigit.org. Stay ohsome!

Older Posts »