IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v40y2006i3p179-206.html
   My bibliography  Save this article

Stochastic quasi-gradient algorithm for the off-line stochastic dynamic traffic assignment problem

Author

Listed:
  • Peeta, Srinivas
  • Zhou, Chao

Abstract

This paper proposes a stochastic quasi-gradient (SQG) based algorithm to solve the off-line stochastic dynamic traffic assignment (DTA) problem that explicitly incorporates randomness in O-D demand, as part of a hybrid DTA deployment framework for real-time operations. The problem is formulated as a stochastic programming DTA model with multiple user classes. Due to the complexities introduced by real-time traffic dynamics and system characteristics, well-behaved properties cannot be guaranteed for the resulting formulation and analytical functional forms that adequately capture traffic realism typically do not exist for the associated objective functions. Hence, a simulation-based SQG method that is applicable for a generalized differentiable (locally Lipschitz) non-convex objective function and non-convex constraint set is proposed to solve the problem. Simulation is used to estimate quasi-gradients that are stochastic to incorporate demand randomness. The solution approach is a generalization of the deterministic DTA solution methodology; under it, deterministic DTA models are special cases. Of practical significance, it provides a robust solution for the field deployment of DTA, or an initial solution for hybrid real-time strategies. The solution algorithm searches a larger feasible domain of the solution space, leading to a potentially more robust and computationally more efficient solution than its deterministic counterparts. These advantages are highlighted through simulation experiments.

Suggested Citation

  • Peeta, Srinivas & Zhou, Chao, 2006. "Stochastic quasi-gradient algorithm for the off-line stochastic dynamic traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 40(3), pages 179-206, March.
  • Handle: RePEc:eee:transb:v:40:y:2006:i:3:p:179-206
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191-2615(05)00041-X
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Patrick Jaillet, 1988. "A Priori Solution of a Traveling Salesman Problem in Which a Random Subset of the Customers Are Visited," Operations Research, INFORMS, vol. 36(6), pages 929-936, December.
    2. Yannis Pavlis & Markos Papageorgiou, 1999. "Simple Decentralized Feedback Strategies for Route Guidance in Traffic Networks," Transportation Science, INFORMS, vol. 33(3), pages 264-278, August.
    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. Sumalee, A. & Zhong, R.X. & Pan, T.L. & Szeto, W.Y., 2011. "Stochastic cell transmission model (SCTM): A stochastic dynamic traffic model for traffic state surveillance and assignment," Transportation Research Part B: Methodological, Elsevier, vol. 45(3), pages 507-533, March.
    2. 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.
    3. Laval, Jorge A., 2009. "Graphical solution and continuum approximation for the single destination dynamic user equilibrium problem," Transportation Research Part B: Methodological, Elsevier, vol. 43(1), pages 108-118, January.

    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. Bertsimas, Dimitris & Van Ryzin, Garrett., 1989. "The dynamic traveling repairman problem," Working papers 3036-89., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    2. Mathias A. Klapp & Alan L. Erera & Alejandro Toriello, 2018. "The One-Dimensional Dynamic Dispatch Waves Problem," Transportation Science, INFORMS, vol. 52(2), pages 402-415, March.
    3. Luca Quadrifoglio & Randolph W. Hall & Maged M. Dessouky, 2006. "Performance and Design of Mobility Allowance Shuttle Transit Services: Bounds on the Maximum Longitudinal Velocity," Transportation Science, INFORMS, vol. 40(3), pages 351-363, August.
    4. Ji, Chenlu & Mandania, Rupal & Liu, Jiyin & Liret, Anne, 2022. "Scheduling on-site service deliveries to minimise the risk of missing appointment times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    5. Wang, Zutong & Guo, Jiansheng & Zheng, Mingfa & Wang, Ying, 2015. "Uncertain multiobjective traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 241(2), pages 478-489.
    6. Roberto Tadei & Guido Perboli & Francesca Perfetti, 2017. "The multi-path Traveling Salesman Problem with stochastic travel costs," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(1), pages 3-23, March.
    7. Hall, Randolph W., 1992. "Pickup and Delivery Systems For Overnight Carriers," University of California Transportation Center, Working Papers qt5j97q5xc, University of California Transportation Center.
    8. Pi, Xidong & Qian, Zhen (Sean), 2017. "A stochastic optimal control approach for real-time traffic routing considering demand uncertainties and travelers’ choice heterogeneity," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 710-732.
    9. Ripplinger, David, 2005. "The Stochastic School Transportation Problem," 46th Annual Transportation Research Forum, Washington, D.C., March 6-8, 2005 208214, Transportation Research Forum.
    10. Edward Kim, M. & Schonfeld, Paul & Roche, Austin & Raleigh, Chelsie, 2022. "Optimal service zones and frequencies for flexible-route freight deliveries," Transportation Research Part A: Policy and Practice, Elsevier, vol. 159(C), pages 182-199.
    11. Barrett W. Thomas & Chelsea C. White, 2004. "Anticipatory Route Selection," Transportation Science, INFORMS, vol. 38(4), pages 473-487, November.
    12. Jabali, Ola & Gendreau, Michel & Laporte, Gilbert, 2012. "A continuous approximation model for the fleet composition problem," Transportation Research Part B: Methodological, Elsevier, vol. 46(10), pages 1591-1606.
    13. Dinopoulou, Vaya & Diakaki, Christina & Papageorgiou, Markos, 2006. "Applications of the urban traffic control strategy TUC," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1652-1665, December.
    14. Albareda-Sambola, Maria & Fernandez, Elena & Laporte, Gilbert, 2007. "Heuristic and lower bound for a stochastic location-routing problem," European Journal of Operational Research, Elsevier, vol. 179(3), pages 940-955, June.
    15. Ann M. Campbell & Barrett W. Thomas, 2008. "Probabilistic Traveling Salesman Problem with Deadlines," Transportation Science, INFORMS, vol. 42(1), pages 1-21, February.
    16. Pages, Laia & Jayakrishnan, R. & Cortes, Cristian E., 2005. "Real-Time Mass Passenger Transport Network Optimization Problems," University of California Transportation Center, Working Papers qt7w88d089, University of California Transportation Center.
    17. Bergmann, Felix M. & Wagner, Stephan M. & Winkenbach, Matthias, 2020. "Integrating first-mile pickup and last-mile delivery on shared vehicle routes for efficient urban e-commerce distribution," Transportation Research Part B: Methodological, Elsevier, vol. 131(C), pages 26-62.
    18. Bertsimas, Dimitris & Van Ryzin, Garrett., 1991. "A stochastic and dynamic vehicle routing problem in the Euclidean plane," Working papers 3286-91., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    19. Soumia Ichoua & Michel Gendreau & Jean-Yves Potvin, 2006. "Exploiting Knowledge About Future Demands for Real-Time Vehicle Dispatching," Transportation Science, INFORMS, vol. 40(2), pages 211-225, May.
    20. Srimathy Mohan & Michel Gendreau & Jean-Marc Rousseau, 2008. "The Stochastic Eulerian Tour Problem," Transportation Science, INFORMS, vol. 42(2), pages 166-174, May.

    More about this item

    Statistics

    Access and download statistics

    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:eee:transb:v:40:y:2006:i:3:p:179-206. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

    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.