The consistent vehicle routing problem considering path consistency in a road network. (November 2021)

• Record Type: Journal Article
• Authors: Yao, Yu; Van Woensel, Tom; Veelenturf, Lucas P.; Mo, Pengli
• Is Part Of: Transportation research. Volume 153(2021)
• Page Start: 21
• Page End: 44
• Publication Date: 2021-11
• Subjects: VRP -- Consistency -- Road network -- Branch-price-and-cut algorithm; Transportation -- Research -- Periodicals; Transportation -- Mathematical models -- Periodicals
• DOI: 10.1016/j.trb.2021.09.005
• Languages: English
• ISSNs: 0191-2615

Abstract

Abstract: This paper investigates a new variant of the consistent vehicle routing problem considering path consistency based on the underlying road network (ConVRP R N ). 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 R N . 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. Highlights: A new variant of the consistent VRP considering road network information and imposing path consistency is proposed. A coupled two-layer network is constructed to consider road network information within a branch-price-and-cut framework. An innovative aggregation technique is customized to speed up the branch-price-and-cut algorithm. A set of numerical experiments based on a real-world road network are implemented.