Multi-robot parcel sorting systems

Allocation and path finding

Bachelor thesis (2018)

Authors

B. van den Heuvel Electrical Engineering, Mathematics and Computer Science

Contributors

L.J.J. van Iersel (supervisor 1)
Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright: © 2018 Bram van den Heuvel
Optimization Planning Benchmark ILP Sorting Allocation Path Collision Makespan Heuristic Greedy Disjoint Parcel Robot Hamiltonian Tree-width Dynamic Programming Multi Commodity Flow Conservation A-star Rust Integrality Gap Test
More Info
expand_more

Published Date

26-07-2018

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

The logistics industry is being modernized using information technology and robots. This change encompasses a new set of challenges in warehouses. Recently, some companies have started using robot fleets to sort products and parcels. This thesis studies those systems, and researches the combinatorial problems that arise within them. Three main optimization problems are identified: 1. Finding an optimal layout of the sorting system on the warehouse floor; 2. Allocating products or parcels to be sorted to robots; 3. Finding paths that all robots can follow concurrently, without colliding. These problems are considered one by one. The first problem is understood on an intuitive level, while the other two are considered more closely. For both problems, several algorithms are considered. Some utilize greedy heuristics while others model the problem at hand precisely using integer linear programming methods. The algorithm’s real world performance is then assessed using a simulation. Slow, ILP-based algorithms are found to produce optimal solutions for small instances. However, they don’t scale well, and are unable to solve large instances. Greedy approximation algorithms solve all problem instance sizes tested, but produce solutions of lower quality.