Meso-parametric value function approximation for dynamic customer acceptances in delivery routing

Marlin W. Ulmer and Barrett W. Thomas

European Journal of Operational Research, 2020, vol. 285, issue 1, 183-195

Abstract: The rise of mobile communication, ample computing power, and Amazon’s training of customers has led to last-mile delivery challenges and created struggles for companies seeking to budget their limited delivery resources efficiently to generate enough revenue. In this paper, we examine the capacitated customer acceptance problem with stochastic requests (CAPSR), a problem in which a company seeks to maximize expected revenue by accepting or rejecting requests. Each accepted request generates revenue and must be routed, consuming driver time and vehicle capacity. To solve the problem, we introduce a novel method of value function approximation (VFA). Conventionally, VFAs are either parametric (P-VFAs) or non-parametric (N-VFAs). Both VFAs have advantages and shortcomings and their performances rely significantly on the structure of the underlying problem. To combine the advantages and to alleviate the shortcomings of P-VFA and N-VFA used individually, we present a novel method, meso-parametric value function approximation (M-VFA). The results of computational experiments show that the M-VFA outperforms benchmarks for the CAPSR and show M-VFA offers the advantages of the individual VFAs while alleviating their shortcomings. Most importantly, we demonstrate that simultaneous approximations lead to better outcomes than either N- and P-VFA individually or some ex-post combination.

Keywords: Dynamic customer acceptances; Dynamic vehicle routing; Dynamic multi-dimensional knapsack problem; Approximate dynamic programming; Value function approximation (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719303637
Full text for ScienceDirect subscribers only

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:eee:ejores:v:285:y:2020:i:1:p:183-195

DOI: 10.1016/j.ejor.2019.04.029

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().