Branch-Cut-and-Price for the Time-Dependent Green Vehicle Routing Problem with Time Windows

Yiming Liu (), Yang Yu (), Yu Zhang (), Roberto Baldacci (), Jiafu Tang (), Xinggang Luo () and Wei Sun ()
Additional contact information
Yiming Liu: State Key Laboratory of Synthetic Automation for Process Industries, Institute of Intelligent Data and Systems Engineering, Northeastern University, 110819 Shenyang, People’s Republic of China
Yang Yu: Dalian University of Technology, School of Economics and Management, 116024 Dalian, Liaoning, People’s Republic of China
Yu Zhang: School of Business Administration, Southwestern University of Finance and Economics, 611130 Chengdu, People’s Republic of China
Roberto Baldacci: College of Science and Engineering, Hamad Bin Khalifa University, Doha, Qatar
Jiafu Tang: College of Management Science and Engineering, Dongbei University of Finance and Economics, 116026 Shahekou, Dalian, People’s Republic of China
Xinggang Luo: School of Management, Hangzhou Dianzi University, 310005 Hangzhou, People’s Republic of China
Wei Sun: Business School, Liaoning University, 110316 Shenyang, People’s Republic of China

INFORMS Journal on Computing, 2023, vol. 35, issue 1, 14-30

Abstract: Motivated by rising concerns regarding global warming and traffic congestion effects, we study the time-dependent green vehicle routing problem with time windows (TDGVRPTW), aiming to minimize carbon emissions. The TDGVRPTW is a variant of the time-dependent vehicle routing problem (TDVRP) in which, in addition to the time window constraints, the minimization of carbon emissions requires determination of the optimal departure times for vehicles, from both the depot and customer location(s). Accordingly, the first exact method based on a branch-cut-and-price (BCP) algorithm is proposed for solving the TDGVRPTW. We introduce the notation of a time-dependent (TD) arc and describe how to identify the nondominated TD arcs in terms of arc departure times. In this way, we reduce infinitely many TD arcs to a finite set of nondominated TD arcs. We design a state-of-the-art BCP algorithm for the TDGVRPTW with labeling and limited memory subset row cuts, together with effective dominance rules for eliminating dominated TD arcs. The exact method is tested on a set of test instances derived from benchmark instances proposed in the literature. The results show the effectiveness of the proposed exact method in solving TDGVRPTW instances involving up to 100 customers. Summary of Contribution: Due to the environmental situation, green vehicle routing problems (GVRPs) aim to consider greenhouse gas emissions reduction, while routing the vehicles, and play a key role in transportation and logistics. Vehicle greenhouse gas emissions strongly depend on the vehicle speeds and traffic conditions which in real life vary continuously over time. To tackle these challenges, we address the time-dependent green vehicle routing problem with time windows (TDGVRPTW) aimed at reducing total carbon emissions under time-dependent travel times and time window constraints. We design an effective exact method for the TDGVRPTW based on a state-of-the-art branch-cut-and-price algorithm. The paper is both of methodological value for researchers and of interest for practitioners. For researchers, the presented algorithm is amenable for various routing constraints and provides a ground for further studies and research. For practitioners, the paper suggests insights on how the carbon emissions change based on different vehicle speed profiles.

Keywords: time dependent; green vehicle routing problem; branch-cut-and-price (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1195 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:35:y:2023:i:1:p:14-30

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().