Search for: All records

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. 

Abstract We propose easy‐to‐implement heuristics for time‐constrained applications of a problem referred to in the literature as the facility location problem with immobile servers, stochastic demand, and congestion, the service system design problem, or the immobile server problem (ISP). The problem is typically posed as one of allocating capacity to a set of M/M/1 queues to which customers with stochastic demand are assigned with the objective of minimizing a cost function composed of a fixed capacity‐acquisition cost, a variable customer‐assignment cost, and an expected‐waiting‐time cost. The expected‐waiting‐time cost results in a nonlinear term in the objective function of the standard binary programming formulation of the problem. Thus, the solution approaches proposed in the literature are either sophisticated linearization or relaxation schemes, or metaheuristics. In this study, we demonstrate that an ensemble of straightforward, greedy heuristics can rapidly find high‐quality solutions. In addition to filling a gap in the literature on ISP heuristics, new stopping criteria for an existing cutting plane algorithm are proposed and tested, and a new mixed‐integer linear model requiring no iterating algorithm is developed. In many cases, our heuristic approach finds solutions of the same or better quality than those found by exact methods implemented with expensive, state‐of‐the‐art mathematical programming software, in particular a commercial nonlinear mixed‐integer linear programming solver, given a five‐minute time limit.