J. Varga:

"Computational Methods for Fleet Scheduling in E-Mobility";

Supervisor: G. Raidl; Institute of Logic and Computation, 2021; final examination: 2021-08-16.

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.

Created from the Publication Database of the Vienna University of Technology.