Modeling the Gateway Location Problem for Multicommodity Flow Rerouting

详细信息    查看全文

• 作者：Maurizio Bruglieri (1) maurizio.bruglieri@polimi.it
  Paola Cappanera (2) paola.cappanera@unifi.it
  Alberto Colorni (1) alberto.colorni@polimi.it
  Maddalena Nonato (3) maddalena.nonato@unife.it
• 刊名：Lecture Notes in Computer Science
• 出版年：2011
• 出版时间：2011
• 年：2011
• 卷：6701
• 期：1
• 页码：262-276
• 全文大小：308.4 KB
• 参考文献：1. Bergendorff, P., Hearn, D.W., Ramana, M.V.: Congestion toll pricing of traffic networks. In: Pardalos, P.M., et al. (eds.) Network Optimization. LNEMS, vol. 450, pp. 51–71. Springer, Heidelberg (1997)
  2. Colson, B., Marcotte, P., Savard, G.: An overview of bilevel optimization. Annals of Operations Research 153(1), 235–256 (2007)
  3. Lombard, K., Church, R.L.: The Gateway Shortest Path Problem: Generating Alternative Routes for a Corridor Routing Problem. Geographical Systems 1, 25–45 (1993)
  4. Avella, P., Sassano, A., Vasilev, I.: Computational study of large-scale p-median problems. Mathematical Programming 109, 89–114 (2007)
  5. Resende, M.G.C., Werneck, R.F.: A hybrid heuristic for the p-median problem. Journal of Heuristics 10, 59–88 (2004)
  6. Kara, B.Y., Verter, V.: Designing a Road Network for Hazardous Materials Transportation. Transportation Science 38(2), 188–196 (2004)
  7. Erkut, E., Gzara, F.: Solving the hazmat transport network design problem. Computers and Operations Research 35, 2234–2247 (2008)
  8. Verter, V., Kara, B.Y.: A path-based approach for hazmat transport network design. Management Science 54(1), 29–40 (2008)
  9. Bruglieri, M., Maja, R., Marchionni, G., Rainoldi, G.: Safety in hazardous material road transportation: state of the art and emerging problems. In: Bersani, C., et al. (eds.) Advanced Technologies and Methodologies for Risk Management in the Global Transport of Dangerous Goods. IOS Press, Amsterdam (2008)
  10. Migdalas, A.: Bilevel programming in traffic planning: Models, methods and challenge. Journal of Global Optimization 7(4), 381–405 (1995)
  11. Garcia, R., Marin, A.: Parking Capacity and Pricing in Parkn Ride Trips: A Continuous Equilibrium Network Design Problem. Annals of Operations Research 116, 153–178 (2002)
  12. Cappanera, P., Scaparra, M.P.: Optimal Allocation of Protective Resources in Shortest-Path Networks. Transportation Science, doi:10.1287/trsc.1100.0340
  13. Labbe茅, M., Marcotte, P., Savard, G.: A bilevel model of taxation and its application to optimal highway pricing. Management Science 44, 1608–1622 (1998)
  14. Marcotte, P., Mercier, A., Savard, G., Verter, V.: Toll policies for mitigating hazardous materials transport risk. Transportation Science 43(2), 228–243 (2009)
• 作者单位：1. INDACO, Via Durando 38a, Milano, Italy2. DSI, Via S. Marta 3, Firenze, Italy3. ENDIF, Via L. Saragat 1, Ferrara, Italy
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

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.