Chengqi Lu, Michal Maciejewski, Kai Nagel
Effective Operation of Demand-Responsive
Transport (DRT): Implementation and Evaluation of
Various Rebalancing Strategies
Open Access via institutional repository of Technische Universität Berlin
Document type
Conference paper | Accepted version
(i. e. final author-created version that incorporates referee comments and is the version accepted for
publication; also known as: Author’s Accepted Manuscript (AAM), Final Draft, Postprint)
This version is available at
https://doi.org/10.14279/depositonce-18426
Citation details
Lu, Chengqi; Maciejewski, Michal; Nagel, Kai (2021). Effective Operation of Demand-Responsive Transport
(DRT): Implementation and Evaluation of Various Rebalancing Strategies.27th ITS World Congress, Hamburg,
Germany, 11-15 October 2021. Paper ID 266.
Terms of use
This work is protected by copyright and/or related rights. You are free to use this work in any way permitted by
the copyright and related rights legislation that applies to your usage. For other uses, you must obtain
permission from the rights-holder(s).
522
SUMMARY
27th ITS World Congress, Hamburg, Germany, 11-15 October 2021
Paper ID 266
Effective Operation of Demand-Responsive Transport (DRT):
Implementation and Evaluation of Various Rebalancing Strategies
Chengqi Lu1*, Dr. Michal Maciejewski1, Prof. Dr. Kai Nagel1
Institut für Land- und Seeverkehr, TU Berlin, Germany
Abstract
In this study, four rebalancing strategies are implemented in an open-source multi-agent traffic
simulation platform, MATSim. The impact of the rebalancing strategies on service quality of the
Demand-Responsive Transport (DRT) is examined and compared. A comprehensive evaluation scheme,
consisting of both conventional and innovative criteria, is introduced for this purpose. Results indicate
that the claimed effectiveness of all the rebalancing strategies included in this study can be materialized
in the agent-based simulation platform to certain degrees. Depending on the role a DRT system plays,
different strategies may be the preferred choice. In addition, as the by-product of this study, the structure
update of MATSim and the introduction of new evaluation criteria enable convenient implementation
and evaluation of custom rebalancing strategies.
Keywords:
Demand-Responsive Transport and Fleet Rebalancing
Introduction
Demand-Responsive Transport (DRT) is a mobility-on-demand service, where customers can submit
their travel demand spontaneously and the operator will try to send a vehicle to fulfil that demand.
Nowadays, DRT services at different scales can be found in many places around the world. Most of
them are operated by Transportation Network Companies or conventional taxi companies. Recently,
there have also been several studies that propose the idea of viewing DRT as (part of) the public transport
service provided by the city government or transport authority (Wang, 2018), (Sieber, Ruch, Horl,
Axhausen, & Frazzoli, 2019) and (Vakayil, Gruel, & Samaranayake, 2017). When we consider DRT as
a public service, instead of a commercial one provided by profit-making companies, the way to operate
the DRT system can be different from those we are often seeing now. Rather than putting profitability
at the top place, service quality, accessibility as well as the impact on environment and traffic congestion
will probably move up the rank in the priority list of the designer and operator of the system.
The operation of the DRT service mainly consists of the following two parts: assignment strategy and
rebalancing strategy. As suggested by its name, the assignment strategy matches the available vehicles
and travel requests. The rebalancing strategy repositions the DRT fleet such that there will be enough
vehicles in every region and the travel requests can be served shortly after the submission. In this study,
we focus on the rebalancing strategy in the DRT operation. We implement several existing rebalancing
◀
▶
523
SUMMARY
Effective Operation of Demand-Responsive-Transport (DRT)
2
strategies into MATSim, a multi-agent transport simulation platform. Then we will evaluate and
compare the impact of the rebalancing strategies on the service quality.
About the MATSim simulation platform
Multi-Agent Transport Simulation (MATSim) is an open-source agent-based framework for traffic
simulations (W. Axhausen, Horni, & Nagel, 201). Because of its efficient design, city-scale traffic
simulation can be conducted. There are multiple extension modules in the MATSim library, focusing on
modelling various components or aspects of transport systems. In this study, we add new rebalancing
strategies to the DRT extension module (Bischoff, Macieewski, & Nagel, 2017). The MATSim DRT
module enables the simulation of the on-demand transport service with the help of within day planning
feature in MATSim. At the departure time, the customer will walk to the closest link (i.e., the technical
term for road segment in MATSim) to the departure location (e.g., home, work). The DRT system will
then try to arrange an available vehicle to pick up the passenger. After arriving at the link closest to the
destination point, the vehicle will drop off the passenger and the travel request is considered to be
completed. Within this framework, fleet operational strategies can be implemented to provide a good
service quality at a possibly low cost.
As the by-product of this study, the newly implemented rebalancing strategies as well as the evaluation
criteria have been added to MATSims DRT extension and made available via a configuration file.
Implementation and evaluation of additional custom rebalancing strategies can also be performed
conveniently. More details on this can be found in the supplementary materials.
Ileentation of ebalancing trategies
In this section, we will briefly introduce the rebalancing strategies used in this study. As this study
focuses on the implementation and the comparison of the rebalancing strategies, we will not go into the
details of each strategy. Interested readers are advised to refer to the original literature.
Background information
Before introducing the rebalancing strategies used in this study, we will first clarify two concepts which
can be found in some of the rebalancing strategies: zonal aggregation model and reliance on previous
data (i.e., data-driven). Because of these features, it was necessary to add some new elements to the
MATSim simulation environment, in order to make the rebalancing strategies work properly.
onal aggregation model divides the whole service area into smaller zones. This feature enables the use
of optimization tools when generating rebalancing plans, because the zonal aggregation greatly reduces
the problem size by condensing multiple links into one zone. onal aggregation model also allows
computing indicators used in decision making and which may be hard to obtain at the level of single
links or coordinates. When a zone-based (i.e., based on zonal aggregation model) rebalancing strategy
is used, rebalancing actions are first planned and calculated at the zone level, instead of the link or
◀
▶
524
SUMMARY
Effective Operation of Demand-Responsive-Transport (DRT)
coordinate level. Then, we convert the zonal level rebalancing plans into link-to-link rebalancing
instructions that are sent to individual vehicles. There are many ways to generate zonal system and to
convert zonal rebalancing plans into individual vehicle rebalancing instructions. In this study, we
generate the zonal system by applying k-mean clustering technique on requests departure locations.
More details on the zonal system setup can be found in the Scenario and simulation setup section below.
A rebalancing that relies on previous data strategy generates rebalancing plans based on the historical
demand data. Such strategies are also often referred to as data-driven strategies in the literature. As
pointed out by many studies (hang, Rossi, & avone, 201) and (Song, anasugi, & Shibasaki, 201),
by analysing the previous data on how people move around in the traffic network, predictions on the
future trips can be made in an accurate manner. With the prediction of potential DRT trips, we can
proactively relocate vehicles closer to zones for which we expect a higher demand in the near future.
Minostlo ebalancing Strateg
The Min-Cost-Flow Rebalancing Strategy, introduced in (Bischoff & Macieewski, 2020) is an intuitive
and straightforward rebalancing strategy that stocks vehicles in the popular zones based on the past
travel data. A day is also divided into multiple time bins. At the beginning of each time bin, selected
available vehicles will be sent across the network such that the target value of available vehicles for each
zone could be met when there are enough available vehicles. The target value of available vehicles in a
zone during a time bin is based on the historical demand data. The mapping from the historical data to
the target value requires manual parametrisation. ones with more idling vehicles than the target value
will send vehicles to the zones where the target is not met. Rebalancing is modelled as the transportation
problem and the interzonal rebalancing plan is calculated using the Hungarian algorithm (Ford r &
Fulkerson, 19), such that the total cost of the rebalancing drives is minimized.
Adaptie ealtime ebalancing Strateg
The Adaptive Real-time Rebalancing Strategy, originally proposed in paper from (avone, Smith,
Frazzoli, & Rus, 2012), distributes available (idling) vehicles in the DRT system evenly across the
network periodically, such that vehicles will be available at any place in the system. At each rebalancing
period, the strategy will count the number of available vehicles in the system. The target number of
vehicles a zone should possess is calculated by dividing the total number of available vehicles by the
number of zones. Similar to the Min-Cost-Flow Rebalancing Strategy, this strategy also uses the zonal
aggregation model and the interzonal rebalancing plan is calculated by solving the transportation
problem. But unlike the Min-Cost-Flow strategy, this strategy does not rely on the previous travel data.
eedforard ebalancing Strateg
The Feedforward Rebalancing Strategy, also proposed in the paper from (avone, Smith, Frazzoli, & Rus,
2012), models the travel demand in the DRT system as fluidic flow. The rebalancing plan is then generated
by calculating the optimal counter flow to the demand flow such that the system stays balanced. It is a data-
◀
▶
525
SUMMARY
Effective Operation of Demand-Responsive-Transport (DRT)
driven and zone-based rebalancing strategy. The service area is divided into zones and a day is divided into
small time bins. During each time bin, we assume the travel demands are entering the system at a constant
rate. With this framework, we can compute the optimal counter flow of the travel demands based on past
data. And the optimal counter flow will be used as the feedforward signal when generating the rebalancing
plan.
To better adapt this strategy to the iterative approach in MATSim, a feedback mechanism is added to this
strategy. With the feedback mechanism, the rebalancing strategy will maintain a minimum number of vehicles
in each zone. The feedback mechanism has a higher priority than the feedforward part. If a zone does not
have spare vehicles (i.e., in addition to the minimum requirement), no vehicle will be sent out from that zone
even if there is a feedforward signal instructing this zone to send out vehicles.
lusne ebalancing Strateg
The lus-ne Rebalancing Strategy is a novel and model-free rebalancing strategy (Ruch, Gachter,
Hakenberg, & Frazzoli, 2020). It uses the real-time travel demand as the only input to determine the
way to relocate available vehicles in the system. As suggested by its name, this rebalancing strategy will
relocate one idle vehicle to the departure location of each request that has been matched during the last
rebalancing period. In other words, this strategy relies on the logic that a request is likely to appear in a
currently popular departure area and therefore it is a good idea to send rebalancing vehicles to that area.
This is particularly the case during the peak hours where commuters travel from residential areas to
work or the other way round. A more formal proof on the sturdiness of this Rebalancing strategy can be
found in (Ruch, Gachter, Hakenberg, & Frazzoli, 2020).
Summar
The four rebalancing strategies included in this study is summarized in Table 1. The features introduced
above are included in the table to differentiate the strategies. If a strategy is zone-based, then the network
needs to be pre-processed to generate the zonal system. If a strategy is data-driven, then historical travel
demand data is needed.
able 1 uar of the ebalancing trategies
Abbreiation onebased Datadrien
Min-Cost-Flow Rebalancing Strategy Min-Cost-Flow
Adaptive Real Time Rebalancing Strategy Adaptive
Feedforward Rebalancing Strategy Feedforward
lus-ne Rebalancing Strategy lus-ne
iulation etu and aluation Criteria
Scenario and simulation setup
In this study, we use a MATSim model of Vulkaneifel to simulate and compare the rebalancing strategies.
Vulkaneifel is a sparsely populated area consisting of many scattered small cities, towns and villages in
◀
▶
Loading more pages...