Transportation Science · 2015 · 134 citations · 27 references
ManagementIndustrial EngineeringOperations ManagementInventory ManagementOptimizationSchedulingCombinatorial OptimizationInteger ProgrammingRoute PlanningRoutingTransportation ProblemsVehicle SchedulingBranch-and-cutBranch-and-priceColumn GenerationFeasible FlowRouting ProblemsValid InequalitiesVehicle RoutingVehicle Routing Problems
The inventory-routing problem (IRP) integrates two well-studied problems, namely, inventory management and vehicle routing. Given a set of customers to service over a multiperiod horizon, the IRP consists of determining when to visit each customer, which quantity to deliver in each visit, and how to combine the visits in each period into feasible routes such that the total routing and inventory costs are minimized. In this paper, we propose an innovative mathematical formulation for the IRP and develop a state-of-the-art branch-price-and-cut algorithm for solving it. This algorithm incorporates known and new families of valid inequalities, including an adaptation of the well-known capacity inequalities, as well as an ad hoc labeling algorithm for solving the column generation subproblems. Through extensive computational experiments on a widely used set of 640 benchmark instances involving between two and five vehicles, we show that our branch-price-and-cut algorithm clearly outperforms a state-of-the-art branch-and-cut algorithm on the instances with four and five vehicles. In this instance set, 238 were still open before this work and we proved optimality for 54 of them.
27
Branch-and-Price: Column Generation for Solving Huge Integer Programs
Cynthia Barnhart, Ellis L. Johnson, George L. Nemhauser et al. · Operations Research · 1998 · 2.2K citations
Selected Topics in Column Generation
Marco E. Lübbecke, Jacques Desrosiers · Operations Research · 2005 · 1.1K citations