A Branch-Price-and-Cut Algorithm for Single-Product Maritime Inventory Routing

• 成果类型: Article
• 署名作者: Engineer, Faramroze G.; Furman, Kevin C.; Nemhauser, George L.; Savelsbergh, Martin W. P.; Song, Jin-Hwa
• 署名单位: University of Newcastle; Exxon Mobil Corporation; University System of Georgia; Georgia Institute of Technology
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1110.0997
• 发表日期: 2012
• 页码: 106-122
• 关键词: management

摘要

A branch-price-and-cut algorithm is developed for a complex maritime inventory-routing problem with varying storage capacities and production/consumption rates at facilities. The resulting mixed-integer pricing problem is solved exactly and efficiently using a dynamic program that exploits certain extremal characteristics of the pricing problem. The formulation is tightened by using the problem's boundary conditions in preprocessing and to restrict the set of columns that are produced by the pricing problem. Branching schemes and cuts are introduced that can be implemented efficiently and that preserve the structure of the pricing problem. Some of the cuts are inspired by the capacity cuts known for the vehicle-routing problem, whereas others specifically target fractional solutions brought about by individual vessels competing for limited inventory at load ports and limited storage capacity at discharge ports. The branch-price-and-cut approach solves practically sized problems motivated by the operations of an oil company to optimality, and it provides reasonable bounds for larger instances.