Set covering in fuel-considered vehicle routing problems

The paper studies set covering in fuel-considered vehicle routing problems (FVRP). Firstly, we study the FVRP with distance constraint and time windows (FVRP-TW) whose objective is to find a set covering with the minimum cardinality, which means the number of used vehicles is minimized and hence the fuel consumption is minimized in the real logistics. We give a bicriteria approximation algorithm for this problem. Secondly, we study the set covering in the FVRP with distance constraint and constant time windows (FVRP-CTW), which has a constant number of the time windows provided by logistics companies. We give a bicriteria approximation algorithm with (2+ϵ,O(log⁡1/ϵ))(2+ϵ,O(log⁡1/ϵ)) for this problem, in which the first term is the approximation ratio on the distance constraint and the second term is the approximation ratio on the cardinality of the covering set. Thirdly, we study the set covering in general FVRP and propose a lower bound for this problem which is based on total unimodularity. Finally, we design an algorithm framework based on the lower bound for solving the set covering in general FVRP. Simulation results demonstrate the effectiveness of the algorithms for solving the set covering in FVRP-TW and general FVRP.