Optimization of Vehicle Routes with Delivery and Pickup for a Rental Business: A Case Study

Optimization of vehicle routes with delivery and pickup for a rental industry is considered. The company delivers to or pickups from customers rented products. Several types of products exist, and customers rent the specified number of products of the specific type. Time windows exist for delivery and pickup. There exist two sizes of vehicles, and their trips start from and end at depot and vehicles can make several trips during a day. Delivery must precede pickup on any trip of a vehicle. Capacity of vehicles depends on product type and also on how products are loaded on vehicles. Depending on demand quantity, split deliveries/pickups may be necessary. The company wants to minimize the total transportation cost. Based on the fact that the total number of distinct trips is rather small due to limited capacity of the vehicles, our solution strategy first enumerates all possible trips. Routes (i.e., collection of trips) are obtained by assigning trips to vehicles so that the total cost is minimized subject to constraints on demand, an upper limit on the number of trips per vehicle, and time compatibility of trips assigned to each vehicle. Since there exist many time compatibility constraints, the problem is first solved without them, we then check the compatibility and if necessary add compatibility constraints, and the problem is solved again until all routes become time compatible. Computational performance of the proposed solution approach is evaluated.