Routing considering path consistency in a road network

Our paper:

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

Jointly written with Yu Yao, Luuk Veelenturf and Pongli Mo, is now published in Transportation Research Part B: Methodological. It is available the coming month for free via this link.

This paper investigates a new variant of the consistent vehicle routing problem considering path consistency based on the underlying road network (ConVRP). 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.

Another critical issue is how to evaluate path consistency. Most of the existing studies about ConVRP are based on customer-based graphs. A fundamental assumption is that, for every two points of interest (e.g., customers and depots), the best path between them is determined in advance. However, adopting a customer-based graph misses the information of the road network structure, such that the path consistency cannot be evaluated directly. Therefore, we consider our problem based on a road-network graph, which mimics the real-world road network structure.

The following figure (a) and (b) illustrate the optimal results of M-10-5(1) without and with considering the path consistency, respectively. We use blue nodes to represent the customers who are served by different drivers on different days. It is observed that the number of customers served by different drivers decreases from 7 to 2 after considering the path consistency.