Department of Policy and Planning Sciences
Discussion Paper Series

No.1353

Optimization-based analysis of last-mile one-way
mobility sharing

byMasaki YAMADA, Masashi KIMURA, Naoki TAKAHASHI, and Akiko YO
SHISE

March 2018
Revised September 2018

UNIVERSITY OF TSUKUBA
Tsukuba, Ibaraki 305-8573
JAPAN

Optimization-Based Analysis
of Last-Mile One-Way Mobility Sharing
Masaki YAMADA ∗, Masashi KIMURA, Naoki TAKAHASHI †, and Akiko YOSHISE ‡March 25, 20018
Revised September 23, 2018

Abstract
One-way carsharing is becoming increasingly popular because it is more convenient for users thanconventional round-trip carsharing. However, a one-way service suﬀers from a mismatch between
user demand and the distribution of vehicles (supply). A number of methods have been studiedin attempts to resolve this issue. In particular, “last-mile mobility”, a type of one-way carsharing
providing short trips between stations at public transport hubs and origins/destinations in local
areas, reserves destination parking spaces in addition to vehicles at origins, and it needs to control
both resources carefully.
Here, we develop a mixed integer linear programming (MILP) model of an existing short-trip lastmile mobility service (Ha:mo RIDE) in Japan and optimize the vehicle distribution and relocations
to maximize the operator’s proﬁt. The optimal solution indicates that the operator should reduce
relocations disproportionately because of the low revenue per short trip. However, a low satisﬁeddemand rate would result in customer defection and lead to a long-term loss. As a solution, we
propose autonomous relocation by low-speed automated driving and show that slow but frequent
relocations would yield both a beneﬁt to the user (high satisﬁed demand) and proﬁt for the operator
as well as a virtual increase in parking capacity for last-mile-mobility operations with many small
stations.

Keyword: one-way carsharing; last-mile mobility; Ha:mo; autonomous vehicle relocation; Mobility as
a Service; MaaS; optimization-based analysis; mixed integer linear programming

1

Introduction

The Japanese government is promoting “Society 5.0” [31], a super smart society as a successor tohunter-gatherer, agricultural, industrial, and information societies that came before it. Society 5.0 is
described in the 5th Science and Technology Basic Plan [13]; one of its pillars is MaaS, mobility as aservice, including carsharing and ridesharing.
∗ yamadam@mail.toyota.co.jp,

Frontier Research Center, Toyota Motor Corporation, 1-4-18 Koraku, Bunkyo-ku,
Tokyo, 112-8701, Japan.
† s1720593@s.tsukuba.ac.jp, Department of Policy and Planning Sciences, Graduate School of University of Tsukuba,
1-1-1 Tennoudai, Tsukuba, Ibaraki 305-8577, Japan.
‡ Corresponding author, yoshise@sk.tsukuba.ac.jp, Faculty of Engineering, Information and Systems, University ofTsukuba, 1-1-1 Tennoudai, Tsukuba, Ibaraki 305-8577, Japan.

1Carsharing has become a popular means of transportation in the 21st century. For instance, Zipcar,
founded in 2000 in the US, has expanded to Canada and Europe: it provided services to more than 1
million members in 2017. Members can ﬁnd and reserve vehicles with a smartphone app and get access tovehicles simply by using their member’s cards as entry badges. In 2007, car2go started as a free-ﬂoating
one-way carsharing experiment in Ulm, Germany, and it is now the world s largest carsharing company
with operations all over the globe. Car2go has a convenient one-way service which allows users to returnvehicles anywhere within the service area, while a round-trip service requires vehicles to be returned totheir original points. Autolib’, initiated in Paris in 2011, is a one-way carsharing scheme that provides
electric vehicles (EVs). Autolib’ is a non-ﬂoating (station-base) system and EVs have to be returned toAutolib’ stations to be recharged.
Station-base one-way carsharing using ultra-compact EVs started in Japan in 2012. Yokohama city andNissan launched “Choimobi Yokohama”, a two-person EV sharing service, whose main objectives are toencourage low-carbon emission transport and promote tourism. One-way service was available for theﬁrst two years, and round-trip service is currently available. In the same year, Toyota launched “Ha:mo
RIDE” [36], a new type of mobility service for last-mile transport. Providing one-way sharing service
with ultra-compact EVs such as i-ROAD [37] and COMS [10], Ha:mo is intended to be a stress-free andeco-friendly “Harmonious Mobility Network” that utilizes both personal and public transport. Since its
launch in Toyota city, Ha:mo RIDE has expanded to Tokyo, Okinawa, and Okayama in Japan, Grenoble
in France, and Chulalongkorn University in Thailand.
One-way carsharing provides more ﬂexibility for users, but has an issue of imbalanced user demandand vehicle supply. To increase satisﬁed demand, many carsharing operators hire personnel to relocate
vehicles from lower demand areas to higher demand areas in a time-dependent manner, but the labor
cost of the relocation staﬀ puts pressure on their proﬁtability. Another approach to ease the imbalanceis adaptive pricing, which controls user demand by placing premiums on trips from high-demand areas(or giving discounts for trips to high-demand areas). There are several studies on adaptive pricing foron-demand mobility, such as that of Drwal, Gerding, Stein, Hayakawa, and Kitaoka [16]. Ridesharing
services such as Uber and Lyft use dynamic pricing to control both demand and supply [32]. To increase
both the number of demands served and revenue, companies have placed premiums on attracting drivers(increasing supply) as well as discouraging potential users (decreasing demand). By allying with car
makers, ridesharing companies are developing self-driving vehicles [38] to maximize vehicle utilization.
In this paper, we focus on last-mile mobility, one-way carsharing designated for short trips within a city,and develop an optimization model for making optimal operation decisions. The next section 2 reviews
previous research related to one-way carsharing optimization. Section 3 explains the characteristics oflast-mile mobility and develops an optimization model for Ha:mo RIDE. Section 4 describes our application and the developed model for Ha:mo RIDE in Toyota city (Ha:mo RIDE Toyota), and it compares
the optimal solution with the actual operation. It also describes several case studies involving modiﬁcations to the model: (1) a “premium service” guaranteeing reservations in return for price premiums and(2) autonomous relocation by slow-speed automated self-driving. The last section 5 provides conclusions
and ideas for future research.

2

Recent research on optimization-based analysis ofcarsharing

There is a growing body of research on optimization-based analysis of carsharing and other kinds ofmobility sharing. Jorge and Correia [25] reviewed the history of carsharing, from its beginnings as acooperative initiative to recent one-way services and related research. Boyaci, Zografos, and Gerolimi2

nis [3] classiﬁed models related to planning and operation of carsharing systems into two categories: (i)models addressing strategic planning decisions and (ii) models supporting operational decisions. In orderto maximize performance metrics such as the number of uses, strategic planning decides the locations
and sizes of stations and the number of vehicles assigned to each station, while operational decisions
relocate the vehicles among the stations.
Correia and Antunes [11] presented an optimization approach for determining the locations of stations
to maximize the proﬁt of the one-way carsharing operator. The approach included determining locations
that would maximize revenues from users and reduce the costs of maintaining vehicles, parking spaces,
and relocating vehicles. The interest of the study was strategic decision making, and neither detailed
relocation operations nor constraints on the maximum parking space per station or total number ofvehicles were considered. Later, Jorge and Correia [27] incorporated a relocation operation into theiroptimization models for maximizing proﬁt and examined relocation policies in simulations. They foundthat a dynamic (frequent) relocation policy signiﬁcantly improved proﬁtability.
Correia, Jorge, and Antunes [12] introduced a notion of user ﬂexibility by oﬀering a choice of disembarking at the second- or third-closest stations. When exploited in combination with real-time information
about vehicle availability, such user ﬂexibility increases the number of demands served and raises theoperator’s proﬁt. Although this notion reﬂects the situation of actual carsharing services that provide information on nearby vehicles, an actual user’s willingness to use alternative stations can only be
supposed until he or she states it.
Kek, Cheu, Meng, and Fung [28] proposed a three-phase optimization-trend-simulation (OTS) decision
support system for dealing with the staﬀ-based vehicle relocation problem. Phase one of the OTS the
Optimizer returns the lowest-cost resource allocation, phase two the Trend Filter ﬁlters the output
through a series of heuristics, and phase three the Simulator evaluates the performance of the result. In
the optimization, the problem is modeled as a mixed integer linear programming (MILP) on a time-space
network in which nodes represent staﬀ behaviors. It was found that an increase in variables such as thenumber of stations and time steps increased the computational complexity of the model, and no eﬀective
solution was presented in their paper.
Boyaci, Zografos, and Geroliminis [4] proposed an integrated multi-objective mixed integer linear programming (MMILP) optimization and discrete event simulation framework for vehicle and personnel
relocation in a one-way carsharing system with reservations. By clustering stations, the number ofvariables is reduced and the computational complexity of the optimization decreases as result. The optimization model was developed on a time-augmented network, using time intervals (15 minutes) during
which each vehicle and each staﬀ member had only one status. This network contributes to a clear formulation including the ﬂow conservations of the vehicles and relocation staﬀ. Our optimization modelingfor last-mile mobility in section 3.2 uses the same network structure.
He, Mak, Rong, and Shen [24] provided a robust optimization problem for designing a geographical service region in which to operate the service based on the second-order cone optimization model presented
in Ghaoui, Oks, and Oustry [21] and usage data of the car sharing service car 2go.
Wang [40] considered a last-mile transportation system which supports movement from the nearest
public transportation system (train, bus, etc.) to home or another destination. The author formulated
an MILP model for ﬁnding optimal routes and operation schedules to minimize the user’s waiting andboarding times.
Braverman, Dai, Liu, and Ying [2] performed optimization to make empty-car relocation schedules byusing the usage data of a ride-sharing service in China. Their optimization model includes a ride-sharing
network and Markov chain analysis of space-time networks.

3

Linag, Correia, Arem [29] considered last-mile self-driving taxi services and proposed two MILP models
for examining the quality of services expected to be implemented in the future: a model that maximizes
proﬁt by determining the acceptable trip demand and a more restrictive model with the constraint thatthe demand for a speciﬁed zone must be satisﬁed.
Several other recent studies were conducted on robust optimization analysis of car shearing service(Naoum-Sawaya et al. [30], Brandstatter, Kahr, and Leitner [5], Deng, Cardin [14], Erera, Morales,
and Savelsbergh [17], etc.), on ride-sharing service (Agatz et al. [1], Stiglic et al. [35], Xu, Yin, andZha [43], Dong et al. [15], etc.), on bicycle-sharing service (Chardon, Caruso [7], Forma, Raviv, andTzur [20], Celebi, Yorusun, and Isik [6], Wang et al. [41], etc.), on autonomous car-sharing service
Fagnant, Kockelman, and Bansal [18], Chen, Kockelman, and Hanna [8], Hanna et al. [23], Farhan, andChen [19], etc.), and on pricing of car-sharing service (Jorge, Molnar, and Correia [26], Schwieterman,
Bieszczat [33], Chen, Wang [9], Xu, Meng, and Liu [42], etc.).
As shown above, there has been substantial research pursuing optimal vehicle distributions and relocation operations for one-way carsharing. However, the developed models are inappropriate for last-milemobility because of the characteristics described in section 3.1.

