(471b) A Graph Sampling and Coarsening Approach for the Solution of Supply Chain Models with Vehicle Routing Decisions

Enhancing the supply chain efficiency is crucial for companies to gain a competitive advantage. A strategy to achieve this goal is through coordinating various supply chain operations, such as sourcing, conversion, storage, and distribution. [1,2]. A large number of works have introduced holistic approaches to enable this [3]. One of the most challenging issues in integrated supply chain models is simultaneously optimizing production, inventory, and vehicle routing [4]. The applications of such an approach are numerous, such as industrial gas supply chains [5], petrochemical shipment using seagoing vessels (also referred to as maritime routing) [6], perishable or cold food supply chains [7,8], and biomass transportation [9,10]. Supply chain models that integrate vehicle routing lead to large-scale mixed-integer programming formulations. This is because the number of possible routes increases exponentially as the number of customers increases. To address this computational challenge, specialized solution approaches have been proposed, such as column generation [11,12] and costumer clustering heuristics [13,14]. Despite the progress made in this field, there remain unresolved issues such as the limited unification of formulations to address diverse industrial problems and the challenge of handling large-scale instances.

In this work, we propose a unifying supply chain model that makes simultaneous supply, demand, conversion, inventory, and vehicle routing decisions, which can be used across various industrial problems. To deal with the astronomically large number of routes embedded in realistic models, we adopt a graph sampling and coarsening paradigm, which creates a simplified supply chain model by randomly selecting a small subset of routes from the entire set of routes. We show that the resulting low-complexity approximate model yields a suboptimal but feasible solution and a valid upper bound. Furthermore, we apply a constraint aggregation/coarsening approach to relax the feasible region and derive a valid lower bound to determine the optimality of the approximate solution derived via sampling. This approach extends the graph sampling and coarsening (gSC) scheme proposed in previous work for supply chain models (which do not incorporate inventory and vehicle routing decisions) [15]. We apply our model to a large waste-to-energy case study in the State of Wisconsin where agricultural organic waste is used to generate biogas and electricity via anaerobic digestion and revenue is obtained by exploiting dynamic electricity markets. The results indicate that our approach is capable of obtaining high-quality solutions with guaranteed optimality and under a limited time budget for formulations that cannot be handled using state-of-the-art solvers.

Reference:

[1] Sampat, Apoorva M., Edgar Martin, Mariano Martin, and Victor M. Zavala. "Optimization formulations for multi-product supply chain networks." Computers & Chemical Engineering 104 (2017): 296-310.

[2] Tominac, Philip A., Weiqi Zhang, and Victor M. Zavala. "Spatio-temporal economic properties of multi-product supply chains." Computers & Chemical Engineering 159 (2022): 107666.

[3] Snyder, L.V. and Shen, Z.J.M., 2019. Fundamentals of supply chain theory. John Wiley & Sons.

[4] Zhang, Qi, Arul Sundaramoorthy, Ignacio E. Grossmann, and Jose M. Pinto. "Multiscale production routing in multicommodity supply chains with complex production facilities." Computers & Operations Research 79 (2017): 207-222.

[5] Dong, Yachao, Jose M. Pinto, Arul Sundaramoorthy, and Christos T. Maravelias. "MIP model for inventory routing in industrial gases supply chain." Industrial & Engineering Chemistry Research 53, no. 44 (2014): 17214-17225.

[6] Jiang, Yongheng, and Ignacio E. Grossmann. "Alternative mixed-integer linear programming models of a maritime inventory routing problem." Computers & Chemical Engineering 77 (2015): 147-161.

[7] Amorim, Pedro, and Bernardo Almada-Lobo. "The impact of food perishability issues in the vehicle routing problem." Computers & Industrial Engineering 67 (2014): 223-233.

[8] Awad, M., Ndiaye, M. and Osman, A., 2020. Vehicle routing in cold food supply chain logistics: a literature review. The International Journal of Logistics Management, 32(2), pp.592-617.

[9] Gracia, Carlos, Borja Velázquez-Martí, and Javier Estornell. "An application of the vehicle routing problem to biomass transportation." Biosystems engineering 124 (2014): 40-52.

[10] Cao, Jin Xin, Zongxi Zhang, and Yuguang Zhou. "A location-routing problem for biomass supply chains." Computers & Industrial Engineering 152 (2021): 107017.

[11] Grønhaug, Roar, Marielle Christiansen, Guy Desaulniers, and Jacques Desrosiers. "A branch-and-price method for a liquefied natural gas inventory routing problem." Transportation Science 44, no. 3 (2010): 400-415.

[12] Engineer, Faramroze G., Kevin C. Furman, George L. Nemhauser, Martin WP Savelsbergh, and Jin-Hwa Song. "A branch-price-and-cut algorithm for single-product maritime inventory routing." Operations Research 60, no. 1 (2012): 106-122.

[13] Dondo, Rodolfo, and Jaime Cerdá. "A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows." European journal of operational research 176, no. 3 (2007): 1478-1507.

[14] Santini, Alberto, Michael Schneider, Thibaut Vidal, and Daniele Vigo. "Decomposition strategies for vehicle routing heuristics." INFORMS Journal on Computing (2023).

[15] Ma, Jiaze, and Victor M. Zavala. "Solution of large-scale supply chain models using graph sampling & coarsening." Computers & Chemical Engineering 163 (2022): 107832.