A Dynamic and Stochastic Cumulative Capacitated Vehicle Routing Problem

Yu Wu
Additional contact information
Yu Wu: School of Transportation and Logistics, Southwest Jiaotong University, Chengdu, Sichuan 611756, P. R. China2National United Engineering Laboratory of Integrated and Intelligent Transportation, Chengdu, P. R. China3National Engineering Laboratory of Big Data Application in Integrated Transportation, Chengdu, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2025, vol. 42, issue 02, 1-38

Abstract: The cumulative capacitated vehicle routing problem (CCVRP) is a variant of the classical capacitated vehicle routing problem in which the objective is the minimization of customers’ total waiting time prior to service. Inspired by the first-mile pick-up service within 3rd-Party Logistics operations, we study a dynamic and stochastic variant of the CCVRP. In this variant, a capacitated vehicle undertakes a single tour to collect customers’ parcels, taking into account stochastic service requests, stochastic service cancellations, and stochastic demand (i.e., changes in parcel size) simultaneously. Conditional on maximizing the usage of the vehicle’s capacity, we minimize the total waiting time of both customers who are served and those who request services but are not served due to cancellation or capacity violation. We formulate this problem as a Markov decision process and solve it using a hybrid approach that combines approximate dynamic programming and rollout algorithm. Our main contributions include (i) the construction of the stage cost that leverages a property of the Poisson process, and (ii) consideration of service fairness-based acceptance/rejection rule in response to excessive stochastic service requests. In the numerical study, our approach is examined to outperform an 2-Opt-based re-optimization policy in terms of both customers’ waiting time and service-request satisfying rate. More importantly, computational results heuristically show that there is no cost to adopting the service fairness-based rule, which is obviously a valuable managerial insight.

Keywords: Capacitated vehicle routing problem; parcel pick-up; service fairness; approximate dynamic programming (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595924500088
Access to full text is restricted to subscribers

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:wsi:apjorx:v:42:y:2025:i:02:n:s0217595924500088

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595924500088

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().