An Effective Decomposition Approach for Solving Large Supply Chain Oriented Pick-up and Delivery Problems

DONDO, RODOLFO; MENDEZ, CARLOS; CERDÁ, JAIME

10th International Symposium on Process System Engineering - PSE2009 (Eds : Rita M. de Brito Alves, Claudio A. Oller do Nascimento and Evaristo Chalbaud Biscaia Jr.)

Elsevier

Lugar: Amsterdam; Año: 2009; p. 2043 - 2048

Pick-up and delivery problems (PDP) are receiving a growing attention in process systems engineering due to its close relationship with major supply chain issues. Its aim is to discover the best routes/schedules for a vehicles fleet fulfilling a number of transportation requests at “minimum cost”. In the conventional PDP, each request defines the shipping of a given load from a specified pickup site to a given customer. However, in order to account for a wider range of logistics problems, the so-called supply-chain oriented PDP (SC-PDP) problem has been defined as a three-tier network of interconnected factories, warehouses and customers. Multiple products are to be efficiently delivered through this network in order to meet a set of given demands. The selected vehicle routes/schedules must satisfy capacity and timing constraints while minimizing transportation costs. The pickup points for each demand are decision variables rather than problem specifications and several commodities can be transported between sites. Moreover, every customer can be visited several times. The general SC-PDP has been represented as an MILP formulation that is able to address moderate size instances. In order to efficiently address large-scale SC-PDP problems, a decomposition method based on a column generation (CG) procedure is introduced in this work. In contrast to traditional CG approaches lying on dynamic-programming-procedures as route generators, an MILP formulation is here proposed to implicitly create the set of feasible routes/ schedules at the slave level of the method.