[Zurück]

J. Varga:
"Computational Methods for Fleet Scheduling in E-Mobility";
Betreuer/in(nen): G. Raidl; Institute of Logic and Computation, 2021; Abschlussprüfung: 16.08.2021.

In this work we investigate the Fleet Scheduling Problem, which arises in the context of
E-carsharing. Given are a fleet of electric vehicles and a set of reservations. A reservation
consists of the timespan in which a vehicle is needed and the amount of energy that
is expected to be used. The task is to find a feasible assignment from reservations to
vehicles as well as a charging plan for each vehicle that minimize a cost function. The
problem can be shown to be NP-hard.
We aim to solve the problem in an exact manner. For that purpose we make use of
solvers for Mixed Integer Linear Programs (MILPs). We consider two different solution
approaches. First we formulate the problem directly as one MILP, which is strengthened
in several ways. In particular we also propose a class of strengthening constraints
that prohibit the assignment of subsets of reservations to a vehicle, if that assignment
is not possible due to charging constraints. In our second approach we perform a
Benders decomposition which decomposes the problem into a master problem (MP) and
a subproblem and solves them iteratively in an alternating manner. We perform the
decomposition in two different ways. First we do it in a more classical way, then we
choose different subsets of variables making the MP stronger and more complex and
the subproblem smaller. It turns out that the MP is the bottleneck of the Benders
decomposition. We therefore investigate different measures that aim to improve the
performance of solving the MP instances. The first measure implements Branch-and-
Check which embeds the Benders decomposition in a single Branch-and-Bound tree.
That way the MP does not need to be solved from scratch in each iteration. For the
second and third measure we speed up the solving process of the MP by solving it in an
inexact manner, either allowing a gap for the MILP solver or applying a heuristic. The
heuristic is based on General Variable Neighborhood Search and we are able to make
use of delta evaluation in order to speed up the search of the neighborhoods. We also
propose a network flow formulation that can be used to solve the subproblem. However,
we found that the network flow formulation solved with a network simplex algorithm
does not perform better than the linear program solved with a general purpose linear
program solver. Therefore we do not investigate further here.
As it turns out directly solving the single MILP usually performs better than the Benders
decomposition approach for small to medium sized problem instances. For large instances
however the MILP solvers are not able to find any reasonable primal solutions while the Benders decomposition was able to do so and therefore achieved smaller gaps. Especially
the variant that uses a heuristic for the MP is able to find good feasible solutions for
large instances, altough at the cost of not finding reasonable dual bounds for many of
these instances.