This paper introduces a new problem, involving the optimal location of a limited number of gateways on the nodes of an uncapacitated network. A multicommodity flow, where each commodity is of single-origin-single-destination type, moves on the network according to its linear objective function c. Gateways are used by the network administrator to reroute flows by obliging each commodity to detour from its c-optimal path and pass by its assigned gateway. Gateways are located and assigned by the administrator so that the resulting c-optimal flows on the detours minimize the administrator's objective function r. Gateways thus provide the administrator with a mechanism for indirect flow control, so that the flow value according to r is improved with respect to the unregulated scenario. To the authors knowledge, this is a new combinatorial optimization problem, that we call the gateway location problem for multicommodity flow rerouting. We present three alternative formulations and discuss pros and cons of each. Interesting applications arise in the field of hazardous material transportation. The discussion is supported by computational results on realistic instances from this field. © 2011 Springer-Verlag.

Modeling the gateway location problem for multicommodity flow rerouting

NONATO, Maddalena
2011

Abstract

This paper introduces a new problem, involving the optimal location of a limited number of gateways on the nodes of an uncapacitated network. A multicommodity flow, where each commodity is of single-origin-single-destination type, moves on the network according to its linear objective function c. Gateways are used by the network administrator to reroute flows by obliging each commodity to detour from its c-optimal path and pass by its assigned gateway. Gateways are located and assigned by the administrator so that the resulting c-optimal flows on the detours minimize the administrator's objective function r. Gateways thus provide the administrator with a mechanism for indirect flow control, so that the flow value according to r is improved with respect to the unregulated scenario. To the authors knowledge, this is a new combinatorial optimization problem, that we call the gateway location problem for multicommodity flow rerouting. We present three alternative formulations and discuss pros and cons of each. Interesting applications arise in the field of hazardous material transportation. The discussion is supported by computational results on realistic instances from this field. © 2011 Springer-Verlag.
2011
9783642215261
hazardous material transport; bilevel programming; location
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in SFERA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11392/1534795
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 4
social impact