IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v167y2015i2d10.1007_s10957-015-0749-1.html
   My bibliography  Save this article

Adjoint-Based Optimization on a Network of Discretized Scalar Conservation Laws with Applications to Coordinated Ramp Metering

Author

Listed:
  • Jack Reilly

    (University of California)

  • Samitha Samaranayake

    (University of California)

  • Maria Laura Delle Monache

    (Inria Sophia Antipolis - Méditerranée)

  • Walid Krichene

    (University of California)

  • Paola Goatin

    (Inria Sophia Antipolis - Méditerranée)

  • Alexandre M. Bayen

    (University of California)

Abstract

The adjoint method provides a computationally efficient means of calculating the gradient for applications in constrained optimization. In this article, we consider a network of scalar conservation laws with general topology, whose behavior is modified by a set of control parameters in order to minimize a given objective function. After discretizing the corresponding partial differential equation models via the Godunov scheme, we detail the computation of the gradient of the discretized system with respect to the control parameters and show that the complexity of its computation scales linearly with the number of discrete state variables for networks of small vertex degree. The method is applied to the problem of coordinated ramp metering on freeway networks. Numerical simulations on the I15 freeway in California demonstrate an improvement in performance and running time compared with existing methods. In the context of model predictive control, the algorithm is shown to be robust to noise in the initial data and boundary conditions.

