{'fraction_non_alphanumeric': 0.010970464135021098, 'fraction_numerical': 0.0, 'mean_word_length': 4.813725490196078, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Rolling Horizon Heuristic with Optimality Guarantee for an On-Demand Vehicle Scheduling Problem

We consider a basic vehicle scheduling problem that arises in the context of travel demand models: 
Given demanded vehicle trips, what is the minimal number of vehicles needed to fulfill the demand? 
In this paper, we model the vehicle scheduling problem as a network flow problem. Since instances 
arising in the context of travel demand models are often so big that the network flow model becomes 
intractable, we propose using a rolling horizon heuristic to split huge problem instances into smaller 
subproblems and solve them independently to optimality. By letting the horizons of the subproblems 
overlap, it is possible to look ahead to the demand of the next subproblem. We prove that composing 
the solutions of the subproblems yields an optimal solution to the whole problem if the overlap of 
the horizons is sufficiently large. Our experiments show that this approach is not only suitable for 
solving extremely large instances that are intractable as a whole, but it is also possible to decrease 
the solution time for large instances compared to a comprehensive approach.