Column generation for scheduling shipments within a supply chain network with the minimum number of vehicles

Abstract

We consider the problem of scheduling a set of shipments between different nodes of a supply chain network. Each shipment has a fixed departure time, as well as an origin and a destination node, which, combined, determine the duration of the associated trip. The aim is to schedule as many shipments as possible, while also minimizing the number of vehicles utilized for this purpose. We develop an integer programming model and an associated branch and price solution algorithm for this problem. The optimal solution to the LP relaxation of the problem is obtained through column generation, a methodology for solving linear programs with a huge number of variables, without explicitly considering all of them. In the context of our application, the proposed methodology utilizes a master problem that schedules the maximum possible number of shipments using only a small set of vehicle-routes, and a column generation (colgen) sub-problem that generates cost-effective vehicle-routes which are fed into the master problem. The optimal solution to the colgen sub-problem is obtained with an efficient network optimization solution algorithm, which outperforms existing commercial optimization software packages that can be used alternatively for that purpose. After finding the optimal solution to the LP relaxation of the problem, the algorithm branches on the fractional decision variables (vehicle-routes), in order to reach the optimal integer solution. Special branching rules that expedite the algorithm's performance are utilized for this purpose. We describe in detail the steps of the proposed solution algorithm, focusing on several problem aspects that have a strong influence on its performance. We conclude with limited computational results that demonstrate the algorithm's performance on a particular case study, and a discussion of how various computational difficulties that can possibly arise can be handled.