Abstract
Corporate mobility is often based on a fixed assignment of vehicles to employees. Relaxing this fixation while including alternatives such as public transportation or taxis for business and private trips could increase fleet utilization and foster the use of battery electric vehicles. Along this idea we propose a flexible booking system, leading to the introduction of the NP-hard mobility offer allocation problem which is closely related to multi-interval scheduling problems. We describe problem specific conflict graphs for representing and exploring the structure of feasible solutions. A characterization of all maximum cliques in these conflict graphs reveals symmetries which allow to formulate stronger integer linear programming models. We also present an adaptive large neighborhood search based approach which makes use of conflict graphs as well. In a computational study, the approaches are evaluated and it is demonstrated that, depending on instances and run-time requirements, either a solver for the integer linear programming model, fast greedy heuristics, or the adaptive large neighborhood search outperforms the others.
Abstract (translated by Google)
URL
http://arxiv.org/abs/1810.05659