# An iterated local search metaheuristic using ALNS and PyVRP

I have wanted to try implementing an iterated local search metaheuristic on top of the alns and pyvrp packages for some time. In this post I am going to do so, by building a very simple metaheuristic that already works very well for the vehicle routing problem with time windows.

# Set operations using bit arrays

Let $X, Y \subseteq \lbrace 0, 1, \ldots, N \rbrace$. These sets can be written in equivalent form as bit arrays of size $N + 1$. Let $x$ be the bit array form of $X$ (and similarly, $y$ of $Y$): the bit $x_i$ is flipped iff $i \in X$, and not set otherwise (where $i \in \lbrace 0, \ldots, N \rbrace$). Such bit arrays enable the following set operations:

• The membership test of $i \in X$ is given by (x >> i) & 1.
• The complement $X^\complement$ is given by ~x.
• The intersection $X \cap Y$ is given by x & y.
• The union $X \cup Y$ is given by x | y.
• The relative complement $X \setminus Y$ is given by x & ~y.
• The symmetric difference $X~\Delta~Y$ is given by (x & ~y) | (y & ~x), which is equivalent to x ^ y.

These operations can be performed very efficiently in hardware, which sometimes offers substantial performance gains over other approaches (e.g., those based on hash sets).

# 2D bin-packing of unequal circles

This post is inspired by this issue in the ALNS repository. We aim to efficiently solve a 2D packing of unequally-sized circles onto a minimum number of pallets, using column generation enhanced with some simple heuristics.

# Tail-call optimisation in Python using ast

Python does not have tail-call optimisation (TCO), and it likely never will. Several packages exist that add TCO via decorators (e.g., tco). Most of these packages use some lambda calculus to implement TCO. In this post I want to explore an alternative way to achieve TCO, using the ast module to rewrite the decorated function.

# Population and market integration in the Roman hinterland

This post is a based on our presentation at the EAA Annual Meeting in August 2020 (slides)

The Roman Empire was a remarkable achievement in world history: extending from the north of England to the Syrian Desert and Morocco at the height of its powers it integrated a population of some 60-100 million into one political, cultural and economic unit. For a few centuries this generated a remarkable growth in population.

To understand how this could be we have to focus on rural developments, and the best data for that are obtained by the many archaeological field surveys of the last half century.

# Test post

First post using Nikola. I use this post to compare how things render in various themes.