Conference Agenda

This paper considers the scheduling of electric vehicles in a public transit system. The restriction on range of electric vehicles is alleviated by allowing charging stops in between consecutive service trips.

To solve this multiple depot vehicle scheduling problem, we develop a machine-learning-assisted matheuristic based on column selection. A machine-learning model is trained to predict whether a vehicle schedule is likely to be part of a good solution. We use the machine-learning model to decide which branch of an enumeration tree should be extended until a feasible solution is found. The optimal charging stops are then inserted into every created vehicle schedule using dynamic programming. A set partitioning model is formulated to choose the best subset of vehicle schedules and solved by applying Gurobi. We also use the machine-learning model to derive a simple decision rule to create a second heuristic approach that is fast enough to solve large instances of the AF-VSP. The algorithms are then tested on randomly generated data and a subset of a real world dataset extracted from the Berlin City Open Data Portal, containing 6,583 service trips. Both algorithms outperform a state-of-the-art literature heuristic.

The use of drones makes it possible to reach areas that are inaccessible by vehicles operating on the ground. However, the limited energy capacity of a drone’s battery limits its flight range. This drawback can be mitigated when the drone is carried by trucks to advantageous launching points and when the drone’s battery is exchanged along its way. We propose a MILP in the Euclidean space where one drone must reach a faraway target location and where on its way, it lands on moving trucks for a battery exchange. The objective is to reach the target location as early as possible. Furthermore, we consider the following aspects: obstacles with which the drone must not collide, a service time for the battery exchange and a drone energy consumption dependent on velocity.

We consider two interesting variants of routing problems inspired by applications in manufacturing and healthcare, where vehicles must visit the depot multiple times.

The first, called Collection and Delivery problem of biomedical Specimens (CDSP), addresses healthcare logistics. In this problem, specimens (blood, plasma, urin etc.) collected from patients in doctor's offices are transported to a central laboratory for analysis. It involves multiple trips, time windows, a homogeneous fleet, and aims to minimize total completion time of delivery requests. We propose a two-index MIP that, when used with an off-the-shelf solver, outperforms both the state-of-the-art model and metaheuristic from the literature.

The second problem involves Autonomous Guided Vehicles (AGVs) that must perform a set of transport requests within the constraints of their battery capacity, necessitating regular battery swaps. This results in a parallel machine scheduling problem with job-dependent activity cycles and constant maintenance time, where the machines are AGVs, and maintenance time refers to the battery swap duration. For this problem, we introduce a novel MIP that surpasses existing state-of-the-art models. We also develop a logic-based Benders decomposition strengthened by valid inequalities, enabling to solve previously unsolved instances reported in the literature.