3

Framework and modeling

3.1

Last-mile mobility sharing

Last-mile mobility sharing has diﬀerent aspects from the usual one-way carsharing. Here, taking Ha:mo
RIDE as an example, we describe the characteristics of last-mile mobility. To be used as last-miletransport, vehicles are parked at stations close to public transport stations, bus stops, and other points
of interest such as shopping malls, oﬃce, and homes (Fig.1). Users of last-mile mobility typically travelfrom the origin to the destination without taking any detours, as in the case of other kinds of last-miletransportation such as bus or taxi. Round-trips account for only a few rides, and most last-mile one-way
trips end in a shorter time than other kinds of one-way carsharing. The actual data on use of Ha:mo
RIDE Toyota clearly reﬂects these features.

Fig. 1: Last-mile mobility network - Ha:mo RIDE [36]4A characteristic of last-mile mobility is that users reserve parking spaces at destinations as well as vehicles
at origins. Assigning parking spaces before departure allows users to end their trips on arrival, just asother last-mile transports, such as bus and taxi, do. This feature is necessary for last-mile mobility:
while it is frustrating if it takes 10 minutes to ﬁnd a parking space after driving for 1 hour, it is nearly
intolerable if it takes 10 minutes to park after driving for only 10 minutes. On the other hand, users
cannot make reservations if they cannot ﬁnd available parking spaces at the destinations, even if theyﬁnd vehicles at the origin station (Fig.2). In last-mile mobility with parking assignments, both vehicles
and parking spaces need to be managed more carefully than in carsharing without parking assignments
in order to meet demand.

Fig. 2: No parking, no reservation. Users reserve parking spaces as well as vehicles. Users don’t need to look
for available parking spaces when they arrive, but parking spaces have to be available when they makereservations.

Ha:mo RIDE is operated by local operators in each area under common service procedure, as follows.
First, users reserve vehicles with smartphone apps or through a web page by registering both origin anddestination stations. If there is no “free” (available) vehicle at the origin or no “free” parking space atthe destination, the applications fail (vanish). Once made, reservations are valid for 20 to 30 minutes
depending on each service, and both vehicles and parking spaces become “assigned”, i.e., not available toother users. When a registered user depart from an origin station, a parking space becomes “free”, i.e.,
available to other users and vehicles. When the user arrives at the destination station, the driven vehicle
becomes “free” again. Fig. 3 shows this process together with the changes in state of the resources.

Fig. 3: Service procedure and changes in resource status. Note that optimization modeling assumes that users
depart the origin station immediately after making a reservation; i.e., the resource state transitions
reﬂecting reservation and departure occur at the same time.

5

To avoid imbalances between supply and demand and at the same time increase the number of uses,
operators set vehicle distribution targets (relocation thresholds at each station) based on use-history
analyses and experience. In practice though, actual operations depend on the on-site relocation staﬀ.
Despite the operators’ eﬀorts and costs, there still remains customer dissatisfaction due to imbalances,which means lost business and if, not corrected, long-term reductions in the number of customers. In
the next section 3.2, we develop a mixed integer linear programming (MILP) model that optimizes thevehicle distribution and relocations to maximize the operator’s proﬁt.

3.2

Optimization modeling

Our optimization model is based on the idea described in Boyaci et al. [4], but it is more restrictive thantheirs [4]. In particular, it puts speciﬁc assumptions on last-mile mobility sharing, as follows.
1. Last-mile mobility is modeled on a time-augmented network, which consists of stations and timeintervals. Note that each time interval is 5 minutes, shorter than in previous research (e.g., 15
minutes), because last-mile mobility is used for relatively short trips.
2. The demand for the whole day is given at once, though actual reservations are made 30 minutes before rides. There is no time gap between reservation and departure, and there are nocancellations.
3. For a trip to occur, there have to be vehicles at the origin and parking spaces at the destination
at the time of departure.
4. Travel time is the trip duration plus a constant period, assuming one-way short trips without
making any detours. The constant period is thus a margin for departure and arrival that includes
the time spent getting into and out of the vehicle and getting the vehicle ready to move. The
travel time of moving staﬀ and relocating vehicles is calculated in the same way.
5. The trip duration is expressed in terms of parameters depending on the traﬃc conditions as wellas the distance between stations. Travel times between the same stations at diﬀerent times of the
day can be diﬀerent.
6. Every trip or relocation takes at least 1 time interval.
7. Each node of the network is represented as (j, t), where j identiﬁes the station and t the timeinterval, is a state including the number of parked vehicles, number of assigned parking spaces,
and number of relocation staﬀ.
8. In each time interval, each vehicle can have only one status: “free” or “assigned”. “Assigned”
includes rides of users and relocation of staﬀ.
9. In each time interval, each parking space can have only one status: “free” (available) or “assigned”
or “parked” (both unavailable).
10. In each time interval, each relocation staﬀ can have only one status: “idle”, “moving”, or “relocating”.
11. Relocation staﬀ work for one shift, and each shift has a beginning time and a ﬁnishing time. The
manager must work a speciﬁc shift (the shift in dark green in Fig. 4), while other staﬀ work whenrelocation becomes necessary.

Fig. 4: Staﬀ shift

12. The relocation staﬀ move on a staﬀ vehicle as a team (a two-man team), and they relocate vehicles
6

by one driving the vehicle that was used and the other driving the staﬀ vehicle (Fig.5). Previous
research did not clearly deﬁne how the staﬀ moves or otherwise assumed they did so by bicycle
over a long distance. Instead, we followed the actual operation procedure of Ha:mo RIDE Toyota*1 . In this setting, there is only one staﬀ vehicle, but in section 4.4, we discuss a model with more
staﬀ vehicles and the eﬀect of increasing the number of vehicles.

Fig. 5: Moving and relocating using staﬀ vehicle

13. The state of charge (SOC) of the vehicle s battery is not considered. Last-mile mobility is mostly
intended for one-way short trips, and electricity consumption is low enough for the battery to berecharged in the time between one trip and the next. In the Ha:mo RIDE Toyota case study, we
ran simulations on a simulator (updated by Shimazaki, Kuwahara, Yoshioka, Homma, Yamada,and Matsui [34]) and found that no vehicles became unavailable because of a low SOC.
14. The number of vehicles and the number, capacity (number of parking spaces), and locations ofstations are given as parameters.
Assumptions 2, 3, 4, 5, 9, 12, 13, 14 are diﬀerent from previous research.

Fig. 6 shows the time-augmented network and arcs representing trips and relocations.

Fig. 6: Time-augmented network and arcs representing vehicle movements• The arcs represent movements of vehicles between nodes. There are four vehicle movements,
three for trips and one for relocation: three vehicles driven by users from node (2, 2) to (j, t) (fromstation 2 at time interval 2 to station j at time interval t), from (2, t − 1) to (1, t + 1), from (j, t + 1)
to (1, t + 2), and one vehicle driven by relocation staﬀ from (1, t + 2) to (2, t + 3).
• Because each vehicle can have only one status during each time interval, a vehicle starting at
station j in time interval t must be ready by the end of the previous time interval t − 1. Moreover,*1

Staﬀ walk between neighboring stations within walking distance, but for the sake of simplicity, we assume that theywalk between all stations.

7

a vehicle arriving at station j in time interval t must be ready starting from the next time intervalt + 1. The same is true for parking spaces and relocation staﬀ.
• Parking spaces must be assigned to each trip from the beginning of the trip. For example, for atrip from (2, 2) to (j, t), a parking space at station j must be assigned from the beginning of timeinterval 2. The reservation of parking spaces at destinations is important for actual smooth Ha:mo
RIDE Toyota operation.However, it may place severe constraints on the optimization settings. In
section 4.5, we consider a case in which there is no parking space reservation constraint and discuss
its eﬀect.
• Relocation staﬀ are needed to relocate vehicles. During the relocation from (1, t + 2) to (2, t + 3),
the relocation staﬀ move just the same as the vehicle.
• Besides using the staﬀ vehicle for relocation, staﬀ also use it to move between stations, as describedin section 3.2. The operation is limited to serial relocation from a station where the staﬀ startworking when only one member is working. For example, after relocation to (2, t + 3), the staﬀ
cannot move from station 2 without the staﬀ vehicle.
For moving staﬀ and relocating vehicles, stations are clustered in order to decrease the number ofvariables and reduce computational complexity. Fig. 7 shows the moving and relocating arcs on thetime-augmented network with clusters of stations.

Fig. 7: Time-augmented network with clusters of stations and moving and relocating arcs

• The moving and relocating operations are divided into three parts. Taking relocation from node(j, t) to (l, t + 2) as an example, part (i) is from origin station j to the origin station’s cluster b intime interval t, part (ii) is from cluster b at time interval t to the destination station’s cluster d intime interval t + 2, while part (iii) is from cluster d to destination station l in time interval t + 2.
• Stations are clustered by using an algorithm based on the one in Boyaci et al. [4]. The station
clustering algorithm is described in section 3.3.

3.2.1

Sets and indices– i ∈ I: trips– j, l ∈ J : stations– t ∈ T : time interval– s ∈ S: relocation staﬀ shift– b, d ∈ B: station clusters∪– J b : set of stations in cluster b, i.e. J =
Jb
b∈B

8

3.2.2

Parameters– begins , ﬁns ∈ T : beginning and ﬁnishing time intervals of shift s– starti , endi ∈ T : start and end time intervals of trip i– origini , desti ∈ J : origin and destination stations of trip i– traveltbd ∈ N: travel time starting at time interval t from cluster b to cluster d– t.endtbd ⊂ T : set of departing time intervals of driving or relocating from cluster b to cluster darriving during time interval t *2
– Pi : price for trip i– PCs : personnel cost of relocation staﬀ for shift s
˜ bd : relocating cost from cluster b to cluster d (fuel cost)– RC
˜ bd : moving cost from cluster b to cluster d (fuel cost of staﬀ vehicle)– MC– Lcost: maximum acceptable labor cost per day in the service– NV: maximum number of vehicles available in the service– capj : number of parking spaces (capacity) at station j– NW: total number of relocation staﬀ able to work in the service

3.2.3

Variables

