(440a) Identifying Cost Saving Opportunities through Coordinating Deliveries to Vendor-Managed Inventory Customers

Last-mile distribution operations are an essential backbone of many businesses, representing a significant portion of supply chain costs. As such, there is a growing need to improve and optimize these operations, most notably by routing delivery vehicles optimally [1]. In networks featuring Vendor-Managed Inventory Customers (VMICs) [2], vendors have the flexibility to decide delivery dates and quantities for VMICs subject to a few contractual restrictions. In the context of such networks, researchers have concentrated on developing methods to co-optimize vehicle routes with delivery schedules. However, distributional networks often have a mix of both VMICs and Customer Managed Inventory Customers (CMICs), and attempting to optimize long-term delivery policies while accounting for both types of customers can be challenging. This is due to the underlying Vehicle Routing Problem (VRP) being NP-Hard combined with the inherent variability in the network. Furthermore, while CMICs exhibit exogenous uncertainty in delivery dates and quantities, VMICs exhibit endogenous uncertainty that we can influence. In this talk, we present a framework that can effectively identify clusters of VMICs whose demands and dates of delivery can be constructively coordinated such that long-term average distribution costs are minimized, in light of the variability of CMICs in the network.

Various works have used sampling-based frameworks in the context of last-mile distribution. For example, sampling was used in [3] to decompose larger stochastic VRPs into smaller deterministic ones, whose solution was then used to heuristically construct routes for the initial VRP, whereas we used a scenario sampling framework in [4] to estimate the expected marginal cost of a single new customer in a network. Here, we focus on the network as a whole and implement a framework to identify expensive customers based on their impact on long-term average network cost. These customers are revealed by sampling the network over both VMICs and CMICs, where each resulting sample constitutes a "Multi-Depot Vehicle Routing Problem with Inter-Depot Replenishment" (MDVRPI) [5]. This VRP variant, which mimics real-life operations in industrial gasses distribution, can be formulated as a mixed-integer linear program with an exponential number of variables and solved by employing an effective, purpose-built Brach-Price-and-Cut solver [4,6,7]. By studying a sufficient number of sampled scenarios, we estimate the average cost under various demand realizations of various clusters involving the target. This information then allows us to proactively manipulate and coordinate VMIC demands and delivery dates, instead of allowing them to realize independently, via the solution of a carefully constructed LP model that determines the optimal coordination of VMIC deliveries and delivery quantities for each cluster to minimize average network costs. This process can thus be repeated to extract more efficiencies from forming additional VMIC clusters, further reducing overall network costs.

We conduct extensive computational studies on augmented benchmark instances from the literature and showcase the ability of the framework to identify VMIC clusters and their optimal coordination. The framework systematically provides rules of thumb on optimal dispatching policies, through which we were able to reduce long-term average network costs by over 7% in the instances that we studied.

References

[1]. Toth, Paolo, and Daniele Vigo, eds. Vehicle routing: problems, methods, and applications. Society for industrial and applied mathematics, 2014.

[2]. Archetti, Claudia, Luca Bertazzi, Gilbert Laporte, and Maria Grazia Speranza. "A branch-and-cut algorithm for a vendor-managed inventory-routing problem." Transportation science 41, no. 3 (2007): 382-391.

[3]. Wang, Akang, Jeffrey E. Arbogast, Gildas Bonnier, Zachary Wilson, and Chrysanthos E. Gounaris. "Estimating the marginal cost to deliver to individual customers." Optimization and Engineering (2023): 1-39.

[4]. Hvattum, Lars M., Arne Løkketangen, and Gilbert Laporte. "Solving a dynamic and stochastic vehicle routing problem with a sample scenario hedging heuristic." Transportation Science 40, no. 4 (2006): 421-438.

[5]. Crevier, Benoit, Jean-François Cordeau, and Gilbert Laporte. "The multi-depot vehicle routing problem with inter-depot routes." European journal of operational research 176, no. 2 (2007): 756-773.

[6]. Pecin, Diego, Artur Pessoa, Marcus Poggi, and Eduardo Uchoa. "Improved branch-cut-and-price for capacitated vehicle routing." Mathematical Programming Computation 9 (2017): 61-100.

[7]. Baldacci, Roberto, and Aristide Mingozzi. "A unified exact method for solving different classes of vehicle routing problems." Mathematical Programming 120 (2009): 347-380.