Solving Large Distribution Problems in Supply Chain Networks by a Column Generation Approach

Solving Large Distribution Problems in Supply Chain Networks by a Column Generation Approach

Rodolfo G. Dondo (National University of Litoral, Institute of Technological Development for the Chemical Industry, Santa Fe, Argentina) and Carlos A. Mendez (Instituto National University of Litoral, Institute of Technological Development for the Chemical Industry, Santa Fe, Argentina)
DOI: 10.4018/ijoris.2014070103
OnDemand PDF Download:
No Current Special Offers


Vehicle routing problems (VRP) are receiving a growing attention in process systems engineering due to its close relationship with 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”. Pick-up and delivery problems (PDP) are a class of VRP on which each request defines the shipping of a given load from a specified pickup site to a given customer. In order to account for a wider range of logistics problems, the so-called supply-chain management VRP (SCM-VRP) problem has been defined as a three-tier network of interconnected factories, warehouses and customers. In this problem, multiple products are to be delivered from some supply-sites to a number of customers through a routes-network in order to meet a set of given demands. The vehicle routes must satisfy capacity and timing constraints while minimizing an objective function stating the specified transportation cost. Pickup sites for each demand are decision variables rather than problem specifications. The SCM-VRP had been modeled as an MILP problem and the resolution of this formulation via a standard branch-and-cut software can provide optimal solutions to moderate size instances. In order to efficiently address larger problems, a decomposition method based on a column generation procedure is introduced in this work. In contrast to traditional columns generation approaches lying on dynamic-programming-procedures as route generators, an MILP formulation is here proposed to create the set of feasible routes and schedules at the slave level of the method. Furthermore, a branch-and-price method based on node-to-routes assignment decisions is constructed to better exploit the MILP route-generator. Finally, several benchmark examples were presented and satisfactorily solved.
Article Preview


A typical supply chain covers the procurement of raw materials from suppliers and their shipping to one or more factories, the conversion of such inputs into intermediate and final products, their shipping to warehouses or depots for intermediate storage and the delivery of products to retailers and customers (Simchi-Levi et al., 2004). The supply chain management field and the emerging area of enterprise wide optimization have focused the attention on developing tools to efficiently coordinate factories, warehouses and customers so that product demands are satisfied with the specified quality service level at the minimum system cost. The pickup and delivery problem (PDP) is a widely studied problem that involves orders matching the pick-up of a given load at one or more locations and the subsequent delivery to one or several locations. This classical transportation research problem can be useful in the context of supply-chain management if properly modified and if its scope is expanded to a supply chain point of view. As many transportation research articles related to the PDP originated from work on practical problems, there were a few papers focusing exactly on the same problem (Savelsbergh & Sol, 1995). I.e. problem constraints can be different, understanding of “customer satisfaction” or “service quality level” can be different, objective functions can be different and so on. The most known and extensively studied PDP involves time-window constraints and assumes that each transportation request specifies the size of the load to be transported, a single load-origin and a single destination and that all available vehicles depart from and return to a central warehouse. It is usually called the PDP with time windows (PDPTW). Needless to say, in many realistic logistic operations, the load from multiple pick-up nodes must be transported to a single delivery location or the load from a single supply site must be delivered to several locations.

Some other variants are also possible but have received considerable less attention than the PDPTW. They are loosely labelled as “the general pick-up and delivery problem” (G-PDP). Despite the importance of the PDPTW and some new modelling issues introduced by the G-PDP, it is clear that new features must be considered to obtain a better representation of realistic supply chains. Some of these new possibilities to consider are: (1) Several commodities may be transported on the same vehicle. (2) Alternatives sources for each commodity are available. (3) Each vehicle may operate on more than a single route if the total time spent on these routes is less than the specified maximum service time. (4) The problem may involve multiple depots with known inventories of commodities. (5) Depots may arise as intermediate stops on the vehicles routes. To model these possibilities, Dondo et al. (2009) proposed a new variation of the PDP that involves a set of facilities from which multiple products are to be delivered to many consumers in order to meet some demands while satisfying capacity and timing constraints. The problem was called the vehicle routing problem for supply-chains management (VRP-SCM) and was addressed by an MILP formulation. The high flexibility provided to the routes design process allows finding efficient operational strategies to manage complex multi-site distribution systems. In the other hand, a lot of effort of the operational research community has been directed to the development of heuristic and exact procedures capable of dealing with the inherent complexity of large routing problems. In this way, Desrochers et al. (1992) presented for the VRP with time windows (VRPTW) a technique now widely known as the column generation approach. The technique decomposes the routing problem in a couple comprising a restricted master problem (RMP) and a slave tour-generator problem. This couple is recursively solved to produce feasible routes (also called columns) until no more can be generated. In such a case, the RMP is solved again to verify the integrality of its solution. If the solution is integer, the optimal solution to the routing problem has been found and the procedure ends. Otherwise, a feasible column that would provide an integer solution may not be present in the pool of generated routes. Then, more routes must be produced after branching and the so called branch-and-price algorithm is obtained when the column-generation procedure is embedded into a branch-and-bound tree. The column generation procedure must run at all nodes of the branch-and-price tree. The whole algorithm remains as one of the most efficient optimization techniques for solving large routing problems.

Complete Article List

Search this Journal:
Volume 14: 1 Issue (2023): Forthcoming, Available for Pre-Order
Volume 13: 2 Issues (2022)
Volume 12: 4 Issues (2021)
Volume 11: 4 Issues (2020)
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing