Capacitated Schedule-Based Transit Assignment Using a Capacity Penalty Cost

Persistent Link:
http://hdl.handle.net/10150/314676
Title:
Capacitated Schedule-Based Transit Assignment Using a Capacity Penalty Cost
Author:
Noh, Hyunsoo
Issue Date:
2013
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
Schedule-based transit assignment models have been studied extensively from 2000, considering more time-dependent transit passenger behavior associated with the transit schedule. Currently, transit schedule information is more easily accessed using new telecommunications systems, such as mobile devices and the internet. One critical example of information sharing is Google's General Transit Feed Specification (GTFS). The information of the schedule per se, however, is not enough to explain the transit passenger's behavior, especially in a congested transit system. Regarding the congestion issues on a transit system, numerous researches have studied a transit schedule network (Nguyen et al., 2001; Nuzzolo et al., 2001; Poon et al., 2004; Hamdouch and Lawphonpanich, 2008, 2010).Along the stream toward understanding transit passenger behavior in the capacitated transit schedule network, we propose solution models for solving the deterministic and stochastic user equilibrium (SUE) problems on a capacitated transit schedule network. Nguyen et al. (2001) introduced how the capacitated user equilibrium (UE) on a transit schedule network is different from the auto user equilibrium. For the foundation of the study, we utilize the link-based and time-expanded (LBTE) transit schedule network introduced by Noh et al. (2012a) which effectively captures turning movements like transfers easily as well as maintaining the efficient size of a schedule-based network. In the LBTE transit network, time points are assigned to each link connecting two stops by each run (or route). Utilizing the "link-based" structure, a link-based shortest path (LBSP) and hyperpath search (LBHP) models (Noh et al., 2012a) are introduced. Especially, the hyperpath employs a log-sum weighting function for incorporating multiple schedule alternatives at each stop node considering passenger's stochastic behavior. One distinctive transit passenger behavior over a congested transit system is a first-in-first-out (FIFO) priority on boarding. A passenger already on board has the higher priority than passengers who are about to boarding, and the passengers arriving earlier at a stop will have higher priority than the passengers arriving later at the stop. To consider the capacitated UE considering the relation between the FIFO boarding priority and vehicle capacity constraint, we apply a "soft-capacity" cost (Nguyen et al., 2001). This soft capacity cost function allows some violation of the predefined vehicle capacity, but the violation will be penalized and affect the cost of the path in the next iteration. The penalty of the soft capacity cost function allows not to assigning passengers on the alternatives having the lower priority of boarding, which finally leads to the solution of the capacitated transit deterministic user equilibrium (DUE) or SUE problems. For the main transit assignment models, we proposed path- and hyperpath-based methods and a self-adaptive method considering deterministic and stochastic passenger behaviors. First, we developed the hyperpath-based assignment method by Noh et al. (2012b). For the FIFO transit passenger behavior, typically accompanying asymmetric (non-separable) cost relation, we also introduce a diagonalization technique (Sheffi, 1985) with the method of successive average (MSA) assignment technique. As expecting a better performance, second, we introduced the path-based assignment models using gradient projection. For the FIFO passenger behavior on boarding, we considered the same diagonalization approach used in the hyperpath-based assignment model and a full-Hessian scaling matrix in the gradient projection. By utilizing a full path set for each O-D pair, a better performance is guaranteed with the path-based model but the diagonalization technique may result in longer iterations. For improving the diagonalization steps, third, we explored several other possible methods. Above all, we proposed the better initial solution (BIS) model which assigns the initial flows on the priority path over congested links and also maintains feasible flows below the capacity constraint. On the other hand, we also added two additional assignment models to improve the diagonalization technique. One utilizes a full Hessian scaling matrix in the proposed path-based assignment model instead of diagonalization and the other is the self-adaptive gradient projection (SAGP) model introduced by Chen et al. (2012) which does not require a scaling matrix by optimizing the step-size in the path-based projection model. For improving the SAGP model, we modified the SAGP model. First, we applied the SAGP at a disaggregate level for each O-D pair as expecting a compact set of path alternatives limited by each O-D pair, called disaggregate self-adaptive gradient projection (DSAGP). Second, we applied a type of diagonalization technique in the SAGP model by maintaining the residual capacities for the estimated flows in the next iteration. Beyond just a single model development, the proposed transit assignment models not only showed various possibilities of the transit assignment, but also showed which model is more efficient and practical in terms of a real application. A computational model structure using the proposed models was mainly designed for an effective model development by sharing numerous components as well as maintaining the efficient data structure. The nine combination models based on the proposed three main models (hyperpath- and path-based and DSAGP assignment models) and the efficient BIS technique for solving the problems were tested and analyzed on a sample network and a partial Sacramento regional transit network.
Type:
text; Electronic Dissertation
Keywords:
Path-based Assingment; Schedule-based Transit Assignment; Soft Capacity Penalty; Civil Engineering; Hyperpath-based Assignment
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Graduate College; Civil Engineering
Degree Grantor:
University of Arizona
Advisor:
Hickman, Mark D.

Full metadata record

