Generalized Riskiness Index in Vehicle Routing Under Uncertain Travel Times: Formulations, Properties, and Exact Solution Framework

Zhenzhen Zhang (), Yu Zhang () and Roberto Baldacci ()
Additional contact information
Zhenzhen Zhang: School of Economics and Management, Tongji University, Shanghai 200092, China
Yu Zhang: Department of Supply Chain Management, School of Business Administration, Southwestern University of Finance and Economics, Chengdu 611130, China
Roberto Baldacci: Division of Engineering Management and Decision Sciences, College of Science and Engineering, Hamad Bin Khalifa University, Qatar Foundation, Doha, Qatar

Transportation Science, 2024, vol. 58, issue 4, 761-780

Abstract: We consider a vehicle routing problem with time windows under uncertain travel times where the goal is to determine routes for a fleet of homogeneous vehicles to arrive at the locations of customers within their stipulated time windows to the maximum extent while ensuring that the total travel cost does not exceed a prescribed budget. Specifically, a novel performance measure that accounts for the riskiness associated with late arrivals at the customers, called the generalized riskiness index (GRI), is optimized. The GRI covers several existing riskiness indices as special cases and generates new ones. We demonstrate its salient managerial and computational properties to motivate it better. We propose alternative set partitioning-based models of the problem. To obtain the optimal solution, we develop an exact solution framework combining route enumeration and branch-price-and-cut algorithms, in which the GRI is dealt with in route enumeration and column generation subproblems. We mainly reduce the solution space by exploiting the GRI and budget constraints’ properties without losing optimality. The proposed method is tested on a collection of instances derived from the literature. The results show that a new instance of the GRI outperforms several existing riskiness indices in mitigating lateness. The exact method can solve instances with up to 100 nodes to optimality. It can consistently solve instances involving up to 50 nodes, outperforming state-of-the-art methods by more than doubling the manageable instance size.

Keywords: vehicle routing; uncertain travel times; riskiness indices; route enumeration; branch-price-and-cut (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2023.0345 (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:ortrsc:v:58:y:2024:i:4:p:761-780

Access Statistics for this article

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