People want to rely on optimization algorithms for complex decisions but verifying the optimality of the solutions can then become a valid concern, particularly for critical decisions taken by non-experts in optimization. One example is the shortest-path problem on a network, occurring in many contexts from transportation to logistics to telecommunications. While the standard shortest-path problem is both solvable in polynomial time and certifiable by duality, introducing side constraints makes solving and certifying the solutions much harder. We propose a proof system for constrained shortest-path problems, which gives a set of logical rules to derive new facts about feasible solutions. The key trait of the proposed proof system is that it specifically includes high-level graph concepts within its reasoning steps (such as connectivity or path structure), in contrast to, e.g., using linear combinations of model constraints. Thus, using our proof system, we can provide a step-by-step, human-auditable explanation showing that the path given by an external solver cannot be improved. Additionally, to maximize the advantages of this setup, we propose a proof search procedure that specifically aims to find small proofs of this form using a procedure similar to A* search. We evaluate our proof system on constrained shortest path instances generated from real-world road networks and experimentally show that we may indeed derive more interpretable proofs compared to an integer programming approach, in some cases leading to much smaller proofs.

This study proposes a hybrid deep-learning-metaheuristic framework with a bi-level architecture for road network design problems (NDPs). We train a graph neural network (GNN) to approximate the solution of the user equilibrium (UE) traffic assignment problem and use inferences made by the trained model to calculate fitness function evaluations of a genetic algorithm (GA) to approximate solutions for NDPs. Using three test networks, two NDP variants and an exact solver as benchmark, we show that on average, our proposed framework can provide solutions within 1.5% gap of the best results in less than 0.5% of the time used by the exact solution procedure. Our framework can be utilized within an expert system for infrastructure planning to determine the best infrastructure planning and management decisions under different scenarios. Given the flexibility of the framework, it can easily be adapted to many other decision problems that can be modeled as bi-level problems on graphs. Moreover, we foreseen interesting future research directions, thus we also put forward a brief research agenda for this topic. The key observation from our research that can shape future research is that the fitness function evaluation time using the inferences made by the GNN model was in the order of milliseconds, which points to an opportunity and a need for novel heuristics that 1) can cope well with noisy fitness function values provided by deep learning models, and 2) can use the significantly enlarged efficiency of the evaluation step to explore the search space effectively (rather than efficiently). This opens a new avenue for a modern class of metaheuristics that are crafted for use with AI-powered predictors.

The possibility of having driverless cars on the streets seems to be more real than ever. In this paper, we focus on developing exact methods that can determine the effects of privately owned automated vehicles (AVs) and how switching to those vehicles is going to change mobility in urban environments. The considered problem determines the routes of family owned AVs that minimize the transportation costs of that family while considering the possibility of using public transport as an alternative for some trips. We introduce a novel exact linear formulation for this problem which includes a linearized traffic congestion model and which is able to solve the user and system optimum variant of the problem to optimality. The introduced formulation can easily be adapted to consider the current situation with conventional vehicles and a situation where not only the travel time costs of the driver but also costs of the other passengers are taken into account. The main advantage of our novel formulation is that the optimal results can be obtained to explore potential changes of flows with vehicle automation in small networks. We investigated the behavior of the system, given the described scenarios, by applying our formulation to a case study.

One-way carsharing systems allow travelers to pick up a car at one station and return it to a different station, thereby causing vehicle imbalances across the stations. In this paper, a way to mitigate that imbalance is discussed, which is relocating vehicles between stations. For this purpose, two methods are presented, i.e., a new mathematical model to optimize the relocation operations that maximize the profitability of a carsharing service and a simulation model to study different real-time relocation policies. Both methods were applied to networks of stations in Lisbon, Portugal. Results show that relocating vehicles, using any of the methods developed, can produce significant increases in profit. For instance, in the case where the carsharing system provides maximum coverage of the city area, the imbalances in the network resulted in an operating loss of C1160/day when no relocation operations were performed. When relocation policies were applied, however, the simulation results indicate that profits of C854/day could be achieved, even with increased costs due to relocations. Using the mathematical model, the results are even better, with a reached profit of C3865.7/day. This improvement was achieved through reductions in the number of vehicles needed to satisfy the demand and the number of parking spaces needed at stations. These results demonstrate the importance of relocation operations for profitably providing a network of stations in one-way carsharing systems that covers the entire city, thus reaching a higher number of users.