Exact Algorithms for the Vehicle Routing Problem with Time Windows and Combinatorial Auction

Abstract

In this paper, we address an interesting variant of the vehicle routing problem with time windows (VRPTW) faced by the China National Petroleum Corporation (CNPC). The CNPC owns a limited number of tanker trucks for delivering the petroleum to oil stations within specific time windows in the regular seasons. However, during the peak seasons, some requests need to be outsourced to external third-party logistics companies. These companies provide several bids, each of which includes the oil stations to be served and the corresponding charges. The CNPC needs to select some bids and design routes for the self-owned trucks, so that all requests are satisfied and the total cost is minimized. To study this problem, we formulate it into an arc-flow model and a set-partitioning model, and propose six families of valid inequalities to strengthen the set-partitioning model. Based on the set-partitioning model, we propose a branch-and-price-and-cut algorithm and a branch-and-bound algorithm to solve the problem exactly. The proposed algorithms are tested on instances generated according to the well-known Solomon’s benchmark instances for the VRPTW and read-world data of the CNPC. The computational experiments demonstrate the effectiveness of the proposed algorithms.