A decomposition approach for split delivery in the distribution of industrial gases

COCCOLA, MARIANA; MENDEZ, CARLOS; DONDO, RODOLFO

Santiago

Congreso; Congreso Latino-Iberoamericano de Investigación Operativa - CLAIO 2016; 2016

Pontificia Universidad Católica de Chile

We propose a decomposition procedure based on a three-level column generation framework for the optimal delivering of industrial gases. The industrial problem can be modelled as a split-delivery routing problem plus some constraints associated the delivery of gases. The lowest-level problem computes several cargo patterns for each route generated on the intermediatelevel routes-generator problem. Routes and cargo patterns form the so-called cargo-routes that are coordinated on the top-level master-problem to fulfil the demands of different gases by customers. We tested two cargogeneration procedures: via column generation leading to a nested procedure and via a procedure that implicitly generates all cargos as a convex combination of extreme cargo-patterns. Both strategies were evaluated by solving several instances derived from a real-world case including 3 plants producing LIN and LOX destined to satisfy the demand of up to 50 clients. All were solved in less than an hour.