DC FieldValue Language
dc.language.isoen_USen
dc.titleCapacitated Schedule-Based Transit Assignment Using a Capacity Penalty Costen_US
dc.creatorNoh, Hyunsooen_US
dc.contributor.authorNoh, Hyunsooen_US
dc.date.issued2013en
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractSchedule-based transit assignment models have been studied extensively from 2000, considering more time-dependent transit passenger behavior associated with the transit schedule. Currently, transit schedule information is more easily accessed using new telecommunications systems, such as mobile devices and the internet. One critical example of information sharing is Google's General Transit Feed Specification (GTFS). The information of the schedule per se, however, is not enough to explain the transit passenger's behavior, especially in a congested transit system. Regarding the congestion issues on a transit system, numerous researches have studied a transit schedule network (Nguyen et al., 2001; Nuzzolo et al., 2001; Poon et al., 2004; Hamdouch and Lawphonpanich, 2008, 2010).Along the stream toward understanding transit passenger behavior in the capacitated transit schedule network, we propose solution models for solving the deterministic and stochastic user equilibrium (SUE) problems on a capacitated transit schedule network. Nguyen et al. (2001) introduced how the capacitated user equilibrium (UE) on a transit schedule network is different from the auto user equilibrium. For the foundation of the study, we utilize the link-based and time-expanded (LBTE) transit schedule network introduced by Noh et al. (2012a) which effectively captures turning movements like transfers easily as well as maintaining the efficient size of a schedule-based network. In the LBTE transit network, time points are assigned to each link connecting two stops by each run (or route). Utilizing the "link-based" structure, a link-based shortest path (LBSP) and hyperpath search (LBHP) models (Noh et al., 2012a) are introduced. Especially, the hyperpath employs a log-sum weighting function for incorporating multiple schedule alternatives at each stop node considering passenger's stochastic behavior. One distinctive transit passenger behavior over a congested transit system is a first-in-first-out (FIFO) priority on boarding. A passenger already on board has the higher priority than passengers who are about to boarding, and the passengers arriving earlier at a stop will have higher priority than the passengers arriving later at the stop. To consider the capacitated UE considering the relation between the FIFO boarding priority and vehicle capacity constraint, we apply a "soft-capacity" cost (Nguyen et al., 2001). This soft capacity cost function allows some violation of the predefined vehicle capacity, but the violation will be penalized and affect the cost of the path in the next iteration. The penalty of the soft capacity cost function allows not to assigning passengers on the alternatives having the lower priority of boarding, which finally leads to the solution of the capacitated transit deterministic user equilibrium (DUE) or SUE problems. For the main transit assignment models, we proposed path- and hyperpath-based methods and a self-adaptive method considering deterministic and stochastic passenger behaviors. First, we developed the hyperpath-based assignment method by Noh et al. (2012b). For the FIFO transit passenger behavior, typically accompanying asymmetric (non-separable) cost relation, we also introduce a diagonalization technique (Sheffi, 1985) with the method of successive average (MSA) assignment technique. As expecting a better performance, second, we introduced the path-based assignment models using gradient projection. For the FIFO passenger behavior on boarding, we considered the same diagonalization approach used in the hyperpath-based assignment model and a full-Hessian scaling matrix in the gradient projection. By utilizing a full path set for each O-D pair, a better performance is guaranteed with the path-based model but the diagonalization technique may result in longer iterations. For improving the diagonalization steps, third, we explored several other possible methods. Above all, we proposed the better initial solution (BIS) model which assigns the initial flows on the priority path over congested links and also maintains feasible flows below the capacity constraint. On the other hand, we also added two additional assignment models to improve the diagonalization technique. One utilizes a full Hessian scaling matrix in the proposed path-based assignment model instead of diagonalization and the other is the self-adaptive gradient projection (SAGP) model introduced by Chen et al. (2012) which does not require a scaling matrix by optimizing the step-size in the path-based projection model. For improving the SAGP model, we modified the SAGP model. First, we applied the SAGP at a disaggregate level for each O-D pair as expecting a compact set of path alternatives limited by each O-D pair, called disaggregate self-adaptive gradient projection (DSAGP). Second, we applied a type of diagonalization technique in the SAGP model by maintaining the residual capacities for the estimated flows in the next iteration. Beyond just a single model development, the proposed transit assignment models not only showed various possibilities of the transit assignment, but also showed which model is more efficient and practical in terms of a real application. A computational model structure using the proposed models was mainly designed for an effective model development by sharing numerous components as well as maintaining the efficient data structure. The nine combination models based on the proposed three main models (hyperpath- and path-based and DSAGP assignment models) and the efficient BIS technique for solving the problems were tested and analyzed on a sample network and a partial Sacramento regional transit network.en_US
dc.typetexten
dc.typeElectronic Dissertationen
dc.subjectPath-based Assingmenten_US
dc.subjectSchedule-based Transit Assignmenten_US
dc.subjectSoft Capacity Penaltyen_US
dc.subjectCivil Engineeringen_US
dc.subjectHyperpath-based Assignmenten_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.disciplineCivil Engineeringen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorHickman, Mark D.en_US
dc.contributor.committeememberChiu, Yi-Changen_US
dc.contributor.committeememberMirchandani, Pituen_US
dc.contributor.committeememberHead, Kenneth L.en_US
dc.contributor.committeememberHickman, Mark D.en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.