The request-trip-vehicle assignment problem is at the heart of popular decomposition strategies for online vehicle routing. We study an integer linear programming formulation and the complexity of its linear programming relaxation. Our main result is a linear programming based randomized algorithm that, whenever the instance is feasible, leverages assumptions typically met in practice to return an assignment whose: i) expected cost is at most that of an optimal solution, and ii) expected fraction of unassigned requests is at most 1/e. If trip-vehicle assignment costs can only be a-approximated, we pay an additional factor of a in the expected cost. Our techniques generalize to a class of set-partitioning problems.
Copyright. All Rights Reserved.