CO2 Transport: A new application of the assignment problem

The possibility exists that Ohio River Valley coal-burning power plant stack gases rich in CO2 can be profitably disposed of by transportation via existing reversed flow natural gas trunklines to the Gulf Coast, where they can be sold as an injectant for enhanced oil recovery. Part of the uncertainty arises from the difficulty in identifying, from among the large number of power plants and oil fields which could supply and demand the CO2, which set would provide maximum profit for the pipeline companies, given the revenues expected from each, the feeder and gathering line construction costs, and the costs of shipment over existing trunklines. The profit-maximizing problem is viewed as a variant of the familiar knapsack problem, where the pipelines are viewed as containers to be filled by portions of differing volume and value per unit volume, transported, and emptied by dividing up their contents into portions of differing volume and value per unit volume. The problem is formulated, and a set of solution techniques examined. A real problem is solved, using a greedy algorithm.