ABSTRACT
Title of dissertation: DESIGN AND ANALYSIS OF
VEHICLE SHARING PROGRAMS:
A SYSTEMS APPROACH
Rahul Nair, Doctor of Philosophy, 2010
Dissertation directed by: Professor Elise Miller-Hooks
Department of Civil &
Environmental Engineering
Transit, touted as a solution to urban mobility problems, cannot match the
addictive flexibility of the automobile. 86% of all trips in the U.S. are in personal
vehicles. A more recent approach to reduce automobile dependence is through the
use of Vehicle Sharing Programs (VSPs). A VSP involves a fleet of vehicles located
strategically at stations across the transportation network. In its most flexible form,
users are free to check out vehicles at any station and return the vehicle at a station
close to their destination. Vehicle fleets are comprised of bicycles, cars or electric
vehicles. Such systems o?er innovative solutions to the larger mobility problem
and can have positive impacts on the transportation system as a whole by reduc-
ing urban congestion. This dissertation employs a network modeling framework
to quantitatively facilitate design and operate VSPs. At the strategic level, the
problem of determining the optimal VSP configuration is studied. A bilevel opti-
mization model and associated solution methods are developed and implemented
for a large-scale case study in Washington D.C. The model explicitly considers the
intermodalism, and views the VSP as a ?last-mile? connection of an existing transit
network. At the operational level, by transferring control of vehicles to the user
for improved system flexibility, exceptional logistical challenges are placed on oper-
ators who must ensure adequate vehicle stock (and parking slots) at each station
to service all demand. Since demand in the short-term can be asymmetric (flow
from one station to another is seldom equal to flow in the opposing direction),
service providers need to redistribute vehicles to correct this imbalance. A chance-
constrained program is developed that generates least-cost redistribution plans such
that most demand in the near future is met. Since the program has a non-convex
feasible region, two methods for its solution are developed. The model is applied
to a real-world car-sharing system in Singapore where the value of accounting for
inherent stochasticities is demonstrated. The framework is used to characterize the
e?ciency of V?elib?, a large-scale bicycle sharing system in Paris, France.
DESIGN AND ANALYSIS OF VEHICLE SHARING
PROGRAMS: A SYSTEMS APPROACH
by
Rahul Nair
Dissertation submitted to the Faculty of the Graduate School of the
University of Maryland, College Park in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy
2010
Advisory Committee:
Professor Elise Miller-Hooks, Chair/Advisor
Professor Kelly J. Clifton
Professor Chengri Ding
Professor Steven A. Gabriel
Professor Hani S. Mahmassani
Professor Lei Zhang
c? Copyright by
Rahul Nair
2010
Acknowledgments
Much is owed to many who made this thesis possible. My deepest gratitude
is to my advisor, Dr. Elise Miller-Hooks. Her mentorship, support, and encourage-
ment has enriched my graduate experience beyond measure. Working with her has
provided exceptional opportunities to learn, teach, travel, and research interesting
areas of our field. Her openness to new ideas, strong work ethic, attention to detail,
and promptness have helped me develop from my more chaotic beginnings.
I would like to thank Prof. Hani Mahmassani at Northwestern University,
for being a constant source of intellectual inspiration and for exposing me to many
facets of transportation. I thank Dr. Steve Gabriel for his courses on stochastic
programming and equilibrium modeling techniques that form the basis for much
of this work. Additionally, I thank him for reviewing preliminary versions of the
presented work, and for providing thorough and constructive suggestions to move
forward. I would like to thank Dr. Kelly Clifton at Portland State University, Dr.
Zhang and Dr. Ding at the University of Maryland for being a part of my thesis
committee.
The idea for studying shared-vehicle systems stem from my involvement with
the Bicycle Advisory Group (BAG) at the University of Maryland. I am very grateful
to Dr. Gulsah Akar for getting me involved. I am also grateful to the Transporta-
tion Research Board committee on Emerging and Innovative Public Transport and
Technologies (AP020) for the opportunity to meet several researchers that lead to
all the presented case studies. In particular, I would like to thank Jim Sebastian,
Chris Holben, and Anna McLaughlin from the District Department of Transportion
ii
(DDOT), James Graham from the District O?ce of Planning, Dr. Fred Ducca and
Dr. Xin Ye from the Center for Smart Growth, for facilitating the Washington D.C.
case study. I would like to thank Dr. Ruey (Kelvin) Cheu, from the University of
Texas at El Paso, for graciously sharing data on the Singapore car-sharing system.
I would like to thank Dr. Robert Hampshire from Carnegie Mellon University for
sharing data and collaborating on the Paris bike-sharing case study.
I would not be at this juncture without the sacrifices my parents, Kunhikr-
ishnan and Premalatha Nair, have made to ensure that I have a good education.
The constant support and encouragement that I have had from them is something I
deeply value. Thanks to my brother Rohit for all the memorable moments. Finally,
thanks to my beloved Amrita who has shared this journey with me and without
whose endearing support this would not have been possible.
iii
Table of Contents
List of Tables vi
List of Figures vii
1TheThesis 1
1.1 Motivation and Background ....................... 3
1.2 Research Objectives ............................ 7
1.3 Specific Problems Addressed ....................... 9
1.3.1 Strategic Level: Equilibrium Network Design .......... 9
1.3.2 Operational Level: Fleet Management ............. 10
1.3.3 Case Studies ............................ 11
1.4 Contributions ............................... 11
1.5 Dissertation Outline ........................... 13
2SystemDesign 14
2.1 Introduction ................................ 14
2.2 Formulation ................................ 18
2.2.1 Supply Processes ......................... 19
2.2.2 Demand Processes ........................ 21
2.2.3 Model Development ........................ 22
2.3 Solution Algorithm ............................ 28
2.3.1 An Exact Solution Approach ................... 29
2.3.1.1 KKT Conditions for Lower Level ........... 29
2.3.1.2 Dealing with Complementarity ............ 32
2.4 Experimental Results ........................... 34
2.5 Conclusions ................................ 37
3 Operational Models 41
3.1 Introduction ................................ 41
3.2 Problem Formulation ........................... 44
3.3 Solving Program CCM-p ......................... 50
3.3.1 Solution based on PEP Enumeration .............. 53
3.3.1.1 A Divide-and-Conquer PEP Enumeration Algorithm 55
3.3.1.2 Reducing Computational E?ort ............ 60
3.3.2 A Cone Generation Method ................... 62
3.4 A Failure Apportionment Bound ..................... 65
3.5 Application ................................ 66
3.5.1 Computational Experiments ................... 70
3.6 Conclusions ................................ 77
iv
4 System Design For Washington D.C. 83
4.1 Introduction ................................ 83
4.1.1 Setting ............................... 85
4.1.2 Model Components ........................ 87
4.1.2.1 VSP Candidate Stations ................ 88
4.1.2.2 Travel Demand ..................... 89
4.1.2.3 Transit Network .................... 91
4.1.2.4 Walk and Bicycle Network ............... 91
4.2 Formulation ................................ 92
4.3 Genetic Algorithm Based Solution Method ............... 96
4.3.1 Solution Representation ..................... 97
4.3.2 Initialization ............................ 98
4.3.3 Evaluation ............................. 98
4.3.4 Evolution ............................. 99
4.3.5 Termination Criteria .......................100
4.4 Analysis ..................................101
4.5 Conclusions ................................108
5 V?elib? Case Study 110
5.1 Setting ...................................110
5.2 System Characteristics ..........................113
5.2.1 Transit-V?elib? Interaction ....................114
5.2.2 Flow Asymmetry at Stations ...................117
5.3 Fleet Management ............................120
5.3.1 Probabilistic Characterization of Demand ...........123
5.3.2 Framework ............................125
5.4 Analysis ..................................128
5.5 Conclusions ................................129
6 Conclusions 133
6.1 Benefits to Society ............................134
6.2 Extensions .................................135
References 137
v
List of Tables
2.1 Results for Instance24 (24 nodes ? 129 links) ............. 36
2.2 Results for Instance35 (35 nodes ? 200 links) ............. 36
2.3 Results for Instance46 (46 nodes ? 221 links) ............. 37
2.4 Results for Instance50 (50 nodes ? 263 links) ............. 39
2.5 Results for Instance64 (64 nodes ? 365 links) ............. 40
3.1 Number of PEPs for each stage (in millions) .............. 71
3.2 Summary of 100,000 simulation runs for Day 1 ............. 75
3.3 Summary of 100,000 simulation runs for Day 2 ............. 76
3.4 Systemwide resource needs ........................ 77
4.1 Summary of network component for Washington D.C. .........102
4.2 Number of VSP stations by ward ....................106
5.1 Top 20 V?elib? stations with highest inflows ...............117
5.2 Top 20 V?elib? stations with highest outflows ..............119
5.3 Summary of V?elib? simulation results ..................131
vi
List of Figures
1.1 A unimodal view of transport ...................... 5
2.1 Hierarchical transit-VSP network .................... 15
2.2 Network configuration .......................... 20
2.3 Random transit networks tested ..................... 35
2.4 Flow patterns and VSP configuration for 46 node instance ...... 38
3.1 Illustration of PEP definitions for a single dimension ......... 56
3.2 Three cases for arbitrary hyper-rectangles in 2-dimensions ...... 58
3.3 Demand scenarios covered by the chance constraint at one station .. 66
3.4 Characteristics of the IVCS Singapore system ............. 68
3.5 Trip characteristics ............................ 68
3.6 Relative inter and intra station flows .................. 69
3.7 Actual and theoretical demand distributions for two Stations ..... 80
3.8 The Skellam distribution function for sample ? combinations. .... 80
3.9 Average actualized reliabilty vs. relocation costs over entire day ... 80
3.10 System snapshots for various time periods (Day 1) ........... 81
3.11 Number of vehicles relocated ....................... 82
4.1 Social characteristics of Washington D.C. ................ 85
4.2 Urban characteristics of Washington D.C. ............... 86
4.3 Access modes of passengers to metro stations .............. 87
4.4 Candidate VSP stations with ward boundaries ............. 89
4.5 Best solution at each generation of GA .................102
4.6 Recommended VSP Configuration ....................104
4.7 Transit-based flows without VSP ....................105
4.8 Average travel time reduction in minutes ................106
4.9 Flow potential between designed stations ................107
5.1 Spatial distribution of V?elib? stations ..................114
5.2 Temporal distribution of trips ......................115
5.3 Cumulative distribution of travel characteristics ............115
5.4 Distribution of distances from V?elib? stations to closest transit stops . 116
5.5 Average inter-station flows ........................118
5.6 Flows to and from Les Halles V?elib? station ..............121
5.7 Theoretical demand distribution for selected V?elib? stations ......126
5.8 Component reliability p
i
for selected stations ..............129
5.9 Stations with persistent shortages ....................130
vii
Chapter 1: The Thesis
Vehicle sharing programs (VSPs) have been gaining ground around the world
for providing an environment-friendly, socially responsible and economical mode of
transport. These programs involve a fleet of vehicles positioned strategically at
stations across the transportation network. In its most flexible form, users are free
to lease a vehicle to complete a trip and drop the vehicle at a station close to their
destination. The shared vehicle fleet can be comprised of cars, electric vehicles or
bicycles. Such systems o?er innovative solutions to the larger mobility problem
and can have positive impacts on the transportation system as a whole by a?ecting
modal choice. They do so in multiple ways. For short trips, these systems can be
construed as an alternate mode of transport. Users enrolled in sharing programs
have been shown to undertake fewer trips [46]. When viewed in conjunction with
transit networks, a VSP can serve to increase transit use.
Compared to the automobile, transit services in the United States (US) do not
enjoy high levels of patronage, in part due to low accessibility, and lack of flexibility
and convenience. The US has also been behind the trend in transit adoption when
compared with other industrialized countries. VSPs have the potential to improve
the accessibility of a public transit system by o?ering a competitive ?last mile? con-
nection, the lack of which dissuades potential transit riders. The e?ective catchment
area of a transit line is increased by providing a vital leg of an intermodal route. By
transferring control of vehicles to the user, the system becomes vastly more flexible,
o?ering more choices with regard to departure time, destinations and transit routes.
1
These projected improvements can serve to attract new transit ridership.
Vehicle sharing arose from social experiments in sustainable transportation
and now finds willing private participants (even a company like Exxon Mobil has
a pilot project in Baltimore City called AltCar [25]). Public agencies positioned to
leverage this increased interest from the private sector profit, because this form of
transportation provides net social benefit. The predominant revenue source for car
and electric vehicle programs are from customer usage fees, while advertising rev-
enue supports bicycle sharing programs. As opposed to central, structured, resource-
intensive solutions that are typically employed to alleviate congestion, proponents
of vehicle sharing schemes claim it o?ers a distributed, unstructured, sustainable,
and economical solution. In essence, VSPs provide a market opportunity for private
entities that aid in achieving public goals of a?ecting a modal shift from road to
transit. To maximize transit mode share, a public-private partnership can be forged
that shares the same objective of increased ridership. Several design decisions are
critical for the success of such systems (e.g. pricing, station locations, fleet com-
position and size). Determining the optimal system configuration is vital to their
success.
This dissertation formulates models and develops associated solution algo-
rithms that quantitatively facilitate design, assessment, and operation of vehicle
sharing systems based on probabilistic information on demand, modal preferences,
and the existing transit system configuration. A network modeling framework is
employed as a basis to support the formulation and analysis.
The principle components of the research include the following. The key de-
2
mand and supply processes, and their interaction, are characterized. The VSP
design is approached from the perspective of intermodalism, whereby the existing
transit network is viewed as the backbone with VSPs serving as a ?last-mile? con-
nection. Fleet management strategies for system operators are devised that account
for the stochastic nature of demand. The tradeo?s between level-of-service and op-
erating costs are examined within the context of a specific strategy. Critical design
parameters are evaluated for real-world systems under a wide range of scenarios to
assess performance.
1.1 Motivation and Background
Transit, touted as a solution to urban mobility problems, cannot match the
addictive flexibility of the automobile. 86.5% of all trips in the U.S. are in personal
vehicles [55]. Public transit does not compare favorably when attributes that influ-
ence mode choice (travel times, costs, accessibility, convenience and flexibility) are
considered and accounts for just 1.5% of all trips and 4.7% of all commute trips.
Additionally, the majority of federal investment in transportation infrastructure is
used for capital improvements to existing highways. Despite the increasing disutility
of automobiles (worsening congestion, price of gasoline and the supply of infrastruc-
ture that has been outpaced by demand), transit continues to be underappreciated
as a viable alternative [52].
Transit is e?cient and o?ers low negative socio-environmental external costs
(defined as the collective adverse impact of transport not borne by the user, e.g. pol-
3
lution) [20]. Planners have strived to improve transit patronage through measures
that increase transit utility by alleviating its shortcomings. To increase accessibility,
transit is integrated with other modes, such as cars (in the form of park-and-ride),
bicycles [54], and other slow mode connections [42, 47]. The emphasis on the inter-
face of transit to other modes has been demonstrated to increase catchment areas
of transit lines and provide viable intermodal solutions.
A more recent approach to reduce automobile dependence is through the use
of VSPs. For a user, a shared vehicle reduces cost of ownership minimally impacting
flexibility. Vehicles, viewed as a resource, spend most of their time idle and depreci-
ating in value. More e?cient use of this resource implies lower costs. Shared vehicle
fleets o?er a mechanism for exploiting this down-time. In addition to cost benefits
to individual users, there are system-wide benefits from a decrease in motor vehi-
cles in the system (recent European study estimates one shared vehicle leads to a
reduction of between four and 10 privately owned cars; estimates for North America
range from six to 23 cars [45]). These programs typically have pricing structures
that charge based on usage, which has been shown to reduce travel amongst partic-
ipants [46]. In essence, a smaller fleet of vehicles o?ers a comparable level of service
to users as vehicle ownership, and provides system-wide benefits.
Users around the world have found VSPs to be profitable. As of 2007, car
sharing programs exist in 600 cities around the world [45], and bicycle sharing
programs in 102 cities [12]. By membership, North America accounts for 35% of
car sharing programs worldwide. V?elib?, the bicycle sharing program in Paris, has
20,600 bicycles spread over 1,450 stations across the city with an average of 120,000
4
trips daily [21].
VSPs build on para-transit concepts of on-demand ?peer-to-peer? transport
with flexible routes and no schedules. The principle di?erence is that VSPs transfer
control of vehicles to users. Para-transit aims, as articulated in [30], to be an
intermediate solution between the flexibility of automobiles and the rigidness of
transit. A unimodal view of paratransit is espoused by Kirby [30]asshowninFigure
1.1, where the appeal of di?erent modes is limited to specific distance windows.
When the true intermodal nature of transport is considered, these limitations are
not insurmountable. These limitations depend solely on the ease with which users
can interface between di?erent modes.
Figure 1.1: A Unimodal View of Urban Transport, adapted from [30]
The weak enthusiam for transit and other non-automobile based modes is
partly a result of an auto-centric culture. The true cost of automotive travel is not
borne by drivers. Several cost components can be shown to be e?ectively subsidized.
One example is parking, where business owners are forced to o?er subsidized (or free)
parking to lure customers, recuperating the costs through higher commodity prices
5
[57]. These factors make the transport market an uneven playing field. With fewer
resources, transit operators are expected to match the level-of-service of automobiles.
VSPs o?er a mechanism for private players to participate in aiding public goals of
modal shift. As on-demand feeder services, VSPs can help realize the economies of
scale that transit o?ers.
Earlier generations of VSPs, mainly bicycles, were plagued by theft and van-
dalism. VSP operators now have substantial Information Technology (IT) infras-
tructure for various functions, including tracking of vehicles for theft prevention,
smart cards for member access, vehicle availability across the network, charging
consoles for electric vehicles, payment systems, and online traveler information ser-
vices. This data-rich environment provides a real-time awareness of the system that
can be leveraged for better fleet management. These technologies, taken together,
have proven to be a great enabler. System managers have real-time information
on the location of the fleet, and users can be made more accountable (though the
V?elib? in Paris reports losing 3,000 bicycles annually, or around 15% of its fleet).
This reliance on real-time information lends the system to data-intensive operations
research methods to provide decision support. Thus, technology is a key driver of
current innovations.
The literature on VSPs is dominated by qualitative demand-side studies that
predominately aim at market potential and feasibility aspects of the system. These
studies are discussed in relevant chapters. The supply side of the equation relating
to design and operations has by contrast received very limited attention. The tools
developed herein address this gap in the literature. From a theoretical perspective,
6
the relevance of this research is in analyzing innovative transport solutions that fall
outside the traditional realms. From a societal perspective, as urban communities
grapple with finding ways to provide e?cient, sustainable mobility to their populace,
the developed tools provide a quantitative framework for the analysis of one strategy,
namely the shared-vehicle program.
1.2 Research Objectives
Driven by the gap in literature, unique challenges associated with VSPs, the
need for sustainable urban mobility solutions, and the increased interest in VSPs
across the world, this research has the following objectives.
Address vital strategic network design needs of VSP operators. The research
seeks to determine the optimal VSP configuration. Two distinct perspectives under-
line the model development. From the perspective of users seeking to optimize travel
itineraries, the sharing program must o?er value-added service, either as a mode or
by making transit more attractive by serving as a ?last-mile? connection. From the
perspective of VSP service providers who benefit from increased usage, resources
are directed to areas with a critical mass of users that warrant the investment.
Develop operational strategies for VSPs. From an operational standpoint, the
operator reliquishes control of vehicles to users (who decide where to check out
vehicles, how long to use them, and where they are returned). This makes the
system highly uncertain and places exceptional logistical challenges on operators.
This research seeks to answer the following key questions. (1) Given the uncertainty
7
of user demand, what operational strategies ensure adequate levels-of-service? (2)
What fleet management strategies can minimize cost to operators?
Develop a network-based conceptual framework for VSP strategic design and
operations. Mathematical models for the identified problems are formulated that
account for inherent uncertainty, multiple stakeholder objectives, and equilibrium
conditions, and explicitly model intermodalism. The models yield (1) the optimal
VSP configuration (locations of stations, vehicle inventory, and station sizes), and
(2) operational fleet management plans that aid in maintaining desired level-of-
service at minimal cost to operators.
Develop exact and heuristic solution approaches for identified problems. The
developed bilevel and chance-constrained programming models are computationally
challenging to solve. Several exact algorithmic approaches and a meta-heuristic
scheme are developed for their solution.
Demonstrate applicability of developed models and solution algorithms to real-
world instances. The developed methodologies are implemented for several real-
world case studies and on synthetic networks to demonstrate the value of a network
optimization based approach to analyze VSPs. The strategic network design model
is implemented for a large-scale model in Washington D.C. and several synthetic net-
works. The operational model is implemented for a car-sharing system in Singapore,
and a bike-sharing system in Paris.
8
1.3 Specific Problems Addressed
1.3.1 Strategic Level: Equilibrium Network Design
Taking the perspective of a VSP service provider working with a public transit
agency to increase transit mode share, the primary aim of this work is to determine
optimal configuration of VSP resources (in terms of where to locate stations, the
size of stations, and the vehicle fleet) to increase transit share. To quantify the
e?ects of VSPs, a network representation of the system and models of underlying
processes that govern mobility within the system are conceptualized. The principle
components of this framework, models of the demand-side process, and supply of
transport (links, modes and interfaces) are developed. Since response of potential
users to innovative transport solutions is inherently uncertain, simple quantative
measures are used to depict preferences of system users.
A bilevel, mixed-integer, equilibrium network design model is developed to
determine the optimal VSP system configuration. The model uses a leader-follower
framework to consider the di?ering objectives. Within this framework, the VSP
operator (leader) provides the system configuration that users (followers) utilize to
improve their travel utilities. In the overall network modeling framework, the pres-
ence of a sharing program alters the supply conditions and, therefore, demand for the
service is revised. This supply-demand interaction iteratively equilibrates to a VSP
design that supports the estimated demand based on the o?ered level-of-service.
The optimal VSP configuration, therefore, represents a supply-demand equilibrium,
where the VSP configuration (supply) supports its utilization (demand). The de-
9
sign of a VSP pertains to location and size of stations and estimation of resource
requirements to achieve target level-of-service.
Bilevel programs, in general are computationally challenging to solve due to a
non-convex feasible region. An exact technique is proposed that uses the Karush-
Kuhn Tucker conditions of the lower-level to transform the problem to a generalized
linear complementarity problem. Using additional transformations, the program
is converted to a mixed-integer program that is more readily solvable by existing
optimization suites.
1.3.2 Operational Level: Fleet Management
Operational fleet management strategies under demand uncertainty are de-
veloped. Specifically, a mixed-integer, chance-constrained, stochastic program for
anticipative fleet redistribution in VSPs is formulated that generates least-cost fleet
plans such that most near-term demand is met. By transferring control of vehicles to
the user, exceptional logistical challenges are placed on operators who must ensure
adequate vehicle stock (and parking slots) at each station to service all demand.
Since demand in the short-term can be asymmetric (flow from one station to an-
other is seldom equal to flow in the opposing direction), service providers need to
redistribute vehicles to correct this imbalance. The developed model accounts for
demand uncertainty and generates partial redistribution plans when resources are
insu?cient.
Chance-constrained programs are di?cult to solve due to a non-convex feasible
10
region. Two exact solution techniques are developed that exploit the discrete-valued
nature of demand using the theory of p-e?cient points. A equal failure apportion-
ment bound is also presented.
1.3.3 Case Studies
The strategic and operational models are implemented for several synthetic
networks and three real-world case studies. The strategic network design model is
employed to aid the District of Columbia (D.C.) Department of Transportation in
expanding their bicycle sharing program. The operational model is employed on
a carsharing system in Singapore. A framework used for the operational model is
used to characterize V?elib?, a large-scale bicycle sharing system in Paris. These real-
world case studies demonstrate the applicability of developed models and methods
to real-world instances.
1.4 Contributions
This thesis makes the following contributions to the literature on sustainable
transportation solutions for urban mobility problems.
At the strategic level, a network modeling framework for the discrete equi-
librium network design problem is formulated as a mixed-integer bilevel program.
This framework explicitly considers the modal interface of VSPs with other modes.
Bilevel programs are intractable and their solution presents a significant computa-
tional hurdle. An exact solution approach is developed that exploits the convex-
11
ity of the lower level. The Karush-Kuhn Tucker conditions are used to transform
the bilevel program into an mathematical program with equilibrium constraints
(MPEC). Using an additional transformation, the MPEC is transformed to a mixed-
integer linear program that can be readily solved through the application of o?-the-
shelf optimization suites such as CPLEX. This exact solution approach is tested
on several synthetic networks. A metaheuristic approach using concepts of genetic
algorithm is developed for large networks and is applied to aid the D.C. Department
of Transportation in designing their bicycle sharing program expansion.
At the operational level, a chance-constrained stochastic program to generate
fleet management strategies is developed. When resources are insu?cient, the pro-
gram recovers partial redistribution plans that utilize the available resources in the
most e?cient manner. Two solution algorithms are developed for exact solution of
the problem. The first method solves multiple MIPs for special realizations of the
random vector called p-e?cient points (PEP). This method relies on the enumeration
of PEPs where a novel divide-and-conquer PEP generation is presented, a contri-
bution that transcends the current application. A second cone generation method
employs concepts from the column generation approach in linear programming to
probabilistically constrained programs. The method uses a slave optimization model
to determine promising PEPs to consider in the master problem.
Three large-scale, real-world case studies are implemented for the proposed
models to demonstrate the e?cacy and applicability of the conducted research. The
strategic network design model is implemented for a new bike-sharing system in
Washington, D.C. The model outputs a near-optimal VSP configuration, quanti-
12
fying the flows between stations and the improvement in transit accessibility for
various neighborhoods within the District. The forecast inter-station flows and ef-
fects on transit accessibility are measures that have not been previously studied in
the context of VSPs and they are studied herein.
The operational model is implemented for a car-sharing system in Singapore,
and the framework used to analyze a bicycle sharing system in Paris. A simulation
framework is developed for the analysis of various redistribution plans. The benefit
of accounting for inherent uncertainty (?value of stochastic solution?) is demonstrated
by a comparative analysis with static methods.
1.5 Dissertation Outline
Chapter 2 describes the strategic equilibrium discrete network design problem.
Chapter 3 presents the fleet management models and the case study for the Singa-
pore carsharing system. Chapter 4 documents the design of a bicycle sharing system
for Washington, D.C. Chapter 5 presents the application of the fleet management
model to characterize a large-scale bicycle sharing system in Paris. The research
conclusions are summarized in Chapter 6.
13
Chapter 2: System Design
2.1 Introduction
Since established transport solutions are unsustainable, changes in the way
transport is supplied and consumed are imminent. Planners have long embraced
the idea that transit will solve urban mobility woes. However, data on users travel
choices shows transit to be a losing proposition [55]. Transit simply cannot match the
flexibility of the automobile. In recent years, shared-vehicle systems have garnered
the interest of urban communities as an integral component in the basket of mobility
solutions for the future.
The focus of this chapter is on the design of flexible shared-vehicle systems
that allow users to check out vehicles (bicycles, electric vehicles, or cars) close to
their origins and drop them o? at VSP stations near their destinations. The system
is envisioned to be utilized in two ways. For short trips, the shared-vehicles serve
as an individual modal alternative. For longer trips, they serve as a vital leg of
an intermodal route. In the latter case, VSPs increase travel utility by improving
flexibility, o?ering greater departure time choice, and increasing transit accessibility.
The existing transit network is viewed as the backbone of a hierarchical network,
with the shared-vehicle system serving as a feeder system (see Figure 2.1). When
viewed in conjunction with transit networks, shared-vehicle systems o?er a compet-
itive ?last-mile? connection, the lack of which dissuades potential riders.
For the purposes of this chapter, the term ?VSP operator? is designated as
14
Figure 2.1: Hierarchical transit-VSP network
the entity responsible for designing the VSP system. In practice, the organizational
structure behind the design and operation of VSPs varies considerably for di?erent
cities. The primary stakeholders involved with the design tasks can include public
transportation agencies, public transit authorites, non-profit organizations, private
for-profit companies, and advertising companies. Local transportation agencies typ-
ically initiate the process by developing operating standards. These standards can
pertain to location of VSP stations, shared-vehicle inventories, integration of pay-
ment systems, and desired level-of-service. The agency may then work with external
service providers (non-profit entities, commercial providers, advertising agencies) to
build out the system and operate it. These external service providers are paid
through revenue-sharing agreements with the city or through other means, such as
advertising rights at VSP stations and vehicles. Another business model involves
private companies solely determining the configuration of the system, choosing to
provide services where they may be most utilized. Given the myriad forms in which
the organizational roles can be structured, the VSP operator can therefore be either
15
a public agency, or a private participator.
VSP operators want to decide (1) where to locate stations, (2) how many slots
to locate, and (3) how many vehicles to place at each station. In this chapter, a
bilevel programming model is developed that optimally determines a VSP configu-
ration. The model recognizes the operator?s lack of control over the utilization of
the system, since the usage of the VSP is driven by myopic decisions on the part of
patrons who seek to maximize their travel utility. The framework also incorporates
the intermodal nature of transport and links the shared-vehicle system to existing
transit. At the upper level, the VSP operator determines the optimal configuration
of the system (supply). At the lower level, users respond to the VSP configuration
and optimize their personal itineraries (demand). The VSP operator in turn adjusts
the VSP configuration to maximize ridership. At equilibrium, the optimal configu-
ration is one that supports travellers who derive utility from using the shared-vehicle
to complete trips. Since bilevel programs are computationally challenging to solve,
two solution approaches, one exact and the other heuristic, are developed. The ex-
act technique exploits the convex nature of the lower level problem to derive a large
mixed-integer program (MIP) that can be solved using existing MIP solvers. The
second meta-heuristic based approach that is developed is suitable for the solution
of large instances, as would arise in the real-world. It is presented in Chapter 4.
The literature on design of shared-vehicle systems is very limited. Many stud-
ies focus on the qualitative characteristics that aim at determining the feasibility of
such systems [23, 53] and the market potential based on surveys and demographic
information [28, 46]. Awasthi et al. [3, 4] present a multicriteria decision mak-
16
ing tool based on the analytic hierarchy process (AHP). Their framework relies on
experts ranking stations based on various criterion, including landuse, population
density, vehicle ownership, transit access, and presence of target groups. Another
pertinent aspect of the literature is the integration of transit with other modes for
improving mobility. Several works have studied the role of ?feeder? modes to transit
lines [42, 50, 48, 47, 54]. The main focus of these studies have been in integrating
bicycles and other slow modes with transit to provide better accessibility. From
a conceptual standpoint, the developed model is strongly aligned with the access
network design problem, which arises in other sectors, such as telecommunications
[5, 11], computer networks [37], and capacity expansion problems in various in-
dustries. These previous studies are tailored to problems where the same entity
allocates the resources and then determines how it is utilized. In the case of VSPs,
however, the operator who designs the network has little control over the fleet of
vehicles. Users independently decide where to check out vehicles, the duration of
the trip, and where to return them. The control of the resource e?ectively rests
in the hands of users. This important distinction precludes the use of previously
proposed models and warrants the development of problem specific tools.
It appears that no previous work has studied the design of shared-vehicle sys-
tems from a quantitative, network-based approach. The main contribution of this
work is developing a quantitative framework for designing a shared-vehicle system
that works in conjunction with existing transit services and infrastructure. While
the high level of flexibility of VSPs is a boon for users, operators often rely on quali-
tative information to decide on the best utilization of their shared-vehicle fleet. The
17
work presented herein closes this gap in the literature by providing a quantitative
framework for designing shared-vehicle systems.
2.2 Formulation
Given (a) an existing transit network configuration, (b) a set of candidate sites
for sharing stations, (c) resource and other site and equity constraints for the VSP
operator, (d) behavioral assumptions of transit riders, and (e) static demand, we
seek an optimal VSP system configuration that maximizes ridership on the shared-
vehicle system.
The VSP system configuration is defined by where VSP stations are located,
the capacity (or slots) at each station and the number of vehicles at the station.
The role of VSPs within the overall context of urban transportation is explicitly
considered. While for shorter trips VSPs can be construed as a modal alternative,
longer intermodal trips can involve the use of shared-vehicle segments for access to
transit-based services. Since users act independently of the VSP operator, a leader-
follower framework is developed to model the di?ering objectives. The resulting
optimal VSP configuration respresents a supply-demand equilibrium, where the VSP
configuration (supply) supports its utilization (demand). The framework relies on
a network representation of demand and supply processes which are described next.
18
2.2.1 Supply Processes
To explicitly consider the interaction of VSPs with transit, the network repre-
sentation of supply stems from the unique characteristics of transit systems. Transit
networks possess characteristics that di?er from highway networks mainly due to
the manner in which users navigate through the system. A transit network must
account for walk access, waiting at transit stops, and intermodal paths, and ad-
ditionally model various services that allow users to reach their destinations. The
introduction of a new shared-vehicle system to access the transit network adds an
additional means of access. Users moving from origins to destinations could poten-
tially use the VSP to complete their trips should the VSP provide greater travel
utility than using transit. Alternatively, users could couple the VSP with transit to
generate an intermodal route that maximizes travel utility. This coupling is achieved
through the provision of e?cient modal interfaces between VSP and transit systems.
In practice, a quick transfer from VSP to transit would imply physical proximity
of shared stations to transit stations, unified payment systems for VSP and transit
for quick transfers, and adequate VSP station capacity near transit stations to en-
sure level-of-service. The resulting network has a hierarchical structure as shown in
Figure 2.2.
The network is represented by a graph G(V,A), where V is a set of nodes and
A is a set of arcs connecting nodes of the network. The set A includes a subset of
non-frequency based arcs denoted by A. These include all sharing links, transfer
links, and walk links. For frequency-based links that represent transit services, each
19
Figure 2.2: Network configuration
link has an associated frequency parameter f
ij
,(i, j) ? A \ A.Eacharc(i, j) ? A
is characterized by a pair (c
ij
,g
ij
), where c
ij
is a nonnegative travel time (or cost)
and g
ij
is the distribution function for the waiting time for transit service [51]. For
arcs where no waiting is involved, g
ij
=0.
A VSP operator aims to configure a shared-vehicle system around existing
transit lines. The graph G(V,A) includes all candidate sites that a VSP operator
considers. The sharing sub-network is denoted as G
s
(V
s
,A
s
), where V
s
is the set of
candidate sharing sites and V
s
? V . Since users of shared vehicles can potentially
return vehicles at any station, G
s
is a strongly connected graph. The shared-vehicle
edge set A
s
can be construed in two ways, either as having a single arc for each
pair of sharing stations, or as a set of arcs that link each sharing station to the
transport network. Similar to each arc in G, each arc in the sharing network G
s
has
an associated travel cost (or time).
20
2.2.2 Demand Processes
The core of any system designed to provide and improve mobility is its users.
Users are assumed to behave in a myopic manner to maximize their personal travel
utilities. Demand for VSP services is determined by value addition of shared-vehicles
to existing routes. Should the VSP configuration provide users with improved trip
times (or lower costs), the VSP would attract trips. From a modeling perspective,
the demand aspect is incorporated by explicitly considering this utility-maximizing
user behavior. However, two considerations limit the sophistication with which user
behavior can be incorporated. First, VSPs are a novel and innovative mobility
solution. The reaction of users to innovation is inherently uncertain and di?cult
to ascertain. To this extent, the user reaction is based solely on trip attributes of
travel time and cost, while the alternative specific utility (or disutility) is omitted. In
the context of mode choice models, alternative specific utilities quantify the innate
preferences of users for specific modal alternatives. Secondly, with the inclusion of
transit networks, a model of how users navigate through transit is needed. Over the
past few decades, several works have focused on transit assignment problems that
deal with this issue. More recent developments such as those that apply optimal
strategies [51], hyperpaths [35, 24, 59, 33], and dynamic intermodal paths [60, 32],
incorporate the probabilistic aspect by which users choose transit services. These
models aim to increase the realism of transit-based trips, where waiting users may
adapt paths during travel to take advantage of more frequent services.
In this chapter, the optimal strategy concept of Spiess and Florian [51]is
21
extended to include the VSP component. An optimal strategy is defined by a set
of arcs denoted by
?
A. A strategy can include any number of simple paths and
defines elements of the user?s route/service choice until the destination is reached.
Users waiting at a transit stop with multiple service lines choose the service that is
more frequent, thereby reducing waiting time. This approach is used in state-of-the-
practice transit assignment software, such as EMME/2. The problem of finding an
optimal strategy can be formulated as a linear program. In this work, the optimal
strategy is developed that considers VSP access links and capacity constraints on
the VSP portion of the strategy.
2.2.3 Model Development
With a network representation of supply and the characterization of demand
through optimal strategies, the problem faced by the VSP operator is formulated.
The VSP operator has at its disposal shared-vehicle resources that need to be allo-
cated to various parts of the existing network. A ?good? allocation leads to better
utilization of VSP resources and presumably more revenue for the operator. How-
ever, VSP utilization is governed by users who will employ shared-vehicles in their
trips only if there is increase in travel utility.
The model uses a leader-follower paradigm to accomodate di?ering objectives
and the VSP operator?s lack of control over system resources. VSP operators take on
theroleofleaders supplying a VSP configuration (VSP stations and vehicles). Users,
or the followers, respond to the VSP configuration by adjusting travel itineraries.
22
The leader can then adjust the configuration to maximize their objective, which
can result in new flow patterns of users. At an optimal solution, equilibrium is
reached between the objectives of the leader and followers. For the VSP operator,
the equilibrium solution represents a configuration that is designed for flows that
users will generate following their myopic objectives.
From the set of candidate sites, the VSP operator must decide where to build
new VSP stations. Additionally, the operator must determine the capacity of each
built station and the base inventory of vehicles at each station that is available at
the start of any time period. The VSP operator?s decision variables are x
i
, a binary
variable on whether or not to build at site i, i ? V
s
; y
i
, an integer variable on the
capacity at node i;andz
i
, the number of vehicles located at i. The location and
capacities of shared-vehicles are determined by equilibrium flows, which in turn are
determined by where the shared-vehicles are located. A shared-system configuration
is characterized by the tuple (x, y, z).
The upper-level problem faced by the VSP operator is to determine the optimal
VSP configuration (x, y, z) such that the shared-vehicle flows are maximized. The
VSP operator is subject to site limitations for each candidate site, budget constraints
that limit the number of stations that can be built, and additional political or equity
constraints. The total available budget is denoted by C. The cost components
include station setup costs c
s
, additional cost for an additional parking slot c
p
,and
unit cost of a vehicle c
v
.
The flows of shared-vehicles are determined by the lower-level problem by users
who have di?erent objectives from the upper-level VSP operator. Users traveling
23
between various origin-destination (OD) pairs minimize their travel and waiting
time. OD pairs are denoted by the set K (indexed by k). A link from node i to j
has an associated flow for each OD pair denoted by v
ijk
. Additionally, each node of
the transit network has an associated quantity w
ik
, representing the total waiting
time experienced by users in OD pair k at node i. The flows (v) and waiting times
(w) are continuous decision variables of the lower-level model. The notation used is
summarized next.
Sets
V Set of nodes, includes candidate sharing stations
V
s
Set of candidate sharing stations
A Set of all arcs
A
s
Set of all sharing arcs
A Set of all non-frequency arcs (e.g. walk access)
K Set of OD pairs
Indices
i, j Index to set of nodes V or V
s
k Index into set of OD pairs K
(i, j) Index to any set of arcs
VSP operator inputs
c
s
Fixed costs associated with opening one station
c
p
Incremental cost of providing a vehicle slot
24
c
v
Cost of one vehicle
C Total budget
y
ub
Maximum allowable capacity of sharing station due to site limita-
tions
VSP operator decision variables
x
i
Binary variable indicating if station is located at node i
y
i
Capacity of station at i in terms of number of slots
z
i
Number of vehicles located at node i
Lower level parameters
c
ij
Cost (or time) incurred in traversing arc (i, j)
g
ik
Demand from node i to destination node associated with OD pair
k
f
ij
Frequency parameter associated with transit service link (i, j)
a Checkout-returns replacement ratio. a = 1 implies avaiable capac-
ity must meet both checkouts and returns. a>1 implies returns
may exceed capacity in anticipation of future checkouts.
Lower level decision variables
v
ijk
Flow on link (i, j)forODpairk
w
ik
Total waiting at node i from users on OD pair k
Other
M A large constant
25
?,?,?,.. Dual variables for lower level problem
u
l
.
Binary decision variable used to model complementarity constraints
With these preliminaries, the bilevel network design problem (BLNDP) can
be formulated as follows.
Upper level:
max
x,y,z
summationdisplay
k
summationdisplay
(i,j)?A
s
v
ijk
(2.1)
subject to
summationdisplay
i?V
s
c
s
x
i
+ c
p
y
i
+ c
v
z
i
? C (2.2)
Mx
i
? y
i
i ? V
s
(2.3)
z
i
? y
i
i ? V
s
(2.4)
y
i
? y
ub
i ? V
s
(2.5)
x
i
?{0, 1} (2.6)
y
i
,z
i
? Z
n
+
(2.7)
lower-level:
min
u,v
summationdisplay
k
?
?
summationdisplay
(i,j)?A
c
ij
v
ijk
+
summationdisplay
i?V
w
ik
?
?
(2.8)
26
subject to
summationdisplay
j,(i,j)?A
v
ijk
?
summationdisplay
j,(j,i)?A
v
jik
= g
ik
i ? V, k ? K (?
ik
) (2.9)
v
ijk
? f
ij
w
ik
(i, j) ? A \ A,k? K (?
ijk
)(2.10)
Mx
i
?
summationdisplay
k
v
ijk
(i, j) ? A
s
(?
ij
) (2.11)
Mx
j
?
summationdisplay
k
v
ijk
(i, j) ? A
s
(?
ij
) (2.12)
summationdisplay
k
summationdisplay
j,(i,j)?A
s
v
ijk
? z
i
i ? V
s
(?
i
) (2.13)
summationdisplay
k
summationdisplay
j,(j,i)?A
s
v
jik
? a(y
i
? z
i
) i ? V
s
(?
i
) (2.14)
w
ik
? 0 i ? V, k ? K (?
ik
) (2.15)
v
ijk
? 0(i, j) ? A, k ? K (?
ijk
) (2.16)
The VSP operator seeks to maximize flow through the sharing network (2.1).
The flow, however, is not determined by the operator. The operator provides a
network configuration (x, y, z) subject to budget constraint (2.2). Constraints (2.3)
state that slots can be available only if a station exists at the site. Constraints
(2.4) restrict the number of vehicles assigned to a particular site to be less than
the site capacity. The site limitations are stated in constraints (2.5). Constraints
(2.6) restrict the location variables x
i
to be binary and constraints (2.7) restrict the
decision variables y
i
and z
i
to be integer.
In the lower-level problem, users react to a VSP configuration (x, y, z)by
minimizing their travel costs and waiting times (2.8). The set of flow conservation
relations for each node are given by constraints (2.9) . Constraints (2.10)relatethe
travel time and waiting time for frequency based links. The detailed derivation of
27
this set of constraints from the optimal strategies concept is presented in Spiess and
Florian [51]. Constraints (2.11)and(2.12) restrict flow on sharing arcs that have
stations to support the travel. Constraints (2.13)and(2.14) are capacity constraints
of the sharing stations. Flow and waiting times must be non-negative as enforced
by constraints (2.16)and(2.15). Note that the upper-level formulation has an
objective involving lower-level variables. In addition, the dual variables for each of
the lower-level constraints are indicated in parenthesis.
The equilibrium network design problem is a bilevel, mixed-integer program.
Programs of this class typically have non-convex feasible regions rendering them in-
tractable for most cases. For cases when the lower-level portion of the formulation is
convex, transformation techniques have been presented in the literature that convert
bilevel programs to mathematical programs with equilibrium constraints (MPEC).
The optimal strategies formulation possesses the required convexity property moti-
vating its use in the presented formulation. The lower-level convexity is exploited
for an exact solution approach presented next.
2.3 Solution Algorithm
The presented bilevel program is transformed to a large mixed integer pro-
gram (MIP) that can be solved using o?-the-shelf MIP solvers. The transformation
outlined in this section exploits the convexity of the lower-level problem.
28
2.3.1 An Exact Solution Approach
The basic solution concept follows methods proposed in the literature [2, 14].
Foragivendesigntuple(x, y, z), the lower level problem is a program with linear
objective and linear constraints. This is equivalent to the optimal strategy pro-
gram of Spiess and Florian [51] with the additional constraints to model VSP flows
and capacities. Since it is a convex program and satisfies linear constraint qualifi-
cations (CQ), the Karush-Kuhn-Tucker (KKT) conditions are both necessary and
su?cient. The lower level optimization problem can be replaced by the KKT condi-
tions to yield a mathematical program with equilibrium constraints (MPEC). The
only nonlinearities are due to the presence of complementarity constraints, which
can be transformed to a set of linear disjunctive constraints using auxilary binary
variables. The resulting program is a large MIP that can be solved using existing
MIP solvers.
2.3.1.1 KKT Conditions for Lower Level
Before deriving the KKT conditions for the lower level program defined by
Equations (2.8)?(2.16), the existence of a solution needs to be demonstrated.
Proposition 2.3.1 If the subgraph G
prime
(V
prime
,A
prime
),whereV
prime
= V \V
s
and A
prime
= {(i, j) |
i, j ? V
prime
, (i, j) ? A}, is strongly connected, the lower level problem defined by Equa-
tions (2.8)?(2.16) is feasible for all design vectors (x, y, z).
Proof If the subgraph G
prime
(V
prime
,A
prime
) is strongly connected, there exists a feasible transit
path from every origin to every destination. Since there are no capacity constraints
29
on transit links, the optimal strategy for each OD pair is never infeasible, as it can
involve at least one feasible transit path. This is independent of the design vector
(x, y, z). A set of path flows uniquely determines arc flows (Theorem 3.5 Ahuja et
al. [1]), therefore, the lower level program is always feasible.
Using the strongly connected property, the KKT conditions are derived for the
lower level program defined by objective (2.8) and constraint set (2.9)?(2.16). For
brevity, the conditions are merely stated, since the derivation from the Lagrangian
function is straighforward (but tedious).
The stationarity conditions are
1 ? ?
ik
? A =0 i ? V, k ? K (2.17)
and
c
ij
+ ?
ik
? ?
jk
? ?
ijk
+ B + C =0 (i, j) ? A, k ? K, (2.18)
where
A =
?
?
?
?
?
?
?
summationtext
k?K
?
ijk
f
ij
if(i, j) ? A \ A
0o.w
B =
?
?
?
?
?
?
?
?
ijk
if(i, j) ? A \ A
0o.w.
C =
?
?
?
?
?
?
?
?
ij
+ ?
ij
+ ?
i
+ ?
j
if(i, j) ? A
s
0o.w
30
The primal feasibility constraints are (2.9)?(2.16). Dual feasibility implies the
following.
?
ijk
? 0(i, j) ? A \A,k? K (2.19)
?
ij
,?
ij
? 0(i, j) ? A
s
(2.20)
?
i
,?
i
? 0 i ? V
s
(2.21)
?
ik
? 0 i ? V, k ? K (2.22)
?
ijk
? 0(i, j) ? A, k ? K (2.23)
The set of complementarity conditions are as follows.
?
ijk
(v
ijk
? f
ij
w
ik
)=0 (i, j) ? A \ A,k? K (u
1
ijk
)(2.24)
?
ij
parenleftBigg
summationdisplay
k
v
ijk
?Mx
i
parenrightBigg
=0 (i, j) ? A
s
(u
2
ij
) (2.25)
?
ij
parenleftBigg
summationdisplay
k
v
ijk
? Mx
j
parenrightBigg
=0 (i, j) ? A
s
(u
3
ij
) (2.26)
?
i
?
?
summationdisplay
k
summationdisplay
j,(i,j)?A
s
v
ijk
? z
i
?
?
=0 i ? I
s
(u
4
i
) (2.27)
?
i
?
?
summationdisplay
k
summationdisplay
j,(i,j)?A
s
v
ijk
?a(y
i
? z
i
)
?
?
=0 i ? I
s
(u
5
i
) (2.28)
?
ik
w
ik
=0 i ? V, k ? K (u
6
ik
) (2.29)
?
ijk
v
ijk
=0 (i, j) ? A, k ? K (u
7
ijk
)(2.30)
The MPEC is defined by objective (2.1), upper-level constraints (2.2)?(2.7),
KKT primal feasibility constraints (2.9)?(2.16), KKT stationarity conditions (2.18)
and (2.17), dual feasibility constraints (2.19)?(2.23), and complementarity con-
straints (2.24)?(2.30). All functions involved are linear, with decision variables that
31
are both integer and continuous. The only problematic nonlinear constraint set is
the complementarity constraint set (2.24)?(2.30).
2.3.1.2 Dealing with Complementarity
The complementarity constraints can be made linear by using a binary vari-
able. In general, a complementarity constraint of the form z(q + Qz)=0can
be modeled as two linear constraints using a binary variable, u,asz ? Mu and
q+Qz ? M(1?u),whereM is a large constant that provably exists [2]. Using this
transformation, all complementarity constraints can be reduced to linear constraints
as follows.
?
ijk
? Mu
1
ijk
(i, j) ? A \ A,k? K (2.31)
v
ijk
? f
ij
w
ik
? M(1 ? u
1
ijk
)(i, j) ? A \ A,k? K (2.32)
?
ij
? Mu
2
ij
(i, j) ? A
s
(2.33)
summationdisplay
k
v
ijk
?Mx
i
? M(1 ? u
2
ijk
)(i, j) ? A
s
(2.34)
?
ij
? Mu
3
ijk
(i, j) ? A
s
(2.35)
summationdisplay
k
v
ijk
? Mx
j
? M(1 ? u
3
ijk
)(i, j) ? A
s
(2.36)
32
?
i
? Mu
4
ijk
i ? V
s
(2.37)
summationdisplay
k
summationdisplay
j,(i,j)?A
s
v
ijk
? z
i
? M(1 ? u
4
ijk
) i ? V
s
(2.38)
?
i
? Mu
5
i
i ? V
s
(2.39)
summationdisplay
k
summationdisplay
j,(i,j)?A
s
v
ijk
?a(y
i
? z
i
) ? M(1 ? u
5
i
) i ? V
s
(2.40)
?
ik
? Mu
6
i
i ? V, k ? K (2.41)
w
ik
? M(1 ? u
6
i
) i ? V, k ? K (2.42)
?
ijk
? Mu
7
i
(i, j) ? A, k ? K (2.43)
v
ijk
? M(1 ? u
7
i
)(i, j) ? A, k ? K (2.44)
The BiLevel Network Design Problem (BLNDP) can, therefore, be expressed
as a mixed integer program (MIP). The BLNDP is defined by objective (2.1) upper-
level constraints (2.2)?(2.7), KKT primal feasibility constraints (2.9)?(2.16), KKT
stationarity conditions (2.18)and(2.17), dual feasibility constraints (2.19)?(2.23),
and transformed complementarity constraints (2.31)?(2.44). This large MIP can be
solved exactly by using existing MIP solvers, such as CPLEX.
The large constant M must be chosen apriori and is critical from a computa-
tional standpoint. A very large value for M introduces numerical stability issues.
An M that is too small risks cutting o? the optimal solution. In the implementation,
the M was computed as a factor of maximum possible flow times a factor of 2.5.
33
2.4 Experimental Results
The proposed transformation scheme is implemented in Java and solved using
the CPLEX 11.2 solver. The model is tested on five randomly generated transit
networks for varying problem parameters. The random networks are built by gen-
erating random coordinates for nodes within the unit kilometer interval. Nodes can
represent VSP candidate sites, transit stops, transit service, or origin/destination
nodes. Links representing transit service, walk access, VSP acess, modal transfers,
and origin/destination connectors are generated by randomly connecting pertinent
nodes. Each node is assigned a degree greater than two, to ensure that the network
is strongly connected. The links are classified into three categories. Walk links are
assumed to be traversed at a speed of 4.5 km/h. Shared-vehicle links are traversed
at a speed of 12 km/h. Transit service links run at 30 km/h. Users are assumed to
minimize travel time in going from origin to destination. Figure 2.3 depicts the five
tested networks.
For each instance, the four problem parameters (budget, cost of stations, cost
of vehicles, and cost of slots) are varied to test sensitivity of the model. The solution
of one run is used as a starting solution of the next to provide a warm start to the
CPLEX solver. The solver finds good solutions (MIP gap < 5%) relatively early
in the branch-and-bound tree for most instances. However proving optimality for
some instances takes considerable time. Therefore, each run is limited to a run time
of one hour and the resulting MIP gap is reported.
The main outputs of the models are the VSP design configuration, the shared-
34
(a) 24 Nodes (b) 35 Nodes (c) 46 Nodes
(d) 50 Nodes (e) 64 Nodes
Figure 2.3: Random transit networks tested
flows that result for each budget scenario, and the e?ect of various cost components
on the optimal design. The results of runs are summarized in Tables (2.1)?(2.5).
The tables show the input cost vector (c
s
,c
p
,c
v
), along with total budget C for
various runs. The summary shows the shared-flow captured increases as a result of
larger budgets. The variation of various cost components shows an interesting trend.
When station setup costs are high and parking slots costs are comparatively low (as
is the case for bicycle sharing systems), more stations are built than compared to
the alternate scenario, where the setup costs are low, but costs of parking slots are
high (as is the case for car sharing systems). Thus, the higher cost of parking slots
35
presents agglomeration e?ects for the system where available resources are pooled
at fewer stations.
c
s
c
p
c
v
C
summationtext
x
i
summationtext
y
i
summationtext
z
i
Shared flow MIP Gap (%) Run time (sec)
5 1 2 0 000 0 - 5.58
50 2181 10.5 3.343% 35.63
100 33923 23 2.174% 175.3
150 45935 35 1.504% 3537.45
200 67746 46 2.975% 3576.95
300 8 118 71 70.5 0.426% 13.63
1 4 2 0 000 0 - 4.5
50 295 5 10% 152.17
100 2191 11 2.02% 623.98
150 32817 16.5 2.831% 73.47
200 4382 22 3.238% 3591.67
300 45734 34 0.452% 320.27
Table 2.1: Results for Instance24 (24 nodes ? 129 links)
c
s
c
p
c
v
C
summationtext
x
i
summationtext
y
i
summationtext
z
i
Shared flow MIP Gap (%) Run time (sec)
5 1 2 0 000 0 - 1.52
50 2181 10.5 4.762% 16.2
100 33923 23 0.791% 158.59
150 46035 35 1.504% 3577.91
200 67746 46 1.902% 3582.02
300 8 118 71 70.5 0.784% 3592.83
1 4 2 0 000 0 - 1.52
50 295 5 10% 60.97
100 2191 11 3.567% 3.36
150 32817 16.5 3.03% 1221.72
200 4382 22 3.322% 3578.01
300 55634 33 3.567% 3596.55
Table 2.2: Results for Instance35 (35 nodes ? 200 links)
The flow patterns and VSP configuration are graphically summarized in Figure
2.4 for the 46 node instance when the cost of stations c
s
= 5 and cost of parking
slots c
p
= 1. The results from other instances follow similar characteristics and are
36
c
s
c
p
c
v
C
summationtext
x
i
summationtext
y
i
summationtext
z
i
Shared flow MIP Gap (%) Run time (sec)
5 1 2 0 000 0 - 0.53
50 2181 10.5 4.762% 81.13
100 33923 23 2.174% 203.83
150 46035 35 1.504% 3563.33
200 67746 46 2.975% 3603.69
300 8 118 71 70.5 0.784% 3609.06
1 4 2 0 000 0 - 0.52
50 395 5 10.286% 3599.44
100 2191 11 3.567% 3.27
150 42817 16.5 3.03% 1152.38
200 4382 22 3.322% 3612.47
300 85634 33 3.567% 3610.06
Table 2.3: Results for Instance46 (46 nodes ? 221 links)
omitted. The VSP stations chosen for construction are highlighted along with the
associated number of slots and vehicles in parenthesis. The VSP configuration can
be seen to grow in terms of number of stations when a larger budget is presumed.
However, comparing the budget scenarios in Figures 2.4(b) and 2.4(c), though the
budget increases by 50 units, the number of stations chosen for construction is
reduced. However the capacities at the two stations is augmented so as to maximize
shared-flow. When the budget is 300 units, the budgetary constraint is no longer
binding, leading to configurations where stations are chosen for construction, but
without capacity. The shared-flow corresponding to this budget scenario represents
the maximum shared-flow that can be captured.
2.5 Conclusions
The design of a shared-vehicle system in conjunction with a transit network
is formulated as a bilevel program. The problem is transformed to a more readily
37
(a) Budget = 0
(2,0)
(4,2)
(3,3)
(b) Budget = 50
(8,0)
(11,11)
(c) Budget = 100
(10,0)
(15,15)
(5,0)
(8,7)
(d) Budget = 200
(15,15)
(1,1)
(6,0)
(0,0)
(15,9)
(0,0)
(10,0)
(9,9)
(e) Budget = 300
Figure 2.4: Flow patterns and VSP configuration for 46 node instance
38
c
s
c
p
c
v
C
summationtext
x
i
summationtext
y
i
summationtext
z
i
Shared flow MIP Gap (%) Run time (sec)
5 1 2 0 000 0 - 2.91
50 2181 10.5 4.762% 345.5
100 33923 23 2.174% 249.02
150 55734 34 4.489% 3608.41
200 67746 46 2.975% 3610.16
300 9 117 69 69 2.975% 3610.97
1 4 2 0 000 0 - 2.89
50 464 1 465.385% 3613.75
100 2191 11 3.533% 30.56
150 32817 16.5 3.473% 3610.61
200 7372 22 3.567% 3612.42
300 45734 34 0.521% 211.02
Table 2.4: Results for Instance50 (50 nodes ? 263 links)
solvable mixed integer program. Tests on random networks illustrate the applica-
bility of the model for determining optimal VSP configurations and yield insights
into optimal system configurations. These include agglomeration e?ects for various
cost inputs. When station setup costs are low and parking slot costs are high (as is
the case in car sharing systems), fewer stations are developed and resources are ag-
gregated. The proposed model incorporates the transit assignment routine of Spiess
and Florian, though any transit assignment routine can be explored as alternatives
in the lower level of the formulation. The proposed model can be extended along
several dimensions. Though the fixed-demand assumption is common in practice
for strategic design problems, a framework where variable demand is considered as
a function of VSP level-of-service can yield additional insights. Congestion e?ects
on transit networks can be incorporated despite the relatively low volumes of tran-
sit flows in the US. An extension of this work could consider joint optimization of
prices and design (see [13] for example) and include price sensitivity of users in route
39
c
s
c
p
c
v
C
summationtext
x
i
summationtext
y
i
summationtext
z
i
Shared flow MIP Gap (%) Run time (sec)
5 1 2 0 000 0 - 1144.78
50 2181 10.5 4.762% 1719.56
100 33923 23 2.174% 786.23
150 45935 35 1.504% 3609.42
200 67846 46 2.975% 3605.58
300 8 118 71 70.5 0.784% 3602.3
1 4 2 0 000 0 - 1149.23
50 395 5 13.146% 3613.61
100 2191 11 3.567% 11.47
150 42817 16.5 3.475% 3606.94
200 4382 22 3.497% 3604.56
300 75634 33 3.497% 3604.25
Table 2.5: Results for Instance64 (64 nodes ? 365 links)
choice.
40
Chapter 3: Operational Models
3.1 Introduction
This chapter deals with operational strategies of fleet management that VSP
operators can pursue to maintain desired levels-of-service. To match automobile
flexibility, VSPs transfer control of vehicles to users. This places exceptional logisti-
cal challenges on operators who must ensure that demand in the near future is met.
For the shared-vehicle user, good service is defined by adequate stock of vehicles
at intended station of origin and adequate parking slots at the intended destina-
tion station. Since flow from one station to another is seldom equal to flow in the
opposing direction, the VSP fleet can become spatially imbalanced. To meet near-
future demand, operators must then redistribute vehicles to correct this asymmetry.
The focus of this chapter is to provide models that generate e?cient, cost-e?ective
operational strategies for fleet management.
The management of VSP fleets di?ers from previously studied models in re-
lated areas. These di?erences preclude the direct application of prior work and
motivate the development of problem specific tools. Firstly, since users determine
the trip characteristics, critical system attributes (where vehicles are checked out
and returned, and the duration of lease) are beyond the control of operators. Sec-
ondly, there is a ?duality? of demand between vehicles and slots. A successful trip
needs a vehicle available at the origin station and an available docking slot at the
destination. A vehicle checkout reduces vehicle inventory at a station, but increases
41
the slot inventory. This duality has significant implications and reduces the range of
acceptable inventory levels for vehicles. Thirdly, the inventory is never consumed,
but is merely moved. The fleet management strategy involves correcting imbalances
at the various stations.
Supply-side analyses of VSPs are predominantly qualitative and the literature
dealing specifically with fleet management for VSP?s is limited. [7]proposedthree
strategies to generate redistribution plans. These are based on immediate demand,
expected demand and perfect demand information. The time period looks 20 min-
utes into the future and uses simulation to evaluate the redistribution strategies.
No details on how redistribution plans are generated are presented. [8] studied the
redistribution problem, but attempt to shift the burden of redistribution on users
through two mechanisms of ride splitting and joining. [29]usedamixed-integer
program (MIP) to generate redistribution plans and allocate operator sta? to redis-
tribution and maintenance activities. Their model uses a time-expanded network,
with static, known demand. Unserviced demand is penalized by a penalty cost in
the objective function. A simulation model is used to evaluate the redistribution
strategy. In these works, the redistribution plans are based on static demand.
In this chapter, the problem of fleet management for shared-vehicle systems is
formulated considering demand uncertainty (Section 3.2). The management strategy
involves anticipative fleet redistribution that operators initiate to correct short-term
demand asymmetry (since flow from one station to another is seldom equal to flow in
the opposite direction). When operators have inadequate resources to meet demand,
then the model generates partial redistribution plans. The model takes a form of
42
a stochastic MIP with joint chance constraints. Stochastic programs of this class
have non-convex feasible regions. Two solution methods are presented (Section
3.3). When demand at stations is correlated, the first approach deals with the
problem non-convexity using the concept of p-e?cient points (PEPs) to transform
the problem to a disjunctive MIP that is more readily solvable. A divide-and-conquer
algorithm to generate PEPs is designed to reduce the computational burden of
existing methods (Section 3.3.1). The algorithm can be applied to any problem with
joint chance constraints given that the vector of random variables is discrete. This
contribution transcends the current application. A second cone generation solution
method (Section 3.3.2), akin to the column generation procedure, is developed when
the demand at each station is assumed to be independent. Under this limiting
assumption, this method provides quick solutions even for shared systems with large
numbers of stations. Additionally, an equal-apportionment bound is derived for the
problem that is valid even when demand is correlated (Section 3.4). We compare
various redistribution strategies in a real-world application to a car sharing system
in Singapore (Section 3.5). Extensive computational experiments and simulation
studies show that when the redistribution strategies developed herein are employed,
the system operates at a reliability level that would otherwise be possible only with
capital improvements to the system.
In the next section, the model formulation is outlined. Section 3.2 describes the
model formulation and a solution algorithm is presented in Section 3.3. Section 3.4
describes a failure apportionment bound for the model. A real-world application for
a system in Singapore is described in Section 3.5 along with results. The conclusions
43
are presented in Section 3.6.
3.2 Problem Formulation
Given (a) the system configuration (stations, capacities, fleet size), (b) current
inventory levels at each station, (c) relocation costs, and (d) a probabilistic charac-
terization of demand at each station, we wish to find a least-cost fleet redistribution
plan such that most near future demand scenarios are satisfied.
VSP operators have substantial ITS infrastructure for various functions, in-
cluding tracking of vehicles for theft prevention, smart cards for member access, ve-
hicle availability across the network, charging consoles for electric vehicles, payment
systems, and traveler information services. This data-rich environment provides a
real-time awareness of the system that can be leveraged for fleet management. Since
individual users decide where and when trips are made, demand at each station is
uncertain from a system perspective. The aim of operators is to serve all demand.
However, it is typically cost-prohibitive to design the system to satisfy all possible
demand realizations and operators can expect demand to outstrip supply in high-
demand scenarios. By characterizing demand probabilistically, as can be done using
historical information, operators can quantify the existing level-of-service. If the
desired level-of-service at a station is not met, then a fleet redistribution action can
be initiated to bring the system to an acceptable state.
The VSP system can be defined on a network of n stations. Each station i has
capacity, C
i
, the maximum number of vehicles it can accommodate. The capacity
44
represents parking bays for car-sharing, docking slots in bike-sharing systems, or
charging stations for electric vehicles. The number of vehicles at station i,termedthe
station inventory, is denoted by V
i
. The cost of relocating vehicles from station i to
station j, i negationslash= j, is denoted by a
ij
.Thereisapenalty? to move each vehicle between
two stations. The system operator has perfect information on available inventories
at each station. The system operator plans for a fixed short-term planning horizon
for which demand is known probabilistically. Redistribution tasks are assumed
to be completed before the planning period commences. The operator considers
redistribution actions periodically throughout the day. At each station i,thereare
two types of demand processes, one to check out vehicles, ?
1
i
, and the other to
return vehicles, ?
2
i
.Both?
1
j
and ?
2
j
are random variables with known probability
distributions. The operator seeks a least-cost redistribution plan that would make
the system p-reliable during the planning period. That is, the system satisfies all
demand at every station (1,...,n), for p proportion of all possible realizations. This
can be described by the following joint-chance constraint.
P
?
?
?
?
?
?
?
?
?
?
?
?
Available vehicles at stn 1 ? ?
1
1
, Available spaces at stn 1 ? ?
2
1
Available vehicles at stn 2 ? ?
1
2
, Available spaces at stn 2 ? ?
2
2
.
.
.
.
.
.
Available vehicles at stn n ? ?
1
n
, Available spaces at stn n ? ?
2
n
?
?
?
?
?
?
?
?
?
?
?
?
? p.
(3.1)
Equation (3.1) represents a level-of-service constraint for the operator who
seeks a p-reliable system. To achieve this, the operator looks at available inventory
at each station. If the available resources, both vehicles and free spaces, are adequate
45
to satisfy p-proportion of all possible demand scenarios, then no further corrective
actions are necessary. If the available vehicles are insu?cient, then vehicles can be
?borrowed? from adjacent stations. If available spaces are inadequate, then vehicles
can be ?lent out? to other stations to free up spaces. Since there are costs involved in
these actions, the operator seeks an optimal method to perform this redistribution.
To derive the level-of-service constraint, we note that the available vehicle
inventory at each station depends on the current inventory and the number of returns
and checkouts during the time period. If the redistribution plan calls for vehicles
to be relocated into (or out of) the station, then these vehicles are assumed to be
available (or unavailable) at the start of the planning period. This assumption is
not restrictive, since redistribution tasks can commence well before the planning
period begins. Similarly, the available spaces inventory at each station depends on
the current inventory, the number of returns, and the number of vehicles relocated
in and out of the station during the planning period. Therefore,
Available vehicles at Stn i =
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
Vehicle inventory at i (V
i
)
+
Returns at i (?
2
i
)
+
Vehicles relocated to i (
summationtext
j
y
ji
)
?
Vehicles relocated out of i (
summationtext
j
y
ij
)
(3.2)
46
Available spaces at Stn i =
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
Spaces inventory at i (C
i
? V
i
)
+
Checkouts at i (?
1
i
)
+
Vehicles relocated out of i (
summationtext
j
y
ij
)
?
Vehicles relocated to i (
summationtext
j
y
ji
).
(3.3)
It is assumed that redistribution is completed before the planning period.
Therefore, return (?
2
i
) and checkout(?
1
i
) random variables are for the future planning
period, while the inventory (V
i
) and redistribution variables (y
ij
) denote operator
actions before the planning period commences. The current vehicle inventory, V
i
,is
known, as is the corresponding spaces inventory, C
i
? V
i
.Letx
ij
denote a binary
decision variable indicating if vehicles are moved from i to j in anticipation of fu-
ture demand. Let y
ij
denote an integer decision variable indicating the number of
vehicles moved from i to j. In terms of decision variables y
ij
, the level-of-service
constraint (3.1) can be written as
P
?
?
?
?
?
V
i
+
n
summationtext
j=1
(y
ji
? y
ij
)+?
2
i
? ?
1
i
,i=1, ..n
C
i
?V
i
+
n
summationtext
j=1
(y
ij
? y
ji
)+?
1
i
? ?
2
i
,i=1, ..n
?
?
?
?
?
? p. (3.4)
Let ?
i
to be the net demand at a station i for the planning period. That
is, ?
i
= ?
1
i
? ?
2
i
. The two types of demand (vehicles and spaces) exhibit duality
(reduction of one type implies an increase of the other), so the net demand ?
i
encodes both types of demand in one random variable and represents the imbalance
47
between demand for vehicles and checkouts. For a particular time period, if the
realization of ?
i
is positive, there are more checkouts than returns. Similarly, if ?
i
is
negative, there are more returns than checkouts.
The level-of-service constraint (3.4) cannot be met for every demand realiza-
tion. For example, in scenarios where the demand outstrips available resources, this
constraint is infeasible. To recover partial redistribution plans that help operators
make the best possible use of available resources (though still shy of the desired
level-of-service), phantom vehicle and space variables are introduced. For each sta-
tion, let w
i
be the number of phantom vehicles and z
i
be the number of phantom
spaces. Additionally, let ? be a large penalty cost that forces the use of phantom re-
sources only if necessary. The variables w
i
and z
i
relax the level-of-service constraint
as shown in constraint (3.6). This relaxation allows the model to generate partial
redistribution plans and maintains feasibility even if resources are inadequate. The
optimal fleet redistribution plan can be formulated as a chance constrained model
with desired reliability p (CCM-p) as follows.
(CCM ? p)min
n
summationdisplay
i=1
n
summationdisplay
j=1
(a
ij
x
ij
+ ?y
ij
)+
n
summationdisplay
i=1
? (w
i
+ z
i
) , (3.5)
s.t. P
?
?
?
?
?
V
i
+
n
summationtext
j=1
(y
ji
?y
ij
)+w
i
? ?
i
,i=1,...,n
C
i
? V
i
+
n
summationtext
j=1
(y
ij
?y
ji
)+z
i
???
i
,i=1,...,n
?
?
?
?
?
? p, (3.6)
48
n
summationdisplay
j=1
y
ij
? V
i
i =1,...,n, (3.7)
n
summationdisplay
j=1
y
ji
? C
i
? V
i
i =1,...,n, (3.8)
y
ij
? M ? x
ij
i =1,...,n,j =1,...,n, (3.9)
y
ij
,w
i
,z
j
? Z
+
i =1,...,n,j =1,...,n, (3.10)
x
ij
? [0, 1] i =1,...,n,j =1,...,n. (3.11)
Theobjective(3.5) represents the fixed cost for relocating vehicles, the cost of
moving additional vehicles, and the penalty costs for utilizing phantom resources.
Fixed cost of redistribution between two stations can be based on distance. The
operator seeks to minimize the total cost of redistribution. The probabilistic level-of-
service constraint (3.6) states that the redistribution plan must result in inventories
that satisfy p proportion of all demand scenarios in the planning horizon. If available
resources are insu?cient, then this constraint is relaxed using phantom resources.
There are capacity constraints (3.7) that limit the number of vehicles relocated out
of a station to be no greater than the vehicles available at the start of the planning
period. Similarly, there are capacity constraints (3.8) for slots at a station stating
that the number of vehicles relocated to a station does not exceed the number of
slots available. Constraints (3.9) relates the decision variables. All decision variables
are non-negative integer valued (3.10), except x
ij
which is binary (3.11).
Program CCM-p is a stochastic MIP for determining the optimal redistribution
plan to satisfy p proportion of demand. In situations where available resources are
inadequate to match anticipated demand, the program yields a partial redistribution
49
plan. In this case, the phantom resources are utilized (w
i
> 0orz
i
> 0) and the
system is no longer p-reliable. The true reliability must be recomputed as shown in
Section 3.3.1.2. If phantom resources are not utilized, the joint chance constraint
(3.6) states that the probability that demand (in terms of vehicles and slots) exceeds
supply is no greater than 1 ?p.
Unless the joint distribution of ? is log-concave, this stochastic MIP may have
a non-convex feasible region, making it computationally challenging to solve. The
next section presents two specialized techniques for a solution that deals with this
non-convexity. These techniques are applicable when the random vector is only on
the right-hand side (RHS) and is discrete as is the case in this application.
3.3 Solving Program CCM-p
CCM-p is a stochastic MIP with joint chance constraints. In general, these
programs are di?cult to solve, but since the random vectors are discrete and appear
only in the RHS of the constraints, a specialized technique involving p-e?cient
points (PEPs) can be employed. Two solution procedures are presented. In the
first method (Section 3.3.1), the main idea is to transform the non-convex feasible
space to a disjunctive set of convex spaces. This transformation leads to a family of
MIPs, one for each convex set. A single PEP characterizes one such convex set by
substituting the chance constraint by linear constraints. A PEP is formally defined
shortly, but generally speaking, a PEP is the smallest possible (non-dominated)
vector for which the joint chance constraint is valid. For example, if v is a PEP,
50
then the chance constraint P(Ax ? ?) ? p can be substituted by a linear constraint
Ax ? v,sincev represents a realization of ? that ensures that the chance constraint
is met (see Figure 3.1). Solving the family of MIPs yields a set of solutions, the best
amongst which is optimal for the original non-convex program.
To generate the family of MIPs, the set of PEPs needs to be enumerated. When
the dimension of the random vector is large, enumerating PEPs can be problematic,
since the set of PEPs can be very large. Once the set of PEPs is enumerated, the
family of MIPs is solved using existing MIP solvers. While this method is not new,
our contribution is a PEP enumeration algorithm that aims to address the major
bottleneck in the enumeration phase of the algorithm. The proposed divide-and-
conquer procedure is more e?cient than existing methods [40, 41, 10]. Additionally,
we extend the PEP concept to dual-bounded chance constraints.
The second solution method (Section 3.3.2) reduces the computational burden
of PEP enumeration, but makes a limiting assumption on the independence of the
random vector. The main idea is similar to column generation, where only necessary
columns (or PEPs) that improve the objective are generated. The master problem is
a convexified linear approximation of the CCM-p. The simplex multipliers from the
master problem are used in the subproblem to direct the PEP enumeration phase
of the algorithm.
The idea of PEPs was first proposed by Prekopa [38] who also presented ways
to deal with the chance constraint if the marginal distribution of the random vec-
tor is log-concave [39]. Beraldi et al. [9] documents an application. Prekopa et
al. [40] presented a nested algorithm for generating PEPs. The main idea is to
51
recursively explore the search space while keeping certain dimensions fixed. Beraldi
et al. [10] proposed two enumeration schemes, backward and forward, along with
hybrid schemes that attempt to avoid complete enumeration of PEPs under some
restrictive conditions on the properties of the random vector. Their scheme targets
the non-convexity due to integral variables by reducing the number of MIPs to be
solved. They also derived conditional bounds that aid in determining if a candidate
vector is a PEP. Saxena [43] combined the enumeration scheme with the solution
phase to avoid explicit enumeration. They introduced the concept of p-ine?ciency
to reduce constraints in the resulting program. Dentcheva et al. [18, 19]proposed
hybrid methods, called convexification and cone generation methods, with the aim
of avoiding explicit PEP enumeration. Though the cone generation method assumes
independence of the random vector, this approach is very attractive, since only a
limited number of PEPs need to be generated. In this chapter, their approach is
adapted to deal with dual-bounded constraints and is presented in Section 3.3.2.
For a joint chance constraint of the form P(Ax ? ?) ? p,where? is discrete,
the enumeration of PEPs is challenging, since the search space includes all possible
realizations of the discrete random vector. The performance of any enumeration
scheme depends on (a) the dimensionality of the random vector, (b) the support of
the random vector, (c) complexity of evaluating the joint distribution function, and
(d) the value of p. Increasing the dimensionality causes a combinatorial explosion
in the search space. Increasing the support of the random vector also increases
the search space, although not combinatorially. All enumeration schemes must
evaluate the joint distribution function repeatedly. Thus, even moderate complexity
52
in calculating the distribution function negatively impacts performance. Lastly, if
the value of p is closer to either 0 or 1, the number of possible PEPs is considerably
less than if it is close to 0.5, because there are fewer combinations along di?erent
dimensions of the random vector.
3.3.1 Solution based on PEP Enumeration
Since a MIP needs to be solved for each PEP, the solution procedure is designed
to reduce the number of MIPs that need to be solved using some problem specific
properties. First, as complete redistribution plans are preferable to partial ones,
conditions for which a particular PEP will yield a guaranteed sub-optimal (partial)
solution are derived in Section 3.3.1.2. If a complete redistribution plan has been
found, these infeasibility conditions help in screening PEPs that will yield partial
solutions, thereby reducing the number of MIPs to be solved. Second, a zero-cost
redistribution plan implies that no imbalance exists, so this forms the absolute
lower bound on the problem. Third, since the set of PEPs, denoted by S
p
, is large,
it may preclude a complete enumeration and alternate termination criteria can be
used to settle on an acceptable solution. A partial enumeration provides a solution
that is not guaranteed to be optimal. The algorithm for solving CCM-p,giventhe
inventories V
i
,i=1,...,n at each station and the desired reliability level p,isas
follows.
Algorithm ENUM-p:
Step 0. Initalization. Initialize the objective value of best solution z
opt
= ?.Set
53
the PEP counter k =1. LetCR be a boolean flag that is true if a complete
redistribution plan exists. Set CR =false.
Step 1. PEP Enumeration. Generate the set of all PEPs S
p
(see Section 3.3.1.1).
Step 2. For the k-th PEP (u
k
,v
k
) ? S
p
proceed to Step 3.
Step 3. Feasibility Test. If CR = true, check all n + 2 feasibility conditions (3.14),
(3.15), and (3.16) (see section 3.3.1.2)for(u
k
,v
k
). If feasible or if CR =false,
proceed to Step 4; otherwise, set k = k +1andreturntoStep2.
Step 4. Solve Deterministic Equivalent. For a PEP (u
k
,v
k
), solve the program
(3.5)?(3.11) by replacing the joint chance constraint (3.6) by the two linear
constraints
V
i
+
n
summationdisplay
j=1
(y
ji
? y
ij
)+w
i
? v
k
and (3.12)
?
parenleftBigg
C
i
?V
i
+
n
summationdisplay
j=1
(y
ij
?y
ji
)+z
i
parenrightBigg
? u
k
. (3.13)
Step 5. Solution Check. If the objective value z
k
<z
opt
,thenz
opt
= z
k
and save
the redistribution plan corresponding to z
k
as optimal. If this redistribution
plan does not use phantom resources, set CR =true.Ifz
k
= 0, absolute lower
bound reached, terminate.
Step 5. If termination criteria are met, stop; else k = k +1andreturntoStep2.
54
3.3.1.1 A Divide-and-Conquer PEP Enumeration Algorithm
As all past developments of PEPs have dealt with random vectors having an
upper or lower bound but not both, the concept is extended to the case when the
random vector is dual-bounded as is the case in constraint (3.6). Essentially, the
procedure is developed for chance constraints of the form P(A
prime
x ? ? ? Ax) ? p,
but also applies to the classical chance constraint P(Ax ? ?) ? p. The principle
di?erence in the treatment of dual-bounded constraints is that PEPs are expressed as
vector pairs and the cumulative distribution function is replaced by a function g(u,v)
that handles dual bounds. Barring these distinctions, the following development
emulates concepts proposed by [41] and others [10, 19].
Definition For p ? (0, 1) a vector pair(u,v), u ? Z
n
and v ? Z
n
,issaidtobea
p-e?cient point (PEP) if g(u,v) ? p,whereg(u,v)=P(u
i
? ?
i
? v
i
, ?i =1, .., n)
and there exists no vectors y and z such that g(y,z) ? p, z ? v,andy ? u.
For dual-bounded chance constraints, the definition employs a function g(u,v)
instead of the cumulative distribution function to ensure that the lower bound is
also met as shown in Figure 3.1.
For this modified dual-bounded case, we first derive a bound that will serve to
test if a candidate vector is a PEP similar to the bounds based on the conditional
marginal distribution derived by [10].
Proposition 3.3.1 Avectorpair(u,v) is PEP if and only if l(u)=u and h(v)=v,
55
?
u
f(?)
p
(a) Standard definition when Ax ? u ? P(Ax ? ?) ? p
?
uv
f(?)
p
(b) Modified dual-bounded definition when A
prime
x ? u
and Ax ? v ? P(A
prime
x ? ? ? Ax) ? p
Figure 3.1: Illustration of PEP definitions for a single dimension
where
l
i
(u) = arg max{k | g(u,v) ? p, u
i
= k},i=1, .., n and
h
i
(v)=argmin{k | g(u,v) ? p, v
i
= k},i=1, .., n
for g(u,v)=P(u
i
? ?
i
? v
i
, ?i =1, .., n).
Proof Bounds ? PEP. The proof is by contradiction and is shown for the lower
bound only. Similar arguments can be applied to the upper bound. Assume a pair
of vectors (u,v), where l(u)=u and h(v)=v. Take a vector pair (y,v)thatis
PEP, such that y ? u with y
k
<u
k
for an arbitrary dimension k.Sinceg(u,v)
monotonically decreases in u, g(y,v) ? g(u,v)sincey ? u. The bounds l(u)=u
and h(v)=v imply that g(u,v) ? p. Therefore, (y,v) cannot be PEP, since there
exists a larger vector u such that g(u,v) ? p. Now assume another vector pair (y,z)
that is a PEP, such that y ? u. For an arbitrary dimension k,wherey
k
>u
k
,
56
construct a new vector w such that w
i
= u
i
,?i, i negationslash= k and w
i
= y
i
,i= k.Weknow
g(y,z) ? p as (y,z) is a PEP. Since y ? u and the function g(w,z) monotonically
decreases in w, g(w,z) ? p. Therefore, l
k
(u) ? y
i
, which implies (y,z) is not a PEP,
contradicting our assumption.
PEP ? Bounds. Follows from the definition, since if (u,v) is PEP, then
there exists no larger vector y such that (y,v) is PEP and no smaller vector z such
that (u,z) is PEP.
This bound is used to check if a candidate vector is PEP. The concept of the
proposed enumeration algorithm is that instead of a linear traversal suggested by
previous methods, we exploit the monotonic property of the cumulative distribution
function (or g(u,v)) to allow us to focus on areas of the search space that contain
the p-frontier where g(u,v)=p. The function g(u,v) monotonically increases with v
and monotonically decreases with u. The search space can be construed as a lattice,
since the random vector takes only discrete values. Any arbitrary hyper-rectangle
within the search space can be defined by two ?corner? points. The ?low? corner
point, consisting of the smallest possible v component and the largest possible u
component within the hyper-rectangle and is denoted by (u
s
,v
s
). The ?high? corner
point consists of the largest v and the smallest u components within the hyper-
rectangle and is denoted by (u
e
,v
e
). All lattice points within the hyper-rectangle
are candidate PEPs. Due to the monotonic nature of g(u,v), the lowest possible
value within the hyper-rectangle is g(u
s
,v
s
) and the highest possible value it can
take is g(u
e
,v
e
).
57
Based on the two corner points, three cases may occur as illustrated in Figure
3.2.
Case 1. If g(u
e
,v
e
) <p, then the entire hyper-rectangle can be ignored, since it is
guaranteed not to contain a PEP.
Case 2. If g(u
s
,v
s
) >pthen the hyper-rectangle is ?above? the p-frontier. The only
possible PEP is the corner point (u
s
,v
s
). If the corner point is PEP, then
it is the sole PEP in the hyper-rectangle, since it would dominate all other
candidate solutions. If it is not PEP, then no other PEPs exist within the
hyper-rectangle, since they would be dominated by (u
s
,v
s
).
Case 3. If g(u
s
,v
s
) ? p ? g(u
e
,v
e
), then the hyper-rectangle may contain one or more
PEPs and is marked for further exploration.
Figure 3.2: Three cases for arbitrary hyper-rectangles in 2-dimensions
Large swaths of the search space can be disregarded quickly using Cases 1 and
2. When the hyper-rectangle is marked for further exploration (Case 3), it can be
58
partitioned arbitrarily with the same cases applied recursively. With each iteration,
the partitions get smaller until they can no longer be divided. The terminal partition
is a hyper-rectangle with at most two lattice points along any dimension. For an n-
dimensional random vector, enumeration of PEPs in the terminal partition could, in
the worst-case, require examination of 2
2n
candidate vector pairs. The PEPs in this
case can be completely enumerated using existing enumeration schemes [40, 41, 10].
This procedure obviates the need for complete enumeration by focusing on
areas of the search space that contain the p-frontier where g(u,v)=p.Onlytwo
evaluations of g(u,v) are needed to determine if a candidate hyper-rectangle contains
the p-frontier. Complete enumeration is saved for portions of the search space that
are promising. The procedure has a small memory footprint, since the algorithm
only keeps track of two vector pairs for each hyper-rectangle. While Pr?ekopa?s
procedure [40] nests the search along the di?erent dimensions of the random vector,
here we nest in the domain of each component of the vector.
The recursive PEP enumeration algorithm is presented for a random vector
? =(?
1
,?
2
,...,?
r
). Each component of the random vector ?
i
can take values between
l
i
and u
i
.
Step 0. Initialization. Define the starting corner vector pairs (u
s
,v
s
)and(u
e
,v
e
),
where u
s
i
= v
e
i
= u
i
and v
s
i
= u
e
i
= l
i
. Initialize the set of PEPs S
p
= ? and p
the desired probability level.
Step 1. p-Frontier check. For two vector pairs (u
s
,v
s
) (start) and (u
e
,v
e
) (end) if
g(u
s
,v
s
) ? p ? g(u
e
,v
e
) then proceed to Step 2, otherwise, terminate.
59
Step 2. Partition. Along an arbitrary dimension k,k =1, ..., 2r, determine a scalar
w
k
that partitions the hyper-rectangle defined by (u
s
,v
s
)and(u
e
,v
e
)intotwo
non-empty, non-overlapping hyper-rectangles. If no partition exists, then go
to Step 4.
Step 3. Recurse.Ifk ? r, then construct s =(u
e
1
,u
e
2
,...,w
k
,...,u
e
k
). Go to Step 1
first with the vector pairs (u
s
,v
s
), (s, v
e
) and then again with the vector pairs
(s, v
s
), (u
e
,v
e
). If k>r, then construct s =(v
e
1
,v
e
2
,...,w
k
,...,v
e
r
)andgoto
Step 1 first with vector pairs (u
s
,v
s
), (u
e
,s) and then with (u
s
,s)(u
e
,v
e
).
Step 4. Enumerate. For each candidate vector pair (u,v) in the hyper-rectangle,
compute the conditional bounds l(u)andh(v). If l(u)=u and l(v)=v,add
to set of PEPs S
p
= S
p
? (u,v). Stop.
This procedure terminates with the set S
p
required in the solution procedure
of CCM-p (Section 3.3.1).
3.3.1.2 Reducing Computational E?ort
Conditions that provide a quick test on whether a PEP (u,v) will provide a
sub-optimal solution (without solving the MIP) are derived. These conditions are
based on the premise that the cost of a partial redistribution plan always exceeds
that of a complete redistribution plan, since the phantom resources (the decision
variables w
i
and z
i
) are utilized with a high penalty (?). As the solution algorithm
involves determining redistribution for a series of PEPs, if a complete plan has been
found (that is not necessarily optimal), then all successive PEPs that lead to partial
60
solutions can be safely ignored. A partial plan is used only when resources are
outstripped by demand and operators cannot cover p-proportion of demand. These
conditions utilize the physical signifance of a PEP pair (u,v). v
i
represents the
number of vehicles (if positive) needed at station i for the desired level-of-service
and u
i
, if negative, represents the required number of spaces.
At any station the total number of spaces and vehicles needed cannot exceed
the capacity. This condition is termed the capacity infeasibility condition and can
be expressed as
? min(u
i
, 0) + max(v
i
, 0) >c
i
i =1,...,n. (3.14)
These capacity constraints are ?local?, since they are applied to each station.
There are ?global? supply infeasibility conditions when the available inventory in the
system is insu?cient for the operator to meet anticipated demand. These supply
infeasibilities can be expressed as
n
summationdisplay
i=1
V
i
<
n
summationdisplay
i=1
max (v
i
, 0) and (3.15)
n
summationdisplay
i=1
(C
i
? V
i
) < ?
n
summationdisplay
i=1
min (u
i
, 0). (3.16)
Eq. (3.15) states that the total inventory of vehicles available across the net-
work is exceeded by total anticipated demand across the entire network. Eq. (3.16)
states the same principle for spaces.
When the model suggests partial redistribution, the system operates at reli-
ability levels that are lower than the desired p. The true system reliability in this
case can be computed as follows. Let (u
?
,v
?
) be the PEP for which the (partial)
61
redistribution plan is optimal. Let w
?
i
and z
?
i
be the optimal values of the phantom
resources. Then, the true system reliability ?p can be expressed as
?p = P(u
?
i
+ w
?
i
? ?
i
? v
?
i
? z
?
i
,i=1,...,n) (3.17)
= g(u
?
+ w
?
,v
?
? z
?
)
3.3.2 A Cone Generation Method
When demand across stations is assumed to be independent, the cone gener-
ation method proposed by Dentcheva et al. [18, 19] can be employed. The solution
algorithm presented here mirrors their procedure, but proposes a new subproblem
formulation to deal with the dual-bounded chance constraint. The method can
generate redistribution plans quickly and is suitable for large systems where PEP
enumeration is prohibitive. The master problem is an approximation of CCM-p and
the subproblem generates p-e?cient points as needed. The basic idea is similar to
column generation, where each PEP can be viewed as a column.
Algorithm CGM-p:
Step 0. Initialization. Choose an arbitrary starting PEP pair (u
0
,v
0
)andsetk =0,
J
k
=0.
Step 1. Master problem. Convexify CCM-p (Eqs. (3.5)-(3.11)) relaxing integral
constraints and solve the resulting linear program
min
n
summationdisplay
i=1
n
summationdisplay
j=1
(a
ij
x
ij
+ ?y
ij
)+
n
summationdisplay
i=1
? (w
i
+ z
i
) , (3.18)
62
V
i
+
n
summationdisplay
j=1
(y
ji
?y
ij
)+w
i
?
summationdisplay
j?J
k
?
j
v
j
i
i =1,...,n, (3.19)
C
i
?V
i
+
n
summationdisplay
j=1
(y
ij
?y
ji
)+z
i
??
summationdisplay
j?J
k
?
j
u
j
i
i =1,...,n, (3.20)
summationdisplay
j?J
k
?
j
=1, (3.21)
n
summationdisplay
j=1
y
ij
? V
i
i =1,...,n, (3.22)
n
summationdisplay
j=1
y
ji
? C
i
? V
i
i =1,...,n, (3.23)
y
ij
? M ? x
ij
i =1,...,n,j =1,...,n, (3.24)
x
ij
,y
ij
,w
i
,z
j
? 0 i =1,...,n,j =1,...,n, (3.25)
?
j
? 0 j ? J
k
(3.26)
Let ?
k
v
and ?
k
u
be the simplex multipliers of constraints (3.19)and(3.20),
respectively.
Step 2. Upper bound. Calculate the bound for the subproblem over the set of gen-
erated PEPs.
?
d(u
k
,v
k
)=min
j?J
k
(?
k
v
)
T
? v
j
? (?
k
u
)
T
? u
j
(3.27)
Step 3. Solve subproblem. Find the PEP pair (u
k+1
,v
k+1
)bysolving
min
braceleftbig
(?
k
v
)
T
? v
k+1
? (?
k
u
)
T
? u
k+1
| g(u
k+1
,v
k+1
) ? p
bracerightbig
, (3.28)
and compute d(u
k
,v
k
)=(v
k+1
)
T
? ?
k
v
? (u
k+1
)
T
? ?
k
u
.
63
Step 4. Termination Condition.Ifd(u
k
,v
k
)=
?
d(u
k
,v
k
), then stop; otherwise, set
J
k+1
= J
k
? (k +1),k = k + 1 and goto Step 1.
The subproblem in Step 3 has a nonlinear constraint g(u,v) ? p.When
demand at each station is assumed to be independent, this constraint can be written
as
ln(g(u
k
,v
k
)) =
n
summationdisplay
i=1
ln(g
i
(u
k
i
,v
k
i
)) ? lnp. (3.29)
If each component of the random vector ?
i
takes values between l
i
and b
i
,the
subproblem can formulated as an MIP. Denote y
ijk
as a binary decision variable
that is one if for the i-th dimension of ?, u
i
= j and v
i
= k and zero otherwise. For
a given set of multipliers (?
k
u
,?
k
v
) and a desired probability level p, the subproblem
can be written as
min
n
summationdisplay
i=1
b
i
summationdisplay
j=l
i
b
i
summationdisplay
k=l
i
(?
v
i
k ? ?
u
i
j)y
ijk
(3.30)
subject to
n
summationdisplay
i=1
b
i
summationdisplay
j=l
i
b
i
summationdisplay
k=l
i
ln(q
ijk
)y
ijk
? ln(p) (3.31)
b
i
summationdisplay
j=l
i
b
i
summationdisplay
k=l
i
y
ijk
=1 i =1,...,n (3.32)
y
ijk
? [0, 1], (3.33)
where q
ijk
= g
i
(j, k)=P(j ? ?
i
? k). The subproblem yields a PEP that can be
reconstructed from the decision variables. When y
ijk
=1,thei-th component of
the PEP is given by u
i
= j and v
i
= k. The resulting PEP is then added to the
64
master problem as a column and the procedure terminates when the PEP leading
to the best solution has been found.
3.4 A Failure Apportionment Bound
If the systemwide reliability level can be translated to a component-level mea-
sure, the joint chance constraint can be decoupled to give linear constraints. These
constraints provide a bound on the original problem. This transformation requires
no assumption of independence across stations. The VSP stations can be viewed
as being ?in series?, since the unserviced demand at any station implies lower reli-
ability. A system that is p-reliable has an acceptable failure rate of at most 1 ? p.
The Boole-Bonferroni inequality [39] implies that the sum of the station failure rates
cannot exceed the systemwide failure rate.
n
summationdisplay
i=1
(1 ?p
i
) ? 1 ? p. (3.34)
Under an equal apportionment of failure we have 1?p
i
=(1?p)/n. Decoupling
the joint chance constraint (3.6)resultsinn joint constraints:
P
?
?
?
?
?
?
?
bracketleftBigg
C
i
? V
i
+
n
summationtext
j=1
(y
ij
?y
ji
)+z
i
bracketrightBigg
? ?
i
V
i
+
n
summationtext
j=1
(y
ji
?y
ij
)+w
i
? ?
i
?
?
?
?
?
?
? p
i
i =1,...,n, (3.35)
where p
i
=(n ? 1+p)/n.Thissetofn joint chance constraints can be further
reduced by allowing the acceptable failure rate to be divided among unserviced
demand for vehicles and unserviced demand for spaces. This is shown in Figure 3.3.
65
p
i
(1 ?p
i
)/2(1 ?p
i
)/2
?
i
?
parenleftBigg
C
i
?V
i
+
n
summationtext
j=1
(y
ij
?y
ji
)+z
i
parenrightBigg
V
i
+
n
summationtext
j=1
(y
ji
?y
ij
)+w
i c
i?c
i
Figure 3.3: Demand scenarios covered by the chance constraint at one station
This results in 2n chance constraints:
P
parenleftBigg
V
i
+
n
summationdisplay
j=1
(y
ji
?y
ij
)+w
i
? ?
i
parenrightBigg
?
1 ? p
i
2
i =1,...,n,(3.36)
P
parenleftBigg
?
bracketleftBigg
C
i
? V
i
+
n
summationdisplay
j=1
(y
ij
?y
ji
)+z
i
bracketrightBigg
? ?
i
parenrightBigg
?
1 ? p
i
2
i =1,...,n.(3.37)
In terms of the inverse marginal distribution, the constraints (3.36)and(3.37)
can be derived as
V
i
+
n
summationdisplay
j=1
(y
ji
? y
ij
)+w
i
? F
?1
?
i
parenleftbigg
1+p
i
2
parenrightbigg
i =1,...,n, (3.38)
?
bracketleftBigg
C
i
? V
i
+
n
summationdisplay
j=1
(y
ij
? y
ji
)+z
i
bracketrightBigg
? F
?1
?
i
parenleftbigg
1 ? p
i
2
parenrightbigg
i =1,...,n. (3.39)
The solution to the MIP defined by the objective (3.5) and constraints (3.7),
(3.8), (3.9), (3.10), (3.11), (3.38), (3.39) provides a bound on the optimal solution.
3.5 Application
The Intelligent Community Vehicle System (ICVS) operated by the Honda
Motor company in Singapore City, Singapore was a car-sharing system with 14
stations mainly in the downtown region and one at the Changi Airport. The system
66
was also studied by [29]. The program is no longer operational. Data from the
program available from March 2003 through January 2006 documents 45, 570 trips.
Across the 14 stations, the system had an assumed capacity of 202 spaces, with 94
vehicles spread around the network. The characteristics of the fleet are not known
and are assumed to be homogeneous. The trip characteristics are summarized in
Figures 3.4 and 3.5.Figure3.6 shows the inter and intra station flow patterns.
While most trips start and terminate at the same station, a considerable proportion
of flows are oneway. Also note that inter-station flows between any two stations are
asymmetric and not equal.
The realized demand process is assumed to be the true demand process. This
implies that extreme demand scenarios are not represented in the inputs (since they
are never observed). The demand-supply interaction is ignored and treated as exoge-
nous and inelastic. Each day is divided into four time periods when redistribution is
considered. During each time period at each station, the number of vehicles checked
out and the number returned were found to be Poisson distributed. Of all 112 input
distributions (one for each station and each period during the day for checkouts
and returns), 28 failed the ?
2
test due to the low number of observations. Sample
distributions for two stations are shown in Figure 3.7.
For each station j and time period t, the Poisson vehicle checkout rate (?
1
tj
)
and the Poisson vehicle return rate (?
2
tj
) are determined. Since the random variable
?
i
in program CCM-p is the di?erence of the two, the distribution of the di?erence
is needed. When two random variates are Poisson distributed with means ?
1
tj
and
?
2
tj
, their di?erence ?
tj
is Skellam distributed with pmf
67
0 3 6 9 12 15 18 21 24
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Haw Par Centre
Wisma Atria
Millenia Walk
Market Street
Raffles City
Temasek Tower
StarHub Centre
United Square
Changi Airport
Park Mall
Orchard Hotel
Tanjong Pagar
Golden Shoe Car Park
HDB Hub
(a) Average Number of Checkouts
?10 ?8 ?6 ?4 ?2 0 2 4 6 8 10
0
0.1
0.2
0.3
0.4
0.5
0.6
Wisma Atria
Millenia Walk
Market Street
Raffles City
Temasek Tower
StarHub Centre
United Square
Changi Airport
Park Mall
Orchard Hotel
Tanjong Pagar
Golden Shoe Car Park
HDB Hub
(b) Distribution of Daily Imbalance
Figure 3.4: Characteristics of the IVCS Singapore system
0 500 1000 1500 2000 2500
0.25
0.5
0.75
0.9
0.95
0.99
0.995
0.999
0.9995
0.9999
(a) Distribution of Trip Distance
0 24 48 72 96 200 300 400
0.25
0.5
0.75
0.9
0.95
0.99
0.995
0.999
0.9995
0.9999
(b) Distribution of Trip Duration
Figure 3.5: Trip characteristics
68
Figure 3.6: Relative inter and intra station flows
69
P(?
tj
= k)=e
?(?
1
tj
+?
2
tj
)
parenleftbigg
?
1
tj
?
2
tj
parenrightbigg
k/2
I
k
(2
radicalBig
?
1
tj
?
2
tj
), (3.40)
where I
k
(z) is the modified Bessel function of the first kind. Since this is a discrete
distribution, F
?1
?
(p) exists when we define the inverse function as the infimum and
when 0 <p<1. Figure 3.8 shows the Skellam distribution for some sample values.
3.5.1 Computational Experiments
Nine strategies for redistribution based on expected value, doing nothing, the
enumeration-based solution method, the cone generation method, and the failure
apportionment bound are tested. A single day is divided into four planning peri-
ods and a redistribution plan is generated for each period using each of the nine
strategies. Starting from base inventories in the first period (common for all so-
lution methods), the di?erent redistribution plans are enacted. Consequently, the
state of the system at subsequent periods across the di?erent solution methods may
not be the same. A demand scenario is randomly generated and the fleet invento-
ries are adjusted to serve as the start point to generate a new redistribution plan.
The performance of the system is measured in terms of actualized or true reliabil-
ity ?p, redistribution cost (without the penalties for phantom resources, since this
component of the objective functions is what operators will experience) involved in
implementing the redistribution plan, and the robustness of the plan over a wide
range of demand scenarios.
A do-nothing (DN) approach is when operators relocate only once before the
70
start of each day, but do not redistribute during the day. An expected value approach
(AVG) generates redistribution based on the expected value of demand. The PEP
enumeration based solution approach (ENUM-p) is used to generate strategies for
three values of p (0.8, 0.9, and 1.0). Since the support of the Skellam distribution
is Z, for the last case p is very close to, but not equal to, 1.0. The cone generation
method (CGM-p)isrunforp =0.8, 0.9. The results for CGM-1.0 and ENUM-1.0
are exactly the same, since only one PEP is considered. Therefore, only results from
ENUM-1.0 are reported. The failure apportionment bounds (FAB-p)presentedin
Section 3.4 are computed for two values of p:0.8and0.9. The proposed procedures
(DN, AVG, ENUM-p,CGM-p,FAB-p) were implemented in MATLAB 2009a, java,
and CPLEX 11.2. All experiments were run on an Intel Xeon processor running
at 3.00 GHz with 16GB of RAM. Since for ENUM-p, the PEP enumeration phase
(Step 1) of the algorithm is needed only once, the PEP generation procedure was
allowed to run for 24 hours for each stage using p =0.8and0.9(forp =1.0, there is
only one PEP). The number of PEPs generated for each period are shown in Table
3.1.
State Time Period (hrs) # PEPs p =0.8 # PEPs p =0.9
1 0 ? t<9 50.10 9.41
2 9 ? t<12 37.60 22.68
3 12 ? t<18 64.60 173.80
4 18 ? t<24 77.20 202.00
Table 3.1: Number of PEPs for each stage (in millions)
Since the set of PEPs is extremely large, the run time for ENUM-p experi-
ments at each time period was restricted to one hour. Consequently, the solutions
71
presented next are not guaranteed to be optimal. Should the ENUM procedures run
to completion, the results would be exact and match those obtained via the CGM-p
method. Since demand at each station is assumed to be independent, the results
from CGM-p (where independence is forced) can be directly compared with other
strategies.
Results are presented for a 2-day period. Figure 3.9 shows the actualized
reliability ?p (averaged over time periods) versus the total relocation costs over the
entire day. The relocation costs are computed as the value of the objective function
minus the penalties for using the phantom resources. For ENUM-p methods, the
family of solutions is depicted for p =0.8, 0.9. CGM-p methods with p =0.8or0.9
provide the best actualized reliability at the lowest cost. For the same reliability level
p, CGM methods outperform ENUM, since by terminating prematurely all PEPs
are not explored for ENUM and, therefore, optimality is not necessarily achieved.
FAB-p strategies provide high reliability, but are expensive to implement. The
ENUM-1.0 and CGM-1.0 (not reported) methods yield the same results and both
perform poorly. Since the resource requirements to satisfy such a high level-of-
service are extraordinary, the redistribution plan that the model achieves in this
case is always partial, since phantom variables must be utilized. The actualized
reliability achieved for this case is very low.
Snapshots of the system at the start of each period illustrate the role of com-
plete and partial redistribution plans. Figure 3.10 shows the actualized reliability
and redistribution costs dissaggregated by period for Day 1. After starting at base
inventory levels in the first period, the system state at each subsequent period is
72
di?erent for various strategies as the enacted redistribution plans vary across strate-
gies. Hence, the solutions at each snapshot are not commensurate and should be
viewed as a time slice through an evolving system. Nonetheless, these figures il-
lustrate that when resources are adequate at the start of the day (Figures 3.10(a)
and 3.10(b)), most strategies provide complete redistribution plans. When inven-
tories are low (Figure 3.10(d)), a complete redistribution plan is only achieved by
the CGM-0.8 strategy. Under these circumstances, all other solutions show drops
in true reliability and represent partial redistribution plans. When the plans are
complete, the FAB-p solutions cost more than the ENUM-p and CGM-p strategies
(for a comparable p). When the plans are partial, this need not be the case, since
the penalty costs are not included. This is also illustrated in Figure 3.11,where
FAB strategies involve the largest number of redistributed vehicles.
To determine the value of considering stochasticity in generating redistribution
plans, simulation is employed. The strength of a particular system configuration can
be tested over a range of demand realizations. The number of unserviced users, or
dropped demand, is measured for each realization. Given a random realization of
demand
?
?, the dropped demand for vehicles d
v
and spaces d
s
can be computed as
d
v
=
n
summationdisplay
i=1
max(0,
?
?
i
?V
i
), (3.41)
d
s
= ?
n
summationdisplay
i=1
min(0,
?
?
i
+ C
i
?V
i
). (3.42)
These quantities are computed for all the strategies and time periods for two
days over 100, 000 realizations. Results are summarized in Tables 3.2 and 3.3.The
ENUM-0.8, ENUM-0.9, and CGM-p strategies do not drop any demand for a high
73
proportion of realizations, regardless of resource availability. When resources are
adequate, at the start of the day, all strategies do well. During later time periods,
the AVG, ENUM-1.0, and DN approaches are more likely to leave demand unser-
viced. The FAB strategies perform as well as CGM, but these are more expensive
to implement. Tables 3.2 and 3.3 also show the worst-case demand realization for
each algorithm. The CGM-p methods consistently drop fewer number of demand
requests for vehicles and spaces compared to other methods even in the worst-case
realization, indicative of robustness of the redistribution strategy.
The solutions yield additional insights on system characteristics. Since the
PEPs have a physical interpretation, for the PEP that resulted in the best known
solution, the system resource requirements can be computed (see Table 3.4). These
numbers directly relate the desired level-of-service with the resources. For example,
in Day 1, to achieve a systemwide reliability of 0.9 requires 77 vehicles during the
18:00-24:00 Hours (Hrs) time period for the CGM and ENUM methods. A reliability
of 0.8 requires eight fewer vehicles for the same period. These values are contin-
gent on starting inventories, thus, their purpose is illustrative. In a similar vein,
the stations which have frequent local infeasibilities can be the target of capacity
improvements, because local infeasibilities indicate recurrent imbalance in flows.
In summary, fleet management strategies that explicitly account for demand
stochasticity o?er greater reliability than plans based on static methods. Redistri-
bution strategies based on the proposed stochastic MIP also weather scenarios in
which demand outstrips supply. In simulation studies, the CGM-p, and even the po-
74
Time
(Hrs)
Algorithm Probability
of no
dropped
ve-
hicle
de-
mands
Average
num-
ber of
dropped
vehicle
demands
Number
of
dropped
vehicle
demands
for
worst-
case
Probability
of no
dropped
spaces
Average
num-
ber of
dropped
space
demands
Number
of
dropped
space
de-
mands
for
worst-
case
Partial
Re-
dis-
tri-
bu-
tion
Relocation
Costs
?p
0-9 DN 0.998 0.00 2 1.000 0.00 3 - 0.00 0.599
AVG 0.998 0.00 2 1.000 0.00 3 - 0.00 0.599
FAB-0.9 0.998 0.00 3 1.000 0.00 2 No 38817.33 0.994
FAB-0.8 1.000 0.00 2 1.000 0.00 2 No 36291.29 0.992
ENUM-1.0 0.998 0.00 2 1.000 0.00 3 Yes 0.00 0.599
ENUM-0.9 1.000 0.00 3 1.000 0.00 3 No 11590.26 0.984
ENUM-0.8 1.000 0.00 2 1.000 0.00 3 No 10749.17 0.961
CGM-0.9 0.999 0.00 2 1.000 0.00 3 No 10250.17 0.954
CGM-0.8 0.999 0.00 2 0.999 0.00 3 No 10077.12 0.910
9-12 DN 0.487 0.80 8 0.391 1.16 9 - 0.00 0.289
AVG 0.754 0.34 7 0.423 1.06 9 - 1495.01 0.483
FAB-0.9 0.988 0.01 4 0.990 0.01 4 No 11335.09 0.988
FAB-0.8 0.997 0.00 3 0.986 0.02 4 No 5294.02 0.995
ENUM-1.0 0.487 0.80 8 0.391 1.16 9 Yes 1279.01 0.289
ENUM-0.9 0.985 0.02 4 0.970 0.04 5 No 3626.02 0.978
ENUM-0.8 0.998 0.00 3 0.822 0.24 6 No 3959.04 0.984
CGM-0.9 0.990 0.01 4 0.944 0.07 5 No 5294.04 0.982
CGM-0.8 0.989 0.01 4 0.817 0.24 6 No 1668.03 0.959
12-
18
DN 0.121 2.94 16 0.219 2.42 16 - 0.00 0.044
AVG 0.323 1.66 14 0.328 1.75 14 - 592.01 0.168
FAB-0.9 0.773 0.40 11 0.882 0.18 8 Yes 34089.16 0.767
FAB-0.8 0.854 0.24 10 0.829 0.27 9 Yes 28025.11 0.840
ENUM-1.0 0.121 2.94 16 0.226 2.38 16 Yes 0.00 0.045
ENUM-0.9 0.852 0.24 10 0.773 0.37 9 Yes 29310.14 0.843
ENUM-0.8 0.866 0.21 7 0.835 0.26 9 No 30574.13 0.853
CGM-0.9 0.954 0.06 7 0.710 0.50 10 Yes 28554.15 0.912
CGM-0.8 0.934 0.09 7 0.690 0.53 10 No 6043.06 0.876
18-
24
DN 0.022 4.86 18 0.024 4.88 20 - 0.00 0.018
AVG 0.156 2.68 15 0.220 2.34 17 - 4175.05 0.140
FAB-0.9 0.924 0.11 7 0.477 1.12 13 Yes 25102.27 0.919
FAB-0.8 0.919 0.12 7 0.480 1.10 13 Yes 22069.24 0.915
ENUM-1.0 0.022 4.86 18 0.026 4.78 20 Yes 0.00 0.019
ENUM-0.9 0.912 0.13 7 0.473 1.13 13 Yes 16865.20 0.908
ENUM-0.8 0.841 0.25 9 0.602 0.75 11 Yes 10984.16 0.839
CGM-0.9 0.950 0.07 7 0.398 1.39 14 Yes 14639.17 0.945
CGM-0.8 0.906 0.13 8 0.458 1.14 12 No 13413.16 0.887
Table 3.2: Summary of 100,000 simulation runs for Day 1
75
Time
(Hrs)
Algorithm Probability
of no
dropped
ve-
hicle
de-
mands
Average
num-
ber of
dropped
vehicle
demands
Number
of
dropped
vehicle
demands
for
worst-
case
Probability
of no
dropped
spaces
Average
num-
ber of
dropped
space
demands
Number
of
dropped
space
de-
mands
for
worst-
case
Partial
Re-
dis-
tri-
bu-
tion
Relocation
Costs
?p
0-9 DN 0.998 0.00 3 1.000 0.00 2 - 0.00 0.599
AVG 0.998 0.00 3 1.000 0.00 2 - 0.00 0.599
FAB-0.9 0.998 0.00 3 1.000 0.00 1 No 38817.33 0.994
FAB-0.8 1.000 0.00 1 1.000 0.00 1 No 36291.29 0.992
ENUM-1.0 0.998 0.00 3 1.000 0.00 2 Yes 0.00 0.599
ENUM-0.9 1.000 0.00 1 1.000 0.00 2 No 11590.25 0.985
ENUM-0.8 0.999 0.00 3 1.000 0.00 2 No 10575.22 0.957
CGM-0.9 0.999 0.00 3 1.000 0.00 2 No 10250.17 0.954
CGM-0.8 0.999 0.00 3 0.999 0.00 2 No 10077.12 0.910
9-12 DN 0.965 0.04 4 0.332 1.33 11 - 0.00 0.341
AVG 0.965 0.04 4 0.332 1.33 11 - 0.00 0.341
FAB-0.9 0.995 0.01 3 0.998 0.00 3 No 4950.03 0.995
FAB-0.8 0.999 0.00 3 0.989 0.01 4 No 1125.02 0.997
ENUM-1.0 0.965 0.04 4 0.332 1.33 11 Yes 0.00 0.341
ENUM-0.9 0.999 0.00 2 0.975 0.03 5 No 0.00 0.987
ENUM-0.8 0.999 0.00 2 0.979 0.02 4 No 2542.03 0.974
CGM-0.9 0.991 0.01 4 0.958 0.05 5 No 2501.02 0.967
CGM-0.8 0.989 0.01 4 0.908 0.12 6 No 1641.03 0.932
12-
18
DN 0.494 1.05 11 0.089 3.95 21 - 0.00 0.098
AVG 0.495 1.05 11 0.115 3.50 20 - 1125.01 0.116
FAB-0.9 0.896 0.16 7 0.846 0.24 9 Yes 13059.07 0.859
FAB-0.8 0.947 0.08 7 0.780 0.36 10 Yes 11480.08 0.893
ENUM-1.0 0.494 1.05 11 0.089 3.95 21 Yes 0.00 0.098
ENUM-0.9 0.946 0.08 6 0.789 0.35 10 Yes 13418.09 0.910
ENUM-0.8 0.888 0.17 8 0.841 0.25 10 No 12392.19 0.874
CGM-0.9 0.963 0.05 6 0.671 0.59 11 Yes 12119.17 0.910
CGM-0.8 0.955 0.06 6 0.632 0.68 11 No 8908.14 0.887
18-
24
DN 0.052 3.76 20 0.005 7.28 27 - 0.00 0.031
AVG 0.330 1.60 16 0.083 3.80 23 - 4577.07 0.262
FAB-0.9 0.917 0.12 10 0.485 1.09 15 Yes 26147.22 0.913
FAB-0.8 0.927 0.11 9 0.400 1.39 17 Yes 20664.19 0.922
ENUM-1.0 0.052 3.76 20 0.005 7.28 27 Yes 0.00 0.031
ENUM-0.9 0.914 0.12 10 0.536 0.94 15 Yes 19417.15 0.909
ENUM-0.8 0.844 0.24 11 0.629 0.69 13 No 19441.17 0.841
CGM-0.9 0.952 0.07 9 0.395 1.42 17 Yes 18299.14 0.944
CGM-0.8 0.910 0.13 10 0.501 1.04 16 No 13766.12 0.904
Table 3.3: Summary of 100,000 simulation runs for Day 2
76
Day 1 Required Vehicles Required Spaces Local Infeasibility
Strategy p 0-9 9-12 12-18 18-24 0-9 9-12 12-18 18-24 0-9 9-12 12-18 18-24
AVG - 2.49 8.97 25.73 27.15 14.55 6.72 17.79 10.47 00 0 0
FAB 0.8 22 47 76 84 74 51 69 54 00 8 6
FAB 0.9 19 41 71 79 68 48 63 48 00 5 2
ENUM 1.0 137 149 245 240 161 141 228 207 13 13 13 13
ENUM 0.9 21 45 71 77 67 46 66 54 00 5 2
ENUM 0.8 20 41 62 69 61 48 62 51 00 0 0
CGM 0.9 17 39 77 77 53 32 51 34 00 0 0
CGM 0.8 14 36 63 69 46 26 41 28 00 0 0
Day 2 Required Vehicles Required Spaces Local Infeasibility
Strategy p 0-9 9-12 12-18 18-24 0-9 9-12 12-18 18-24 0-9 9-12 12-18 18-24
AVG - 2.49 8.97 25.73 27.15 14.55 6.72 17.79 10.47 00 0 0
FAB 0.8 22 47 76 84 74 51 69 54 00 8 6
FAB 0.9 19 41 71 79 68 48 63 48 00 5 2
ENUM 1.0 137 149 245 240 161 141 228 207 13 13 13 13
ENUM 0.9 22 48 71 76 65 46 68 57 00 5 3
ENUM 0.8 21 45 63 70 60 44 63 52 00 0 0
CGM 0.9 17 39 76 77 53 32 53 34 00 0 0
CGM 0.8 14 36 63 69 46 26 41 28 00 0 0
Table 3.4: Systemwide resource needs based on various strategies with the number
of stations with local capacity infeasibilities
tentially suboptimal ENUM-0.9 and ENUM-0.8 strategies, demonstrate robustness
over all sampled demand scenarios.
3.6 Conclusions
Fleet management strategies that explicitly consider demand stochasticity are
developed for vehicle sharing systems. In developing these management strategies,
no assumptions are made on the specific operational characteristics and demand
processes of a particular system. However, system specific attributes can be in-
corporated with relative ease. For example, if a sharing system allows advance
reservations of vehicles, then the demand process splits into a static known compo-
nent and an uncertain one. By adjusting start inventories at each stage, the static
77
portion can be guaranteed service.
The main contributions of this work are in formulating the VSP fleet man-
agement problem as a stochastic MIP. The approach taken herein overcomes the
limitations of prior works that assume static or known demand. The proposed
framework quantifies the systemwide level-of-service o?ered based on a probabilistic
characterization of demand. Two solution techniques, one based on enumeration and
the other on cone generation, are presented. For the enumeration-based technique,
the PEP enumeration algorithm improves on existing tools by using a divide-and-
conquer paradigm that is able to quickly eliminate areas of the search space that are
guaranteed not to contain PEPs. Our technique has a smaller memory and compu-
tational footprint than previously proposed methods. Additionally, the concept of
PEP is extended to include dual-bounded chance constraints. For a more restrictive
case when demand is assumed to be independent across stations, a second solution
technique can be employed which is quick even for large systems. An equal-failure
apportionment bound is also derived that is applicable even when demand across
stations is correlated. Under these limiting assumptions (independence or equal fail-
ure probability), exact solutions can be quickly obtained. In an application of the
proposed framework to a system in Singapore, the operational strategies were found
to be robust in simulation studies. Additionally, trade-o?s between redistribution
costs and level-of-service were explored.
Future work along this direction could relax some assumptions, namely im-
mediate fleet relocation, incorporate sta? availability to perform redistribution, and
tackle heterogeneous fleets. To address large-scale systems, such as the bicycle-
78
sharing system in Paris, faster heuristics can be developed. The exact solution
techniques proposed herein can be used to provide benchmark solutions for use in
evaluating these heuristics. One might also study the assignment and routing of
relocation teams to carry out fleet redistribution.
79
0 2 4 6 8 10
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
0<= t < 9
9<= t < 12
12<= t < 18
18<= t < 24
Theoretical
(a) Station 10
0 2 4 6 8 10
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
09<= =9=t
t9<= =9=12
129<= =9=18
189<= =9=24
Theore ical
(b) Station 12
Figure 3.7: Actual and theoretical demand distributions for two Stations
?10 ?5 0 5 10
0
0.05
0.1
0.15
0.2
Figure 3.8: The Skellam distribution function for sample ? combinations.
024681012
0
0.2
0.4
0.6
0.8
1
? 10
4
(a) Day 1
024681012
0
0.2
0.4
0.6
0.8
1
? 10
4
(b) Day 2
Figure 3.9: Average actualized reliabilty vs. relocation costs over entire day
80
00.511.522.533.544.5
0
0.2
0.4
0.6
0.8
1
? 10
4
(a) Period 00:00 to 09:00 Hrs
00.511.522.533.544.5
0
0.2
0.4
0.6
0.8
1
? 10
4
(b) Period 09:00 to 12:00 Hrs
00.511.522.533.544.5
0
0.2
0.4
0.6
0.8
1
? 10
4
(c) Period 12:00 to 18:00 Hrs
00.511.522.533.544.5
0
0.2
0.4
0.6
0.8
1
? 10
4
(d) Period 18:00 to 24:00 Hrs
Figure 3.10: System snapshots for various time periods (Day 1)
81
0
5
10
15
20
25
30
35
40
(a) Day 1
0
5
10
15
20
25
30
35
40
(b) Day 2
Figure 3.11: Number of vehicles relocated
82
Chapter 4: System Design For Washington D.C.
4.1 Introduction
The Washington D.C. metropolitan region ranks second in tra?c congestion
in the U.S. [44]. To address the growing transportation problems in the region, the
District of Columbia Department of Transportation (DDOT) has actively promoted
the use of alternate solutions to highway congestion. These strategies include facili-
tating increased bicycle use, improvement of pedestrian facilities, and the promotion
of shared-vehicle systems. These goals are being met through the innovative use of
transportation related policy. In the North American context, DDOT has pioneered
the use of on-street parking for shared cars to increase the utility of shared vehicles
for users. The Washington Metropolitan Area Transit Authority (WMATA) exclu-
sively reserves several parking spots at its transit stations to integrate shared-vehicle
and transit use.
In August, 2008, Washington D.C. was the first city in the US to implement a
bicycle sharing program named SmartBikeDC. As a public-private partnership, the
program started with 10 stations, with capacities ranging from 10 to 15 bicycles in
the downtown areas of Washington. Following the success of this initial system, in
March 2010, DDOT in collaboration with neighboring Arlington County, announced
a new system of 100 stations and 1000 bicycles that will supersede SmartBikeDC.
The new system will be operational in the Fall of 2010 and will use the ?Bixi?
modular concept already in place in cities like Montreal. The Bixi concept was
83
developed for Montreal to overcome some design and implementation issues faced by
earlier generation of systems. By making solar-powered stations and using wireless
communications, the setup costs are reduced since utilities need not be extended to
each station. This also allows for quick installation, easy removal of stations over
the winter, and capacity enhancements.
In this chapter, based on the framework introduced in Chapter 2,anoptimal
configuration for the proposed bike sharing system is determined. In discussions
with DDOT representatives, several site and equity constraints were established.
The new program, termed Capital BikeShare, spans Washington D.C. and Arlington
County, Virginia. Several program characteristics were determined in negotiations
between the city and the service provider. The program is to have 114 stations,
with 100 stations in the District of Columbia and 14 stations in Arlington County.
Tentative pricing information released indicates an annual membership of $80 that
would allow for unlimited number of rides under 30 minutes. Trips lasting more
than 30 minutes will be charged a yet undecided fee for every additional half-hour.
Day-use memberships with a cost of $5 and monthly memberships for $30 are also
planned.
The main contributions of this chapter are in extending the bilevel VSP net-
work design problem presented in Chapter 2 for a real-world case study for Wash-
ington D.C. The proposed bicycle sharing program expansion has problem specific
characteristics that are incorporated into the VSP design problem. A Genetic Algo-
rithm (GA) based meta-heuristic approach is developed for its solution. In addition
to determining the near-optimal VSP configuration, the system usage patterns are
84
forecasted and flow potential between stations is quantified. Improvement in travel
times through the use of shared-vehicles is also estimated.
4.1.1 Setting
As the nation?s captial, Washington D.C. is home to several large federal insti-
tutions, museums, foreign embassies, and relatively dense residential neighborhoods.
Key relevant social and urban characteristics of the city are summarized in Figures
4.1 and 4.2.
(a) Percent Black (Darker = Higher) (b) Percent Caucasian (Darker = Higher)
Figure 4.1: Social characteristics of Washington D.C.
Transportation related issues for the greater Washington region are handled
through the Metropolitan Washington Council of Governments (MWCOG), a re-
gional planning entity that serves the Greater Washington metropolitan area, in-
85
(a) Population Density (Darker = Higher) (b) Landuse
Figure 4.2: Urban characteristics of Washington D.C.
cluding D.C., Maryland, and Virginia. The main transit agency for the region is
WMATA that runs a metro system with six lines, 88 stations, and 106 miles of
transit lines. In addition, WMATA operates the Metrobus service consisting of 319
routes, serving 12,227 bus stops across the region. Transit plays a vital role in the
region, especially in the urban core, where 42% of all work-based trips use transit
[58]. As shown in Figure 4.3, access to metro stations in the downtown region of
D.C. are predominantly by walk or bicycle, while stations in the outer suburban ar-
eas have large parking facilities that attract park-and-ride users from the suburban
residential communities [36].
86
Figure 4.3: Access modes of passengers to metro stations
4.1.2 Model Components
Following the conceptual developments in Chapter 2, the key supply and de-
mand characteristics need to be represented in a network modeling framework. The
network is defined by a set of nodes that represent various elements in the tran-
sit and VSP system. Nodes can represent transit stops, transit services, origins,
destinations, link intersections for walk, bicycle and road networks, and candidate
VSP stations. Network links are used to connect the nodes and can represent walk
links, shared-vehicle movement, transit services, transit access and egress, waiting
links, bicycle links, and road links. The case study network uses data collected from
87
various sources. The transit information is based on data from WMATA, while
the walk and bicycle network information are from the D.C. O?ce of Planning.
DDOT provided information on VSP candidate stations. The data attributes and
its limitations are described in greater detail next.
4.1.2.1 VSP Candidate Stations
Washington, D.C. consists of eight wards. Wards are political districts used to
elect members to the City Council. The design of any public system faces equity con-
cerns regarding the distribution of facilities across wards. Therefore, in determining
the candidate shared-bicycle stations, an adequate number of candidate facilities
must be considered for each ward. To generate the set of candidate stations, all ma-
jor transit stations within the D.C. jurisdiction were considered. Additionally, from
the 1,403 signalized intersections in D.C., a randomly selected subset was chosen
to serve as candidate VSP sites. Signalized intersections are chosen as candidate
sites, since they tend to have greater visibility in an urban setting. Figure 4.4 shows
the candidate stations along with ward boundaries. A total of 455 candidate sites
for VSP stations are considered. The modular Bixi bicycle sharing technology uses
solar-powered stations and wireless communications. Since the proposed VSP sta-
tions are self-supporting, the selection of VSP candidate stations is limited only by
physical space and not by site accessibility to electricity or communication utilities.
Site accessibility to utilities is not considered in determining candidate sites.
88
Figure 4.4: Candidate VSP stations with ward boundaries
4.1.2.2 Travel Demand
The VSP design is based on flow patterns in the region. The demand for travel
for the analysis is based on the Maryland Statewide Transportation Model (MSTM)
[15]. The MSTM has 89 zones within D.C and uses the four-step transportation
planning process to determine flows between zone pairs for base year 2000. Starting
from landuse patterns, the models use trip generation, distribution, and mode choice.
Additionally, MSTM performs a temporal allocation for four di?erent time periods
during the day. Inputs from a coarser regional model that has visitor and long-
distance travel models are also incorporated.
For the purposes of this study, the total demand (without the mode choice
89
component) from the MSTM model provides input to determine flow potential of
the proposed shared-bicycle network. An ideal representation of the demand pro-
cess would include the transit-based flows along with utility functions that could be
used to estimate the fraction of automobile trips that are induced due to the im-
proved service from the presence of VSPs. However, three reasons preclude such a
detailed representation. First, the fraction of auto users that shift to VSPs requires
detailed stated preference information that is typically gleaned from surveys. Such
an analysis is beyond the resources available for this study and is outside the focus
of this research. Second, the response of users to new and innovative programs is
highly uncertain and di?cult to predict. In this light, the value of stated preference
surveys can be limited. Third, transit flows from MSTM are undergoing revisions
to address quality issues while this research was being conducted. Should better
estimates of demand be available, these can be easily incorporated.
Since the state-wide model includes long distance trips from outside the region,
five external zones were defined that serve as proxy zones for all external zones. Each
zone outside D.C. is assigned to one of the external zones. Only inter-zonal flows
that generate more than 20 trips/hour are considered. This corresponds to 1,000
origin-destination pairs. Each zone is associated with a centroid, where the flows
are assumed to originate. Each zone centroid is linked to the walk network to allow
flows to access transit services.
90
4.1.2.3 Transit Network
The transit component of the network is built from the Google Transit Feed
Specification (GTFS) data from WMATA. While the data includes stops, service,
and schedule information for all WMATA services in the region, computational issues
involved in modeling a large transit network preclude the use of the entire network.
Instead only the main transit services are considered including the metrorail lines.
For these services, travel times and frequencies are computed from the schedule
information. Each transit stop within D.C. is associated with a VSP candidate
station.
4.1.2.4 Walk and Bicycle Network
Transit access is considered through walk and bicycle modes. Based on avail-
able data for metro access, for regions within D.C., a large majority of transit based
trips are accessed by these two modes (see Figure 4.3). Transit and bicycle access
networks are based on the network data provided by the D.C. O?ce of Planning.
The network information includes information on bicycle lanes, travel times, and
metro entry points, thereby providing reasonably accurate estimates of access times.
The VSP candidate stations are located on the bicycle network and topologically
linked to the bicycle network.
91
4.2 Formulation
The problem faced by D.C. Department of Transportation (DDOT) is to deter-
mine locations of VSP stations that provide an e?cient and equitable configuration
so as to maximize the flow potential of the proposed system. The number of stations
to be located is known apriori; however their locations are to be determined. Unlike
the network design problem addressed in Chapter 2, the station capacities and base
vehicle inventories at each station are not considered for the following reasons. The
technology used by DDOT for the proposed system developed by Bixi is modular in
design. This implies that vehicle and slot inventories can be easily altered to better
match demand. Secondly, many of the program parameters (number of stations,
pricing, and technology) have already been determined by policy makers, so the
value of this case study is in determining the optimal locations for VSP stations.
Given (a) an existing transit configuration, (b) the bicycle and walk network,
(c) a set of candidate bicycle sharing stations, (d) equity and resource constraints
for DDOT, (e) behavioral assumption of users, and (f) fixed demand, DDOT seeks
an optimal VSP configuration that maximizes VSP flow potential.
Following the notation and development of Chapter 2, the VSP operator deci-
sion variable is x
i
,i? V
s
, which is a binary variable indicating if the bicycle sharing
station is located at node i and V
s
is the set of candidate sharing stations. Let p
represent the number of stations to be located and W be the set of wards in the
district (indexed by w). Define ?
iw
,w? W, i ? V
s
, as an indicator variable that is
set to one if the VSP station candidate i is located in ward w. Additionally, denote
92
w
min
as the minimum number of stations at each ward that represents an equitable
resource allocation.
The model presented in this chapter and used for the D.C. case study is a
variant of the BLNDP (Chapter 2, Section 2.2) and is denoted by BLNDP-DC.
At the upper level, VSP operators decide the optimal locations for VSP stations
subject to equity constraints and the number of stations. DDOT seeks to maximize
the potential shared-flow on the proposed bicycle sharing system. The lower level
model mirrors the one presented in Section 2.2. OD pairs are denoted by the set
K (indexed by k). A link from node i to j has an associated flow for each OD pair
denoted by v
ijk
. Additionally, each node of the transit network has an associated
quantity w
ik
, representing the total waiting time experienced by users in OD pair k
at node i. The flows (v) and waiting times (w) are continuous decision variables of
the lower level model.
The network design problem, BLNDP-DC, can be formulated as a bilevel
mixed-integer program as follows.
Upper level:
max
x,y,z
summationdisplay
k
summationdisplay
(i,j)?A
s
v
ijk
(4.1)
subject to
summationdisplay
i?V
s
x
i
= p (4.2)
summationdisplay
i?V
s
?
iw
x
i
? w
min
w ? W (4.3)
x
i
?{0, 1} (4.4)
93
Lower level:
min
u,v
summationdisplay
k
?
?
summationdisplay
(i,j)?A
c
ij
v
ijk
+
summationdisplay
i?V
w
ik
?
?
(4.5)
subject to
summationdisplay
j,(i,j)?A
v
ijk
?
summationdisplay
j,(j,i)?A
v
jik
= g
ik
i ? V, k ? K (4.6)
v
ijk
? f
ij
w
ik
(i, j) ? A \ A,k? K (4.7)
Mx
i
?
summationdisplay
k
v
ijk
(i, j) ? A
s
(4.8)
Mx
j
?
summationdisplay
k
v
ijk
(i, j) ? A
s
(4.9)
w
ik
? 0 i ? V, k ? K (4.10)
v
ijk
? 0(i, j) ? A, k ? K (4.11)
The BLNDP-DC is defined by the upper level objective for DDOT of max-
imizing VSP flow potential (4.1). Constraint (4.2) limits the number of bicycle
sharing stations chosen for construction to the maximum allowable number of sta-
tions, which is determined aprioriand is equal to 100. Constraints (4.3) ensure
that each ward in D.C. receives a minimum number of stations for the configuration
to be equitable. The upper level decision variables are restricted to be binary (4.4).
The lower level program is formulated from the perspective of users who seek
to minimize their travel time. Objective 4.5 minimizes the travel time and waiting
time for transit services for all OD pairs. Constraints (4.6) are the flow conservation
constraints. Constraints (4.7) relate waiting time at nodes to frequency of services on
transit links servicing that node. Constraints (4.8) permit flow on links originating
from a candidate VSP station only if a station exists. Similarly, constraints (4.9)
ensure that shared-bicycle flows terminate at a node only if a station exists at the
94
node. The flow and waiting variables are non-negative and continuous as required
by constraints (4.10)and(4.11).
This model di?ers from the one presented in Section 2.2 on the following as-
pects. The VSP configuration is simply defined by station locations. Therefore, the
upper level problem is solely a location problem. The station capacities and vehicle
fleet inventories are not considered in this case study for two reasons. First, accu-
rate estimates of demand were unavailable for this study (for reasons documented in
Section 4.1.2.2). Since the vehicle inventory and VSP station sizes serve as capacity
constraints in the BLNDP formulation, their inclusion could result in suboptimal
configurations in the face of ?true? demand. Therefore, this variant recognizes limi-
tations of the available data. Second, the Bixi technology is highly modular. This
implies that stations can easily be reconfigured to match observed demand levels.
The value of determining VSP station sizes and vehicle inventories is therefore lim-
ited. VSP station locations, on the other hand, are less flexible. Frequent users
expecting a bicycle sharing station at a particular location are likely to be surprised
if the entire station is relocated. Therefore, changes to VSP stations can only be
done judiciously. Instead of total VSP system flows, the BLNDP-DC problem mea-
sures flow potential that represents the market potential of the VSP system at a
particular configuration. Despite the fewer VSP configuration design variables, the
size of the network precludes the direct application of the exact solution method
presented in Section 2.3. A metaheuristic scheme for the solution of the problem is
presented next.
95
4.3 Genetic Algorithm Based Solution Method
A GA is proposed for the solution to the BLNDP-DC. The use of a GA is moti-
vated by the computational challenges that bilevel mixed-integer programs present.
In addition, the size of a real-world instance such as that involving the proposed
bicycle sharing program in D.C. make the exact solution method presented in Sec-
tion 2.3 impractical. Details of GAs have been comprehensively discussed elsewhere
[26, 27] and are omitted here. The basic concept in the context of optimization
involves a set of solutions (termed a population). Each solution is represented by a
vector (termed a chromosome) that encodes a solution to the problem. A solution
vector can be a vector of real numbers, a list of nodes, a path, or a bit string. The
representation of the solution is highly problem-dependent and can be determined
by the algorithm designer. The algorithm progresses by ranking the chromosomes
based on a fitness function. At each generation, chromosomes reproduce through a
variety of operators to create a new set of chromosomes. Chromosomes with good
fitness values are preferred to ones with poor fitness values. With subsequent gener-
ations, the chromosomes evolve towards the optimal solution. The exact nature of
operators to use, the proportion of the population to use them on, and the manner
in which newly create chromosomes are included or disregarded are left to the algo-
rithm designer. Some typical operators include elitism, whereby the best solution
(or solutions) are retained and directly carried over to the next generation; muta-
tion, which involves random changes to a chromosome; and crossover,wheretwo
chromosomes are combined to generate two or more new solutions. For constrained
96
programs, such as the upper-level program in BLNDP-DC, several techniques exist
to address the feasibility of solutions. The penalty method involves penalizing in-
feasible solutions to drive them to extinction. Alternatively, the operators can be
designed in a manner that no infeasible solution is generated. Finally, the algorithm
terminates when there is inadequate improvement in the fitness function.
The main idea behind the GA developed herein is that the two levels of the
bilevel program can be solved separately. The mutual dependence of the two levels
can be replaced by a scheme where the upper-level variables are generated externally
and the resulting flows recorded by solving the lower-level problem. The generation
of upper-level location variables can be performed in a genetic algorithmic frame-
work. The design vector is encoded as a genome and uses the lower-level transit
assignment based model to evaluate the fitness of the design vector. A design config-
uration that maximizes the shared-vehicle flow is considered as propogated through
the generations to yield an near-optimal configuration. The advantage of such an
approach is that the optimization component of the problem is reduced to solving
multiple linear programs (as opposed to MIPs), while the GA operators are used to
deal with the integrality constraints. Steps in developing a GA for the BLNDP-DC
are presented next.
4.3.1 Solution Representation
The chromosome is characterized simply by the location variables x and is
represented by a bit string. If the candidate VSP site is to be constructed, the
97
respective bit has the value 1, and 0 otherwise. The entire chromsome is a bit
string that has the length equal to the number of candidate sites. This represen-
tation is straightforward and allows for operates to verify feasibility of a particular
chromosome easily.
4.3.2 Initialization
The initial population is generated by solving multiple times the binary integer
program
max
summationdisplay
i
?
i
x
i
(4.12)
s.t. Constraints (4.2),(4.3),(4.4) ,
where ?
i
is a randomly generated coe?cient in the unit interval. By changing the
objective coe?cient, the value of each station varies randomly, thereby generating a
diverse set of starting solutions. By this method, all generated initial solutions are
feasible, since all constraints of the BLNDP-DC are explicitly considered.
4.3.3 Evaluation
To evaluate the fitness of a particular solution, the lower-level portion of the
BLNDP-DC, i.e. (4.5)?(4.11), needs to be solved. Note that when the design
vector x is fixed, the lower-level problem is a linear program that represents a
transit assignment model with side constraints to deal with shared-vehicle flows. The
evaluation step requires the solution of a linear program. If a network has m links,
n nodes, and k OD pairs, the number of continuous variables in this formulation is
98
k(n + m). If the network is large with many OD pairs, as is the case with the D.C.
network, this may result in millions of variables. For such cases, the problem can
be solved independently for each OD pair and the link flows on each link summed
across all OD pairs. This dissaggregated approach is employed for this case study.
For smaller networks, where the lower-level model is solved jointly for all OD pairs,
one additional insight aids in reducing run times. Since the design vector occurs only
on the right hand side of the lower-level model, the optimal basis from one function
evaluation can saved as a starting basis for the next evaluation after changing the
right hand side. For large networks this may be computationally advantageous
since new problem instances need not be recreated and few simplex iterations may
be needed to find the optimal solution.
4.3.4 Evolution
To evolve the population of solutions from one generation to the next, three
operators are utilitized. Methods for handling infeasibilities are presented, along
with the description of the operators.
Crossover: The crossover operator works on two solution strings jointly. A solu-
tion substring, representing the location configuration for a randomly selected ward,
is swapped between the two solutions. Essentially, a spatially proximate subset of
the VSP configuration is exchanged between the solutions. Two new solutions are
generated whose feasibility is not guaranteed, since the total number of stations in
the configuration may not equal the number of required stations p. To rectify po-
99
tential infeasibilities, two corrective procedures are initiated. For the new solution,
if the number of VSP stations exceeds the designated number of stations p,then
the required number of VSP stations are randomly dropped in a manner so as not
to violate the minimum number of stations in each ward w
min
.Ifthenumberof
VSP stations is less than the designated p, then the required number of stations is
randomly added to the solution string.
Mutation: The mutation operator is applied to one randomly selected solution in
the population. Two VSP candidate sites within a ward, one with and the other
without a VSP station, are selected and swapped. This operator e?ectively relocates
one VSP station from one candidate site to another. By selecting two candidate sites
within the same ward the total number of VSP stations within the ward remains
unchanged. Therefore, if the original solution is feasible, the result of the mutation
operator is also feasible.
Elitism: The elite, a small percentage of chromosomes that have the best fitness
function value, are directly moved to the subsequent generation.
4.3.5 Termination Criteria
Several criteria are considered jointly to terminate the algorithm. If any one
of the criterion are met, the procedure terminates. The maximum number of gen-
erations is limited to 100. The number of stall generations, defined as the number
of generations that are evaluated without an improvement in objective function, is
set to 5. The amount of time without improvement in objective function is set to
100
10, 000 seconds.
The proposed GA is implemented in MATLAB with the lower-level transit
assignment routines run using CPLEX 11.2 accessed through Java. Results and
analysis from the GA are presented next.
4.4 Analysis
The D.C. study area resulted in a network with 10, 380 nodes and 32, 402 links
as summarized in Table 4.4. Flows between 1, 000 OD pairs were considered. The
chosen OD pairs generate 20 trips/day or more. The metaheuristic solution method
described ran to termination in 41 generations. The procedure terminates since
there is no improvement in objective function over 5 generations. The values for
the best upper-level objective function and its corresponding lower-level objective at
each generation are shown in Figure 4.5. Note that at termination, the final solution
for the upper-level does not correspond to the best lower-level solution. A better
lower-level solution is found at generation 30 (Figure 4.5(b)) though this does not
lead to a better VSP configuration for the VSP operator. This demonstrates that
the objectives are not complementary and that what is best for the VSP operator
is not necessarily the best for individual system users. Additionally, the lower-level
objective represents the total travel and waiting time for all OD pairs and is not
weighted by demand for travel for that OD pair, which is taking into account only
at the upper level.
Next, the VSP configuration chosen by the GA upon termination is discussed.
101
Nodes Links
Type # Num Type # Num
VSP candidates 455 Bicycle network 28,502
Origins/destinations 89 Transit services 226
Transit stops 88 Transit access 454
Transit services 236 Walk network 2,226
Bike network 9514 VSP station connector 910
VSP-transit modal interface 84
Total 10,382 Total 32,402
Table 4.1: Summary of network component for Washington D.C.
0 5 10 15 20 25 30 35 40 45
4
4.5
5
5.5
6
6.5
7
7.5
8
? 10
5
(a) Upper-level objective function
0 5 10 15 20 25 30 35 40 45
7.7
7.75
7.8
7.85
7.9
7.95
? 10
4
(b) Lower-level objective function
Figure 4.5: Best solution at each generation of GA
102
The map of recommended VSP stations along with induced flows are presented in
Figure 4.6. Of the 100 stations, the near-optimal solution locates 19 stations at
metro stations for VSP integration with transit. In comparison, the base flows are
shown in Figure 4.7.
The improvements in travel times for users can be dissaggregated by zone
to see the e?ects of introducing the bicycle sharing system. Figure 4.8 shows the
average travel time reduction for trips by origin and destination zone with darker
zones indicating higher improvements.
In addition to the configuration of the bicycle sharing program, the inter-
station flows can be forecasted. The results of the lower-level model include path
information. All intermodal paths that use a shared-vehicle component are examined
and the origin and destination VSP stations are recorded. These statistics are
aggregated across all OD pairs. The result is a large matrix of inter-station flows. To
discern flow patterns, the matrix of flows is plotted as a circular diagram using Circos
[31]asshowninFigure4.9. The stations are represented along the circumference
of the diagram. The length of each arc represents the flow potential at each station
relative to the system. The bands between two stations are wider when the flow
potential is greater. Based on Figure 4.9 the flow potential at transit stations and
commuter hubs (such as Union station) are largest. This provides a key insight into
the configuration of VSP stations and the important of VSP-transit integration.
There are considerable asymmetries in flow potential from one station to another.
Table 4.2 shows the number of stations per ward associated with the solution.
The number of stations for each ward satisfies the upper-level equity constraints
103
Figure 4.6: Transit-based flows with VSP showing recommended VSP configuration
104
Figure 4.7: Transit-based flows without VSP
105
(a) for trips originating from zone (b) for trips terminating in zone
Figure 4.8: Average travel time reduction in minutes
Ward # VSP Stns
111
224
312
410
513
618
77
85
Table 4.2: Number of VSP stations by ward
(4.3). This equity constraint is binding only for Ward 8. Should the equity con-
straints be relaxed, it is beneficial to the VSP operator to relocation VSP stations
from within Ward 8 to other parts of the network. Therefore, the utilization of
the stations located in Ward 8 can be expected to be lower than in the rest of the
network.
106
Figure 4.9: Flow potential between designed stations
107
4.5 Conclusions
A bilevel mixed-integer program for the design of a bicycle sharing system
in Washington D.C. is developed. A GA, designed for the solution of large real-
world problem instances, is proposed. The metaheuristic solution recommends a
VSP system configuration that provides several insights. 19% of all stations are
located at metro stations indicating that optimal VSP configurations integrate with
existing transit facilities to maximize flows on the shared-vehicle segments. The
improvement in travel times as the result of VSP introduction is quantified. From
the case study analysis, the average travel time for a trip can be reduced by 3.55
minutes solely due to the use of the shared-bicycle program. In addition to the
e?ects on the environment of using a green mode, such information can potentially
be used for economic analysis to justify (or oppose) investment in shared-vehicle
systems. The analysis results also provide forecasts of flows between the proposed
stations. Since the flows are asymmetric, operational policies can be developed for
newly designed systems that can employ such information to maintain a desired
level-of-service.
Several extensions of this research warrant further investigation. Since the
genetic algorithm-based solution method separates the two levels of the bilevel pro-
gram, the lower-level linear program can be sustituted by computationally more
e?cient transit assignment procedures, such as one that employs a hyperpath formu-
lation (eg. [24, 35]). A new hyperpath procedure that accounts for the probabilistic
availability of vehicles at VSP stations can also be developed. Large flow asymme-
108
tries between proposed stations imply larger operational costs involved in relocating
bicycles. An alternate formulation could include the future operational costs into
the design process so that asymmetries are avoided. The proposed framework can
be placed in the context of the larger transportation problem by the inclusion of
various modal alternatives, mode choice functions, and congestion e?ects.
109
Chapter 5: V?elib? Case Study
5.1 Setting
The draft strategic plan of the United States (US) Department of Transporta-
tion (DOT) seeks to diversify the transportation landscape in the US [56] through
new livable community initiatives. With coordinated policies and investment strate-
gies across federal entities in housing and the environment, the strategic plan refo-
cuses the goal of providing safe, clean, and sustainable transport. Amongst several
initiatives that aim to reduce automobile dependence, the draft strategic plan also
places greater credence on pedestrian and bicycle modes. These federal level initia-
tives mirror the e?orts of some local DOT?s who grapple with increasing congestion
and mobility problems. Though transit has long been preferred by transportation
planners as a solution to congestion woes, data on traveler choices in the US shows
it to be a losing proposition with just 1.5% of all trips and 4.7% of all commute
trips [55]. A more recent approach to reduce automobile dependence in urban areas
is through the use of shared-vehicle programs.
Shared-vehicle programs involve a network of strategically located stations that
host a fleet of vehicles (bicycles, cars, or electric vehicles). In its most flexible form,
users making a trip can check out a vehicle close to their origin and return it close to
their destination. A shared-vehicle system can be construed as an individual mode
(for short trips), or as a vital segment of an intermodal route (for longer trips). In
the latter case, it serves as a vital ?last-mile? connection, the lack of which dissuades
110
potential riders. In this role, shared-vehicle systems increase transit accessibility.
They are strongly aligned with integrated transit systems explored in the past that
also aim to increase the catchment area of transit ([54, 42, 47]).
The emphasis on livability at the federal level, growing urban mobility prob-
lems at the local level, and the potential benefits of shared-vehicles in alleviating
some of the problems have lead to an increased interest in these systems for the U.S.
The widespread adoption of such innovations in the urban transport sector is hin-
dered to some extent by the uncertainty surrounding the response of the traveling
public to such systems. Though bicycle sharing systems exist in over 100 cities [12],
in the U.S. context, local transportation agencies and policymakers have limited
precedent to aid in developing such systems for their communities. Several papers
have studied the shared-vehicle system through the prism of marketing aspects [16],
policy considerations [49], environmental concerns [28], technology challenges [54],
growth trends [45], political issues [17], and user response [46]. The focus of this
paper is on system configuration and operational aspects. Using trip information
from the pioneering V?elib? bicycle sharing system in Paris, France, key system de-
sign aspects are highlighted. The system accounts for as many as 120,000 trips daily
[21] and is considered very successful.
For users, shared-bicycles o?er increased travel utility through flexibility and
cost. They are free to choose their departure time, routes, and destinations. Com-
pared to other modes, these systems are attractively priced. For the V?elib? system,
a nominal annual membership fee ($37.50 as of July, 2010) entitles a member to
and unlimited number of free trips that last 30 minutes or less for a year. To ensure
111
circulation, trips lasting longer are charged for every additional half hour accrued.
V?elib? also o?ers daily or weekly passes. Additionally, transit fare passes (Passe
Navigo)alsoworkontheV?elib?,though there are no preferential fares for transit
customers using V?elib?.
Increased flexibility of shared-bicycles places an exceptional logistical challenge
on V?elib? operators who need to ensure future short-term demand for vehicles and
parking slots are met. Since flow from one station to another is seldom equal to flow
in the opposing direction, the VSP fleet can become spatially imbalanced over time.
To meet near-future demand, operators must then redistribute vehicles between
stations to correct this asymmetry. Since future demand is not known exactly and
is highly variable (as shown in later sections), the challenges faced by operators is
amplified. There is limited literature on fleet management for shared vehicles. A
variety of approaches have been studied including approaches that employ simulation
[7], mixed-integer programming [29], and multi-stage stochastic programming with
recourse [22]. The mixed-integer chance-constrained program presented in Chapter
3 generates redistribution plans to meet a target reliability level. Should resources in
the system be insu?cient to meet the desired levels of reliability, the model generates
partial redistribution plans that utilize existing resources at lower levels-of-service.
While generating redistribution plans is not the focus of this chapter, the chance
constrained program provides a probabilistic characterization of the system. Such
a characterization quantifies key system performance measures that elucidates the
e?ciency of stations in dealing with uncertain demand. These measures allow for a
quantitative, reliability-based analysis that is performed on the V?elib? system.
112
In this chapter key attributes of the V?elib? bicycle sharing program pertain-
ing to system configuration and utilization are discussed. The public transit-V?elib?
connection is explored. Flow patterns based on observed data and the extent of
flow asymmetries between stations are presented. The demand for bicycles and
parking slots is characterized probabilistically. Using the chance-constrained fleet
management model from prior work [34] described above, several reliability-based
performance measures are quantified to provide insights into the workings of a suc-
cessful bicycle sharing system.
5.2 System Characteristics
As one of the largest bicycle sharing programs in the world, V?elib? has a fleet
of 20,000 bicycles spread across 1,450 stations. Figure 5.1 shows the map of all
stations in the Paris region. The operator of the system, JCDeaux, has provided
trip data for a four month period from 1st March, 2009 through 9th July, 2009. Due
to the proprietary nature of the dataset, the scale of some descriptive statistics are
not presented though patterns suggested by the data are highlighted. The system
logged 10,392,808 trips during this period, at an average of 79,945 trips per day.
The temporal distribution of trips over the course of a day is plotted in Figure 5.2,
showing that usage on a weekday follows familiar travel patterns with two peaks.
The morning rush hour is shorter in duration than the evening one. The weekend
use is void of commuter peaks and shows a di?erent pattern.
The system is designed for a quick turnaround of bicycles and the pricing
113
Paris
Bobigny
Romainville
Meudon
DrancyCourneuve
Alfortville
Colombes
Clamart
Villejuif
Arcueil
Bagneux
Montrouge
Ch?tillon
Vincennes
Clichy
Suresnes
Maisons-Alfort
Bois-Colombes
Aubervilliers
Stains
Saint-Ouen
Gennevilliers
Kremlin-Bic?tre
Neuilly-sur-Seine
Issy-les-Moulineaux
Ivry-sur-Seine
Gentilly
Lilas
Bagnolet
Vanves
Saint-Denis
Bezons
Noisy-le-Sec
Vitry-sur-Seine
Bourget
Argenteuil
Levallois-Perret
Asni?res-sur-Seine
Puteaux
Blanc-Mesnil
Malakoff
Charenton-le-Pont
Cachan
Cr?teil
Fontenay-aux-Roses
le Raincy
Pantin
Nanterre
Garenne-Colombes
Boulogne-Billancourt
Courbevoie
Fontenay-sous-Bois
Saint-Cloud
Saint-Mande
S?vres
Plessis-Robinson
Ile-Saint-Denis
Nogent-sur-Marne
Villeneuve-la-Garenne
Saint-Maur-des-Foss?s
Bondy
Pr?-Saint-Gervais
Montreuilt il
Paris
la Seine Rivi?re
la Marne Rivi?re
??A14
??N311
??N13
??D19
??D911
??A86
??A1
??D909
??N192
??A3
??N187
??D7
??N1
??N10
??A4
??A6-B
??N186
??A13
??A6
??N19
??N314
??N401
??A186
??A15
??A6-A
??N20
??D48
??A3
??A86
?E19
?E15
?E50
?E05
?E54
?E05
?E05
?E15
?E15
Ru
e d
e 
Ri
vo
li
Qu
a
i d
e
 Be
