Members of the MISOR research group were invited to present their latest research at the EURO 2022 conference held in Espoo, Finland. The following three projects were presented:
1. Dynamic taxi-ridesharing with meeting points by Peter Dieter, Miriam Stumpe, Guido Schryen
Increasing urbanization and the associated growth in traffic volumes make innovative mobility concepts increasingly important. Most traditional mobility solutions center around two extreme paradigms: public transport and private transport. Taxi-ridesharing systems are designed to combine the advantages of both these paradigms, i.e., high flexibility at low costs. Critical success factors for such a ridesharing system are high matching rates and minimal inconvenience for customers. Previous literature shows that introducing meeting points, where customers are picked up and dropped off, in ridesharing systems significantly increases the number of matched customers. Additionally, meeting points can avoid detours and thus reduce discomfort caused by longer trips. However, these approaches only consider systems, where all information in a planning horizon is assumed to be known. We contribute to this research gap by suggesting a dynamic taxi-ridesharing system with meeting points where customers receive notifications immediately after their requests enter the system. We develop a parameterized policy function approximation (PFA) with the objective to maximize the total savings of traveled distances. We evaluate the suggested policy on problem instances arising from real-world data and show that it leads to a significant increase in saved distance when compared to myopic policies. The findings underline the importance to anticipate future customer requests in ridesharing systems.
2. Parallel Branch-and-Price Algorithms for the Single Machine Total Weighted Tardiness Scheduling Problem with Sequence-Dependent Setup Times by Philipp Speckenmeyer, Guido Schryen
Scheduling problems occur in a broad range of real-world application fields and have attracted a substantial amount of research articles. In relation to the overall number of published papers on this topic, however, there is only little research on exact algorithms for scheduling problems, many of which are NP-hard in the strong sense. To address this matter, we investigate the problem on a single machine with a total weighted tardiness objective function and sequence dependent setup times between jobs. First, we adopt a serial branch-and-bound algorithm from the literature where lower bounds are computed by column generation (pricing), present a modified branching strategy and develop a primal heuristic to enhance the frequency and quality of generated upper bounds. Second, we use the potential of parallel computing architectures provided by the broad availability of multi-core processor technologies and present two parallel versions of the branch-and-price algorithm. Here, in contrast to the traditional approach of solving multiple subproblems concurrently, we apply parallelization to the solution of the pricing problem. Third, we conduct extensive computational experiments to show that our parallelization approaches provide substantial parallel speedups on well-known benchmark instances from the literature.
3. Gradual deployment of electric bus systems by coordinated optimization of charging infrastructure and mixed vehicle fleets by Miriam Stumpe, Guido Schryen
Given the global efforts to reduce emissions and fossil fuel dependency, public transport operators are under growing pressure not only to replace their diesel buses with electric buses, but also to provide a supporting charging infrastructure. However, the transition from traditional fuel-based bus transport to electric bus systems is still in its early stages in most European cities. This is mainly due to the uncertain technological environment, from which different paths for a gradual expansion may emerge in the foreseeable future. While several studies focus on the strategic implications of uncertainty (e.g., charging stations), few consider the operative side (e.g., vehicle schedules) in sufficient detail. We contribute to closing this research gap by (1) simultaneously optimizing the charging infrastructure and vehicle schedules and (2) analyzing the robustness of the resulting charging infrastructure against technological factors. We extend an application of a Variable Neighborhood Search (VNS) from prior work by considering mixed fleets and by repeatedly executing the VNS, using the result from each iteration as the starting point of its successor. In each iteration, technological factors are varied, such as the fleet share of electric vehicles, battery capacity, and charging power, following realistic development and expansion paths. We present a comprehensive analysis of the effect of such multidimensional variation in factors.
We would like to take this opportunity to thank the audience again for their valuable comments and of course the organizers of the EURO2022 for hostimg a very impressive conference.
