Estimation of Marginal Cost to Serve Individual Customers
Abstract: This paper proposes a scenario-sampling framework to estimate the expected incremental routing cost required so as to incorporate a target customer into the stochastic supply chain network. The cost estimate is shown to converge to its true value with statistical guarantee as the number of samples increases, while the Hoeffding's inequality can be utilized to determine a sufficient sample size for a desired estimation accuracy. Inspired from a real-life setting arising in distribution of industrial gases, we sample instances of multi-depot vehicle routing problems with inter-depot routes, and we use these as scenarios towards a demonstration of the marginal cost estimation framework and towards a detailed study to elucidate the quality of our estimates. In order to solve such rich routing problems exactly, we also develop a tailored branch-price-and-cut algorithm, which is shown to be able to solve to optimality instances of up to 70 customers within reasonable time, significantly outperforming the previous state-of-the-art exact method.
Keywords: marginal cost estimation, multi-depot vehicle routing problems with inter-depot routes, branch-price-and-cut, scenario-sampling, Hoeffding's inequality
Category 1: Applications -- OR and Management Sciences (Transportation )
Category 2: Applications -- OR and Management Sciences (Supply Chain Management )
Citation: Carnegie Mellon University, Pittsburgh, PA 15213, January 2020.
Entry Submitted: 01/16/2020
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|