(442h) Estimation of Marginal Cost to Serve Individual Customers

Supply chain logistics constitutes a significant cost for many businesses, and thus receives a lot of effort for optimization. One primary concern in logistics is to properly quantify the marginal distribution cost of serving a new customer. This problem is challenging mainly because of two reasons: (i) identifying the marginal cost in a deterministic setting usually entails solving NP-hard vehicle routing problems; (ii) customer demands vary from day to day, and thus, the supply chain network of interest is intrinsically stochastic.

Though the estimation of marginal distribution cost is of great significance, it has received little attention in the literature. The work of [1] considers geographical attributes, such as latitude, longitude, and neighborhood density, among others, and builds a predictive model for estimation. In this talk, we follow an approach that rigorously accounts for the intrinsic stochasticity in the supply chain system and propose a scenario-sampling framework. We estimate the number of required scenarios that need to be sampled by utilizing the Hoeffding’s inequality [2], which guarantees from a statistical perspective that we identify a good estimate of the true marginal distribution cost.

In our context, the resulting deterministic problem in each scenario corresponds to the so-called “Vehicle Routing Problems with Intermediate Replenishment Facilities” (VRPIRF). The VRPIRF is formulated as a mixed-integer linear programming (MILP) model with exponentially many variables and is thus solved via the Branch-Price-and-Cut (BPC) algorithm [3]. The BPC algorithm is sophisticated in as much as the linear relaxation at every node in the branch-and-bound tree is solved via column generation and cutting planes are added to strengthen the relaxation. In our context, columns denote feasible routes, and they are generated by solving a Shortest Path Problem with Resource Constraints (SPPRC) via dynamic programming. Various techniques, including ng-route [4], variable fixing [5], route enumeration [6], among others, are also incorporated to expedite the solution of SPPRC. Furthermore, the addition of valid cuts, such as rounded capacity inequalities and limited-memory subset row cuts can effectively tighten the linear model [3].

In the literature, the state-of-the-art approach for exactly solving the VRPIRF comes from the work of [7], in which the authors utilized a branch-and-price method to solve the same MILP model, but proposed a two-level decomposition scheme to solve SPPRC. We conduct a computational study based on a comprehensive suite of 44 benchmark instances, and we show that our approach can solve all instances to guaranteed optimality within minutes, a noticeable improvement over the state-of-the-art algorithm, which could only solve 26 instances within the time limit of 10 hours. We then consider VRPIRF benchmark instances of larger sizes so as to further demonstrate the effectiveness of our approach. The second part of our computational studies focuses on the analysis of our proposed framework on evaluating the marginal cost of serving individual customers. We conduct extensive computational studies on benchmark instances generated from the literature data and demonstrate that our framework can be employed to estimate the marginal distribution cost with high degree of confidence.

References:

[1] Sun, L., Karwan, M.H., Gemici-Ozkan, B. and Pinto, J.M., 2015. Estimating the long-term cost to serve new customers in joint distribution. Computers & Industrial Engineering, 80, pp.1-11.

[2] Wasserman, L., 2013. All of statistics: a concise course in statistical inference. Springer Science & Business Media.

[3] Pecin, D., Pessoa, A., Poggi, M. and Uchoa, E., 2017. Improved branch-cut-and-price for capacitated vehicle routing. Mathematical Programming Computation, 9(1), pp.61-100.

[4] Baldacci, R., Mingozzi, A. and Roberti, R., 2011. New route relaxation and pricing strategies for the vehicle routing problem. Operations research, 59(5), pp.1269-1283.

[5] Irnich, S., Desaulniers, G., Desrosiers, J. and Hadjar, A., 2010. Path-reduced costs for eliminating arcs in routing and scheduling. INFORMS Journal on Computing, 22(2), pp.297-313.

[6] Baldacci, R. and Mingozzi, A., 2009. A unified exact method for solving different classes of vehicle routing problems. Mathematical Programming, 120(2), p.347.

[7] Muter, I., Cordeau, J.F. and Laporte, G., 2014. A branch-and-price algorithm for the multidepot vehicle routing problem with interdepot routes. Transportation Science, 48(3), pp.425-441.