Integer Programming Model for Automated Valet Parking
Name
Karl Tarbe
Abstract
As parking becomes a more and more complex problem with the number of cars and
city density, more complex solutions can be used to rectify it. One of possible
solutions for parking is automated valet parking, where cars are not driven to
parking place by humans but are carried by specially designed robots. Such
solution presents us many possible optimization problems, one of which is
addressed in this work using Integer Programming models, that can by solved
using off-the-shelf solvers. We look at a specific possible implementation of
automated valet parking and succesfully design an Integer Programming model to
solve it. Existing theoretical results have shown that even simplified cases of
the problem can be APX-hard. Using Gurobi,
optimal solution was found for sample cases. The model is compared to another
integer programming model from Algorithms and Theory research group, which
provides comparison and verification for the model performance.
city density, more complex solutions can be used to rectify it. One of possible
solutions for parking is automated valet parking, where cars are not driven to
parking place by humans but are carried by specially designed robots. Such
solution presents us many possible optimization problems, one of which is
addressed in this work using Integer Programming models, that can by solved
using off-the-shelf solvers. We look at a specific possible implementation of
automated valet parking and succesfully design an Integer Programming model to
solve it. Existing theoretical results have shown that even simplified cases of
the problem can be APX-hard. Using Gurobi,
optimal solution was found for sample cases. The model is compared to another
integer programming model from Algorithms and Theory research group, which
provides comparison and verification for the model performance.
Graduation Thesis language
English
Graduation Thesis type
Master - Computer Science
Supervisor(s)
Dirk Oliver Theis
Defence year
2016