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

• Record Type: Journal Article
• Authors: Luo, Hongyuan; Dridi, Mahjoub; Grunder, Olivier
• Is Part Of: Computers & industrial engineering. Volume 177(2023)
• Publication Date: 2023-03
• Subjects: Time-dependent -- Vehicle routing problem -- Carbon emissions -- Branch-price-and-cut; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2023.109093
• Languages: English
• ISSNs: 0360-8352

Abstract

Abstract: 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. Highlights: A TDGVRP with the consideration of traffic congestion is studied in this paper. An exact branch-price-and-cut algorithm is proposed for solving TDGVRP. The experimental results highlight the effectiveness of the proposed approach.