ABSTRACT
ABSTRACT In this chapter, 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 a Dantzig-Wolfe decomposition of the arc-based
CONTENTS
6.1 Introduction ................................................................................................ 154 6.2 Literature Review....................................................................................... 155 6.3 Problem Definition and Formulation ...................................................... 157
6.3.1 Arc-Based Model ............................................................................ 157 6.3.2 Schedule-Based Model .................................................................. 159
6.4 Solution Methods ....................................................................................... 160 6.4.1 Valid Inequality on the Number of Replenishments ................ 161 6.4.2 Nondominated Variables .............................................................. 166 6.4.3 Column Generation ....................................................................... 167 6.4.4 Implementation Issues .................................................................. 169
6.5 Model Extension......................................................................................... 169 6.5.1 Multiple Depots .............................................................................. 170 6.5.2 Depot Capacity ............................................................................... 170 6.5.3 Multiple Fleets ................................................................................ 170 6.5.4 Finite Period Inventory Routing Problem .................................. 171
6.6 Computational Study ................................................................................ 172 6.6.1 Details of the Test Instances ......................................................... 173 6.6.2 Solution by Enumerating All Schedules ..................................... 173 6.6.3 Column Generation Results ......................................................... 175 6.6.4 Schedule Quality in the Best IP Solutions .................................. 175
6.7 Conclusions ................................................................................................. 176 Acknowledgments .............................................................................................. 176 References ............................................................................................................. 176
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 linear programming (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 integer programming (IP)–LP gaps of SBM are within 5% for maximum-level (ML) policy and 7% for order-up-to-level (OU) policy, respectively.
