Publication Date

Fall 8-26-2019

Abstract

Solving an instance of the Backhaul Profit Maximization Problem (BPMP) 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 delivery requests between various locations on the route subject to the vehicle's capacity. We propose and test a series of enhancements to the node-arc and triples mixed integer programming formulations of BPMP found in the literature and develop a multi-criteria Composite Index Method (CIM) to evaluate the results. We find that CPLEX takes 5 to 34 minutes (real time) to solve BPMP instances from the literature with 20 potential pickup/drop-off locations using the original node-arc model on the computers in our lab. Applying our own insights and adapting techniques from the literature on related problems, we develop an enhanced node-arc formulation that reduces the range of solution times of the 20-location instances to 31 to 105 seconds. Additionally, we solve problem instances that are twice as large (40 locations) as those solved in the literature. With the triples formulation from the literature, we find that the 20-location instances take between 2 to 21 seconds to solve. Using our enhanced triples formulation, however, we solve these same instances in six seconds or less. Comparing our two enhanced formulations, we solve 40-location instances in an average of 7 minutes with the enhanced triples formulation compared to an average of 92 hours with the enhanced node-arc formulation. Additionally, we find that the average time to solve 50-node instances with the enhanced triples formulation is 36 minutes.

Document Type

Technical Report

Keywords

Freight Logistics, Pickup and Delivery, Backhauls, Mixed Integer Programming, Multicommodity Flows, Composite Index Method (CIM)

Disciplines

Operational Research

Download

Share

COinS