A mean-variance approach to mixed strategies for dispatching problems under travel time uncertainty

This study provides a mixed strategy model for fleet dispatching problems under travel time uncertainty. We assume a dispatcher, who assigns a fleet of vehicles to the set of route of a given single origin-destination pair. As the travel time of each vehicle fluctuates, the average travel time per vehicle becomes uncertain and its moments are determined by the vehicle assignment. In this situation, the dispatcher can achieve a smaller ATT variance without increasing its mean by using mixed strategies rather than pure strategies. We first formulate the mean-variance routing problem, whose solution is the mixed strategy that achieves the smallest variance amongst alternatives whose mean does not exceed a given upper bound. We then show that this problem can be rewritten as a quadratic programming problem using only link-based variables. This enables us to solve the dispatching problem without resorting to exhaustive route enumeration.