The decision variables are as follows.
– zi ∈ {0, 1}, ∀i ∈ I: binary variables, if trip i is served 1, otherwise 0.
– vs ∈ Z+ , ∀s ∈ S: number of staﬀ in shift s.
– njt ∈ Z+ , ∀j ∈ J , t ∈ T : number of vehicles at station j at the beginning of time interval t.
⋆ n′jt ∈ Z+ , ∀j ∈ J , t ∈ T : number of parking spaces at station j at the beginning of time intervalt that are assigned to vehicles coming to the stations.
– msjt ∈ Z+ , ∀s ∈ S, j ∈ J , t ∈ {begins , ..., ﬁns }: number of staﬀ in shift s at station j at the
beginning of time interval t.
′– rsjt∈ Z+ , ∀s ∈ S, j ∈ J , t ∈ {begins , ..., ﬁns }: number of staﬀ of shift s relocating vehicle(s)from station j during time interval t.
– rsjt ∈ Z+ , ∀s ∈ S, j ∈ J , t ∈ {begins , ..., ﬁns }: number of staﬀ of shift s relocating vehicle(s) tostation j during time interval t.
– p′sjt ∈ Z+ , ∀s ∈ S, j ∈ J , t ∈ {begins , ..., ﬁns }: number of staﬀ of shift s moving from station j
during time interval t.
– psjt ∈ Z+ , ∀s ∈ S, j ∈ J , t ∈ {begins , ..., ﬁns }: number of staﬀ of shift s moving to station j
during time interval t.
– r̃sbdt ∈ Z+ , ∀s ∈ S, b, d ∈ B, t ∈ {begins , ..., ﬁns }: number of staﬀ of shift s relocating vehicle(s)from cluster b to cluster d during time interval t.
– p̃sbdt ∈ Z+ , ∀s ∈ S, b, d ∈ B, t ∈ {begins , ..., ﬁns }: number of staﬀ in shift s moving from clusterb to cluster d during time interval t.
– ljt ∈ {0, 1}, ∀j ∈ J , t ∈ T : binary variables, 1 if relocation staﬀ vehicle exists at station j during
time interval t, 0 otherwise.
– u′jt ∈ {0, 1}, ∀j ∈ J , t ∈ T : binary variables, 1 if relocation staﬀ vehicle moves out from station
j during time interval t, 0 otherwise.
– ujt ∈ {0, 1}, ∀j ∈ J , t ∈ T : binary variables, 1 if relocation staﬀ vehicle moves to station j during*2 Travel time depends not only on OD (origin b and destination d) but also on time of departure t.

suppose that each time interval duration is 1, travel1bd = 4 and travel2bd = 3; then t.end5bd is {1, 2}.

9For example,

time interval t, 0 otherwise.

3.2.4

Formulation

The mixed integer linear programming problem is formulated as follows.

maximize∑Pi zi −i∈I∑