rc
y
R
u
e
 d
e
 la
 C
h
ap
e
lle
B
o
ul
ev
a
r
d S
a
in
t M
ic
h
e
l
Cours de
 Vincen
nes
Ru
e d
u Fa
ub
ou
rg
Qu
ai d
u Lo
uvr
e
R
u
e
 d
u
 Fa
ub
ou
rg
 -Sa
in
t 
M
a
rt
in
B
oul
ev
ar
d P
?r
iph
?r
iq
ue
B
o
u
le
vard Circulai
r
e
Q
u
a
i H
e
n
ry
 IV
Figure 5.1: Spatial distribution of V?elib? stations
structure discourages long term rentals. Figure 5.3(a) shows that majority of trips
are concluded within the alloted free time of 30 minutes. A subset of stations,
called V?elib?+ are located in areas of low bicycle accessibility (high altitude or in
the outskirts of Paris). The allotted maximum free travel time to these stations is
increased to 45 minutes to allow for the additional travel time. Figure 5.3(a) shows
98% of all trips are completed within 45 minutes. Therefore, the overage charge is
incurred by a marginal proportion of users.
5.2.1 Transit-V?elib? Interaction
The Paris M?etro is one of the busiest transit systems in the world. The system
consists of 16 underground lines and 300 stations. With a high density of stations
within the urban core of Paris, it o?ers good transit accessibility and high levels-
114
0 3 6 9 1215182124
0
2
4
6
8
10
12
14
16
? 10
4
Sun
Mon
Tue
Wed
Thu
Fri
Sat
Figure 5.2: Temporal distribution of trips
0 30 60 90 120 150
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
(a) Travel time
0 3000 6000 9000 1000 2000 5000 . 000 4000 7000
0
083
086
089
081
082
085
08.
084
087
3
(b) Travel distance
Figure 5.3: Cumulative distribution of travel characteristics
of-service. For transit users, the V?elib? o?ers a potential segment of transit-based
intermodal trips. The configuration of the metro system and V?elib? are juxtaposed to
evaluated the e?ectiveness of modal transfers between the two systems. Accessibility
is used as a proxy for ease with which users can transfer between the systems. The
nearest transit stop to each V?elib? station is determined. Figure 5.4 shows the
distribution of distances of V?elib? stations and their corresponding closest transit
stops. With the majority of the V?elib? stations being well within the pedestrian
catchment area for transit (the zone defined by the maximum distance a transit
115
0 200 400 600 800 1000 1200 1400
0
5
10
15
20
25
30
35
Figure 5.4: Distribution of distances from V?elib? stations to closest transit stops
user would walk to reach transit services) considered to be around 400 meters, V?elib?
appears to be deeply coupled with the Paris M?etro. By evaluating the utilization
of V?elib? stations for the study period, the e?ectiveness of placing bicycle sharing
stations close to transit stops hypothesized herein can be confirmed.
From the trip data, the stations are ranked based on utilization. The top
20 ranked stations are reported in Table 5.1 for incoming flows and Table 5.2 for
outgoing flows. It can be seen that highly ranked V?elib? stations typically have
spatially proximate transit stops and services. The exception to the rule being the
V?elib? station ?Francs Bourgeois? located in the Marais district that houses several
hotels.
Further evidence of the importance of the close coupling of transit and V?elib?
is shown in Figure 5.5. Stations are represented as segments along the circumference
with the size of the segment proportional to flows (both incoming and outgoing) han-
dled by a particular station. Therefore, a large segment implies a V?elib? station with
116
Rank V?elib? station Closest metro stop (line) Distance (m)
1 BEAUBOURG RAMBUTEAU Rambuteau (m11) 139.87
2 FAUBOURG DU TEMPLE
PLACE DE LA REPUBLIQUE
Republique (m3-5-8-9-11) 118.59
3 SAINT PAUL PAV
?
EE Saint-Paul (m1) 79.00
4 QUAI DE LA LOIRE Jaures (m2-5-7bis) 61.06
5 HOTEL DE VILLE Hotel de Ville (m1-11) 84.83
6 LES HALLES SAINT EUSTACHE Chatelet - Les Halles (rA-
B-D) /m(1-4-7-11-14)
173.93
7 TRAVERSIERE Ledru-Rollin (m8) 97.69
8 BASTILLE RICHARD LENOIR Bastille (m1-5-8) 59.35
9 FAIDHERBE CHALIGNY Faidherbe - Chaligny (m8) 132.59
10 TURENNE BRETAGNE Filles du Calvaire (m8) 67.32
11 FRANCS BOURGEOIS Saint-Paul (m1) 443.80
12 BOULEVARD VOLTAIRE Voltaire (m9) 131.04
13 TOLBIAC NATIONALE Olympiades (m14) 55.92
14 BASTILLE Bastille (m1-5-8) 81.18
15 LOBAU Hotel de Ville (m1-11) 83.84
16 RIVOLI SAINT DENIS Chatelet (m1-4-7-11-14) 145.02
17 GARE DE LYON VAN GOGH Gare de Lyon (m1-14)(rA-
D)
44.68
18 CROZATIER Ledru-Rollin (m8) 113.67
19 JACQUES BONSERGENT Jacques Bonsergent (m5) 138.03
20 ODEON QUATRE VENTS Odeon (m4-10) 26.13
Table 5.1: Top 20 V?elib? stations with highest inflows with distance to closest transit
stop
high utilization. Figure 5.5 shows all inter-station flows that average 10 trips/day
or more. The major V?elib? stations, as depicted by the size of the segment on the
circumference, can be seen to have close correspondence to transit stops (denoted
by ?M?). Though not presented here, the data also reveals the existence of secondary
V?elib? stations that serve as a bu?er to major ones when they are full.
5.2.2 Flow Asymmetry at Stations
By completing trips from one station to another, users shift bicycle inventory
from one portion of the network to another. For operators, this presents a logisti-
117
Figure 5.5: Average inter-station flows exceeding 10 trips/day highlighting V?elib?
stations within 100 meters of M?etro station
118
Rank V?elib? station Closest metro stop (line) Distance (m)
1 BEAUBOURG RAMBUTEAU Rambuteau (m11) 139.87
2 FAUBOURG DU TEMPLE
PLACE DE LA REPUBLIQUE
Republique (m3-5-8-9-11) 118.59
3 SAINT PAUL PAVEE Saint-Paul (m1) 79.00
4 QUAI DE LA LOIRE Jaures (m2-5-7bis) 61.06
5 HOTEL DE VILLE Hotel de Ville (m1-11) 84.83
6 HALLES SAINT EUSTACHE Chatelet - Les Halles (rA-
B-D) /m(1-4-7-11-14)
173.93
7 TRAVERSIERE Ledru-Rollin (m8) 97.68
8 BASTILLE RICHARD LENOIR Bastille (m1-5-8) 59.35
9 FAIDHERBE CHALIGNY Faidherbe - Chaligny (m8) 132.59
10 TURENNE BRETAGNE Filles du Calvaire (m8) 67.32
11 FRANCS BOURGEOIS Saint-Paul (m1) 443.80
12 BOULEVARD VOLTAIRE Voltaire (m9) 131.04
13 TOLBIAC NATIONALE Olympiades (m14) 55.91
14 BASTILLE Bastille (m1-5-8) 81.18
15 GARE DE LYON VAN GOGH Gare de Lyon (m1-14)(rA-
D)
44.68
16 RIVOLI SAINT DENIS Chatelet (m1-4-7-11-14) 145.02
17 LOBAU Hotel de Ville (m1-11) 83.83
18 CROZATIER Ledru-Rollin (m8) 113.67
19 JACQUES BONSERGENT Jacques Bonsergent (m5) 138.03
20 ODEON QUATRE VENTS Odeon (m4-10) 26.13
Table 5.2: Top 20 V?elib? stations with highest outflows with distance to closest
transit stop
cal problem, since they must initiate corrective actions to redistribute bicycles to
stations to ensure that short-term future demands are met. It could potentially be
cost-prohibitive to satisfy all demand needs, thus operators need to maintain ade-
quate inventories such that levels-of-service are maintained. For policymakers and
transportation agencies developing new systems, the extent of operational cost and
associated personnel is di?cult to forecast. The purpose of this section is to high-
light the extent of flow asymmetries in the V?elib? system. V?elib? operates several
teams for redistribution and maintenance activities, including a team on barges that
move up and down the river Siene.
119
The general mobility patterns of urban residents are reflected in the use of
the V?elib? system. There is considerable directionality in movement of bicycles in
both the spatial and temporal dimensions. As an example, Figure 5.6 highlights
the sources and destinations of V?elib? tra?c for a single V?elib? station during two
di?erent time periods. The width of connecting segments represents the flow as
a proportion of total incoming (or outgoing) flows for that time period. Several
observations are worth noting. By comparing Figures 5.6(a) and 5.6(b), inflows and
outflows for the same period are from di?erent stations. Figures 5.6(c) and 5.6(d)
show flows during the evening rush hour with flows from a greater variety of stations
than in the morning. Figure 5.6(d) also shows two heavily utilized routes denoted
by the two thick ribbons connect the segments.
5.3 Fleet Management
To match flexibility of other modes, shared-vehicle programs transfer control
of bicycles to users. This places exceptional logistical challenges on operators who
must ensure demand in the near future is met. For the shared-vehicle users, good
service is defined by an adequate stock of vehicles at the intended stations of origin
and adequate parking slots at the intended destination stations. Thus users seek two
types of resources from the system. As shown in the previous section, flow from one
station to another is seldom equal to flow in the opposing direction and the bicycle
fleet can become spatially imbalanced. To meet near-future demand, operators must
then redistribute vehicles to correct this asymmetry. Redistribution plans can be
120
(a) Average 8-9am inflows (b) Average 8-9am outflows
(c) Average 4-5pm inflows (d) Average 4-5pm outflows
Figure 5.6: Flows to and from Les Halles V?elib? station
121
based on historical information for services at particular stations. In the event of a
?stock out? when there is an absence of either bicycles or spaces, users need to seek
out the nearest alternate station with su?cient resources. This process involves a
loss in level-of-service, since travel times are increased and repeated stock-outs harm
the perception of the system.
The two types of demand for bicycles and parking slots are related. The
increase in one implies a reduction in the other. Users checking out bicycles free up
parking spaces for other users to return them. Therefore, at the station-level, the
task of the operator is to maintain the vehicle inventory within acceptable limits.
Too few bicycles leads to unserviced demand as does having too many bicycles at a
station. During the process of redistribution, resources from stations having excess
bicycles are transferred to those approaching the ?stock-out? condition. This action
balances the fleet across all the stations in the network.
Three aspects limit the extent to which redistribution can be carried out. The
task of redistributing vehicles implies operational costs for the operator. Redistribu-
tion activities can only be done judiciously to minimize operational costs. Secondly,
during high-demand scenarios, the resources in the system could potentially be in-
adequate to meet future demand. No amount of redistribution can address the
shortfall. In these cases, there is a drop in system performance. Therefore, the
operator?s goal is to meet most future demand scenarios.
To determine what constitutes most demand scenarios, the demand for ser-
vices is probabilistically characterized based on historical information. This allows
operators to quantify the state of the system in a reliability measure and allows the
122
operator to set target levels-of-service that need to be met using redistribution. The
development presented herein employs concepts from Chapter 3. Next, the demand
processes are described, followed by the system representation and a brief summary
of the analytical framework used.
5.3.1 Probabilistic Characterization of Demand
Demand processes at each V?elib? station are for bicycles and spaces. It is
assumed that at a particular station demand for bicycles is independent of demand
for spaces. The operator is interested in knowing the probability distribution of
the number of vehicle and parking slot requests for a future time period, termed
the planning period. Based on the observed trip patterns, the aggregate resource
requests at each station is tabulated. Note that no assumptions are made on trip
characteristics determined by users (origins, destinations, and duration). Several
distributions were fitted on the observed data on bicycle check outs and returns at
each station and the demand process is closest matched by the negative binomial
distribution. This distribution is related to the Poisson process, though it exhibits
higher dispersion. The Poisson distribution requires the mean and variance to be
equal. Negative binomial distribution has a variance that is larger than the mean.
This implies that there is high variability in demand for vehicles and spaces.
If a variate x follows the negative binomial distribution, then the probability
of x taking a value k is given by
123
P(x = k)=
parenleftbigg
r + k ? 1
k
parenrightbigg
p
r
(1 ? p)
k
, (5.1)
where r and p are the parameters of the distribution. This is denoted by x ?
NB(r, p).
The two demand processes exhibit duality so the random variable of interest
is the di?erence of the two demand processes. The inherent assumption is that
vehicle returns and withdrawals cancel each other out for short planning periods.
An ?aggregate? demand random variable is defined to be the di?erence of demand for
vehicles and demand for spaces. This encodes both types of demand in one random
variable. When the aggregate demand is positive, then there is greater number
of vehicle requests than returns. The redistribution plan could potentially direct
bicycles to the station to meet this higher demand. When the aggregate demand
is negative, there are more requests for spaces. The operator can free up parking
capacity by moving bicycles out of the station to other locations.
If x is a random variable that represents the number of vehicle requests, and y
is a random variable that represents the number of return requests, then aggregate
demand z is defined as z = x?y. z follows the distribution defined by the di?erence
of two negative binomial variates. It can be shown that if x ? NB(r
x
,p
x
)and
y ? NB(r
y
,p
y
), then the distribution of z = x ? y can be expressed as
P(z = k)=
?
?
?
?
?
?
?
p
r
x
x
p
r
y
y
(1 ?p
x
)
k
(r
x
)
k
k!
F(r
x
+ k,r
y
; k +1;(1? p
x
)(1? p
y
)) k ? 0
p
r
x
x
p
r
y
y
(1 ?p
y
)
k
(r
y
)
|k|
|k|!
F(r
x
,r
y
+ |k|;|k|+1;(1? p
x
)(1? p
y
)) k<0
(5.2)
124
where
F(?,?; ?; z)=
?
summationdisplay
0
(?)
n
(?)
n
(?)
n
z
n
n!
(5.3)
is the hypergeometric function [6]and(a)
n
=?(a + n)/?(a). There is no known
closed-form solution for the inverse of this four parameter distribution, which allows
for the computation of reliability. Therefore, simulation is employed to calculate
the distribution. Figure 5.7 shows the fitted demand distribution for vehicles and
spaces along with the simulated four parameter di?erence distribution for selected
stations. In comparison with the Singapore car sharing system presented in Section
3.5, where the aggregate demand distribution was found to be Skellam distributed,
the four parameter distribution for V?elib? has greater dispersion. This indicates
higher demand variability.
5.3.2 Framework
Following the concepts presented in Chapter 3,theV?elib? system is depicted
as a network of n stations represented as nodes (indexed by i) and all links between
all station pairs (a complete graph in graph theory parlance). Each V?elib? station
i is associated with a ?aggregate demand? random variable, denoted by ?
i
,anda
capacity, denoted by c
i
.Asshownabove,the?
i
random variable can be described
by a four parameter distribution. At any given point in time, the system operator
is aware of the inventory of bicycles at each station, denoted by v
i
.Theinventory
of parking spaces is correspondingly c
i
?v
i
.
The operator considers near-term future demand during the planning period
125
?30 ?20 ?10 0 10 20 30
0
0.1
0.2
Station: 8032 Time : 8 ? 9 am
 
 
Vehicles
Spaces
Difference
?30 ?20 ?10 0 10 20 30
0
0.1
0.2
Station: 8032 Time : 4 ? 5 pm
 
 
Vehicles
Spaces
Difference
?30 ?20 ?10 0 10 20 30
0
0.1
0.2
Station: 11012 Time : 8 ? 9 am
 
 
Vehicles
Spaces
Difference
?30 ?20 ?10 0 10 20 30
0
0.1
0.2
Station: 11012 Time : 4 ? 5 pm
 
 
Vehicles
Spaces
Difference
?30 ?20 ?10 0 10 20 30
0
0.1
0.2
Station: 14001 Time : 8 ? 9 am
 
 
Vehicles
Spaces
Difference
?30 ?20 ?10 0 10 20 30
0
0.1
0.2
Station: 14001 Time : 4 ? 5 pm
 
 
Vehicles
Spaces
Difference
?30 ?20 ?10 0 10 20 30
0
0.1
0.2
Station: 11025 Time : 8 ? 9 am
 
 
Vehicles
Spaces
Difference
?30 ?20 ?10 0 10 20 30
0
0.1
0.2
Station: 11025 Time : 4 ? 5 pm
 
 
Vehicles
Spaces
Difference
?30 ?20 ?10 0 10 20 30
0
0.1
0.2
Station: 16013 Time : 8 ? 9 am
 
 
Vehicles
Spaces
Difference
?30 ?20 ?10 0 10 20 30
0
0.1
0.2
Station: 16013 Time : 4 ? 5 pm
 
 
Vehicles
Spaces
Difference
Figure 5.7: Theoretical demand distribution for selected V?elib? stations
126
(assumed here to be one hour). For this period period, the probability that the
current number of bicycles at a station i, termed vehicle inventory, and the number
of free parking slots, termed the spaces inventory, can satisfy demand during the
planning period can be written as
p
i
= P(?(c
i
? v
i
) ? ?
i
? v
i
). (5.4)
Here, p
i
is termed the component-level reliability, since it measures the reliability
level at the V?elib? station level. Figure 5.8 shows the component reliability for all
bicycle inventory levels at selected stations. If demands for bicycles and spaces are
assumed to be independent across stations, the systemwide reliability measure can
be expressed as
p = P(?(c
i
? v
i
) ? ?
i
? v
i
,i=1,...,n)=
n
productdisplay
i=1
p
i
. (5.5)
The operator can quantitatively set target levels-of-service using the mea-
sure p for systemwide reliability, or p
i
for component level measures. With a large
like V?elib?, p can be very small, since it involves the product of component-level
measures. In this case, an average component reliability measure can be used to
aggregate component-level measures.
To generate redistribution plans for bicycles, these component-level measures
can be used to set the desired number of bicycles at all stations. If the operator
defines a systemwide reliability level to be met, then the component-level measures
can be derived using several techniques outlined in Chapter 3. The most straight-
forward approach involves the equal apportionment of failure. In this approach,
127
the acceptable failure rate is divided amongst all stations. Other methods first de-
termine an optimal set of component-level reliabilities, such that the systemwide
reliability is met. To generate redistribution plans, an optimization model is used
to relocate bicycles from stations with excess bicycles to ones with inadequate stock.
Bicycles can also be relocated to free up parking slots should the number of bicycles
at a station be too high.
The target level-of-service is constrained by physical capacity. There are de-
mand scenarios that cannot be met with any amount of redistribution. The desired
level of service needs to be relaxed and partial redistribution carried out that max-
imizes the utilization of available resources. V?elib? stations with low capacity or
high demands that persistently do not meet target reliability levels can be subject
to capacity improvements.
5.4 Analysis
The component level reliability for selected stations is plotted in Figure 5.8.
At stations with low demand levels such as station 15103, a wide range of bicycle
stocks have high reliability. For the V?elib? station 1008, during the busy period
of 4-5pm, at no level of bicycle inventory is teh component reliability greater than
0.5. This implies that capacity limitations exist at this station. Note that even
when stations are empty the component reliability is non-zero since the station still
services demands for spaces.
Redistribution plans for the V?elib? system are generated for various systemwide
128
(a) 8-9am (b) 4-5pm
Figure 5.8: Component reliability p
i
for selected stations and two planning periods
reliability levels p. Over a period of five days, redistribution is considered for two
planning periods, one from 8-9am and the other from 4-5pm. Table 5.3 summarizes
the component reliability measures for two cases when redistribution is performed
and when it is not. Redistribution is shown to improve the average component
reliability in every simulated instance. Additional insights can be gleaned from the
model as well by assessing the infeasibility of location stations in handling demand.
Stations that experience persistent low levels-of-service can be identified, and the
extent of capacity improvements needed can be assessed. Figure 5.9 shows that the
majority of stations have su?cient capacity to handle demand uncertainty. However,
some key stations require capacity enhancements.
5.5 Conclusions
An empirical analysis of the pioneering V?elib? bicycle sharing system in Paris,
France is presented. The analysis provides key insights on the functioning of such
129
Figure 5.9: Stations with persistent shortages
130
Improvement in
Average p
i
Minimum p
i
avg(p
i
) through
Day Period p No Redistr. With Redistr. No Redistr. With Redistr. redistribution
1 8-9am 0.5 0.78 0.844 0.237 0.254 0.064
0.7 0.78 0.84 0.237 0.254 0.06
0.8 0.78 0.836 0.237 0.254 0.056
0.9 0.78 0.831 0.237 0.254 0.05
4-5pm 0.5 0.85 0.938 0.054 0.371 0.088
0.7 0.846 0.932 0.054 0.338 0.086
0.8 0.844 0.929 0.054 0.338 0.085
0.9 0.841 0.922 0.054 0.338 0.081
2 8-9am 0.5 0.795 0.838 0.254 0.254 0.043
0.7 0.791 0.831 0.254 0.254 0.04
0.8 0.788 0.827 0.254 0.254 0.039
0.9 0.784 0.82 0.251 0.279 0.037
4-5pm 0.5 0.847 0.929 0.054 0.366 0.083
0.7 0.844 0.922 0.054 0.356 0.078
0.8 0.84 0.917 0.054 0.356 0.077
0.9 0.834 0.909 0.054 0.356 0.074
3 8-9am 0.5 0.796 0.824 0.269 0.279 0.028
0.7 0.792 0.819 0.269 0.279 0.026
0.8 0.789 0.814 0.269 0.279 0.025
0.9 0.784 0.807 0.269 0.279 0.023
4-5pm 0.5 0.838 0.908 0.267 0.371 0.07
0.7 0.835 0.9 0.267 0.356 0.065
0.8 0.832 0.895 0.267 0.338 0.063
0.9 0.828 0.886 0.267 0.338 0.058
4 8-9am 0.5 0.794 0.814 0.237 0.279 0.02
0.7 0.79 0.81 0.237 0.279 0.02
0.8 0.787 0.806 0.237 0.279 0.019
0.9 0.781 0.798 0.237 0.279 0.017
4-5pm 0.5 0.833 0.885 0.054 0.371 0.051
0.7 0.831 0.878 0.054 0.356 0.047
0.8 0.829 0.872 0.054 0.356 0.043
0.9 0.822 0.864 0.054 0.356 0.042
5 8-9am 0.5 0.789 0.799 0.237 0.279 0.01
0.7 0.785 0.798 0.237 0.279 0.012
0.8 0.783 0.796 0.237 0.279 0.013
0.9 0.781 0.795 0.237 0.279 0.014
4-5pm 0.5 0.824 0.872 0.338 0.371 0.048
0.7 0.824 0.866 0.338 0.356 0.042
0.8 0.825 0.863 0.338 0.356 0.038
0.9 0.824 0.856 0.338 0.356 0.032
Table 5.3: Summray of V?elib? simulation results over five days and two time periods
131
systems and serves to inform policy makers in other urban communities wanting
to explore bicycle sharing systems. This paper studies the V?elib? system from sev-
eral aspects, including system characteristics, utilization patterns, the connection
between public transit and bicycle sharing systems, and flow imbalances between
stations.
The close coupling of transit stops with the bicycle sharing system corresponds
with higher utilization of bicycle sharing. This confirms the hypothesis that inter-
modal trips with shared-vehicle segments provide value addition for users. Policies
that seek to integrate the two systems are, therefore, profitable. Examples of such
policies include seamless fare collection, preferential fares for transit users, and prime
location of shared-bicycle stations.
From the operator?s perspective, the V?elib? system is shown to have highly
variable demand. By characterizing the demand probabilistically, the target relia-
bility levels at the component or system level can be set and the required fleet and
parking slot capacity calculated. Redistribution plans are generated based on these
target levels showing related improvement in component-level reliability.
132
Chapter 6: Conclusions
This dissertation proposes models and associated algorithms for the design
and operation of shared-vehicle systems. Using the developed framework, three real-
world case studies were conducted to analyze system characteristics and demonstrate
the e?cacy of proposed models and methods. The analysis of these real-world sys-
tems provides vital insights for policy makers and transportation agencies wanting
to develop shared-vehicle programs for their communities.
A strategic network design model is developed that takes the form of a bilevel
mixed-integer program. The problem is solved using exact and heuristic approaches
for synthetic networks and a large real-world case study for Washington, D.C. The
output of the model is the optimal design configuration for shared-vehicle systems.
For the Washington, D.C. case, 19% of all shared-vehicle stations are located at
candidate sites that are at transit stops. Thus, policies that push transit-VSP
integration are profitable. Such policies could include seamless fare collection, prime
location of shared-vehicles within the confines of transit stops, and preferential fares.
The average transit-based trip within Washington, D.C. experiences a reduced travel
time of 3.55 minutes solely due to the introduction of the shared-vehicle system.
At the operational level, a fleet management model that generated anticipative
fleet redistribution plans is formulated. Two exact solution techniques are also
proposed for its solution. The model characterizes demand probabilistically and
serves to generate least cost fleet relocation directives that meet most future demand
scenarios. Using a car sharing system in Singapore, the e?cacy of the formulated
133
model, and the e?ciency of the solution methods is demonstrated. The value of
accounting for inherent stochasticities is also quantified. Using the same framework
for a large-scale bicycle sharing system in Paris, France, several key insights on the
nature of system configuration, utilization patterns, and capacity bottlenecks are
identified. The system maintains high levels of service at most locations.
6.1 Benefits to Society
With growing urban congestion problems, rising transportation costs, and a
degrading environment, changes in the way transportation resources are supplied
and consumed are imminent. This thesis explores one innovation in shared-vehicle
systems. As urban communities around the globe are beginning to consider and
implement these shared vehicle systems as viable options for reducing congestion,
several cities in the US have started, or are planning to start, car sharing and bicy-
cle sharing programs, most notably in Washington, D.C., Boston and Denver. This
follows the success of similar programs internationally in cities like Paris, Barcelona
and Montreal. While shared-vehicle systems alone will not solve urban congestion
woes, they have a place in the basket of mobility solutions for the future. Using
optimization tools presented herein, such systems can o?er a value added proposi-
tion to users through high levels-of-service. As demonstrated in the V?elib? system
analysis, shared-vehicle systems are closely coupled with transit. This intermodal
combination presents an economical and sustainable solution.
134
6.2 Extensions
The conducted research opens avenues in several promising directions. An
economic analysis based on system costs, economic benefit to users and society in
terms of reduced travel times and environmental impacts can provide vital input
for policy makers. Such an analysis could use principles from network economics to
evaluate the scale at which such programs should be implemented. In this respect,
the shared-vehicle system is similar to other networked technologies, like commu-
nication devices or social networks, where the value of the system increases when
there are greater numbers of users and stations. A greater number of users would
imply more circulation of vehicle stock. The addition of a single shared-vehicle
station increases the value of all other shared-vehicle stations, since the users have
more destination choice. Equilibrium e?ects incorporating rational user behavior
also presents a promising direction.
The role of pricing in attracting and retaining a user base can be explored.
Given the high cost of automobile ownership, the key question faced by the system
operator is what to charge users. Models and methods could include joint system
design and pricing of a shared-vehicle system, variable pricing as a demand man-
agement tool, or directional pricing to o?set operator redistribution costs by having
the users perform redistribution.
From the methodological perspective, several extensions can be the focus of fu-
ture research. At the strategic level, the model assumptions can be relaxed to better
represent the existing demand and supply processes. For example, the fixed-demand
135
assumption can be relaxed to demand that varies as a function of level-of-service.
Congestion e?ects on transit and shared-vehicle links can be incorporated. The use
of travel times can be replaced by econometric functions of utility that capture var-
ious attributes that users consider in mode and route choice. The strategic model
can use the expected value of future operational costs in designing the system. Al-
ternate solution methods for solving large-scale instances can be developed. These
techniques could use computationally e?cient methods that employ hyperpaths.
The operational level model can be extended to include multi-period relo-
cation costs. Stochastic programs with recourse present an alternate model form
for multiple period extension, where current redistribution decisions are the first
state variables, and the future redistribution decisions are recourse variables. Re-
distribution costs at the present period can be reduced if the operator accounts for
uncertainty from future periods. A variant of the problem could consider the vehicle
routing of redistribution teams through the system. Such work would build on priod
advances in the pick-up and drop-o? problem in the literature. An online version
of the model would trigger redistribution requests by constantly monitoring system
state.
As a sustainable solution to urban mobility that uses existing proven technolo-
gies, shared-vehicle programs will play a greater role in the years to come.
136
References
[1] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin. Network flows: theory, algorithms,
and applications. Prentice-Hall, Englewood Cli?s, NJ, 1993.
[2] C. Audet, P. Hansen, B. Jaumard, and G. Savard. Links between linear bilevel
and mixed 0?1 programming problems. Journal of Optimization Theory and
Applications, 93(2):273?300, 1997.
[3] A. Awasthi, D. Breuil, S. Singh Chauhan, Michel Parent, and T. Reveillere.
A Multicriteria Decision Making Approach for Carsharing Stations Selection.
Journal of Decision Systems, 16(1):57?78, 2007.
[4] A. Awasthi, S.S. Chauhan, X. Hurteau, and D. Breuil. An Analytical Hierarchi-
cal Process-based decision-making approach for selecting car-sharing stations
in medium size agglomerations. International Journal of Information and De-
cision Sciences, 1(1):66?97, 2008.
[5] A. Balakrishnan, TL Magnanti, A. Shulman, and RT Wong. Models for plan-
ning capacity expansion in local access telecommunication networks. Annals of
Operations Research, 33(4):237?284, 1991.
[6] O.E. Barndor?-Nielsen, D.G. Pollard, and N. Shephard. Discrete-valued Levy
processes and low latency financial econometrics. Economics Series Working
Papers, 2010.
[7] M. Barth and M. Todd. Simulation model performance analysis of a multiple
station shared vehicle system. Transportation Research Part C, 7(4):237?259,
1999.
[8] M. Barth, M. Todd, and L. Xue. User-Based Vehicle Relocation Techniques
for Multiple-Station Shared-Use Vehicle Systems. In Transportation Research
Board Annual Conference CD-ROM, Washington, DC, 2004.
[9] P. Beraldi, ME Bruni, and D. Conforti. Designing robust emergency medical
service via stochastic programming. European Journal of Operational Research,
158(1):183?193, 2004.
[10] P. Beraldi and A. Ruszczy?nski. The probabilistic set-covering problem. Oper-
ations Research, pages 956?967, 2002.
[11] R.T. Berger and S. Raghavan. Long-distance access network design. Manage-
ment Science, 50(3):309?325, 2004.
[12] F. Britton. Public bike system inventory, 2008.
[13] L. Brotcorne, Martine Labbe, P. Marcotte, and Gilles Savard). Joint design and
pricing on a network. Operations Research, pages 1104?1115, Sept-Oct 2008.
137
[14] B. Colson, P. Marcotte, and G. Savard. An overview of bilevel optimization.
Annals of Operations Research, 153(1):235?256, 2007.
[15] Pat Costinett, Mayank Jain, Rolf Moeckel, Erin Wardell, and Tara Weidner.
Maryland statewide transportation model user?s guide: Draft report. Technical
report, Maryland DOT State Highway Administration, May 2009.
[16] Ian Skinner Dawn Haines. The marketing of mobility services. Technical report,
Institute for European Environmental Policy, 2005.
[17] P. DeMaio and J. Gi?ord. Will smart bikes succeed as public transportation in
the United States? Journal of Public Transportation, 7(2):1?15, 2004.
[18] D. Dentcheva, A. Pr?ekopa, and A. Ruszczynski. Concavity and e?cient points
of discrete distributions in probabilistic programming. Mathematical Program-
ming, 89(1):55?77, 2000.
[19] D. Dentcheva, A. Prekopa, and A. Ruszczy?nski. Bounds for probabilistic integer
programming problems. Discrete Applied Mathematics, 124(1-3):55?65, 2002.
[20] EPA. Greenhouse gas emissions from the transportation sector 1990-2003. Tech-
nical Report EPA 420 R 06 003, O?ce of Transportation and Air Quality,
Environmental Protection Agency, March 2006.
[21] Steven Erlanger. A new fashion catches on in Paris: Cheap bicycle rentals. The
New York Times, July 13 2008.
[22] W.D. Fan, R.B. Machemehl, and N.E. Lownes. Carsharing: Dynamic Decision-
Making Problem for Vehicle Allocation. Transportation Research Record: Jour-
nal of the Transportation Research Board, 2063(-1):97?104, 2008.
[23] D. Friedman. Public Vehicle Rental System: Determination of Feasibility. In
Selected Proceedings of a Conference on Methods and Concepts of Forecasting
Travel Demands, pages 49?74, 1972.
[24] G. Gallo, G. Longo, and S. Pallottino Sang. Directed hypergraphs and appli-
cations. Discrete Applied Mathematics, 42(2-3):177?201, 1993.
[25] Josie Garthwaite. Exxon, electrovaya roll out electric car sharingslowly. Reuters
New Agency, June 23 2009.
[26] D.E. Goldberg. Genetic algorithms in search, optimization, and machine learn-
ing. Addison-wesley Reading Menlo Park, 1989.
[27] J.H. Holland. Adaptation in natural and artificial systems.MITpressCam-
bridge, MA, 1992.
[28] R. Katzev. Car sharing: A new approach to urban transportation problems.
Analyses of Social Issues and Public Policy, 3(1):65?86, 2003.
138
[29] A.G.H. Kek, R.L. Cheu, Q. Meng, and C.H. Fung. A decision support system
for vehicle relocation operations in carsharing systems. Transportation Research
Part E, 45:149?158, 2009.
[30] RF Kirby, KU Bhatt, MA Kemp, RG McGillivray, and M. Wohl. Para-transit:
neglected options for urban mobility. Technical report, PB-234320, Urban In-
stitute, 2100 M Street NW, Washington, DC 20037; Urban Inst., Washington,
DC (USA), 1974.
[31] M. Krzywinski, J. Schein,
?
I. Birol, J. Connors, R. Gascoyne, D. Horsman,
S.J. Jones, and M.A. Marra. Circos: an information aesthetic for comparative
genomics. Genome research, 19(9):1639?1645, 2009.
[32] Angelica Lozano and Giovanni Storchi. Shortest viable path algorithm in mul-
timodal networks. Transportation Research Part A, 35:225?241, 2001.
[33] P. Marcotte, S. Nguyen, and A. Schoeb. A strategic flow model of tra?c
assignment in static capacitated networks. Operations Research, 52(2):191?212,
2004.
[34] Rahul Nair and Elise Miller-Hooks. Fleet management for vehicle sharing op-
erations. Transportation Science, forthcoming.
[35] S. Nguyen and S. Pallottino. Equilibrium tra?c assignment for large scale
transit networks. European Journal of Operational Research, 37(2):176?186,
1988.
[36] P2D. Metrorail station access and capacity study: Final report. Technical
report, Washington Metropolitan Area Transit Authority, April 2008.
[37] V.M. PATRICK. Network Design:. An Algorithm for the Access Facility Loca-
tion Problem. IEEE Transactions on Communications, 25(1):61, 1977.
[38] A. Pr?ekopa. Dual method for the solution of a one-stage stochastic program-
ming problem with random rhs obeying a discrete probability distribution.
Mathematical Methods of Operations Research, 34(6):441?461, 1990.
[39] A. Pr?ekopa. Stochastic programming. Kluwer, 1995.
[40] A. Pr?ekopa, B. Vizv?ari, and T. Badics. Programming under probabilistic con-
straint with discrete random variable. New trends in mathematical program-
ming: homage to Steven Vajda, pages 235?256, 1998.
[41] Andr?as Pr?ekopa. Probabilistic Programming,volume10ofHandbooks in Op-
erations Research & Management Science, chapter 5, pages 267?352. Elsevier
Science, 2003.
139
[42] CJ Rodier, SA Shaheen, and L. Novick. Improving bay area rapid transit
(BART) district connectivity and access with the segway human transporter
and other low speed mode devices research report. Technical report, UCB-ITS-
PRR-2004-27. California PATH, University of California, Berkeley, 2004.
[43] A. Saxena, V. Goyal, and M.A. Lejeune. MIP reformulations of the probabilistic
set covering problem. Mathematical Programming, 121(1):1?31, 2008.
[44] D. Schrank and T. Lomax. The 2009 urban mobility report. Technical report,
Texas Transportation Institute, 2009.
[45] S.A. Shaheen and A.P. Cohen. Growth in worldwide carsharing: An interna-
tional comparison. Transportation Research Record, 1992(-1):81?89, 2007.
[46] S.A. Shaheen, M. Meyn, and K. Wipyewski. US Shared-Use Vehicle Survey
Findings on Carsharing and Station Car Growth: Obstacles and Opportunities.
Transportation Research Record, 1841:90?98, 2003.
[47] S.A. Shaheen and C.J. Rodier. Easyconnect: Low-speed modes linked to transit
planning project. Working Paper UCB-ITS-PWP-2006-7, California PATH,
Institute of Transportation Studies, University of California, Berkeley, 2006.
[48] S.A. Shaheen, C.J. Rodier, and J. Seelig. Easyconnect ii: Integrating trans-
portation, information, and energy technologies at transit oriented develop-
ments. Proceedings the Transportation Research Board Annual 2006 Meeting,
2006.
[49] S.A. Shaheen, A. Schwartz, and K. Wipyewski. Policy considerations for car-
sharing and station cars: Monitoring growth, trends, and overall impacts.
Transportation Research Record, 1887:128?136, 2004.
[50] Susan A. Shaheen, Caroline J. Rodier, and Joshua Seelig. Easyconnect II: Inte-
grating transportation, information and energy technologies at transit oriented
developments. Technical Report UCD-ITS-RR-05-14, Institute of Transporta-
tion Studies, University of California, Davis, 2005.
[51] Heinz Spiess and Michael Florian. Optimal strategies: A new assignment model
for transit networks. Transportation Research Part B, 23B(2):83?102, 1989.
[52] TAMU. Urban mobility report. Technical report, Texas Transportation Insti-
tute, 2005.
[53] TRB. Transit cooperative research program synthesis 108: Car sharing: Where
and how it succeeds. Technical report, Transportation Research Board, 2005.
[54] TRB. Transit cooperative research program synthesis 62: Integration of bicycles
and transit. Technical report, Transportation Research Board, 2005.
140
[55] USDOT. 2001 national household travel survey. Technical report, U.S. Depart-
ment of Transportation, 2001.
[56] USDOT. Draft U.S. DOT Strategic Plan FY2010-FY2015: Transportation for
a New Generation. Technical report, United States Department of Transporta-
tion, 2010.
[57] T. Vanderbilt. Tra?c: why we drive the way we do (and what it says about
us). Alfred a Knopf Inc, 2008.
[58] WMATA. Wmata facts. Technical report, Washington Metropolitan Area
Transit Authority, 2009.
[59] J.H. Wu, M. Florian, and P. Marcotte. Transit equilibrium assignment: a model
and solution algorithms. Transportation Science, 28(3):193?203, 1994.
[60] Athanasios Ziliaskopoulos and Whitney Wardell. An intermodal optimum path
algorithm for multimodal networks with dynamic arc travel times and switching
delays. European Journal of Operational Research, 125:486?502, 2000.
141