Practical and Effective Heuristics for the Backhaul Profit Maximization Problem

Abstract

The backhaul profit maximization problem (BPMP), which is known to be NP-hard, requires simultaneously solving two problems: (1) determining how to route an empty delivery vehicle back from its current location to its depot by a scheduled arrival time, and (2) selecting a profit-maximizing subset of spot-market delivery requests along the route subject to the vehicle’s capacity. The ability to quickly find high-quality solutions to BPMP and related problems gives logistics providers a competitive edge by allowing them to reduce costly deadhead miles (distances traveled with an empty vehicle). Implemented in our computing environment, the fastest known exact algorithm for BPMP requires approximately 11 hours and 44 minutes on average to solve the largest instances in the literature, which have 70 to 80 potential pick-up/drop-off locations. The fastest available heuristic from the literature is considerably faster, and finds high quality solutions, but requires a state-of-the-art mixed-integer programming solver. We present a heuristic framework for the BPMP based on greedy construction,  iterative local search, and randomization.  Algorithms developed with the framework are implemented in the freely and widely available C++ language and their effectiveness is demonstrated through an extensive computational experiment on both benchmark and randomly generated problem instances. We find that our approach is competitive with approaches from the literature in solution quality as well as running time.