In this work we propose a novel approach addressing the need for a spatially equitable distribution of the flows when routing multiple commodities on a capacitated network. In our model, the spatial distribution of the flows is considered by partitioning the area in which the network is embedded by means of a grid of uniform size cells and then computing the impact of the network flows on each cell by a weighted linear combination of the flows interesting each cell. A spatially equitable distribution of the flows is therefore obtained when all the multicommodity demands are satisfied in such a way to minimize the maximum impact registered on the cells of the grid. We refer to this problem as the spatially equitable multicommodity capacitated network flow problem and propose a minimax linear programming formulation. The need to find a proper trade-off between the total routing cost and the spatial equity is treated as well by considering both the objective functions and computing pareto-optimal solutions for the bicriteria optimization problem. Computational results obtained on a real traffic network are presented and discussed in the paper. © 2011 Springer-Verlag.
The Spatially Equitable Multicommodity Capacitated Network Flow Problem / Dell'Olmo, Paolo; Antonino, Sgalambro. - 6701 LNCS:(2011), pp. 196-209. (Intervento presentato al convegno 5th International Conference on Network Optimization, INOC 2011 tenutosi a Hamburg; Germany) [10.1007/978-3-642-21527-8_25].
The Spatially Equitable Multicommodity Capacitated Network Flow Problem
DELL'OLMO, Paolo;
2011
Abstract
In this work we propose a novel approach addressing the need for a spatially equitable distribution of the flows when routing multiple commodities on a capacitated network. In our model, the spatial distribution of the flows is considered by partitioning the area in which the network is embedded by means of a grid of uniform size cells and then computing the impact of the network flows on each cell by a weighted linear combination of the flows interesting each cell. A spatially equitable distribution of the flows is therefore obtained when all the multicommodity demands are satisfied in such a way to minimize the maximum impact registered on the cells of the grid. We refer to this problem as the spatially equitable multicommodity capacitated network flow problem and propose a minimax linear programming formulation. The need to find a proper trade-off between the total routing cost and the spatial equity is treated as well by considering both the objective functions and computing pareto-optimal solutions for the bicriteria optimization problem. Computational results obtained on a real traffic network are presented and discussed in the paper. © 2011 Springer-Verlag.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
