Route planning with ant system

For a set of destinations, finding the route that gives the smallest length is the well known Traveling Salesman Problem, a combinatorial optimization problem.

For a reduced number of stops, there is no difficulty in looking at all possible combinations. This becomes impossible with increase of the number of destinations because of the factorial relationship between them and the number of routes. For example, for only 12 destinations there are 39,916,800 possible itineraries.

A way to solve this problem, with no guarantee to find the best path, but at least a good one, is inspired on the behavior of ants. Proposed by Dorigo in 1993, it takes the dynamics of pheromones as a mean of selecting the shortest route.

Ant two-way highway by David Short, flickr, CC BY 2.0, cropped

In this post I present my implementation of the ant system in Python. An application to a real world problem will show you how to use ants to plan your next route trip.

Who were the very first to be vaccinated against COVID-19?

Recently, and gladly, vaccination campaigns against COVID-19 are popping up around the world. The first person to be vaccinated is mostly a political choice, a great opportunity to pass a message to the population. After seeing the first images of UK, Europe and Brazil, I got interested in looking for who received the first injection in every country. Until the day I gathered the data, the average first recipient is a 64-years-old retired woman. Next, I present in details my small research.

Noise in my balcony: a lockdown history

From March 17 to May 11 2020, France was in lockdown due to COVID-19 [1, 2]. At these times, leaving your house was limited to essential displacements (buying groceries, work if working from home was impossible, short close-to-home workout, etc). Several locations remained closed after May 11 (like movie theaters), but “non-essential movements” were allowed. As expected, these restrictions had an incredible impact on the motion of people and vehicles, thus, the urban noise. I live next to a 4 lanes avenue, about 8 km from an airport and 3 km from a hospital, so transportation noise is something that is part of my routine. A few days into the start of moving restrictions I had an idea to somehow measure the effect of the lockdown on the noise pollution I’m confronted.

For that, from March 31 to June 30 (92 days), I went to my balcony at 18h30 and recorded 5 minutes of ambiance sound using my smartphone (with Smart Recorder app, at the sampling frequency 44.1 kHz and with automatic gain control disabled). All analysis, from data treatment to plotting, is performed in Python. An example of what I recorded is presented next (note that the audios are downsampled and compressed for publication):

Sample of recording (May 28, after the end of lockdown) where we can hear, for example, vehicles passing by [1:40-2:00, 3:15-3:25] and an airplane landing [2:03-2:40].

The sound of a bottle being filled

I got interested in seeing how do the spectral distribution of everyday sounds look like. So I got an app in my phone (Smart Recorder) and started recording them. The most interesting result (until now) is from the simplest sound I have recorded: a bottle of milk being filled at my kitchen’s tap. I present the audio, associated spectrogram and the theoretical analysis in this post. All the work is performed in Python, from reading the data to plotting.

Audio recording

Here is the audio:

As it sounds, it is just a bottle being filled with water. At the beginning ($$t$$ < 1 second) there is nothing, until I open the tap. After about 32 seconds, the bottle is full and water is overflowing to the sink. There is a constant component lied to the impact of the particles on the bottom of the bottle/water column. Besides that, an indistinguishable and interesting tone that is changing in time can be heard. This sound is a resonance of air column with a closed-end (that is actually the water) and an open-end:

Change of resonance frequency with the air column height.

There is an increase of the frequency with the reduction of the wavelength $$\lambda$$, that is linear in time until around 20 seconds. After that the increase is not constant due to the non linear modification of the available space for the air inside the bottle originated from the reduction of the diameter with the height.

Simple countdown video in Python

So, in a month from now I’m going to participate at the 3 Minute Thesis contest at my university. As one can deduct by its name, the whole idea is presenting your PhD subject in only 3 minutes.

For practicing, I created a simple countdown video using Python, obviously it goes from 180 to 0. For that, I had to install FFMpeg so I could save in a different format than the HTML provided by the matplotlib’s Animation module when you have no real video writer available. The simplest way was just using the conda environment (the one I use for my Python coding):

 conda install -c menpo ffmpeg

The idea is just make one frame per second, so FPS = 1, where each one of them is a centered text with the correspoding time, no axis. The bitrate could be reduced, to make a smaller video. As it’s just a simple countdown, there is not any major losses in the quality with a bitrate of 80 (but reduced from 2.44 MB to 1.82 MB). So the writer options were:

    FFMpegWriter = animation.writers['ffmpeg']
writer = FFMpegWriter(fps=1,
codec='mpeg4',
bitrate=80)


Using the default codec, it was running fine with the VLC player. Just to make it more general for sharing with my colleagues, I tried with Windows Media Player, and it was quite awful. So I just picked the MPEG-4 codec (as you can see in the previous extrait of the program), from the list of available codecs that you can see by typing in your terminal:

 ffmpeg -codecs

A good improvement would be adding a bip when you reach 0 or something close to that. For the moment, the text color just changes to red.
You can check the complete script here: simple_countdown.py

If you got in here because you are also practicing for something similar, I hope this scripts helps you and wish you good luck. Once I do my presentation, I’ll problably put the video here, so stay tuned!