PCs vs −∑njt+1 = njt −∑∑˜ bd r̃sbdt + MC
˜ bd p̃sbdt )
(RC

(1)

∀j ∈ J , t ∈ {0, ..., tlast−1 }

(2)

′
rsjt

s:begins ≤t≤fins

∑

zi +

rsjt

s:begins ≤t≤fins

i:desti =jendi =t

njt ≥

∑

zi −

i:origini =jstarti =t+∑s∈S b,d∈B t∈{begins ,...,fins }s∈Ssuch that

∑ ∑

∑

′
rsjt

∀j ∈ J , t ∈ T(3)∀s ∈ S(4)′
msjt+1 = msjt − p′sjt − rsjt
+ psjt + rsjt

∀s ∈ S, j ∈ J , t ∈ {begins , .., ﬁns − 1}

(5)′
msjt ≥ p′sjt + rsjt

∀s ∈ S, j ∈ J , t ∈ {begins , ..., ﬁns }

(6)

∑

zi +

s:begins ≤t≤fins

i:origini =jstarti =t

msjbegins = vsj∈J∑

msjfins + rsjfins + psjfins = vsj∈J∑r̃sbdt =

d∈B

∑

′
rsjt

j∈J b

∑

∑

r̃sdbt′ =′d∈B t ∈t.endtdb ∩{begins ,...,fins }∑p̃sbdt =∑∑∀s ∈ S, b ∈ B, t ∈ {begins , ..., ﬁns }(7)∀s ∈ S, b ∈ B, t ∈ {begins , ..., ﬁns }

(8)

p′sjt

∑

′

d∈B t ∈t.endtdb ∩{begins ,...,fins }

∑

rsjt

j∈J b

j∈J b

d∈B

∑

p̃sdbt′ =

∑

psjt

j∈J b

nj0 ≤ NV

(9)

j∈J

10

njt ≤ capj∑

n′jt+1 = n′jt −

∑

zi +

i:desti =jendi =tzi∀j ∈ J , t ∈ T(10)∀j ∈ J , t ∈ {0, ..., tlast−1 }(11)∀j ∈ J , t ∈ T(12)i:desti =jstarti =t

njt + n′jt ≤ capj∑vs ≤ NWs∈S∑(ﬁns − begins )vs ≤ Lcosts∈Sv0 ≥ 1∑p′sjt ≤ NWu′jt

(13)
(14)
(15)

s:begins ≤t≤fins∑

psjt ≤ NWujt∀j ∈ J , t ∈ T(16)∀j ∈ J , t ∈ T(17)∀j ∈ J , t ∈ T(18)s:begins ≤t≤fins∑p′sjt ≥ u′jt

s:begins ≤t≤fins∑

psjt ≥ ujt

s:begins ≤t≤fins

ljt+1 = ljt − u′jt + ujt∑
lj0 ≤ 1j∈J

(19)

The objective function (1) maximizes the total daily proﬁt including revenues from users’ served trips,
personnel costs of relocation staﬀ, and relocating and moving costs (cost of fueling the staﬀ vehicle)
between clusters. While carsharing operators want to increase the number of trips, relocation costs
put pressure on their proﬁtability (an easy but unproﬁtable way to increase the number of trips is tohire hundreds of relocation staﬀ). We propose to ﬁnd a way to maximize proﬁts under certain costs
restrictions.

Constraints (2) are the ﬂow conservation equations for vehicles for each station and each time interval.
The number of vehicles at station j at the beginning of time interval t + 1 (njt+1 ) is equal to the numberof vehicles at the beginning of the previous time∑interval t (njt ) minus the number∑ of vehicles departing′) plusfrom station j during time interval t on trips ( i:origini =j zi ) and relocations ( s:begins ≤t≤fins rsjt
start
=t
i
∑
∑
the number of vehicles arriving at j during t on trips ( i:desti =j zi ) and relocations ( s:begins ≤t≤fins rsjt ).
endi =tThis ﬂow is shown in Fig. 8.

Constraints (3) represent that there are enough vehicles forat each station during∑trips and relocations∑
each time interval. Vehicles arriving at station j during t ( i:desti =j zi + s:begins ≤t≤fins rsjt ) cannot beendi =tcounted during the same time interval t. Because of these constraints, every vehicle can have one andonly one status (“free”, “assigned”) during each time interval.

Constraints (4) show the boundary of the number of staﬀ at the beginning shift and ﬁnishing shift time11

Fig. 8: Flow diagram of vehicles at station j at time interval tintervals. The sum of staﬀ in shift s over all stations at the beginning shift time interval begins must
equal the number of staﬀ from shift vs . Moreover, at the ﬁnishing shift time interval ﬁns as well, thetotal number of staﬀ in shift s at all stations must equal the number of staﬀ from shift vs .
Constraints (5) are the ﬂow conservations of staﬀ for each shift, each station, and each time interval.
The number of staﬀ from shift s at station j at the beginning of time interval t + 1 (msjt+1 ) is equal
to the number of staﬀ at the beginning of the previous time interval t (msjt ) minus the number of staﬀ′
departing from station j during time interval t for moving (p′sjt ) and relocating (rsjt) plus the numberof staﬀ arriving at station j during time interval t for trips (psjt ) and relocations (rsjt ). This ﬂow isshown in Fig. 9.

Fig. 9: Flow diagram of relocation staﬀ at station j during time interval t

Similar to the constraints (3) on vehicles, constraints (6) on the number of staﬀ represent whether there
are enough staﬀ for moving and relocating operations at each station during each time interval. Staﬀ
arriving at station j in time interval t (psjt + rsjt ) cannot be counted during the same time interval
t. Because of these constraints, every staﬀ can have one and only one status (“idle”, “moving”, or“relocating”) during each time interval.

Constraints (7) and (8) are respectively the relocating and moving staﬀ ﬂow conservations between
clusters and stations in the clusters. The left equations indicate that the number of staﬀ in shift sstarting to relocate/move from cluster b during time interval t must be equal to the sum of staﬀ fromshift s relocating/moving from all stations in cluster (J b ) during t. Likewise, the right equations represent
that the number of staﬀ in shift s starting to relocate/move into cluster b during t must be equal to the12sum of staﬀ in shift s relocating/moving to all stations in cluster (J b ) during t.
Constraint (9) indicates that the total number of vehicles at all stations at the beginning of the day
must be equal to or less than the maximum number of vehicles available in the service.

Constraints (10) show the parking capacity restriction at each station during each time interval t. The
number of vehicles at station j during t must be equal to or less than the number of parking spaces atstation j.

Constraints (11) are the ﬂow conservation equations for assigned (unavailable) parking spaces at eachstation and each time interval. The number of assigned parking spaces at station j at the beginningof time interval t + 1 (n′jt+1 ) is equal to the number of assigned parking spaces in the previous timeinterval t (n′t ) minus the∑number of (parking spaces assigned for) vehicles arriving at station j during
time interval t on trips ( i:desti =j zi ) plus the number of (parking spaces assigned for) vehicles departing
endi =t∑from station j during t on trips ( i:origini =j zi ). Note that parking spaces are only assigned to user trips
starti =t′
and not for staﬀ relocation, so the equations don’t include the number of relocations (rsjt
or rsjt ), unlike
constraints (2).

Constraints (12) show the parking capacity restrictions, including assigned parking spaces at each stationin each time interval t. The sum of vehicles and assigned parking spaces at station j during t must be
equal to or less than the number of parking spaces at station j.

Constraint (13) represents that the total number of staﬀ in all shifts must be equal to or less than the
total number of relocation staﬀ able to work in the service.

Constraint (14) represents the maximum labor cost per day.

Constraint (15) indicates that at least a manager must work in shift 0, which is the full-time shift.
Constraint (16) indicates that if ujt or u′jt is equal to 0, no staﬀ move from/to station j during timeinterval t. On the contrary, constraint (17) represents that if ujt or u′jt equals 1, there must be staﬀ
moving from/to station j during t. These constraints mean that relocation staﬀ can only move by using
the staﬀ vehicle.

Constraint (18) is the ﬂow conservation of staﬀ vehicles at each station during each time interval. Finally,
constraint (19) is the maximum number of staﬀ vehicles. In this study, it is assumed there is only one
staﬀ vehicle.

Note that the objective function (1) is diﬀerent from that of Boyaci et al. [4], and the constraints (9),(10), (11), (12), (13), (14), (15), (16), (17), (18), (19) are not used in [4].

13

3.3

Station clustering

The stations used for moving staﬀ and relocating vehicles are clustered to decrease the number ofvariables and reduce the computational complexity.
Without clustering, the number of variables for moving and relocating is on the order of O(|S||J |2 |T |),where S is the set of relocation staﬀ shifts, J is the set of stations, and T is the set of time intervals(the number of variables for trip |I| is ignored here). As described in section 3.2, by clustering stations
and dividing staﬀ moving and relocation operations into intra-cluster and inter-cluster parts (Fig. 7),
the number of variables
changes to on the order of O(|S|(|J ||T | + |B|2 |T |)). By setting the number of√clusters as |B| ≤ |J |, the number of variables decreases to on the order of O(|S||J ||T |).
As a result of clustering, the travel time from station j to station l (δtjl ) is replaced with the travel timefrom cluster b of station j to cluster d of station l (traveltbd ), whose diﬀerence remains as a clustering
error (devtjl ).
devtjl = traveltbd − δtjl

∀j ∈ J b , l ∈ J d(20)

To minimize the sum of clustering errors devtjl , we developed an algorithm based on the one in Boyaci
et al. [4]. The algorithm is similar to the k-Medoid algorithm, which minimizes the sum of dissimilarities
within clusters. We deﬁne the travel time from cluster b to cluster d (traveltbd ) as the maximum travel
time between any stations in each cluster as (21) and set the objective function as (22), the sum of theclustering errors to be minimized. Because of the deﬁnition (21), the clustering algorithm always returns
feasible solutions (traveltbd is always equal to or larger than the actual travel time).
travelbd = max{δtjl | j ∈ J b , l ∈ J d }
∑ ∑ ∑
FB =
devjl
b,d∈B j∈J b l∈J d

(21)
(22)

In the objective function (22), the clustering error devtjl is replaced with devjl (without t). Because
the set of clusters B is unique in the optimization formulation, the station clustering requires timeindependent representatives of devtjl . We set devjl as the median of devtjl in the case studies describedlater in section 4.

The station clustering algorithm 1 is based on the one in Boyaci et al. [4].
– J : set of stations– Nk : number of clusters– n: maximum number of iterations– FB : objective function to be minimized– B ∗ : set of clusters with the best objective function– Z ∗ : value of the best objective function
1. Create an initial solution (lines from 1 to 15). For all Nk stations, assign each station to eachcluster one by one, and add the station to a cluster which gives the best (minimum) objectivefunction (22). Note that the initial solution depends on the order of stations added.
14

2. Iteratively search for a better solution by exchanging stations between clusters (line 16 below).
（a）Find a station to be removed (lines 21 to 31). For all stations, temporarily remove each stationfrom its cluster one by one, and ﬁnd the removal which improves the objective function themost. We avoid selecting the same stations repeatedly by remembering the stations selected
to be removed in variable C and excluding them from subsequent searches.
（b）Find a cluster to which the removed station can be added (lines 32 to 40). For all clusters
except the one the station was removed from, assign the station to each cluster one by one,and ﬁnd an addition which gives the minimum objective function.
（c）If the new solution has a better (smaller) objective function than the best solution, replace
the best solution with the new solution (line 41). If the best solution is not updated after
every station has been checked to see if it is to be put in a diﬀerent cluster, run the algorithm
for swapping stations between any two clusters to seek a new set of clusters with the smallest
objective function (Algorithm 2). If the new solution has a better (smaller) objective function
than the best solution, replace the best solution with the new solution.

15

Algorithm 1 Clustering stations
Input: J , Nk , n, FB
Output: B ∗ , Z ∗1: for k ← 1 to Nk do
2:
Bb ← ∅
3: end for
4: for j ← 1 to |J | do
5:
Z←∞
6:
for b ← 1 to Nk do
7:
B b ← B b ∪ {j}8:
if FB < Z then9:b∗ ← b; Z ← FB
10:
end if11:
B b ← B b \ {j}12:
end for13:
B b∗ ← B b∗ ∪ {j}14: end for∗
15: B ← B; Z ∗ ← FB
16: C ← ∅17: for i ← 1 to N do
18:
if C = J then
19:
break
20:
end if21:
Z←∞
22:
for b ← 1 to Nk do
23:
for j ∈ J b \ C do24:
B b ← B b \ {j}25:
if FB < Z then26:j ∗ ← j; b∗ ← b; Z ← FB
27:
end if28:
B b ← B b ∪ {j}29:
end for30:
end for31:
B b∗ ← B b∗ \ {j ∗ }; C ← C ∪ {j ∗ }
32:
Z←∞
33:
for b ← 1 to Nk do34:
B b ← B b ∪ {j ∗ }35:
if FB < Z then36:b∗ ← b; Z ← FB
37:
end if38:
B b ← B b \ {j ∗ }39:
end for40:
B b∗ ← B b∗ ∪ {j ∗ }41:
if FB < Z ∗ then42:
B ∗ ← B; Z ∗ ← FB ; C ← ∅43:else if C = J then44:
B ← Swapping stations(B, Z)
45:
if Z < Z ∗ then46:
B ∗ ← B; Z ∗ ← FB ; C ← ∅47:
end if48:
end if
49: end for16

Algorithm 2 Swapping stations
Input: B, Z
Output: B
1: Z0 ← Z
2: for b ← 1 to Nk − 1 do
3:for d ← b + 1 to Nk do
4:for j ∈ J b do
5:
for l ∈ J d do
6:
B b ← B b \ {j}; B d ← B d \ {l}; B b ← B b ∪ {l}; B d ← B d ∪ {j}7:
if FB < Z then8:b∗ ← b; d∗ ← d; j ∗ ← j; l∗ ← l; Z ← FB
9:
end if10:
B b ← B b \ {l}; B d ← B d \ {j}; B b ← B b ∪ {j}; B d ← B d ∪ {l}11:
end for12:
end for13:
end for
14: end for
15: if Z < Z0 then16:
B b∗ ← B b∗ \ {j ∗ }; B d∗ ← B d∗ \ {l∗ }; B b∗ ← B b∗ ∪ {l∗ }; B d∗ ← B d∗ ∪ {j ∗ }17: end if
18: return B

4

Case studies

This section describes case studies on applying the framework developed in section 3 to Ha:mo RIDE
Toyota, which has been operating in Toyota, Japan since 2012. The models were implemented in an
E5-1630 v3 (3.70GHz), 64GB computer running a Windows 8.1 Pro OS and the Gurobi Optimizer 7.0.2
tool.

4.1

Ha:mo RIDE (current service)

The use history for one year from April 1st, 2016 to March 31st, 2017 and station data were provided
by Toyota Motor Corporation*3 .

4.1.1

Station clustering

There were 55 stations operating during the period when the use data was acquired, including one depot
that was oﬀ-limits to users. The travel time δtjl , starting from time interval t between station j andstation l, was estimated using the Google Maps Distance Matrix API [22]. By setting the travel mode
option to ”driving” and specifying the departure time t, the API returns a route distance and trip
duration between two points, taking traﬃc conditions into account. Deviations in trip duration of up toa maximum of 20 minutes were observed in an OD (origin b and destination d) throughout the day, andwe used the travel time at h : 30 as a representative departure time t during [h:00, (h + 1):00). We added
a 3 minute margin (described in 3.2) to the trip durations to make the travel time δtjl . These travel*3 Not allowed to be publicly shared.

17

times were applied to the user as well as relocation staﬀ travels. Note that the travel times between
the same stations but in opposite directions are generally not the same (δtjl ̸= δtlj ). Fig. 10 shows
histograms of route distances and trip durations returned by the Google Maps Matrix API.

(a) Distance(b) Trip duration

Fig. 10: Distribution of (a) distance and (b) trip duration returned by Google Maps Distance Matrix API√
As described in section 3.3, we set the number of clusters so that |B| ≤ |J | holds, where B is theset of clusters and J is the√ set of stations. For the 55 stations, the number of clusters turned out tobe equal to or less than 55, or around 7.4 to reduce computational complexity. Fewer clusters would
result in more errors in the travel time for moving or relocating.
We varied the number of clusters to see how it would aﬀect the objective function. Because clusteringresults depend on the initial solutions, i.e. on the order of stations added, we shuﬄed the stations
randomly and ran the clustering algorithm 25 times per condition and picked the best result. The
maximum number of iterations n was 1,000. As shown in Fig. 11, the objective function was sharply
worse at less than ﬁve clusters. As a result, we decided to use seven clusters, shown as diﬀerent colors
in Fig. 12.

Fig. 11: Aggregate error of diﬀerent numbers of clusters

18

Fig. 12: Ha:mo RIDE Toyota station map. The colors indicate clusters of seven stations.

4.1.2

Optimization settings∑
As mentioned above, the number of stations was 55, and the total number of parking spaces j∈J capj
was 266. The maximum number of vehicles NV was 90. The time period for optimization was 6 am
to 12 am, when demand was relatively high and all stations were open. Fig. 13 shows trip data takenfrom a 2011 person-trip survey conducted in Toyota city, which have a similar distribution to the Ha:mo
RIDE Toyota use data.
The relocation staﬀ shifts are shown in Fig. 14a. It was necessary to set the number of shifts to 2 orless in order to avoid excessive computational time. Shift 0 is a full-time shift in which a manager has towork, and shift 1 is a part-time shift that covers high-demand hours in the evening. The total numberof relocation staﬀ NW was 5, the personnel costs of relocation staﬀ PCs was ¥900 per hour for any shifts, and the maximum labor cost Lcost was ¥27,000 per day (equivalent to 30 man-hours per day).
Instead of estimating potential demand, we generated demand values from the use history according
to a Poisson distribution *4 to run the optimization many times. From the use history, we aggregated*4 For events with an expected occurrence rate of λ, the Poisson distribution describes the probability of x events

19

Fig. 13: Number of trips from/to Toyota City: data from 2011 person-trip survey(a) staﬀ shift #1(b) staﬀ shift #2(only high-demand hours)
Fig. 14: Staﬀ shift

the one-way use data except the data gathered on holidays and calculated the average number of uses
per hour h per OD from station j to l, λhjl . The number of trips departing on h:m (h ∈ [6,23], m ∈5[0,5,10,...,55]) from station j to l was given by a Poisson distribution with an average λhjl × 60
. The end
time of the trip was determined by adding δtjl to the departing time and rounding up to the nearest
ﬁve-minute interval.
The price for trip i (Pi ) was taken to be the actual price: fare of ¥200 for up to 10 minutes and ¥20
per minute after that. The price for a trip from station j to l was calculated as follows:
Pjl = max{P0 , P0 + (δjl − t0 ) × dP} P0 = 200, t0 = 10, P0 = 20

occurring within a ﬁxed interval of time.
P (x) =

λx −λxex!

5Thus, for demands with an average λh in 1 hour (60 minutes), the Poisson distribution with an average λ = λh × 60
gives the number of demands in 5 minutes.

20

˜ bd (1.0) and MC
˜ bd (1.1) reﬂected the use of fuel-eﬃcient
Finally, the relocating costs and moving costs RC
compact cars.

4.1.3

Optimization results

Table 1 shows the results of the optimization compared with data gathered during actual operation.
The numbers are averages of 50 runs with diﬀerent demand samples (satisﬁed demand and proﬁt related
numbers are shown as ratios of the optimization results to the data gathered during actual operation).
Table. 1: Optimization results compared with data from actual operations that served all trips.

Satisﬁed demand ratio [%]Shift #1
83.5

Shift #2
81.3

1.5×demand
105.9

Actual
100.0

1.0
66.8
4.5
1.97
0.84
0.37
0.22

1.0
68.6
2.0
2.54
0.82
0.10
0.10

1.0
72.5
5.5
2.98
1.14
0.37
0.29

5.0
90.0
21.8
1.0
1.0
1.0
1.0

Number of staﬀ working
Number of vehicles used
Number of relocations
Optimized proﬁt compared with actual
Revenue ratio
Personnel costs ratio
Relocation and moving costs ratio

In spite of using a demand generated from the actual history, the satisﬁed demand was only 83.5%.
While the actual operation relocated vehicles with 5 staﬀ in total, the optimal solution had only 1 staﬀ
(manager, forced to work by constraint (15)), thereby cutting personnel costs to maximize proﬁt. The
average revenue was a little over ¥300 because of the average approximate 15-minute travel time. One
set of relocations often consisted of two trips: moving to a station from which a vehicle was to be removed
and the actual relocation, as shown in Fig. 5. The number of relocations per hour was 2 on average*5 .
A two-man team relocated 2 vehicles and cost ¥1,800 per hour, i.e. ¥900 per relocation, a three-man
team relocated 4 vehicles and cost ¥2,700 per hour, i.e. ¥675 per relocation, and so on*6 . The larger
the team was, the less expensive each relocation became, decreasing the driver staﬀ cost per relocationby ¥450 (¥900 per two sets of relocations).
To conﬁrm the above results, we added another case “staﬀ shift #2” (Fig. 14b) with a staﬀ shiftfocusing only on high-demand hours and a case with a staﬀ shift and 1.5 times the demand (“Shift#2”and “1.5×demand” in Table 1). Both cases had only 1 staﬀ and infrequent relocations, which indicatesthat staﬀ-based relocation does not lead to additional revenue.
In “staﬀ shift#1,” the number of vehicles used was 66.8, about 2/3rds of the maximum number ofavailable vehicles. This result suggests that there is a best ratio of the number of vehicles to the numberof parking spaces depending on the relocation frequency. Obviously, the more frequently vehicles are
relocated, the more vehicles should be added, but when vehicles are relocated often, it is better for fewer
vehicles to leave parking spaces available for incoming trips. We will discuss the parking-to-vehicle ratio
in section 4.3.
The optimal solution maximizing proﬁt indicates that the operator should reduce relocation staﬀ. Additional revenues from the short trips of last-mile mobility are too low to cover relocation personnel costs,
and the best operation policy is distributing an appropriate number of vehicles to stations and leaving*5 60 minutes / (15 minutes × 2) = 2.
*6 Note that one of the team has to drive the staﬀ vehicle and cannot relocate vehicles.

21

them there. However, in doing so, the low satisﬁed demand rate would result in customer dissatisfaction
and long-term defection. The operator must relocate vehicles not to increase proﬁt but to maintaincertain levels of satisﬁed demand and retain users.

4.2

Premium Service

Here, in an attempt to cover the costs of relocating personnel, we introduced a “Premium Service”
guaranteeing reservations in return for price premiums. As mentioned in section 1, ridesharing companies
such as Uber and Lyft are implementing special pricing for high-demand hours, called “surge pricing”
and “Premium Time” [32], respectively.

4.2.1

Settings

Here the idea is that demand for premium service must be satisﬁed before demand for the standard
service is satisﬁed. Vehicles are relocated if necessary.
Although premium service should be more popular during high-demand hours and ODs, it is quite
challenging to estimate the potential demand accurately, as it depends on pricing. Instead, we assumed
a 1.5 times total demand and regenerated trips from the average 1.5 × λhjl in the same manner as insection 4.1.2. From these trips, we picked trips randomly at a uniform rate of p per hour and OD, andformed a premium service trip set I p (I p ⊆ I). As for pricing, we set the starting fare higher than thestandard and lower than that of a taxi, ¥300. We ran the optimization at diﬀerent selection ratios p:
1/6 and 1/3.

(a) Demand setting(b) Price setting

Fig. 15: Assumptions of Premium Service

The premium service formulation added the following constraints to those in section 3.2.

∀i ∈ I pzi = 1

Constraints (23) represent that every premium service demand must be satisﬁed.

22

(23)

4.2.2

Results

Table 2 shows the results of premium service optimization. The numbers for the 1/6 and standard-only
cases are averages of 50 runs with diﬀerent demand samples. The numbers for the 1/3 case are averagesof 39 runs out of 50, terminated by a 5,000-second timeout; the remaining 11 runs are infeasible, as
described later. (The satisﬁed demand and proﬁt related numbers are the ratios of the results of thePremium Service to those of the standard service for the 1.5-times demand.)
Table. 2: Premium service compared with current service (standard only)

Premium service demand ratio pStandard only

1/6

1/3

Satisﬁed demand ratio [%]Premium service
Standard service
Number of staﬀ working
Number of vehicles used
Number of relocations
Proﬁt ratio compared with standard only
Revenue ratio
Personnel costs ratio
Relocation and moving costs ratio

72.4
72.4
1.0
72.5
5.5
1.000
1.00
1.00
1.00

72.0
100.0
66.4
1.0
75.4
5.3
1.059
1.05
1.01
0.96

73.4
100.0
59.9
1.7
72.2
6.8
1.024
1.10
1.37
1.29

In the case of p = 1/6, no big diﬀerences from the standard service were observed. The number of staﬀ
remained 1 (manager only).
In the case of p = 1/3, the total satisﬁed demand ratio was almost the same as in the standard case, but
the satisﬁed demand ratio of the standard service decreased by 12.5%, which means standard service
users were pushed out by premium service users, though some runs returned solutions with 2 or 3
relocation staﬀ working to meet the demand. Also, 11 out of 50 runs (22%) were infeasible because of
constraints (23), i.e., the requirement of satisfying the premium service demand, and other constraints
about vehicles, parking spaces, and relocation staﬀ. In other words, premium service could not guarantee
rides because of the shortage of resources such as vehicles, parking, and staﬀ, even under assumption 2that the demand for the whole day is given in advance.
Although the proﬁt might increase in the short term, this service would result in a long term loss or
become infeasible. We conclude that premium service is not worth implementing in our setting.

4.3

Autonomous relocation

In the previous section 4.2, we investigated premium pricing to cover relocation costs. In this section,
we consider self-driving as a way of low-cost relocation. The majority of the relocation costs consistof personnel costs, which exceed additional revenues from trips aﬀorded by the staﬀ-based relocation.
We supposed that unstaﬀed autonomous relocation could increase the number of trips and cover the
relocation costs (Note that we did not consider ﬁxed costs of self-driving such as vehicle remodeling or
infrastructure investments).

23

4.3.1

Settings

Although car makers and ridesharing providers are developing self-driving systems for drivers (Advanced
Driver Assistance Systems or ADAS) and passengers (so-called “robot taxis”), we assumed that selfdriving would only be for autonomous relocation, not for providing rides for users.
Because of it being a not-for-passenger kind of transport, vehicles being relocated do not need to drive
as fast as a human would drive them. Moreover, the vehicles would be required to drive on designatedpaths at low speed. Assuming a 10 km/h speed limit for automatically commanded steering functions[39]*7 or 6 km/h walking speed *8 , low-speed automated relocation would take approximately ﬁve times
longer than manual driving. (Fig. 16 shows the “walking” trip duration calculated from the Google
Maps Distance Matrix API).

Fig. 16: Trip duration on foot, approx. ﬁve times longer than by car in Fig. 10.

We called a trip duration of ﬁve times the duration of driving 4.1 (with the same margin of 3 minutes)“walking speed” and a trip duration of 50 times that of driving “super slow”. Although automateddriving might actually be allowed only at limited times and in limited areas, we did not limit theautonomous relocation time or placement of stations in this case study. We set three levels of potential
demand, 1.2, 1.5, 2.0 times higher than actual demand (equal to the number of uses), in the expectationthat autonomous relocation would increase demand. Vehicle equipment or infrastructure for autonomous
relocation were not included in the formulations, as they were considered to be sunk.

The transformed objective function shown below does not include terms related to personnel costs.

maximize∑Pi zi −i∈I∑ ∑˜ bd r̃bdt
RC

(24)

b,d∈B t∈T

In addition, constraints on shifting relocation staﬀ (4), (5), (6), (13), (14), (15) and moving relocation
staﬀ (8), (16), (18), (19) are omitted, and the ﬂow conservation equations (2) for vehicles and (7) for*7 Currently under discussion to be modiﬁed in the UNECE World Forum for Harmonization of Vehicle Regulations(WP29).
*8 The Cabinet Oﬃce Ordinance speciﬁes the speed of walking assist vehicles to be at most 6 km/h in Japan.

24

relocation are replaced with (25) and (26), respectively. Note that the suﬃx s indicating the staﬀ shift
is omitted from variables r′ , r, r̃.
∑

njt+1 = njt −∑i:origini =jstarti =tr̃bdt =

d∈B

∑

∑
′

∑

∑

zi + rjt∀j ∈ J , t ∈ {0, ..., tlast−1 }(25)∀b ∈ B, t ∈ T(26)

i:desti =jendi =t

′
rjt

j∈J b

r̃dbt′ =d∈B t ∈t.endtdb

4.3.2

′
zi − rjt
+

∑

rjt

j∈J b

Results

Table 3 and Fig. 17 compare the results of optimization with staﬀ-based relocation. The numbers areaverages of 50 runs with diﬀerent demand samples (satisﬁed demand and proﬁt related numbers areshown as ratios of the results of the optimization to the ones of staﬀ-based relocation).
Table. 3: Autonomous drive relocation compared with base case(a) 5-times trip duration (walking speed)

Total demand
Satisﬁed demand ratio [%]

×1.2
99.8%

×1.5
99.7%

×2.0
99.4%

Number of vehicles used
Number of relocations
Relocation / Vehicle(Parking + 2×Relocation) / Vehicle
Proﬁt ratio compared with base caseRevenue ratio
Relocation and moving costs ratio

69.9
33.8
0.48
4.77
1.6
1.2
6.0

79.2
53.0
0.67
4.69
1.6
1.3
9.7

89.1
83.4
0.94
4.86
1.7
1.4
13.6

(b) 50-times trip duration (super slow)

Total demand
Satisﬁed demand ratio [%]

×1.2
94.7%

×1.5
90.9%

×2.0
84.1%

Number of vehicles used
Number of relocations
Relocation / Vehicle(Parking + 2×Relocation) / Vehicle
Proﬁt ratio compared with base caseRevenue ratio
Relocation and moving costs ratio

73.9
24.2
0.33
4.25
1.6
1.2
3.9

85.5
34.1
0.40
3.91
1.5
1.2
5.2

89.9
44.1
0.49
3.94
1.5
1.2
6.4

25

(a) 5-times trip duration (walking speed)(b) 50-times trip duration (super slow)

Fig. 17: Autonomous relocation with station clustering at diﬀerent demand levels

In the walking speed case, the satisﬁed demand ratio is over 99% for all demand cases, including 2.0
times higher than actual (Table 3a). The super slow case is a bit worse, 90% for 1.5 times demandand 84% for 2.0 times demand, but the number of satisﬁed demands is two times more compared with
the no-relocation solution. The relocation cost increases in either case, but its proportion remains asmall fraction of the of revenue, and the proﬁt improves to over 1.5 times that of the base case. In thewalking speed case, along with the increase in potential demand, the number of vehicles used increases
and almost reaches the maximum number of vehicles available at 2.0 times demand. Not only the
number of relocations but also the number of relocations per vehicle increases. The fFrequent vehicle
relocation is considered to increase the per per-parking parking-space operation ratio as well as the perper-vehicle one*9 and avoids a situation where there is a lack of parking spaces caused by an increase in
vehicles. We found the ratio of (parking + 2×relocation) to vehicle rate gives almost the same value (alittle under 5) as the ratio of the parking to vehicle rate described in section 4.1.3. We conjecture thatthe additional term “2×relocation” for parking spaces comes from that one relocation has two eﬀects on
increasing parking capacity: one relocation obviously leaves open a parking space at a station the vehicle
is relocated from and virtually adds a parking space at a station that the vehicle is to be relocated toduring the period in which it is being dispatched.
In the super slow case, the number of relocations per vehicle does not increase as much as in the walking
speed case. Relocation operations cannot meet the increase in demand, because super-slow driving takes
too long to relocate vehicles (for example, driving a distance that usually takes 15 minutes takes 12.5
hours with super-slow driving, 15minutes × 50 = 750minutes). In addition, because of station clustering,
relocation between adjacent stations in actuality are replaced to the longest travels among the station
clusters.

To check how clustering the stations aﬀects the results, we developed another low-speed autonomous
relocation model without station clustering. Because of the absence of relocation staﬀ variables, thewithout-clustering model would be not as computationally expensive as the original model.
We replaced the variable r̃ representing relocation between clusters with r̄ between stations and modiﬁed
˜ for the relocating costs between clusters to RC¯ between stations.
the parameter RC¯ jl : relocating costs from station j to station l– RC*9 (The number of satisﬁed demands) / (the number of vehicles used + the number of relocations) stays at almost thesame level, which indicates that the relocating vehicles works eﬃciently in high high-demand situations.

26

– r̃jlt ∈ Z+ , j, l ∈ J , j ̸= l, t ∈ T : number of vehicle(s) relocating from station j to station ldeparting during time interval t
The reformulation is as follows.
∑

maximizePi zi −

i∈I∑

njt+1 = njt −i:origini =jstarti =t

∑

+

njt ≥

i:origini =jstarti =t

zi +

(27)

∀j ∈ J , t ∈ {0, ..., tlast−1 }(28)∀j ∈ J , t ∈ T

(29)

rjlt

l∈J \{j}

∑

zi +

rljt

l∈J \{j}i:desti =jendi =t∑¯ jl r̄jlt
RCj,l∈J t∈T
j̸=l

∑

zi −

∑ ∑

∑

r̄jlt

l∈J \{j}The objective function (27) maximizes the proﬁt, i.e., the revenue from satisﬁed trips minus the cost of
autonomous relocation. The ﬂow conservation equations for vehicles (28) replace (25), and constraints
for vehicle status (29) replace (3). Constraints (26) are removed because relocation is represented by r̄
without clusters.

Table 4 and Fig. 18 show the optimization results for with- and without- clustering models at 1.5-times
potential demand. The numbers are averages of 50 runs with diﬀerent demand samples. Each calculation
took less than 10 seconds per 50 runs, as fast as expected.
For super super-slow relocation, the without-clustering cases have more relocations than the withclustering cases, which supports the assumption conclusion that the station clustering prevents relocation between adjacent stations. Even in this case, removing station clustering increases the satisﬁeddemand ratio to almost 99% by exploiting vehicles as much as in the walking speed case. In addition,
the ratio of (parking + 2×relocation) to vehicle rate increased to the same level as in the walking speedcase, which suggests that autonomous relocation suﬃciently expands the parking capacity. This feature,virtual parking increase, especially suits the last-mile mobility scenario with many small stations scattered all over a city. Finally, Fig. 19 shows the results for one-day operation of autonomous relocation
at 50 times the trip duration (super slow ) without station clustering.

27

Table. 4: Autonomous relocation with and without clustering at 1.5-times demand(a) Five-times trip duration (walking speed)

clustering

Yes

No

99.7%

99.9%

Number of vehicles used
Number of relocations
Relocation / Vehicle(Parking + 2×Relocation) / Vehicle

79.2
53.0
0.67
4.69

85.5
68.3
0.80
4.71

Computation time [sec]

0.53

7.44

Satisﬁed demand ratio [%](b) Trip duration 50 times (super slow)

clustering

Yes

No

90.9%

98.8%

Number of vehicles used
Number of relocations
Relocation / Vehicle(Parking + 2×Relocation) / Vehicle

85.5
34.1
0.40
3.91

87.4
69.7
0.80
4.64

Computation time [sec]

0.31

6.32

Satisﬁed demand ratio [%](a) 5-times trip duration (walking speed)(b) 50-times trip duration (super slow)

Fig. 18: Autonomous relocation with and without station clustering at 1.5-times demand

4.4

Adding more staﬀ vehicles

As modeled in section 3, the current Ha:mo RIDE service uses only one staﬀ vehicle. In this section, we
assume that multiple staﬀ vehicles can be used and discuss the eﬀect of increasing the number of staﬀ
vehicles on the models described in section 4.2.

28

(a) Served trips(b) Autonomous relocation

Fig. 19: Diagram of one-day operation in 50-times trip duration (super slow) autonomous relocation without
station clustering at 1.5-times demand

4.4.1

Settings

To model this situation, we introduce the following additional sets and variables.
– v ∈ N SV : staﬀ vehicles.
– p′svjt ∈ Z+ , ∀s ∈ S, v ∈ N SV , j ∈ J , t ∈ {begins , ..., ﬁns }: number of staﬀ of shift s movingfrom station j during time interval t by staﬀ vehicle v.
– psvjt ∈ Z+ , ∀s ∈ S, v ∈ N SV , j ∈ J , t ∈ {begins , ..., ﬁns }: number of staﬀ of shift s moving tostation j during time interval t by staﬀ vehicle v.
– p̃svbdt ∈ Z+ , ∀s ∈ S, v ∈ N SV , b, d ∈ B, t ∈ {begins , ..., ﬁns }: number of staﬀ in shift s movingfrom cluster b to cluster d during time interval t by staﬀ vehicle v.
– lvjt ∈ {0, 1}, ∀v ∈ N SV , j ∈ J , t ∈ T : binary variables, 1 if relocation staﬀ and staﬀ vehicle v
exist at station j during time interval t, 0 otherwise.
– u′vjt ∈ {0, 1}, ∀v ∈ N SV , j ∈ J , t ∈ T : binary variables, 1 if relocation staﬀ moves out fromstation j during time interval t by staﬀ vehicle v, 0 otherwise.
– uvjt ∈ {0, 1}, ∀v ∈ N SV , j ∈ J , t ∈ T : binary variables, 1 if relocation staﬀ moves to station j
during time interval t by staﬀ vehicle v, 0 otherwise.
Using the above set and variables, constraints (4), (5), (6), (8), (16), (17), (18) and (19) are replaced by(30), (31), (32), (33), (34), (35), (36) and (37), respectively.
∑∑
msjfins + rsjfins +psvjfins = vs∀s ∈ S(30)
j∈Jv∈N SV29∑

msjt+1 = msjt −∑′p′svjt − rsjt+

v∈N SV

psvjt + rsjt

∀s ∈ S, j ∈ J , t ∈ {begins , .., ﬁns − 1}v∈N SV(31)
msjt ≥∑′
p′svjt + rsjt

∀s ∈ S, j ∈ J , t ∈ {begins , ..., ﬁns }(32)v∈N SV∑p̃svbdt =d∈B∑p′svjt

j∈J b

∑

∑

p̃svdbt′ =′d∈B t ∈t.endtdb ∩{begins ,...,fins }

∑

psvjt

j∈J b

∀s ∈ S, v ∈ N SV , b ∈ B, t ∈ {begins , ..., ﬁns } (33)∑p′svjt ≤ NWu′vjt

s:begins ≤t≤fins∑

psvjt ≤ NWuvjt∀v ∈ N SV , j ∈ J , t ∈ T(34)

psvjt ≥ uvjt

∀v ∈ N SV , j ∈ J , t ∈ T(35)

lvjt+1 = lvjt − u′vjt + uvjt∑
lvj0 ≤ 1j∈J∀v ∈ N SV , j ∈ J , t ∈ T(36)∀v ∈ N SV(37)

s:begins ≤t≤fins∑p′svjt ≥ u′vjt

s:begins ≤t≤fins∑

s:begins ≤t≤fins

According to the situation, we also modify the objective function (1) which maximizes the total daily
proﬁt including revenues from users’ served trips, personnel costs of relocation staﬀ, and relocating andmoving costs (cost of fueling the staﬀ vehicle) between clusters, as follows:
∑
∑
∑ ∑
∑
˜ bd r̃sbdt
maximizePi zi −
PCs vs −RCi∈Is∈Ss∈S b,d∈B t∈{begins ,...,fins }∑ ∑∑∑˜ bd p̃svbdt
−
MC
(38)
s∈S b,d∈B t∈{begins ,...,fins } v∈N SV

4.4.2

Results

As in section 4.2.1, we assumed a 1.5 times total demand and regenerated trips from the average 1.5×λhjl .
We set the premium service demand ratio p for randomly picking the trips as 1/6, the starting fare as¥300, and the total number of relocation staﬀ to 5.
As the number of staﬀ vehicles increased, the calculation time to obtain an optimal solution became
quite long, and we terminated each run at 5000 seconds. Table 5 shows the results for the cases of one,30

two, and three vehicles. Proﬁt, personnel costs, relocation and moving costs are indicated by the ratio
when the actual operation result is 1. For one vehicle, each number is the average of 49 runs excluding
1 run for which a feasible solution was not obtained within 5000 seconds. For the cases of two (three)vehicles, each number is the average of 47 (48) times excluding 3 (2) runs.
We also performed runs with a premium service demand ratio of p = 1/3 and two staﬀ vehicles, but for
17 runs, no feasible solution could be obtained within 5000 seconds and for the remaining seven runs,
no reasonable objective function values were found. Therefore, we will not discuss those results here.
Table. 5: Increase in the number of staﬀ vehicles for premium service demand ratio of p = 1/6

Number of staﬀ vehicles

1 vehcle

2 vehicles

3 vehicles

Satisﬁed demand ratio [%]Premium service
Standard service
Number of staﬀ working
Number of vehicles used
Number of relocations
Proﬁt ratio compared with actual
Revenue ratio
Personnel costs ratio
Relocation and moving costs ratio
Computation time [sec]Number of variables

72.0
100.0
66.4
1.02
75.4
5.26
3.16
1.19
0.37
0.28
1071.8126366.5

73.3
100.0
67.8
1.06
72.6
7.02
3.17
1.21
0.39
0.41
3652.2
186515.4

74.5
100
69.4
1.10
73.4
8.48
3.17
1.22
0.40
0.52
4437.3246663.8

The number of relocation operations increases with the number of staﬀ vehicles. As a result, the numberof satisﬁed trip demands increases. Taken alone, this result would allow us to conclude that increasing
the number of staﬀ vehicles is eﬀective, but personnel costs and relocation and moving costs would also
increase. Thus, we could not conﬁrm a signiﬁcant increase in proﬁt.
Fig. 20a, 20b, and 20c show diagrams of one-day relocation operations for the cases of one, two, and threestaﬀ. The relocation range is almost the same when there are one or two vehicles and the relocations
concentrate where demand is the highest (see Fig. 19a). For three vehicles, the range of the relocations
is expanded.

4.5

Absence of parking-space reservation

As mentioned on page 8 in section 3, parking spaces must be assigned to each trip from the beginning of
the trip. The reservation of parking spaces at destinations is important for actual smooth Ha:mo RIDE
Toyota operation.However, so far in this study, we have assumed that all users trip data for one day
are given and that the start and end time intervals of each trip are known. In other words, even if there
is no ”free” parking space at the arrival station at the start time, there are cases where ”free” parking
space is available at the end time and which can be computed exactly through optimization. Here, we
modify the premium service model in section 4.2 and the autonomous relocation model in 4.3 to omit
the constraint for reserving parking spaces at destinations and discuss the eﬀect.
If there is no need for reserving parking spaces at destinations, we can remove constraints (11) andthe variable n′jt for the number of parking spaces at station j at the beginning of time interval t from31

(a) One staﬀ vehicle(b) Two staﬀ vehicles(c) Three staﬀ vehicles
Fig. 20: Diagram of one-day relocation operation with station clustering32

constraints (12) as follows:njt ≤ capj∀j ∈ J , t ∈ T(39)

By making these two modiﬁcations to each model, we obtain a modiﬁed premium service and autonomous
relocation model where the destination parking space is not reserved at the beginning of trips.

4.5.1

Results: Premium service

As in section 4.2.1, we assumed a 1.5 times total demand and regenerated trips from the average 1.5×λhjl .
We also set the premium service demand ratio p for randomly picking the trips as 1/6 and 1/3. The
starting fare was ¥300, the total number of relocation staﬀ was 5, and the number of staﬀ vehicles was
1.
We terminated each run at 5000 seconds since the calculation time to obtain an optimal solution became
quite long in some cases. Table 6 compares the cases with- and without- parking space reservation
constraints when the premium service demand ratio is set to 1/6. Proﬁt, personnel costs, relocation andmoving costs are indicated by the ratio when the actual operation result is 1. Each number is the averagevalue of 49 runs excluding 1 run for which a feasible solution was not obtained within 5000 seconds forthe case with the parking space reservation constraint.
Table. 6: Premium service without parking space reservation requirement (p = 1/6)

parking space reservation
Satisﬁed demand ratio [%]Premium service
Standard service
Number of staﬀ working
Number of vehicles used
Number of relocations
Proﬁt ratio compared with actual
Revenue ratio
Personnel costs ratio
Relocation and moving costs ratio
Computation time [sec]Number of variables

Yes

No

72.0
100.0
66.4
1.02
75.4
5.30
3.16
1.19
0.370
0.278
1071.8126366.5

72.3
100.0
66.7
1.04
75.2
5.50
3.17
1.20
0.374
0.285
891.3
114452.7

Table 7 compares results for cases with- and without- parking space reservation constraints when thepremium service demand ratio is set to 1/3. Each number is the average of 39 runs, excluding 11 runs
for which a feasible solution was not obtained within 5000 seconds for the case with a parking spacereservation constraint.
In both cases, removing the parking space reservation constraints slightly increased the satisﬁed demandratio of the premium service to that of the standard service and the proﬁt ratio compared with the cases
in which a parking space reservation is required. The changes were small, although signiﬁcant decreases(about 15%) in calculation time were observed. These results suggest that the parking space reservation
constraint is not so severe a restriction in terms of proﬁt, but that it does have a severe eﬀect on the
optimization calculation under our settings.

33

Table. 7: Premium service without parking space reservation requirement (p = 1/3)

parking space reservation
Satisﬁed demand ratio [%]Premium service
Standard service
Number of staﬀ working
Number of vehicles used
Number of relocations
Proﬁt ratio compared with actual
Revenue ratio
Personnel costs ratio
Relocation and moving costs ratio
Computational time [sec]Number of variables

4.5.2

Yes

No

73.4
100.0
60.0
1.69
72.2
6.80
3.06
1.26
0.500
0.376
3112.9126330.3

73.5
100.0
60.2
1.56
75.3
6.70
3.14
1.26
0.474
0.367
2627.6114450.3

Results: Autonomous relocation

Here, we discuss the results for when parking space reservation constraints are removed from the autonomous relocation model in section 4.3. We assumed a 1.5 times total demand and regenerated trips
from the average 1.5 × λhjl .
Tables 8a and 8 compares results for cases with- and without- parking space reservation constraints
when the trip duration is ﬁve times (walking speed) and ﬁfty times (super slow), respectively. Proﬁt,
personnel costs, relocation and moving costs are indicated by the ratio when the actual operation result
is 1. Each number is the average value of 50 runs.
For both cases, removing the parking space reservation constraint increased the satisﬁed demand ratio
slightly. The changes were small, but there were signiﬁcant decreases (about 16%) in calculation time.
Similarly to the case of the premium service, the parking space reservation constraint may be not sosevere a restriction in terms of proﬁt, but it may have severe eﬀects on the optimization calculation in
our autonomous relocation settings.

5

Conclusion

We developed an optimization model specialized for last-mile mobility, short-trip one-way carsharing.
The model reﬂected the characteristics of last-mile mobility that requires both vehicles and parking
spaces to be reserved and vehicles to be relocated by using a team in staﬀ vehicles. In addition, we
improved the station clustering algorithm by reducing its computational complexity.
We applied the developed model to ﬁve diﬀerent cases, in combination with the improved station clustering. The ﬁrst case, Ha:mo RIDE, revealed that the characteristic short trips did not generate enoughadditional revenue to cover relocation costs. The optimal solution to maximize the operator’s proﬁt
was cutting relocation personnel costs, which would result in dissatisfaction and long-term customer
defection. The operator must relocate vehicles not for proﬁt, but for customer retention. The second
case, “Premium Service,” which guarantees rides in return for price premiums, could not resolve the34Table. 8: Autonomous relocation with the absence of parking space reservation (1.5× demand)(a) Five-times trip duration (walking speed)

parking space reservation

Yes

No

99.7%

99.8%

Number of vehicles used
Number of relocations
Relocation / Vehicle(Parking + 2×Relocation) / Vehicle

79.2
53.0
0.67
4.69

79.2
52.9
0.68
4.69

Computation time [sec]

0.53

0.43

Satisﬁed demand ratio [%](b) Trip duration 50 times (super slow)

parking space reservation

Yes

No

90.9%

91.0%

Number of vehicles used
Number of relocations
Relocation / Vehicle(Parking + 2×Relocation) / Vehicle

85.5
34.1
0.40
3.91

85.5
33.2
0.39
3.89

Computation time [sec]

0.31

0.26

Satisﬁed demand ratio [%]issue; low demand for the new service led to not enough premiums to cover relocation costs, while highdemand was infeasible due to shortage of resources, even when assuming that the whole-day demand wasgiven in advance. The third case, autonomous relocation by low-speed self-driving, showed the prospect
for low-cost operation together with high demand satisfaction. Even driving at 1/10th of walking speed
satisﬁed almost 1.5 times the demand that can be expected in actual use. The workforce case, i.e., increasing the number of staﬀ vehicles, showed that by increasing the number of staﬀ vehicles, the satisﬁeddemand ratio increased, but personnel costs and relocation and moving costs also increased. Thus, we
could not conﬁrm a signiﬁcant increase in proﬁt in this case. The results for the ﬁfth case, removing theparking space reservation requirement, implied that, in both premium service and autonomous relocation
settings, removing parking space constraints may not be so severe from the viewpoint of raising proﬁt,
but it may be rather severe from the viewpoint of the optimization calculation.
Although we assumed that autonomous relocation was available at all stations, this assumption would
face challenges, due to regulations, diﬀerent road environments, etc., in an actual implementation. To
demonstrate the eﬀect of autonomous relocation, the ﬁrst step should be a small-scale ﬁeld test in alimited area, like a small valet parking. The 5th Science and Technology Basic Plan of the Japanese
government [13] calls for implementations in speciﬁc areas such as the Tsukuba Mobility Robot Experimental Zone.
We assumed the demand for the whole day was given at the beginning of the day, but actual demandis at the earliest 30 minutes before a ride. In addition, we generated demand samples from the 1-year
average demand and ignored the deviations. Incorporating a mechanism for dealing with short-noticedemand with deviations will be one of the biggest challenges facing an actual implementation. One idea
to deal with it is combining long-term estimation and short-term modiﬁcation. We observed substantial
deviations in seasonal demand. Perhaps previous uses such as commuting in the morning can explain
the trend. Or perhaps weather, day of the week, or other events can be explanatory variables.

35

Another research idea is adaptive pricing, which has been studied in Ha:mo RIDE but is not implemented
yet. Appropriate pricing in combination with autonomous relocation can balance demand for vehicles
and parking space supply and increase proﬁt.

6

Acknowledgement

This work was supported by the joint program of the University of Tsukuba and Toyota Motor Corporation, titled “Research on the next generation social systems and mobilities”. We are deeply grateful to
Toyota Motor Corporation for providing the data and valuable comments on our work. We also thankthe Toyota InfoTechnology Center and Kozo Keikaku Engineering for the use of the mobility-sharing
simulator.

References[1] N. Agatz, A.L. Erera, M. Savelsbergh, and X. Wang, Dynamic ride-sharing: A simulation study inmetro Atlanta, Transportation Research Part B 45 (2011) 1450–1464. doi:10.1016/j.trb.2011.
05.017[2] A. Braverman, J.G. Dai, X. Lin, and L. Ying, Empty-car routing in ridesharing systems, arXiv
preprint arXiv:1609.07219. https://arxiv.org/abs/1609.07219[3] B. Boyaci, K. Zografos, and N. Geroliminis, An optimization framework for the development ofeﬃcient one-way car-sharing systems, European Journal of Operational Research 240 (2015) 718–
733. doi:10.1016/j.ejor.2014.07.020.
[4] B. Boyaci, K. Zografos, and N. Geroliminis, An integrated optimization-simulation framework forvehicle and personnel relocations of electric carsharing systems with reservations, Transportation
Research Part B 95 (2017) 214–237. doi:10.1016/j.trb.2016.10.007.
[5] G. Brandstatter, M. Kahr, and M. Leitner, Determining optimal locations for charging stations ofelectric car-sharing systems under stochastic demand, Transportation Research Part B 104 (2017)
17–35. doi:10.1016/j.trb.2017.06.009[6] D. Celebi, A. Yorusun, and H. Isik, Bicycle sharing system design with capacity allocations, Transportation Research Part B 114 (2018) 86–98. doi:10.1016/j.trb.2018.05.018[7] C.M. Chardon, and G. Caruso, Estimating bike-share trips using station level data, Transportation
Research Part B 78 (2015) 260–279. doi:10.1016/j.trb.2015.05.003[8] T.D. Chen, K.M. Kockelman, and J.P. Hanna, Operations of a shared, autonomous, electric vehicle
ﬂeet Implications of vehicle & charging infrastructure decisions, Transportation Research Part A 94
(2016) 243–254. doi:10.1016/j.tra.2016.08.020[9] Y. Chen, and H. Wang, Pricing for a last-mile transportation system, Transportation Research Part
B 107 (2018) 57–69. doi:10.1016/j.trb.2017.11.008[10] COMS (Japanese only), Toyota Auto Body, http://coms.toyotabody.jp/ (2012).
[11] G. Correia, and A. Antunes, Optimization approach to depot location and trip selection in oneway carsharing systems, Transportation Research Part E 48 (2012) 233–247. doi:10.1016/j.tre.
2011.06.003.
[12] G. Correia, D. Jorge, and A. Antunes, The added value of accounting for users’ ﬂexibility and information on the potential of a station-based one-way car-sharing system: An application in Lisbon,
Portugal, Journal of Intelligent Transportation Systems: Technology, Planning, and Operations 18(2014) 299–308. doi:10.1080/15472450.2013.836928.
[13] Council for Science, Technology and Innovation Cabinet Oﬃce, Government of Japan, Reporton The 5th Science and Technology Basic Plan, http://www8.cao.go.jp/cstp/kihonkeikaku/
5basicplan_en.pdf (December 2015).
36

[14] Y. Deng, and M.A. Cardin, Integrating operational decisions into the planning of one-way vehiclesharing systems under uncertainty, Transportation Research Part C 86 (2018) 407–424. doi:10.
1016/j.trc.2017.11.018[15] Y. Dong, S. Wang, L. Li, and Z. Zhang, An empirical study on travel patterns of internet based
ride-sharing, Transportation Research Part C 86 (2018) 1–22. doi:10.1016/j.trc.2017.10.022[16] M. Drwal, E. Gerding, S. Stein, K. Hayakawa, and H. Kitaoka, Adaptive pricing mechanisms foron-demand mobility, in: 16th International Conference on Autonomous Agents and Multiagent
Systems, Sao Paulo, Brazil, 2017.
[17] A.L. Erera, J.C. Morales, and M. Savelsbergh, Robust optimization for empty repositioning problems, Operations Research 57(2) (2018) 468–483. doi:10.1287/opre.1080.0650[18] D. Fagnant, K.M. Kockelman, and P. Bansal, Operations of a shared autonomous vehicle ﬂeet for
the Austin, Texas market, Transportation Research Record 2536 (2015) 98–106.
[19] J. Farhan, and D. Chen, Impact of ridesharing on operational eﬃciency of shared autonomous
electric vehicle ﬂeet, Transportation Research Part C 93 (2018) 310–321. doi:10.1016/j.trc.
2018.04.022[20] I.A. Forma, T. Raviv, and M. Tzur, A 3-step math heuristic for the static repositioning problem
in bike-sharing systems, Transportation Research Part B 71 (2015) 230–247. doi:10.1016/j.trb.
2014.10.003[21] L. Ghaoui, M. Oks, and F. Oustry, Worst-Case Value-At-Risk and robust portfolio optimization:
A Conic Programming approach, Operations Research 51(4) (2003) 543–556. doi:10.1287/opre.
51.4.543.16101[22] Google Maps Distance Matrix API, Google, https://developers.google.com/maps/
documentation/distance-matrix/ (2017).
[23] J.P. Hanna, M. Albert, D. Chen, and P. Stone, Minimum Cost Matching for Autonomous Carsharing, IFAC-PapersOnLine 49-15 (2016) 254–259. doi:10.1016/j.ifacol.2016.07.757[24] L. He, H. Mak, Y. Rong, and Z. Shen, Service region design for urban electric vehicle sharing systems,
Manufacturing & Service Operations Management 19(2) 309–327. doi:10.1287/msom.2016.0611[25] D. Jorge, and G. Correia, Carsharing systems demand estimation and deﬁned operations: a literature review, European Journal of Transportation Infrastructure Research 13 (2013) 201–220.
[26] D. Jorge, G. Molnar, and G.H.A. Correia, Trip pricing of one-way station-based carsharing networks
with zone and time of day price variations, Transportation Research Part B 81 (2015) 461–482.
doi:10.1016/j.trb.2015.06.003[27] D. Jorge, G. Correia, and C. Barnhart, Comparing optimal relocation operations with simulated
relocation policies in one-way carsharing systems, IEEE Transactions on Intelligent Transportation
Systems 15 (2014) 1667–1775. doi:10.1109/TITS.2014.2304358.
[28] A. Kek, R. Cheu, Q. Meng, and C. Fung, A decision support system for vehicle relocation operations
in carhsring systems, Transportation Research Part E 45 (2009) 149–158. doi:10.1016/j.tre.
2008.02.008.
[29] X. Liang, G. Correia, and B. Arem, Optimizing the service area and trip selection of an electricautomated taxi system used for the last mile of train trips, Transportation Research Part E 93(2016) 115–129. doi:10.1287/10.1016/j.tre.2016.05.006[30] J. Naoum-Sawaya, R. Cogill, B. Ghaddar, S. Sajja, R. Shorten, N. Taheri, P. Tommasi, R. Verago, and F. Wirth, Stochastic optimization approach for the car placement problem in ridesharing
systems, Transportation Research Part B 80 (2015) 173–184. doi:10.1016/j.trb.2015.07.001[31] Prime Minister of Japan and His Cabinet, 未来投資戦略 2017 (Japanese only), https://www.
kantei.go.jp/jp/singi/keizaisaisei/pdf/miraitousi2017_t.pdf (June 2017).
[32] RideGuru, How to Navigate Lyft’s Prime Time Fares, https://ride.guru/content/newsroom/
how-to-navigate-lyfts-prime-time-fares (October 2016).
[33] J.P. Schwieterman, and A. Bieszczat, The cost to carshare A review of the changing prices andtaxation levels for carsharing in the United States 2011―2016, Transport Policy 57 (2017) 1–9.
doi:10.1016/j.tranpol.2017.03.017
37

[34] K. Shimazaki, M. Kuwahara, A. Yoshioka, Y. Homma, M. Yamada, and A. Matsui, Developmentof a simulator for one-way ev sharing service, in: 20th ITS World Congress Tokyo 2013, Tokyo,
Japan, 2013.
[35] M. Stiglic, N. Agatz, M. Savelsbergh, and M. Gradisar, The beneﬁts of meeting points in ride-sharing
systems, Transportation Research Part B 82 (2015) 36–53. doi:10.1016/j.trb.2015.07.025[36] Toyota Motor Corporation, Ha:mo, Harmonious Mobility Network, http://www.toyota-global.
com/innovation/intelligent_transport_systems/hamo/ (2013).
[37] Toyota Motor Corporation, i-ROAD, http://www.toyota-global.com/innovation/personal_
mobility/i-road/ (2014).
[38] Uber, Steel City’s New Wheels, https://www.uber.com/blog/pittsburgh/new-wheels/ (May2016).
[39] UNECE, Automatically Commanded Steering Function, ACSF-01-11-(J) concept paper, https://wiki.unece.org/display/trans/ACSF+1st+session (2015).
[40] H. Wang, Routing and scheduling for a last-mile transportation system, Transportation Science.
doi:10.1287/trsc.2017.0753[41] Y. Wang, M.A. Douglas, B.T. Hazen, and M. Dresner, Be green and clearly be seen How consumer
values and attitudes aﬀect adoption of bicycle sharing, Transportation Research Part F 58 (2018)730–742. doi:10.1016/j.trf.2018.06.043[42] M. Xu, Q. Meng, and Z. Liu, Electric vehicle ﬂeet size and trip pricing for one-way carsharing
services considering vehicle relocation and personnel assignment, Transportation Research Part B
111 (2018) 60–82. doi:10.1016/j.trb.2018.03.001[43] Z. Xu, Y. Yin, and L. Zha, Optimal parking provision for ride-sourcing services, Transportation
Research Part B 105 (2017) 559–578. doi:10.1016/j.trb.2017.10.003

38