Capacitated-vehicle routing problem with backhauls on trees

Abstract

The capacitated-vehicle routing problem (CVRP) is a classical problem that has been well studied by the transportation science community. A special case of the CVRP in which the network is constrained to have a tree structure (TCVRP) is studied here. Such tree networks arise when the cost of constructing and maintaining roads is much more than the routing cost-or when the transportation network consists of a main highway (e.g., Interstate system) and the customer locations are located off the highway. A new variant of the TCVRP, in which the customers are divided into two subsets-line haul and backhaul customers (TCVRPB)-is introduced in this paper. Line haul customers require delivery from the depot, and backhaul customers have supply that needs to be delivered to the depot. In any vehicle tour, line haul customers must be serviced before backhaul customers. The TCVRPB's relationship to the two-dimensional bin-packing problem is studied and, with the use of that problem, conditions for the lower bound on the problem are derived. An integer-programming (IP) formulation of the problem is presented. A two-approximation algorithm, which gives a feasible set of vehicle routes and customer assignments, is also presented. The problem is tested on two real-world treelike networks of varying sizes and on a randomly generated test network. The IP formulation works exceptionally well on small and medium-sized networks, and the gap between the approximation algorithm and the IP solution did not exceed 2% for nine of the 12 problem instances tested. Show more