Dynamic Distribution through the city of Amsterdam

Abstract

This report explains the design choices, implementation and results of a software engineering project commissioned by MakeTek. The team was tasked with making a system that could solve bike delivery scheduling problems with limited bike carrying capacity, time windows, dynamic delivery additions, movable pickup points and delivery time estimates.

The project started with two weeks of research, which concluded that the main algorithm should be a Genetic Algorithm (GA). The final product contains an app for visualising results as well as a backend that runs the genetic algorithm. Both systems are written in TypeScript and built upon a boilerplate provided by MakeTek. To calculate routes an open source routing provider is used, and the project is executed with an agile development workflow to ensure the product conforms to the client's expectations.

The implemented system contains almost all desired features and the missing ones were chosen to not be included due to time constraints and limited functional benefits. It is well-tested, extensible and adheres to software quality standards.

A solution is constructed by first clustering deliveries by location to distribute them over the bikes, then the genetic algorithm is run on each cluster separately. At the end of every generation of the GA the intermediate best solution is saved in a database. This ensures a valid solution is available at all times. Finally, postprocessing can be run on the final solution which checks if it is more efficient for a deliverer to wait between certain deliverers to prevent them from being early.

Testing shows that the implemented system and its features work as intended on different datasets. The effect of different parameters on the performance of the genetic algorithm is explored, with the following conclusions:

The algorithm should have enough opportunity to explore the solution space. This is achieved by setting an appropriate mutation parameter.

No significant performance differences are present between single point, two-point and uniform crossover.

Tournament selection converges faster than roulette selection, but explores less of the solution space.


The resulting system successfully implements all of the requirements as set by the client. It includes an algorithm that converges to an optimum, it can adapt to new changes and a solution can be requested at any time during runtime. It can be concluded that the project is brought to a successful end.