The consistent vehicle routing problem considering path consistency in a road network

This paper investigates a new variant of the consistent vehicle routing problem considering path consistency based on the underlying road network (ConVRPRN). It is the problem of determining a set of consistent paths for vehicles within a certain period (e.g. a week). We propose a flexible strategy to achieve path consistency, providing a discount for the cost of roads that are traversed every day. The objective is to minimize the total travel costs considering the discount for the paths’ consistent parts. We formulate the problem as a set partitioning model and a general arc-flow model, and then solve the problem by a branch-price-and-cut algorithm. The algorithm is based on a two-layer network, including an underlying road-network graph (lower layer) and a serial of customer-based graphs (upper layer). Furthermore, an innovative aggregation technique is proposed to accelerate the algorithm, which is specifically designed for ConVRPRN. Finally, we construct a road network based on the real road-network structure of West Jordan and demonstrate the effectiveness of our approach on a set of numerical experiments. The impact of consistency discount is also analyzed to provide information and inspiration for tactical decision making.