Jakob Puchinger

Boshuai Zhao, Adam Abdin, Jakob Puchinger

The Electric Autonomous Dial-a-Ride Problem (E-ADARP) involves routing and scheduling electric autonomous vehicles under battery capacity and partial recharging constraints, aiming to minimize total travel cost and excess ride time. In practice, operational data for time and state-of-charge (SoC) are often available only at a coarse granularity. This raises a natural question: can discretization be exploited to improve computational performance by enabling alternative formulation structures? To investigate this question, we develop three formulations reflecting different levels of discretization. The first is an improved event-based formulation (IEBF) with arc-flow SoC variables for the continuous-parameter E-ADARP, serving as a strengthened baseline. The latter two are fragment-based formulations designed for discretized inputs. The second is a time-space fragment-based formulation with continuous SoC arc-flow variables (TSFFCS), which discretizes time while keeping SoC continuous. The third is a battery-time-space fragment-based formulation (BTSFF), which discretizes both time and SoC. Here, an event denotes a tuple consisting of a location and a set of onboard customers, while a fragment denotes a partial path. Computational results show that IEBF improves upon the existing event-based formulation for the original E-ADARP. Under discretized settings, TSFFCS tends to outperform IEBF, particularly when recharging is frequent and time discretization is relatively coarse, indicating that time discretization can improve computational performance across a wide range of settings. In contrast, BTSFF rarely outperforms TSFFCS unless the number of reachable SoC levels is limited, suggesting that explicit SoC discretization is beneficial only in relatively restricted settings.

Shaohua Yu, Wenhao Mao, Zigao Wu et al.

Adaptive Large Neighborhood Search (ALNS) is a widely used heuristic method for solving combinatorial optimization problems. ALNS explores the solution space by iteratively using destroy and repair operators with probabilities, which are adjusted by an adaptive mechanism to find optimal solutions. However, the classic ALNS adaptive mechanism does not consider the interaction between destroy and repair operators when selecting them. To overcome this limitation, this study proposes a novel adaptive mechanism. This mechanism enhances the adaptability of the algorithm through a Dual Actor-Critic (DAC) model, which fully considers the fact that the quality of new solutions is jointly determined by the destroy and repair operators. It effectively utilizes the interaction between these operators during the weight adjustment process, greatly improving the adaptability of the ALNS algorithm. In this mechanism, the destroy and repair processes are modeled as independent Markov Decision Processes to guide the selection of operators more accurately. Furthermore, we use Graph Neural Networks to extract key features from problem instances and perform effective aggregation and normalization to enhance the algorithm's transferability to different sizes and characteristics of problems. Through a series of experiments, we demonstrate that the proposed DAC-ALNS algorithm significantly improves solution efficiency and exhibits excellent transferability.

Miriam Enzi, Sophie N. Parragh, Jakob Puchinger

The aim of the bi-objective multimodal car-sharing problem (BiO-MMCP) is to determine the optimal mode of transport assignment for trips and to schedule the routes of available cars and users whilst minimizing cost and maximizing user satisfaction. We investigate the BiO-MMCP from a user-centred point of view. As user satisfaction is a crucial aspect in shared mobility systems, we consider user preferences in a second objective. Users may choose and rank their preferred modes of transport for different times of the day. In this way we account for, e.g., different traffic conditions throughout the planning horizon. We study different variants of the problem. In the base problem, the sequence of tasks a user has to fulfill is fixed in advance and travel times as well as preferences are constant over the planning horizon. In variant 2, time-dependent travel times and preferences are introduced. In variant 3, we examine the challenges when allowing additional routing decisions. Variant 4 integrates variants 2 and 3. For this last variant, we develop a branch-and-cut algorithm which is embedded in two bi-objective frameworks, namely the $ε$-constraint method and a weighting binary search method. Computational experiments show that the branch-and cut algorithm outperforms the MIP formulation and we discuss changing solutions along the Pareto frontier.