A branch-price-and-cut algorithm for a time-dependent green vehicle routing problem with the consideration of traffic congestion

This paper studies a time-dependent green vehicle routing problem (TDGVRP) with the consideration of traffic congestion. In this work, the objective is to design the vehicle scheduling plan, with the goal of reducing carbon emissions, which has a positive linear relationship with fuel consumption of vehicles. In order to mathematically model traffic congestion, the travel speed is set as time-dependent, thus travel time and carbon emissions are also time-dependent. We develop a set partitioning formulation (SPF) for the TDGVRP, and propose a branch-price-and-cut (BPC) algorithm to solve it, in which a tailored labeling algorithm is designed for solving the pricing problem. Furthermore, we introduce dominance rule to discard unpromising labels. In order to get a more reasonable lower bound, valid inequalities are used to strengthen the SPF in this paper. Extensive computational experiments validate the effectiveness of the proposed BPC algorithm. This study could make a contribution on the theoretical research on vehicle routing problem (VRP), and at the same time presents a mathematical and reasonable method for logistics companies to formulate logistics plans with the consideration of fuel consumption, climate change and carbon emissions reduction.