(181b) Multiscale Production Routing in Multicommodity Supply Chains with Complex Production Facilities

Zhang, Q., Carnegie Mellon University
Grossmann, I., Carnegie Mellon University
Sundaramoorthy, A., Praxair, Inc.
Pinto, J. M., Linde plc
In order to increase the efficiency of industrial supply chains, the simultaneous optimization of production and distribution operations is becoming increasingly important. This problem is especially relevant in the industrial gas industry where multiple products (e.g. liquid and gaseous oxygen and nitrogen) are produced in multiple plants, and distributed to a large set of customers. Among the integrated supply chain planning problems, the so-called production routing problem (PRP) (Adulyasak, Cordeau, & Jans, 2015) is the most comprehensive one as it considers production, inventory, distribution, and routing decisions simultaneously. The PRP in its classical form can be formulated as a mixed-integer linear program (MILP) and integrates two well-known problems, namely the lot-sizing problem (LSP) and the inventory routing problem (IRP). The PRP is notoriously difficult to solve; so far, good solutions to instances of relevant sizes have only been obtained by applying tailored metaheuristics.

In this work, we introduce an extension of the PRP, the multiscale production routing problem (MPRP), which considers multicommodity supply chains with complex production facilities. The complexity in the production processes requires the consideration of operational transitions and time-sensitive prices, which are not modeled in a simple LSP formulation. As a result, the MPRP is an even more difficult problem than the classical PRP.

For modeling the MPRP, we propose an MILP formulation involving two different time grids. While a detailed mode-based production scheduling model captures all critical operational constraints on the fine time grid, vehicle routing is considered in each time period of the coarse time grid. In order to solve large instances of the MPRP, we propose an iterative MILP-based heuristic approach that solves the MILP model with a restricted set of candidate routes at each iteration and dynamically updates the set of candidate routes for the next iteration. The results of an extensive computational study show that the proposed algorithm finds high-quality solutions in reasonable computation times (within an hour), and in large instances, it significantly outperforms a standard two-phase heuristic approach and a solution strategy involving a one-time heuristic pre-generation of candidate routes (Marchetti, et al., 2014). Similar results are achieved in an industrial case study, which considers a real-world industrial gas supply chain with 2 plants, approximately 240 customers, 20 vehicles, and a planning horizon of 4 weeks, resulting in 168 time periods on the fine grid and 56 time periods on the coarse grid.


Adulyasak, Y., Cordeau, J. F., & Jans, R. (2015). The production routing problem: A review of formulations and solution algorithms. Computers & Operations Research, 55, 141-152.

Marchetti, P. A., Gupta, V., Grossmann, I. E., Cook, L., Valton, P.-M., Singh, T., Li, T., & André, J. (2014). Simultaneous production and distribution of industrial gas supply-chains. Computers & Chemical Engineering, 69, 39-58.