Practical and Effective Heuristics for the Backhaul Profit Maximization Problem

Daniel Ryan (), Tran Lam (), Yuanyuan Dong () and Eli Olinick ()
Additional contact information
Daniel Ryan: Southern Methodist University, Computer Science Department
Tran Lam: Southern Methodist University, Computer Science Department
Yuanyuan Dong: Southern Methodist University, Operations Research and Engineering Management Department
Eli Olinick: Southern Methodist University, Operations Research and Engineering Management Department

Networks and Spatial Economics, 2025, vol. 25, issue 4, No 4, 957-984

Abstract: Abstract Given an empty delivery vehicle, the backhaul profit maximization problem (BPMP) is to select a profit-maximizing subset of available pick-up-and-delivery requests to accept considering the vehicle’s capacity and a time limit for the vehicle to reach a specified destination or, equivalently, a driving-distance limit. 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.

Keywords: Selective backhauls; Backhauling; Logisitics; Heuristics (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11067-025-09684-0 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:kap:netspa:v:25:y:2025:i:4:d:10.1007_s11067-025-09684-0

Ordering information: This journal article can be ordered from
http://www.springer. ... ce/journal/11067/PS2

DOI: 10.1007/s11067-025-09684-0

Access Statistics for this article

Networks and Spatial Economics is currently edited by Terry L. Friesz

More articles in Networks and Spatial Economics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().