  We present a compact mixed integer program (MIP) for the backhaul profit
maximization problem in which a freight carrier seeks to generate profit from
an empty delivery vehicle's backhaul trip from its last scheduled delivery to
its depot by allowing it to deviate from the least expensive (or fastest) route
to accept delivery requests between various points on the route as allowed by
its capacity and required return time. The MIP is inspired by a novel
representation of multicommodity flow that significantly reduces the size of
the constraint matrix and the linear programming upper bound on optimal profit
compared to a formulation based on the classical node-arc representation. This
in turn leads to faster solution times when using a state-of-the-art MIP
solver. In an empirical study of both formulations, problem instances with ten
potential pickup/dropoff locations and up to 73 delivery requests were solved
two times faster on average with our formulation while instances with 20
locations and up to 343 delivery requests were solved 7 to 45 times faster. The
largest instances in the study had 50 locations and 2,353 delivery requests;
these instances could not be solved with the node-arc-based formulation, but
were solved within an average of less than 40 minutes of real time using our
compact formulation. We also present a heuristic algorithm based on our compact
formulation that finds near optimal solutions to the 50-location instances
within ten minutes of real time.
