Oil product transportation with combinatorial auctions

This paper discusses a new practical variant of the vehicle routing problem with time windows (VRPTW) that incorporates a combinatorial auction (CA) problem, which originated from the regional transportation planning of oil products for a prominent Chinese petroleum company. During peak seasons, the petroleum company needs to outsource some transportation projects to third party logistics (3PL) providers because the demand for oil products and the corresponding transportation requirements at this time are considerably higher. To minimize the total cost of oil product transportation from the depots to the oil stations, we integrate the CA and the VRPTW problems into a single problem, called the combinatorial auction and vehicle routing problem with time windows. The problem is formulated into a mixed-integer programming model and shown to be NP-hard. We devise a heuristic to separate all the stations into two types (whether to outsource to 3PL companies) according to distance. We then obtain an initial solution by separately solving the CA and VRPTW problems. To improve the initial solution, we design and test multiple heuristic operators to interactively solve the CA and VRPTW. Experiments show that good quality solutions are achieved for problem cases of practical scope.