reporttitle:project management: a schedule-based formulation for the cyclic inventory routing problem reporter(institution):yu chen(tongji university) time:02:00.pm,6th september. 2015location:b-201, building of economics & management, jiulonghucampus abstract:in this paper, we study a cyclic inventory routing problem (cirp). the traditional exact methods for the inventory routing problem (irp) use an arc-based formulation (also known as two-index flow formulation), in which a variable represents a possible vehicle flow between a pair of customers. in this research, we propose a schedule-based model (sbm), in which a variable represents a possible one-day schedule for any vehicle. this model can be considered as a dantzig-wolfe decomposition of the arc-based model. we also propose a set of new valid inequalities to tighten the linear relaxation bound of sbm. to solve sbm efficiently, we develop a column generation algorithm, in which only attractive vehicle schedules are generated. our computational results on five real-life test cases show that the lp relaxation of sbm is tight. sbm can obtain near optimal solutions to very large real-life test cases within a reasonable time, and average ip-lp gaps of sbm are within 5% for ml policy and 7% for ou policy respectively. |