Suggested Citation

  • Jack Reilly & Samitha Samaranayake & Maria Laura Delle Monache & Walid Krichene & Paola Goatin & Alexandre M. Bayen, 2015. "Adjoint-Based Optimization on a Network of Discretized Scalar Conservation Laws with Applications to Coordinated Ramp Metering," Journal of Optimization Theory and Applications, Springer, vol. 167(2), pages 733-760, November.
    • Handle: RePEc:spr:joptap:v:167:y:2015:i:2:d:10.1007_s10957-015-0749-1
    DOI: 10.1007/s10957-015-0749-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-015-0749-1
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10957-015-0749-1?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Athanasios K. Ziliaskopoulos, 2000. "A Linear Programming Model for the Single Destination System Optimum Dynamic Traffic Assignment Problem," Transportation Science, INFORMS, vol. 34(1), pages 37-49, February.
    2. Paul I. Richards, 1956. "Shock Waves on the Highway," Operations Research, INFORMS, vol. 4(1), pages 42-51, February.
    3. Daganzo, Carlos F., 1995. "The cell transmission model, part II: Network traffic," Transportation Research Part B: Methodological, Elsevier, vol. 29(2), pages 79-93, April.
    4. Mapundi Banda & Michael Herty, 2012. "Adjoint IMEX-based schemes for control problems governed by hyperbolic conservation laws," Computational Optimization and Applications, Springer, vol. 51(2), pages 909-930, March.
    5. Louis Blanchard & Régis Duvigneau & Anh-Vu Vuong & Bernd Simeon, 2014. "Shape Gradient for Isogeometric Structural Design," Journal of Optimization Theory and Applications, Springer, vol. 161(2), pages 361-367, May.
    6. M. Gugat & M. Herty & A. Klar & G. Leugering, 2005. "Optimal Control for Traffic Flow Networks," Journal of Optimization Theory and Applications, Springer, vol. 126(3), pages 589-616, September.
    7. B. Rothfarb & H. Frank & D. M. Rosenbaum & K. Steiglitz & D. J. Kleitman, 1970. "Optimal Design of Offshore Natural-Gas Pipeline Systems," Operations Research, INFORMS, vol. 18(6), pages 992-1020, December.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Samitha Samaranayake & Walid Krichene & Jack Reilly & Maria Laura Delle Monache & Paola Goatin & Alexandre Bayen, 2018. "Discrete-Time System Optimal Dynamic Traffic Assignment (SO-DTA) with Partial Control for Physical Queuing Networks," Transportation Science, INFORMS, vol. 52(4), pages 982-1001, August.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Chou, Chang-Chi & Chiang, Wen-Chu & Chen, Albert Y., 2022. "Emergency medical response in mass casualty incidents considering the traffic congestions in proximity on-site and hospital delays," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    2. Georgia Perakis & Guillaume Roels, 2006. "An Analytical Model for Traffic Delays and the Dynamic User Equilibrium Problem," Operations Research, INFORMS, vol. 54(6), pages 1151-1171, December.
    3. Kontorinaki, Maria & Spiliopoulou, Anastasia & Roncoli, Claudio & Papageorgiou, Markos, 2017. "First-order traffic flow models incorporating capacity drop: Overview and real-data validation," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 52-75.
    4. Xiaozheng He & Srinivas Peeta, 2014. "Dynamic Resource Allocation Problem for Transportation Network Evacuation," Networks and Spatial Economics, Springer, vol. 14(3), pages 505-530, December.
    5. Mohebifard, Rasool & Hajbabaie, Ali, 2019. "Optimal network-level traffic signal control: A benders decomposition-based solution algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 121(C), pages 252-274.
    6. Reilly, Jack & Martin, Sébastien & Payer, Mathias & Bayen, Alexandre M., 2016. "Creating complex congestion patterns via multi-objective optimal freeway traffic control with application to cyber-security," Transportation Research Part B: Methodological, Elsevier, vol. 91(C), pages 366-382.
    7. Lu, Chung-Cheng & Liu, Jiangtao & Qu, Yunchao & Peeta, Srinivas & Rouphail, Nagui M. & Zhou, Xuesong, 2016. "Eco-system optimal time-dependent flow assignment in a congested network," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 217-239.
    8. Ngoduy, D. & Hoang, N.H. & Vu, H.L. & Watling, D., 2016. "Optimal queue placement in dynamic system optimum solutions for single origin-destination traffic networks," Transportation Research Part B: Methodological, Elsevier, vol. 92(PB), pages 148-169.
    9. Chi Xie & Jennifer Duthie, 2015. "An Excess-Demand Dynamic Traffic Assignment Approach for Inferring Origin-Destination Trip Matrices," Networks and Spatial Economics, Springer, vol. 15(4), pages 947-979, December.
    10. Kimms, A. & Maiwald, M., 2018. "Bi-objective safe and resilient urban evacuation planning," European Journal of Operational Research, Elsevier, vol. 269(3), pages 1122-1136.
    11. Michael W. Levin, 2019. "A Combinatorial Dynamic Network Trajectory Reservation Algorithm for Connected Autonomous Vehicles," Networks and Spatial Economics, Springer, vol. 19(1), pages 27-55, March.
    12. Zhengfeng Huang & Pengjun Zheng & Gang Ren & Yang Cheng & Bin Ran, 2016. "Simultaneous optimization of evacuation route and departure time based on link-congestion mitigation," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 83(1), pages 575-599, August.
    13. Carey, Malachy & Watling, David, 2012. "Dynamic traffic assignment approximating the kinematic wave model: System optimum, marginal costs, externalities and tolls," Transportation Research Part B: Methodological, Elsevier, vol. 46(5), pages 634-648.
    14. Kachani, Soulaymane & Perakis, Georgia, 2006. "Fluid dynamics models and their applications in transportation and pricing," European Journal of Operational Research, Elsevier, vol. 170(2), pages 496-517, April.
    15. Jiancheng Long & Wai Yuen Szeto, 2019. "Link-Based System Optimum Dynamic Traffic Assignment Problems in General Networks," Operations Research, INFORMS, vol. 67(1), pages 167-182, January.
    16. Xuedong Yan & Xiaobing Liu & Yulei Song, 2018. "Optimizing evacuation efficiency under emergency with consideration of social fairness based on a cell transmission model," PLOS ONE, Public Library of Science, vol. 13(11), pages 1-21, November.
    17. Samitha Samaranayake & Walid Krichene & Jack Reilly & Maria Laura Delle Monache & Paola Goatin & Alexandre Bayen, 2018. "Discrete-Time System Optimal Dynamic Traffic Assignment (SO-DTA) with Partial Control for Physical Queuing Networks," Transportation Science, INFORMS, vol. 52(4), pages 982-1001, August.
    18. Schmitt, Marius & Lygeros, John, 2018. "An exact convex relaxation of the freeway network control problem with controlled merging junctions," Transportation Research Part B: Methodological, Elsevier, vol. 114(C), pages 1-25.
    19. Douglas Bish & Edward Chamberlayne & Hesham Rakha, 2013. "Optimizing Network Flows with Congestion-Based Flow Reductions," Networks and Spatial Economics, Springer, vol. 13(3), pages 283-306, September.
    20. Wang, Peirong (Slade) & Li, Pengfei (Taylor) & Chowdhury, Farzana R. & Zhang, Li & Zhou, Xuesong, 2020. "A mixed integer programming formulation and scalable solution algorithms for traffic control coordination across multiple intersections based on vehicle space-time trajectories," Transportation Research Part B: Methodological, Elsevier, vol. 134(C), pages 266-304.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:joptap:v:167:y:2015:i:2:d:10.1007_s10957-015-0749-1. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.