Optimization Online


Estimation of Marginal Cost to Serve Individual Customers

Akang Wang(akangw***at***andrew.cmu.edu)
Jeffrey E. Arbogast(jeffrey.arbogast***at***airliquide.com)
Gildas Bonnier(gildas.bonnier***at***airliquide.com)
Zachary Wilson(zachary.wilson***at***airliquide.com)
Chrysanthos E. Gounaris(gounaris***at***cmu.edu)

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.

Download: [PDF]

Entry Submitted: 01/16/2020
Entry Accepted: 01/16/2020
Entry Last Modified: 01/16/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society