The Backhaul Problem and Related Topics in Vehicle Routing

Abstract

The problem studied in this dissertation is a variation of the classical vehicle routing problem (VRP) that has received limited research attention, and concerns the routing of vehicles over a set of mixed customers; that is, some customers are delivery or linehaul points but others are pickup or backhaul points. In contrast to deliveries, when a vehicle services a pickup point, product, bound for the distribution center, is loaded on the truck. Practical considerations usually dictate that the number of backhauls per route is small and they are serviced near the end of a route. The vehicle routing problem with backahuls (VRPB) can be stated as follows: Find a set of vehicle routes that service the delivery and backhaul customers such that vehicle capacity is not violated and the total distance traveled is minimized. In this dissertation, we examine three real-world routing applications with backhauls and several first-generation algorithms designed to solve VRPBs. The key dissertation research objective is to develop new heuristics to solve the VRPB that redress the shortcomings of existing solution methods in dealing with real-world considerations. The four new heuristics developed allow common carrier or supplier deliveries, dedicated backhaul routes, and mixed routes. In order to evaluate their performance, the heuristics were coded in Pascal and a series of computation experiments were performed on a Macintosh platform. The experiments consisted of generating twenty seven hundred random problems covering a range of possible combinations of critical problem parameters. These problems were solved by the heuristics and the main findings are as follows: 1) on average, the new heuristics outperformed heuristics which allow only pure delivery and mixed routes, 2) the effectiveness of the new procedures was found to vary with changes in problem size, the percentage of backhaul nodes, and the delivery node concentration region, 3) the effective of the new procedures was found not to vary with changes in the cost to insert backhaul location in mixed routes, or with changes in common carrier costs, and 4) the execution times to solve 40-node and 100-node problems was found to be less than a minute.