Between May and October 2018, I have been writing my bachelor thesis at Viaboxx GmbH as part of my study at the University of Applied Sciences Bonn-Rhein-Sieg. The topic was “Modeling of a planning problem to the optimal use of technicians”, which is a variant of the vehicle routing problem with time windows.
Therefore, the topic can be described in other words with: An optimal tour should be generated, where technicians are performing different kinds of orders with predetermined constraints (duration of a tour, number of technicians, time windows, etc.). My task was to transform the problem into a mathematical model, present algorithms for solving it and compare the different approaches.
From the various available algorithms, I selected some which I then evaluated with the constraint solver OptaPlanner and a self-written tool. For the self-written tool, I chose Java as programming language, as on one hand, I used this language for most of the projects I had worked on before as student, and on the other hand, Viaboxx GmbH frequently uses it for their projects, too.
A majority of the evaluated algorithms were in fact already implemented in OptaPlanner, but they had to be adapted to the data model. Since the integration of other algorithms (e.g. a new construction heuristic) in OptaPlanner could not be realized in time for the thesis, they were implemented separately in the self-written Java tool. With this tool, tours could be calculated, but not graphically represented. The calculated tours could, however, be graphically represented with OptaPlanner.
To determine an optimal solution, a valid starting solution is required first, which is then improved with further algorithms.
After the execution of multiple tests with different test instances, the best results could be achieved by the combination of the following two algorithms: allocate entity from a queue as construction heuristic and late acceptance as local search. The first one was used to get a valid solution (all constraints were satisfied) and the second one to improve this solution.
The thesis showed, however, that by applying a new and not yet in OptaPlanner available construction heuristic, a good and valid initial solution could be quickly determined for the vehicle routing problem with timed windows.
Writing my Bachelor thesis at Viaboxx was the greatest experience so far for me. Encouraged and supported by a very good working atmosphere characterized by young, experienced colleagues, I could develop my skills in many fields like programming and complexity of algorithms.
Special thanks go to Jan Nonnen for his support and pieces of advice!
by Emmanuel Andela