Academic Lectures:A Schedule-based Formulation for the Cyclic Inventory Routing Problem

Publisher:王逢凤Publish Date:2015-09-01Views:115

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. 2015
Location: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.