Name
Abstract | ||
|---|---|---|
We introduce a new model for pipeline transportation of petroleum products with no due dates. We use a directed graph G with n nodes, where arcs represent pipes and nodes represent locations. We also define a set L of r transportation orders and a subset F 驴 L of further orders. A feasible solution to our model is a pumping sequence that delivers the products corresponding to all orders in L-F. We prove that the problem of finding such a solution is NP-hard, even if G is acyclic. For the special case where the products corresponding to orders in F are initially stored at nodes, we propose the BPA algorithm. This algorithm finds a feasible solution in O(r2 log r + s2(rn + logs)) time, where s is the total volume in the arcs of G. We point out that the input size is 驴(s). If G is acyclic, then BPA finds a minimum cost solution. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1007/3-540-45995-2_25 | LATIN |
Keywords | Field | DocType |
r transportation order,due dates,due date,set l,new model,petroleum products,bpa algorithm,graph g,subset f,minimum cost solution,pipeline transportation,feasible solution,directed graph | Canalisation,Discrete mathematics,Combinatorics,Pipeline transport,Computer science,Directed graph,Petroleum product,Graph Node,Special case | Conference |
Volume | ISSN | ISBN |
2286 | 0302-9743 | 3-540-43400-3 |
Citations | PageRank | References |
6 | 0.97 | 3 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ruy Luiz Milidiú | 1 | 192 | 20.18 |
| Artur Alves Pessoa | 2 | 270 | 24.30 |
| Eduardo Sany Laber | 3 | 229 | 27.12 |