TY - JOUR
T1 - The Consistent Vehicle Routing Problem considering path consistency in a road network
AU - Yao, Yu
AU - van Woensel, Tom
AU - Veelenturf, Luuk P.
AU - Mo, Pengli
PY - 2021/11
Y1 - 2021/11
N2 - This paper investigates a new variant of the consistent vehicle routing problem considering path consistency based on the underlying road network (ConVRP
RN). 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 ConVRP
RN. 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.
AB - This paper investigates a new variant of the consistent vehicle routing problem considering path consistency based on the underlying road network (ConVRP
RN). 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 ConVRP
RN. 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.
KW - Branch-price-and-cut algorithm
KW - Consistency
KW - Road network
KW - VRP
UR - http://www.scopus.com/inward/record.url?scp=85115807355&partnerID=8YFLogxK
U2 - 10.1016/j.trb.2021.09.005
DO - 10.1016/j.trb.2021.09.005
M3 - Article
SN - 0191-2615
VL - 153
SP - 21
EP - 44
JO - Transportation Research. Part B: Methodological
JF - Transportation Research. Part B: Methodological
ER -