# Repositioning Bikes with Carrier Vehicles and Bike Trailers in Bike Sharing
Systems

Xinghua Zheng1, Ming Tang1, Hankz Hankui Zhuo1, Kevin X. Wen2
1School of Data and Computer Science, Sun Yat-Sen University, Guangzhou, China
510006
2Department of Computer Science, University of California, Santa Cruz,
California, US
{zhengxh5@mail3,tangm28<EMAIL_ADDRESS><EMAIL_ADDRESS>corresponding author

###### Abstract

Bike Sharing Systems (BSSs) have been adopted in many major cities of the
world due to traffic congestion and carbon emissions. Although there have been
approaches to exploiting either bike trailers via crowdsourcing or carrier
vehicles to reposition bikes in the “right” stations in the “right” time, they
do not jointly consider the usage of both bike trailers and carrier vehicles.
In this paper, we aim to take advantage of both bike trailers and carrier
vehicles to reduce the loss of demand with regard to the crowdsourcing of bike
trailers and the fuel cost of carrier vehicles. In the experiment, we exhibit
that our approach outperforms baselines in several datasets from bike sharing
companies.

## Introduction

Bike sharing systems (BSSs) typically have a set of base stations that are
strategically placed throughout a city and each station has a fixed number of
docks, e.g., Capital Bikeshare111https://www.capitalbikeshare.com,
Bluebikes222https://www.bluebikes.com, Mobike333https://mobike.com/global/,
BIXI444https://montreal.bixi.com, etc. At the beginning of the day, each
station is stocked with a pre-determined number of bikes. Customers can pick
and drop bikes from any station and are charged depending on the hiring
duration (?; ?; ?; ?; ?).

Due to the individualistic and uncoordinated movements of customers, there is
often starvation (empty base stations precluding bike pickup) or congestion
(full base stations precluding bike return) of bikes at certain stations,
which results in a significant loss of customer demand (?; ?). To address this
problem, a variety of systems (?; ?) employ the idea of repositioning idle
bikes with the help of carrier vehicles during the day, by taking into account
the movement of bikes by customers (?; ?; ?). While previous approaches of
repositioning can help reduce imbalance, repositioning idle bikes using
carrier vehicles (c.f. (?)) incurs substantial routing and fuel costs while
covering entire stations555A carrier vehicle is a truck to reposition idle
bikes during the day using myopic and adhoc methods so as to return to a pre-
determined configuration.(e.g., each carrier vehicle can hold 30-40 bikes, its
working distance is 5 kilometers away).. In addition, repositioning idle bikes
using bike trailers just carries a few of bikes once and the moving distance
is limited666A bike trailer is an add-on to a bike that can carry a small
number of bikes (e.g., each bike trailer can hold 3-5 bikes, its working
distance is within 5 kilometers) and is useful to relocate bikes to nearby
stations., which restrict the usage of bike trailers to reposition bikes among
stations.

In this paper, we propose an optimization model called (DRRPVT), which stands
for Dynamically Repositioning and Routing Problem with carrier Vehicles and
bike Trailers, to jointly consider the usage of carrier vehicles and bike
trailers. We aim to better optimize the overall profit of hired bikes and
consequently reduce the expected loss of demand. Specifically, we build a
profit objective function to calculate the value of carrier vehicle routing
(i.e., fuel cost) and bike trailers (i.e., payment for the users of bike
trailers), by considering a variety of constraints with respect to carrier
vehicle routing and bike repositioning. Jointly considering both carrier
vehicles and bike trailers is challenging in the sense that we need to
introduce new constraints to encode relations between carrier vehicles and
bike trailers, and build a novel objective function to minimize the cost of
repositioning (and routing) and the loss of demand. Besides, to improve the
efficiency of our approach with respect to large-scale stations (as well as
carrier vehicles and bike trailers), we need to design an effective mechanism
for computing main base stations to help reduce the computation time.

In summary, our contributions are two folds. We first propose an optimization
model to improve the performance of dynamic bike repositioning by exploiting
both carrier vehicles and bike trailers simultaneously, which is different
from previous approaches which only consider either trailers or carrier
vehicles, but not both. To do this, we build a novel profit objective function
and new constraints considering relationships between carrier vehicles and
bike trailers. Second, we design a clustering mechanism for computing main
base stations to help improve the efficiency of solving the optimization model
regarding large-scale stations and carrier vehicles and bike trailers.

## Related Work

There have been many approaches proposed to deal with bike sharing issues,
which can be categorized into three aspects (?; ?), i.e., static repositioning
using carrier vehicles, dynamic repositioning using carrier vehicles, and
dynamic repositioning using bike trailers.

##### Static repositioning using carrier vehicles

Static repositioning is the problem of finding routes for a fleet of vehicles
to reposition bikes at the end of the day when the movements of bikes by
customers are negligible, to achieve a pre-determined inventory level at the
stations(?). As user demands change frequently during the day, those
approaches are not capable of dynamically adjusting the station inventory
level with respect to user demands.

##### Dynamic repositioning using carrier vehicles

To consider dynamic repositioning using carrier vehicles with respect to the
movements of customers during the day, Lowalekar et al. provide a scalable
online repositioning solution using multistage stochastic optimization with
online anticipatory algorithms (?; ?). Pierre et al. develop a efficient
mechanism to maximize the decision intervals between repositioning events by
online rebalancing operations(?; ?).As dynamic repositioning using vehicles
alone incurs substantial routing and fuel cost, those approaches should be
improved by considering self-sustaining and environment friendly.

##### Dynamic repositioning using bike trailers

To consider the self-sustaining and environment issues, instead of using
vehicles, Ghosh et al. propose a pricing mechanism that takes the global view
of the repositioning requirements and incentives the execution of bike-trailer
tasks (based on crowdsourcing) within the budget constraints (?; ?). Despite
the success of those approaches, bike trailers can only take a few bikes at
once and the distance of movements is limited. Besides, the value of
crowdsourcing tasks may be high (over the available budget).

Different from previous approaches, our DRRPVT approach aims to leverage the
advantage of using both carrier vehicles, which is able to take a large number
of bikes and move to longer distance, and bike trailers, which is able to move
to short distance with limited cost and allow self-sustaining, by considering
the expected profit and the loss demands reduction of repositioning and
routing solution (?; ?).

## Problem Formulation

Our bike sharing problem is formally defined by the following tuple:
$\langle\mathcal{S},\mathcal{V},\mathcal{F},\mathcal{C}^{\\#},\mathcal{C}^{*},d^{\\#},d^{*},\sigma,R,P,\hat{P},D,B\rangle$,
where

  * •

$\mathcal{S}$ denotes the set of base stations.

  * •

$\mathcal{V}$ denotes the set of vehicles used for repositioning which
restricted to carrier vehicles only.

  * •

$\mathcal{F}$ denotes samples of customer requests for the future time steps
with $F_{s,s^{\prime}}^{t}$ indicating the number of customer requests between
stations $s$ and $s^{\prime}$ which start at decision epoch $t$ and end at
decision epoch $t+1$.

  * •

$\mathcal{C}^{\\#}$ denotes the capacity of stations with $C_{s}^{\\#}$
indicating capacity of station $s$.

  * •

$\mathcal{C}^{*}$ denotes the capacity of carrier vehicles with $C_{v}^{*}$
indicating capacity of vehicle $v$.

  * •

$d^{\\#}$ denotes the distribution of bikes at stations with $d_{s}^{\\#,t}$
indicating the number of bikes at station $s$ at decision epoch $t$.

  * •

$d^{*}$ denotes the distribution of bikes in vehicles with $d_{v}^{*}$
indicating the number of bikes in vehicle $v$ at decision epoch $t$.

  * •

$\sigma$ denotes the distribution of carrier vehicles at stations, with
$\sigma_{v,s}^{t}$ set to be 1 if vehicle $v$ is present at station $s$ at
decision epoch $t$ and 0 otherwise.

  * •

$R$ denotes the revenue of bikes being hired, with $R_{s,s^{\prime}}^{t}$
indicating the revenue from station $s$ to $s^{\prime}$ which starts at
decision epoch $t$ and ends at decision epoch $t+1$.

  * •

$D$ denotes the actual distance with $D_{s,s^{\prime}}$ indicating the
distance between stations $s$ and $s^{\prime}$.

  * •

$B$ denotes the total budget for all trailers to bid. In other words, the
total amount of value spent on trailers should not be larger than $B$.

  * •

$\hat{P}$ denotes the value for executing the task of bike trailer with
$\hat{P}_{s,{s}^{\prime}}$ indicating the value for executing the task of bike
trailer picking up idle bikes at station $s$ and dropping off them at station
${s}^{\prime}$.

  * •

$P$ denotes the routing value (e.g., fuel cost) for vehicles travelling with
$P_{s,s^{\prime}}$ indicating the routing value for vehicles travelling from
station $s$ to $s^{\prime}$ which depends on the distance between the two
stations.

We make the following assumptions for the ease of explanation and
representation:

  1. 1.

We assume that users who carry bikes and trailers at decision epoch $t$ always
return their bikes at the beginning of the decision epoch $t+1$. The duration
of each decision epoch is 30 minutes 777We evaluate shorter duration impacts
on runtime performance. Reducing the duration of time step notably increases
the runtime. There is a trade-off between utility and runtime in deciding the
duration of time step. Although the performance in terms of profit and lost
demand decreases by a small amount for 30 minutes of time step (over 15
minutes of time step), it provides a significant computational gain and is
particularly helpful when solving large problems. Therefore, we choose 30
minute as the default setting for the duration of time step.;

  2. 2.

We sampled the empirical distribution of the real historical data of customer
requests to simulate customer requests for the future time steps (?). We
assume that the lost demand at the time of return. Once the distribution of
bikes across the stations for time step $t+1$ is obtained, we utilize this
information to compute the repositioning strategy for trailers and vehicles
for time step $t+1$. This iterative process continues until we reach the last
decision epoch;

  3. 3.

Customers can rent a bike for 30 minutes or more, and they have to know in
advance at which station they will return the bike. On the other hand, they
return their bikes to the nearest available station if the destination station
is full, and they leave the system if they encounter an empty station.

The goal of our DRRPVT approach is to maximize the expected profit over the
entire time horizon. Let $U$ denotes the sum of revenue of hired bikes and the
fuel cost of vehicles and the value of bike trailers. We provide an
optimisation model for a given DRRPVT. Specifically, we provide a mixed
integer linear programming (MILP for short) that computes a profit maximising
repositioning and routing solution. The objective is shown in Equation
(Problem Formulation):

$\displaystyle\max_{y,z,a,b}U=\max_{y,z,a,b}\sum_{s,{s}^{\prime},t}R_{s,{s}^{\prime}}^{t}\times
x_{s,{s}^{\prime}}^{t}-$
$\displaystyle\sum_{t,v,s,{s}^{\prime}}P_{s,{s}^{\prime}}\times
z_{s,{s}^{\prime},v}^{t}-\sum_{t,v,s,{s}^{\prime}}b_{s,{s}^{\prime},v}^{t}\times\hat{P}_{s,{s}^{\prime}}$
(1) $s.t.$ $constraints$ $C1$-$C15$ $which$ $depends$ $on$ $y,z,a,b$.

Objective: To represent the trade-off between lost demand (or alternatively
the revenue from customer trips) and the value $P$ of using carrier vehicles
and the value $\hat{P}$ of bike trailers, we employ the dollar value of both
quantities and combine them into the overall profit at any decision epoch in
Equation (1). The notations used in the formulation are shown:

  * •

$y_{s,v}^{+,t}$ denotes the number of bikes picked up from station $s$ by
vehicle $v$ at decision epoch $t$.

  * •

$y_{s,v}^{-,t}$ denotes the number of bikes dropped at station $s$ by vehicle
$v$ at decision epoch $t$.

  * •

$z_{s,{s}^{\prime},v}^{t}$ denotes whether vehicle $v$ picks up bikes from
station $s$ at decision epoch $t$ and drops off at station ${s}^{\prime}$ at
decision epoch $t+1$.

  * •

$a_{s,v}^{+,t}$ denotes the number of bikes picked up from station $s$ by bike
trailer $v$ at decision epoch $t$.

  * •

$a_{s,v}^{-,t}$ denotes the number of bikes dropped off at station $s$ by bike
trailer $v$ at decision epoch $t$.

  * •

$b_{s,{s}^{\prime}v}^{t}$ denotes a binary decision variable which is set to
be 1 if bike trailer $v$ picks up bikes from station $s$ in at decision epoch
$t$ and returns bikes to station ${s}^{\prime}$ in at decision epoch $t+1$
else 0 otherwise.

  * •

$x_{s,{s}^{\prime}}^{t}$ denotes the number of hired bikes moving from station
$s$ at decision epoch $t$ to station ${s}^{\prime}$ at decision epoch $t+1$.

## Constraints

In this section, we address the constraints (C1-C15) we exploit in our bike
sharing system, where constraints(C1-C4) are newly created in this paper,
while constraints (C5-C8) have presented by (?; ?) and constraints (C9-C15)
have presented by (?).

##### C1: Preservation of Bike Flows in and out of station.

We require that the bike flows in and out of stations should ensure that the
number of bikes $d_{s}^{\\#,t+1}$ is equivalent to the sum of bikes
$d_{s}^{\\#,t}$ in the previous time step and the _net number_ of bikes coming
into the station during that time step, i.e., for each station $s$ and epoch
$t$,
$d_{s}^{\\#,t+1}=d_{s}^{\\#,t}+\sum_{\tilde{s}}x_{\tilde{s},s}^{t-1}-\sum_{{s}^{\prime}}x_{s,{s}^{\prime}}^{t}+\sum_{v}(y_{s,v}^{-,t}-y_{s,v}^{+,t}+a_{s,v}^{-,t}-a_{s,v}^{+,t})$
where the _net number_ is defined by the last three components.

##### C2: Preservation of Bikes Flows between any two stations follow the
transition dynamics observed in the data.

As a subset of arrival demand can be served if the number of bikes present in
a station is less than the arrival demand, we require that bikes flows between
station $s$ and ${s}^{\prime}$ should be less than the product of the number
of bikes present in the source station $s$ ($d_{s}^{\\#,t}$) and the
transition probability that a bike will move from $s$ to ${s}^{\prime}$
according to expected customer demand, i.e., for each $t,s,{s}^{\prime}$,
$x_{s,{s}^{\prime}}^{t}\leq
d_{s}^{\\#,t}\times\frac{F_{s,{s}^{\prime}}^{t}}{\sum_{\widetilde{s}}F_{s,\widetilde{s}}^{t}}$.

##### C3: Value of task for bike trailer.

We require a mechanism for crowdsourcing the repositioning tasks to the users
of bike trailers and generating a payment method to ensure that the users bid
for the tasks truthfully. The valuation of trailer $v$ task is proportional to
the expected lost demand reduced by the trailer job in the training demand
scenario($\xi$ represents unit value of lost demand to compute overall value),
i.e.,for each $s,{s}^{\prime},t$,
$\hat{P}_{s,{s}^{\prime}}^{t}=\xi\times\sum_{s,{s}^{\prime}}(F_{s,{s}^{\prime}}^{t}-d_{s}^{\\#,t})$.

##### C4: Ensuring the Budget Feasibility.

We require to incentive compatibility over all tasks without violating the fix
budget $B$ feasibility. Each task of trailers $v\in V$ has a valuation for the
task is denoted by $\hat{P}$. We aim to allocate the tasks in a fashion that
maximizes the overall valuation of the center while the total payment is
bounded by the given budget $B$, i.e.,
$\sum_{s,{s}^{\prime},v}b_{s,{s}^{\prime},v}^{t}\times\hat{P}_{s,{s}^{\prime}}^{t}\leq
B$.

##### C5: Preservation of Bikes Flows in and out of vehicles.

We require that the number of bikes in a vehicle at a time step
($d_{v}^{*,t+1}$) is equivalent to the sum of the number of bikes in the
vehicle at the previous time step ($d_{v}^{*,t}$) and the net number of bikes
coming into the vehicle during that time step
($\sum_{s}(y_{s,v}^{+,t}-y_{s,v}^{-,t})$, i.e., for each $v,t$,
$d_{v}^{*,t}+\sum_{s}(y_{s,v}^{+,t}-y_{s,v}^{-,t})=d_{v}^{*,t+1}$.

##### C6: Preservation of Vehicles Flows in and out of stations.

We require that the number of vehicles going out of station s
($\sum_{s’}z_{s’,s,v}^{t-1}$) plus the number of vehicles present at station s
at time epoch t-1 ($\sigma_{s,v}^{t-1}$) is equivalent to the sum of the
number of vehicles coming into station s ($\sum_{s’}z_{s,s’,v}^{t}$) and the
vehicles which are present at station s at time epoch t ($\sigma_{s,v}^{t}$).
Note that one of $\sum_{s’}z_{s,s,v}^{t}$ and $\sigma_{s,v}^{t}$ could be one
at most, i.e.,for each $t,s,v$,
$\sum_{s’}z_{s,s’,v}^{t}+\sigma_{s,v}^{t}=\sum_{s’}z_{s’,s,v}^{t-1}+\sigma_{s,v}^{t-1}$.

##### C7: A maximum of one vehicle can be present in one station at any time
step.

Due to limited space availability near base stations and to avoid a
synchronisation issue in pickup or drop-off events by multiple vehicles from
the same station at the same time step, we require that the maximum number of
vehicles at a station ($\sum_{{s}^{\prime},v}z_{s,{s}^{\prime}v}^{t}$) less
than 1, i.e.,for each $t,s$,
$\sum_{{s}^{\prime},v}z_{s,{s}^{\prime},v}^{t}\leq 1$.

##### C8: Vehicles can only pick up or drop off bikes at a station if they are
present at that station.

We require that the number of bikes picked up or dropped off at station at
each time step by each vehicle is bounded by whether the station is visited by
the vehicle at that time step or not, i.e.,for each $s,v,t$,
$y_{s,v}^{+,t}+y_{s,v}^{-,t}\leq
C_{v}^{*}\times\sum_{{s}^{\prime}}z_{s,{s}^{\prime},v}^{t}$.

##### C9: Trailer capacity is not exceeded while picking up bikes.

We require that the number of bikes picked up by trailer $v$ from station $s$
is bounded by the minimum value between the number of bikes present in the
station and the capacity of the trailer. $b_{s,{s}^{\prime},v}$ denotes a
binary decision variable which is set to 1 if bike trailer $v$ picks up bikes
from station $s$ and drop off bikes to any station ${s}^{\prime}$ and 0
otherwise, i.e.,for each $s,v,t$,
$a_{s,v}^{+,t}\leq\sum_{{s}^{\prime}}b_{s,{s}^{\prime},v}^{t}\times
min(d_{s}^{\\#,t},C_{v}^{*})$.

##### C10: Total number of bikes picked up from a station is less than the
available bikes.

As multiple trailers can pick up bikes from the same station, we require that
the total number of picked up bikes by all the trailers from station s during
the planning period $t$ is bounded by the number of bikes present at the
station ($d_{s}^{\\#,t}$), i.e.,for each $s,t$, $\sum_{v}a_{s,v}^{+,t}\leq
d_{s}^{\\#,t}$.

##### C11: Station capacity is not exceeded while dropping off bikes.

We require that the total number of dropped off bikes at station $s$ is
bounded by the number of available slots for bikes at that station, i.e.,for
each $s,t$, $\sum_{v}a_{s,v}^{-,t}\leq C_{s}^{\\#}-d_{s}^{\\#,t}$.

##### C12: Total travelling distance for a trailer is bounded by a threshold
value.

To represent the physical limitation of route, we need to ensure that the
total distance travelled by a trailer in a given planning period is within a
few kilometers. We require that the distance between pick-up station and the
drop-off station for a trailer $v$ is bounded by a threshold value, $D_{max}$,
i.e.,for each $s,{s}^{\prime},v,t$, $b_{s,{s}^{\prime},v}^{t}\times
D_{s,{s}^{\prime}}\leq D_{max}$.

##### C13: A trailer can only pick up or drop off bikes at exactly one
station.

We require that a trailer can go to exactly one station starting from a
specific station, i.e., for each $v,t$,
$\sum_{s,{s}^{\prime}}b_{s,{s^{\prime}},v}^{t}=1$.

##### C14: A trailer should return the exact number of bikes picked up.

We require that the number of bikes dropped off by a bike trailer in a station
is exactly equals to the number of picked up bikes if the station is visited,
i.e.,for each ${s}^{\prime},v,t$,
$a_{{s}^{\prime},v}^{-,t}=\sum_{s}(b_{s,{s}^{\prime},v}^{t}\times
a_{s,v}^{+,t})$. Note that, above equation are non-linear in nature. However,
one component in the right hand side is a binary variable. Therefore, we can
easily linearize them using the following formula, i.e.,for each
${s}^{\prime},v,t$, $a_{{s}^{\prime},v}^{-,t}\leq
C_{v}^{*}\times\sum_{s}b_{s,{s}^{\prime},v}^{t}$,
$a_{{s}^{\prime},v}^{-,t}\leq\sum_{s}a_{s,v}^{+,t}$,
$a_{{s}^{\prime},v}^{-,t}\geq\sum_{s}a_{s,v}^{+,t}-(1-\sum_{s}b_{s,{s}^{\prime},v}^{t})\times
C_{v}^{*}$.

##### C15: Station and vehicle capacities are not exceeded when repositioning
bikes.

We require that the number of bikes at a station $s$ does not exceed the
number of available docks at that station ($C_{s}^{\\#}$). Similarly, these
constraints also enforce that the number of bikes picked up or dropped off by
a vehicle $v$ in aggregate does not exceed the capacity of the vehicle
($C_{v}^{*}$), i.e., $0\leq x_{s,v}^{t}\leq F_{s,v}^{t};0\leq
d_{s}^{\\#,t}\leq C_{s}^{\\#};0\leq d_{v}^{*,t}\leq C_{v}^{*}$, $0\leq
y_{s,v}^{+,t},a_{s,v}^{+,t}\leq d_{s}^{\\#,t};0\leq
y_{s,v}^{-,t},a_{s,v}^{-,t}\leq C_{s}^{\\#}-d_{s}^{\\#,t}$, $0\leq
y_{s,v}^{+,t},y_{s,v}^{-,t},a_{s,v}^{+,t},a_{s,v}^{-,t}\leq
C_{v}^{*};z_{s,v}^{t},b_{s,{s}^{\prime},v}^{t}\in\left\\{0,1\right\\}$.
Given C1-C15, our task is to calculate which vehicles reposition bikes from
state $s$ to $s^{\prime}$, i.e., $z$, and which trailers reposition bikes from
$s$ to $s^{\prime}$, i.e., $b$, by optimizing Equation (Problem Formulation).

## Our DRRPVT Approach

In order to solve Equation (1), we use the well-known Lagrangian dual
decomposition (LDD) (Fisher,1985; Gordon, et al., 2012) technique. While this
is a general purpose approach, its scalability, usability and utility depend
significantly on the following characteristics of the model:
Identifying the right constraints to be dualized: This step is crucial to
ensure that the resulting subproblems are easy to solve and the resulting
bound derived from the dual solution is tight during the LDD process. If the
right constraints are not dualized, then the underlying Lagrangian based
optimization may not be decomposable or it may take significantly more time
than the original MILP to find the desired solution.
Extraction of a primal solution from an infeasible dual solution: The primal
extraction process is important to derive a valid bound (heuristic solution)
during the LDD process. In many cases, the solution obtained by solving the
decomposed dual slaves can be infeasible with respect to the original
formulation and hence, the overall approach can potentially lead to slower
convergence and poor solutions.
Decompose the original problem into a master problem and two slaves
(SOLVEREDEPLOY and SOLVEROUTING): As highlighted in Equation (1), only
constraints (8) contain a dependency between routing and repositioning
variables. We dualize constraints (8) using the dual variables,
$\alpha_{s,t,v}$ and obtain the Lagrangian function as Equation (2).

We exploit LDD to provide a near optimal solution for the dynamic
repositioning of bikes (?; ?). Although the LDD framework was indeed used in
Ghosh et al, 2015 and 2017, challenging to investigate the usage of LDD to
accommodate the new constraints. An overview of DRRPVT is shown in Algorithm
1. We will present main steps of Algorithm 1 in the following subsections.

Algorithm 1 An overview of our DRRPVT approach

Input:
$\langle\mathcal{S},\mathcal{V},\mathcal{F},\mathcal{C}^{\\#},\mathcal{C}^{*},d^{\\#},d^{*},\sigma,P,\hat{P},R,D,B\rangle$
Output: $y,z,a,b$

1: $\widetilde{S}=CalculateMainStations$($\mathcal{S},D$)

2: $\alpha=0$, $iter=0$

3: while $[p-(\rho 1+\rho 2)]\leq\delta$ do

4: $\rho 1,y,a,b\leftarrow SolveReposition(\alpha^{iter})$

5: $\rho 2,z\leftarrow SolveRouting(\alpha^{iter})$

6:
$\alpha^{iter+1}\leftarrow[\alpha^{iter}+\gamma\times(y^{+}+y^{-}-C^{*}\times\sum_{\widetilde{s}}z_{\cdot,\widetilde{s},\cdot})]_{+}$

7: $p,y_{p},a_{p},b_{p}\leftarrow ExtractPrimal(z)$

8: $iter\leftarrow iter+1$

9: end while

10: $SolvingIncentivizeTrailerTask$($d^{\\#},F,a$)

Our task is to optimize Equation (Problem Formulation) to calculate $y,a,b,z$.
To do this, based on Equation (Problem Formulation), we can define a
Lagrangian function as shown below:

$\displaystyle
L(\alpha)=\min_{y,z,a,b}[\textrm{-}\sum_{t,s,{s}^{\prime}}R_{s,{s}^{\prime}}^{t}*x_{s,{s}^{\prime}}^{t}\textrm{+}\sum_{t,v,s,{s}^{\prime}}z_{s,{s}^{\prime},v}^{t}*P_{s,{s}^{\prime}}\textrm{+}\quad\quad$
$\displaystyle\sum_{s,{s}^{\prime},v,t}b_{s,{s}^{\prime},v}^{t}*\hat{P}_{s,{s}^{\prime}}\textrm{+}\sum_{s,v,t}\alpha_{s,t,v}(y_{s,v}^{+,t}\textrm{+}y_{s,v}^{-,t}\textrm{-}C_{v}^{*}*\sum_{{s}^{\prime}}z_{s,{s}^{\prime},v}^{t})]$
$\displaystyle s.t.\ Constraints\ C1-C7\ and\ C9-C15\quad\quad$ (2)

, which is equivalent to

$\displaystyle
L(\alpha)=\min_{y,a,b}[\textrm{-}\sum_{t,k,s,{s}^{\prime}}R_{s,{s}^{\prime}}^{t}*x_{s,{s}^{\prime}}^{t}\textrm{+}\sum_{s,v,t}\alpha_{s,t,v}(y_{s,v}^{+,t}+y_{s,v}^{-,t})\textrm{+}$
$\displaystyle\sum_{s,{s}^{\prime},v,t}b_{s,{s}^{\prime},v}^{t}*\hat{P}_{s,{s}^{\prime}}]\textrm{+}\min_{z}[\sum_{s,{s}^{\prime},v,t}z_{s,{s}^{\prime},v}^{t}*(P_{s,{s}^{\prime}}\textrm{-}C_{v}^{*}*\alpha_{s,t,v})]$
$\displaystyle s.t.\ Constraints\ C1-C7\ and\ C9-C15\quad\quad\quad\quad$ (3)

### Calculating Main Stations

Since nearby stations can be covered by bike trailers, we exploit the
geographical proximity based clustering method to obtain main stations to
reduce the usage of carrier vehicles (?; ?) . We thus provide a clustering
mechanism to calculate main stations in Step 1 of Algorithm 1. The high-level
idea is to first calculate distances between base stations, and then cluster
base stations based on their distances using off-the-shelf clustering
approaches such as k-means. We denote the set of resulting main stations by
$\widetilde{S}$ (?; ?; ?). Therefore, we utilize carrier vehicles to
reposition bikes dynamically for a wide range (i.e., among main stations) and
utilize bike trailers to reposition the bikes dynamically for a small range
(i.e., within each main station).

### Repositioning Bikes and Routing for Vehicles

Our goal is to design a mechanism to incentivize task execution based on the
maximization of profit via dynamically repositioning and routing.
Specifically, we provide a decomposition approach to exploit the minimal
dependency that exists in the model DRRPVT between the repositioning problem
(how many bikes to pick up and drop off at each station) and the routing
problem (how to move vehicles between base stations to pick up or drop off
bikes). The following observation highlights this minimal dependency:

  * •

$y,a,b$ capture the solution to the repositioning problem.

  * •

$z$ captures the solution to the routing problem.

These sets of variables only interact with each other in constraint (8). In
all of the other constraints of our DRRPVT model, the routing variables are
completely independent with repositioning variables.

With the minimal dependency observation, we use LDD in DRRPVT. It is crucial
to ensure that the resulting subproblems are easy to solve and the resulting
bound derived from the dual solution is tight during the LDD process. We first
decompose the original problem into a master problem (i.e., Equation (Our
DRRPVT Approach)) and two slaves _SolveReposition_ and _SolveRouting_. As
highlighted, only constraint (8) contains dependencies between routing and
repositioning variables, i.e., $\alpha_{v,s,t}$. Thus, we dualize constraint
(8) using the dual variables, and obtain the Lagrangian function in Equation
(Our DRRPVT Approach). The first three terms in Equation (Our DRRPVT Approach)
corresponding to the repositioning problem are given in Equation
(Repositioning Bikes and Routing for Vehicles), and the last term
corresponding to the routing problem is given in Equation (Repositioning Bikes
and Routing for Vehicles), respectively, i.e.,

$\displaystyle\min_{y,a,b}\sum_{s,t,v}\alpha_{s,v,t}*y_{s,v}^{t}\textrm{+}\sum_{s,{s}^{\prime},t,v}b_{s,{s}^{\prime},v}^{t}*\hat{P}_{s,{s}^{\prime}}\textrm{-}\sum_{t,s,{s}^{\prime}}R_{s,{s}^{\prime}}^{t}*x_{s,{s}^{\prime}}^{t}$
$\displaystyle s.t.\ Constraints\ C1-C5\ \ and\ C9-C15\quad\quad$ (4)

and

$\displaystyle\min_{z}\sum_{v,s,\widetilde{s}}^{t}z_{s,\widetilde{s},v}^{t}\times\left(P_{s,\widetilde{s}}-C_{v}^{*}\times\alpha_{s,t,v}\right)$
$\displaystyle s.t.\quad Constraints\ C6\textrm{-}C7\ and\ C15$ (5)

From Equation (Our DRRPVT Approach), given $\alpha$, the dual value
corresponding to the original problem is obtained by adding up the objective
function values from the two slaves, which yields a valid lower bound with
respect to the original problem. It should be noted that the decomposition is
only for $L(\alpha)$. The value of _SolveReposition_ is denoted by $\rho_{1}$,
and The value of _SolveRouting_ is denoted by $\rho_{2}$.

Next, we solve the following optimization problem at the master in order to
reduce violations of the dualized constraints: $\max_{\alpha\geq
0}L\left(\alpha\right)$. This master optimization problem is solved
iteratively using a sub-gradient descent method applied on the dual variables
$\alpha$, i.e., Step 6 of Algorithm 1, where $\gamma$ is a step-size
parameter. The algorithm terminates when the difference between the primal
objective (defined as $p$ in Algorithm 1) and the dual objective (the sum of
the slave’s objectives $\rho_{1},\rho_{2}$) is less than a pre-determined
threshold value $\delta$. In order to compute the best primal solution in
conjunction with the dual solution, it is important to obtain a primal
solution after each iteration from the solutions of the slaves. The
infeasibility in the dual solution arises because the routes of the vehicles
(obtained by solving the routing slave) may not be consistent with the
repositioning plan of bikes (obtained by solving the repositioning slave).
However, the solution for the routing slave is always feasible and can be
fixed to obtain a feasible primal solution with respect to the original
problem. Let $z_{s,v}^{t}=\sum_{{s}^{\prime}}z_{s,{s}^{\prime},v}^{t}$. We
extract the primal solution by solving the optimization formulation in
Equation (Repositioning Bikes and Routing for Vehicles):

$\displaystyle\max_{y}$
$\displaystyle\sum_{t,s,{s}^{\prime}}R_{s,{s}^{\prime}}^{t}\times
x_{s,{s}^{\prime}}^{t}-\sum_{t,v,s,{s}^{\prime}}b_{s,{s}^{\prime},v}^{t}\times\hat{P}_{s,{s}^{\prime}}$
$\displaystyle s.t.\ Constraints\ C1-C5\ \ and\ C9-C15$ (6) $\displaystyle
y_{s,v}^{+,t}+y_{s,v}^{-,t}\leq C_{v}^{*}\times z_{s,v}^{t}\quad\forall t,s,v$

Specifically, constraints in Equation (Repositioning Bikes and Routing for
Vehicles) are equivalent to constraint (8) where we use the solution values of
the routing slave $z$ as the input. Thus, _ExtractPrimal_ satisfies
C1-C5,C9-15 and produces a feasible solution to the original problem. Finally,
we subtract the routing value from the objective value to get the correct
primal value

### Incentivize Trailer Tasks

In Step 10, we use an incentivizing mechanism proposed by (?; ?), which
allocates the tasks to users of bike trailers. Firstly, the mechanism computes
the value of the tasks according to the lost demand reduced by the trailer
task. Secondly, it employs an incentive compatible mechanism that ensures
users always bid truthfully on each task . Finally, it assigns the task to a
bidder so that the profit is maximized, and employs a payment method to ensure
that the task is always allocated to the lowest bidder. The total payment
given to the users of trailers due to the resulting allocation should respect
to the given budget $B$.

## Experiments

To exhibit the effectiveness of our approach, we conducted the experiment on
two datasets Capital Bikeshare 888http://www.capitalbikeshare.com/system-data
and Hubway999http://hubwaydatachallenge.org/trip-history-data/, and a
synthetic dataset which was derived from multiple real datasets. We generated
the synthetic dataset by first taking a subset of the stations from the two
real-world datasets, and then taking customer demand, station capacity,
geographical location of stations, initial distribution, bid values and value
model drawn from the two real-world datasets. The _Hubway_ dataset consists of
95 base stations and 3 vehicles, 10 trailers; _Capital Bikeshare_ dataset
consists of 305 active stations and 10 vehicles, 35 trailers; and the
synthetic dataset consists of 60 base stations, 2 vehicles, 7 trailers. We
employed k-means clustering to generate 12 main stations (5 base stations are
grouped into 1 main stations) which are within 5 kilometers between each
other. We took 6 hours of planning horizon in the morning peak (5AM-12PM) and
31 hours of planning horizon in the whole day (5AM-12AM). The duration of each
decision epoch was set to be 30 minutes. The demand scenarios were collected
from three months of historical trip data. Once the distribution of bikes and
vehicles from stations at time step $t$ is obtained, the information is
utilized to compute the repositioning strategy for trailers at time step
$t+1$.

Let $G_{v}$ and $G_{t}$ denote the gains of profit with DRRPV and DRRPT,
respectively, and $L_{v}$ and $L_{t}$ denote lost demand reductions of DRRPV
and DRRPT, respectively. We compute $G_{v}$ and $G_{t}$ as shown below:
$G_{v}=\frac{\mathcal{U}_{vt}-\mathcal{U}_{v}}{\mathcal{U}_{v}}$,
$G_{t}=\frac{\mathcal{U}_{vt}-\mathcal{U}_{t}}{\mathcal{U}_{t}}$,
$L_{v}=\frac{\mathcal{E}_{vt}-\mathcal{E}_{v}}{\mathcal{E}_{v}}$,
$L_{t}=\frac{\mathcal{E}_{vt}-\mathcal{E}_{t}}{\mathcal{E}_{t}}$, where
$\mathcal{U}_{vt}$ and $\mathcal{E}_{vt}$ indicate the profit and lost demand
reduction of using both carrier vehicles and bike trailers, respectively;
$\mathcal{U}_{v}$ and $\mathcal{E}_{v}$ indicate the profit and lost demand
reduction of using carrier vehicles only, respectively; $\mathcal{U}_{t}$ and
$\mathcal{E}_{t}$ indicate the profit and lost demand reduction of using bike
trailers only, respectively.

We would like to verify the following aspects101010All optimization models
were solved based on GUROBI 7.5.2 and 4.0 GHz Intel Core i7.. We first
evaluate that our DRRPVT approach with novel mechanism (LDD + Main station)
outperforms two baselines which use vehicles (?) and trailers (?),
respectively. We then compare LDD and main stations in DRRPVT with MILP to see
the advantage of LDD and Main stations. We finally evaluate DRRPVT remains
robust with respect to variation of the numbers of stations, vehicles and
trailers.

### Experimental Results

#### Comparison against Baselines

We provide the key performance comparison with respect to the overall profit
to show that we can reduce the lost demand without incurring extra value to
the operators. We employ 3 vehicles and 20 bike trailers for the experiments
in both Capital Bikeshare and Hubway, which is also exploited by (?). We
evaluate DRRPVT with respect to different time periods, i.e., the peak period
and the whole day.

Table 1: Comparison of profit gain and lost demand reduction in a whole day (5AM-12AM) datasets | $\mathcal{G}_{v}$ | $\mathcal{L}_{v}$ | $\mathcal{G}_{t}$ | $\mathcal{L}_{t}$
---|---|---|---|---
Hubway | 2.42% | 23.57% | 2.18% | 26.91%
Capital Bikeshare | 1.97% | 14.42% | 1.25% | 17.38%
Table 2: Comparison of profit gain and lost demand reduction in the peak period (5AM-12PM) datasets | $\mathcal{G}_{v}$ | $\mathcal{L}_{v}$ | $\mathcal{G}_{t}$ | $\mathcal{L}_{t}$
---|---|---|---|---
Hubway | 4.63% | 29.71% | 4.26% | 31.12%
Capital Bikeshare | 4.25% | 19.39% | 4.11% | 24.45%

Tables 1 and 2 show the average percentage gain in profit and reduction in
lost demand with our approach in comparison to the baselines on the two real-
world datasets. Based on the aggregate results, our approach DRRPVT is always
able to outperform both DRRPV and DRRPT with respect to both of the profit
gain and lost demand reduction. From Table 1, our approach performs much
better in Hubway than Capital Bikeshare comparing to baselines. This is
because the number of users hiring bikes in Hubway is much larger than Capital
Bikeshare. The more users hire bikes, the better our approach performs.
Similar results can be found in Table 2.

(a)

(b)

(c)

Figure 1: Correlation of demand and supply: (a) DRRPV, (b) DRRPT, and (c)
DRRPVT

Lastly, to see the effect of repositioning, we draw the correlation between
the actual demand and the served demand over decision epoch. Figure (1) shows
the correlation by running the three approaches. Each point in the figure
corresponds to the values of an actual demand and its corresponding served
demand for all time steps and all stations in the Hubway data set. As
expected, our approach has significantly more points closer to the identity
line than the other two, which indicates our approach is able to better match
the supply of bikes with the demand for bikes.

#### Comparison with MILP

We next compare LDD and Main stations of DRRPVT to MILP with respect to
runtime performance, duality gap and main stations.
Runtime performance: We compare the runtime of DRRPVT with MILP, as shown in
Figure (2a). The X-axis denotes the number of stations from 5 to 60. The
Y-axis denotes the total time taken to solve problem in seconds. We can see
that DRRPVT generally outperforms MILP with respect to number of stations.
MILP is unable to finish within a cut-off time of 3 hours for any problem with
more than 20 stations, while DRRPVT is able to obtain near optimal solutions
on problems with 60 stations in less than 3 hour. DRRPVT becomes relatively
stable after reaching 35 stations (the red curve). It could be easily speeded
up by running our approach in a server of higher performance in real-world
applications. Meanwhile, we observed the trend in runtime when using main
station clustering on problems with 100-200 stations and it scaled in similar
trend with respect to using v.s. not using main stations.

(a)

(b)

Figure 2: (a) Runtime comparison between MILP and LDD, (b) duality gap in the
synthetic dataset with 30 stations

Duality gap: We demonstrate the convergence of LDD to near optimal solutions.
LDD achieves an optimal solution if the duality gap, i.e., the gap between
primal and dual solutions, becomes zero. Figure (2b) shows that the duality
gap for the instances with 30 stations (grouped into 6 main stations). For
these larger problems we are able to obtain a solution with the duality gap of
less than 1%.
Main stations: We also would like to demonstrate the performance of the
clustering method in comparison with the optimal solution of instances with 30
base stations (grouped into 6 main stations). Table 3 shows the effect of
using main stations on the generated profit and runtime based on five random
scenarios of customer demand. With main stations, there is obviously an
improvement of more than 13% in profit on average over all of the optimal
solutions from Table 3. Since main stations are based on geographical
proximity, it is ideally suitable for handling such scenarios.

Table 3: Effect of main stations with 30 base stations (MS indicates “main stations”) Instance |  With MS |  Without MS |  profit increase
---|---|---|---
Profit |  Runtime |  Profit |  Runtime
1 | 16576 | 37 | 14635 | 1754 | 13.26%
2 | 16897 | 49 | 14882 | 1774 | 13.54%
3 | 16628 | 41 | 14672 | 1761 | 13.33%
4 | 16511 | 43 | 14560 | 1762 | 13.40%
5 | 16134 | 31 | 14212 | 1759 | 13.52%
Average | 16549 | 40 | 14592 | 1762 | 13.41%

### Varying numbers of stations, vehicles and trailers

We compare the profit of DRRPVT with the ratio of base stations to main
stations, as shown in Figure (3a). The X-axis denotes the ratio of base
stations $s$ over main stations $\widetilde{s}$. The Y-axis denotes the total
profit. We then compare the profit of the DRRPVT with the ratio of base
stations over carrier vehicles, as shown in Figure (3b). Finally, we evaluate
the profit of the DRRPVT with the ratio of base stations over bike trailers,
as shown in Figure (3c).

From Figure 3, we can see that the profit of our DRRPVT approach generally
increases at the beginning, with respect to the increase of the ratios of base
stations over main stations, carrier vehicles and bike trailers, respectively.
After the profit reaches the maximal value, it goes down when the ratios
increase. This is consistent with our intuition since more base stations can
indeed raise the profit on repositioning bikes at the beginning. It will,
however, largely raise the cost of repositioning bikes when base stations
become too many.

(a)

(b)

(c)

Figure 3: The maximal profit of the DRRPVT with the ratio of base stations to:
(a) main stations, (b) vehicles, and (c) trailers

## Conclusion

In this paper we propose an optimization model to jointly consider the usage
of carrier vehicles and bike trailers. We build a profit objective to
calculate the value of carrier vehicle routing and bike trailers by
considering a variety of constraints with respect to vehicle routing and bike
repositioning. In the experiment, we exhibit that our approach is effective
with comparison to baselines. In the future, it would be interesting to study
a budget feasible mechanism which solves the uncertainties in completion time
of trailer tasks and build an iterative scenario generation approach which
provides the update strategies for pre-planned solutions. In this work, we
consider building an objective function and optimizing the objective according
to a set of constraints. The constraints are numerous and sometime difficult
to create by hand. It would be interesting to study the feasibility of
exploiting classical planning models, such as PDDL (?), with state-of-the-art
PDDL model learning approaches (?; ?; ?; ?; ?; ?) to learn PDDL models from
training data automatically, instead of building constraints manually.

## References

  * [Cavallo 2009] Cavallo, R.  2009\.  Mechanism design for dynamic settings.  SIGecom Exchanges 8(2):7.
  * [Chemla, Meunier, and Calvo 2013] Chemla, D.; Meunier, F.; and Calvo, R. W.  2013\.  Bike sharing systems: Solving the static rebalancing problem.  Discrete Optimization 10(2):120–146.
  * [Chen, Liu, and Liu 2018] Chen, Q.; Liu, M.; and Liu, X.  2018\.  Bike fleet allocation models for repositioning in bike-sharing systems.  IEEE Intell. Transport. Syst. Mag. 10(1):19–29.
  * [Gaspero, Rendl, and Urli 2016] Gaspero, L. D.; Rendl, A.; and Urli, T.  2016\.  Balancing bike sharing systems with constraint programming.  Constraints 21(2):318–348.
  * [Geffner 2003] Geffner, H.  2003\.  PDDL 2.1: Representation vs. computation.  J. Artif. Intell. Res. 20:139–144.
  * [Ghosh and Varakantham 2017] Ghosh, S., and Varakantham, P.  2017\.  Incentivizing the use of bike trailers for dynamic repositioning in bike sharing systems.  In Proceedings of ICAPS, 373–381.
  * [Ghosh and Varakantham 2018] Ghosh, S., and Varakantham, P.  2018\.  Dispatch guided allocation optimization for effective emergency response.  In Proceedings of AAAI, 775–783.
  * [Ghosh et al. 2015] Ghosh, S.; Varakantham, P.; Adulyasak, Y.; and Jaillet, P.  2015\.  Dynamic redeployment to counter congestion or starvation in vehicle sharing systems.  In Proceedings of ICAPS, 79–87.
  * [Ghosh et al. 2017] Ghosh, S.; Varakantham, P.; Adulyasak, Y.; and Jaillet, P.  2017\.  Dynamic repositioning to reduce lost demand in bike sharing systems.  J. Artif. Intell. Res. 58:387–430.
  * [Ghosh, Trick, and Varakantham 2016] Ghosh, S.; Trick, M.; and Varakantham, P.  2016\.  Robust repositioning to counter unpredictable demand in bike sharing systems.  In Kambhampati, S., ed., Proceedings of IJCAI, 3096–3102.
  * [Hartuv, Agmon, and Kraus 2018] Hartuv, E.; Agmon, N.; and Kraus, S.  2018\.  Scheduling spare drones for persistent task performance under energy constraints.  In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018, 532–540.
  * [Hulot, Aloise, and Jena 2018] Hulot, P.; Aloise, D.; and Jena, S. D.  2018\.  Towards station-level demand prediction for effective rebalancing in bike-sharing systems.  In Proceedings of SIGKDD, 378–386.
  * [Jha et al. 2018] Jha, S. S.; Cheng, S.; Lowalekar, M.; Wong, N.; Rajendram, R.; Tran, T. K.; Varakantham, P.; Truong, T. N.; and Rahman, F. B. A.  2018\.  Upping the game of taxi driving in the age of uber.  In Proceedings of AAAI, 7779–7785.
  * [Konda, Ghosh, and Varakantham 2018] Konda, M.; Ghosh, S.; and Varakantham, P.  2018\.  Reserved optimisation: Handling incident priorities in emergency response systems.  In de Weerdt, M.; Koenig, S.; Röger, G.; and Spaan, M. T. J., eds., Proceedings of ICAPS, 330–338.  AAAI Press.
  * [Lin, Yang, and Chang 2013] Lin, J.; Yang, T.; and Chang, Y.  2013\.  A hub location inventory model for bicycle sharing system design: Formulation and solution.  Computers & Industrial Engineering 65(1):77–86.
  * [Lowalekar et al. 2017] Lowalekar, M.; Varakantham, P.; Ghosh, S.; Jena, S. D.; and Jaillet, P.  2017\.  Online repositioning in bike sharing systems.  In Proceedings of ICAPS, 200–208.
  * [Pfrommer et al. 2014] Pfrommer, J.; Warrington, J.; Schildbach, G.; and Morari, M.  2014\.  Dynamic vehicle redistribution and online price incentives in shared mobility systems.  IEEE Trans. Intelligent Transportation Systems 15(4):1567–1578.
  * [Schuijbroek, Hampshire, and van Hoeve 2017] Schuijbroek, J.; Hampshire, R. C.; and van Hoeve, W.  2017\.  Inventory rebalancing and vehicle routing in bike sharing systems.  European Journal of Operational Research 257(3):992–1004.
  * [Shu et al. 2013] Shu, J.; Chou, M. C.; Liu, Q.; Teo, C.; and Wang, I.  2013\.  Models for effective deployment and redistribution of bicycles within public bicycle-sharing systems.  Operations Research 61(6):1346–1359.
  * [Singla et al. 2015] Singla, A.; Santoni, M.; Bartók, G.; Mukerji, P.; Meenen, M.; and Krause, A.  2015\.  Incentivizing users for balancing bike sharing systems.  In Proceedings of AAAI, 723–729.
  * [Tsai, Chen, and Hong 2019] Tsai, M.; Chen, P.; and Hong, Y. J.  2019\.  Enhancing the utilization of public bike sharing systems using return anxiety information.  Future Generation Comp. Syst. 92:961–971.
  * [Vulcano, van Ryzin, and Ratliff 2012] Vulcano, G. J.; van Ryzin, G. J.; and Ratliff, R.  2012\.  Estimating primary demand for substitutable products from sales transaction data.  Operations Research 60(2):313–334.
  * [Wang et al. 2018] Wang, N.; Zgaya, H.; Mathieu, P.; and Hammadi, S.  2018\.  An agent-based distributed approach for bike sharing systems.  In Proceedings of ICCS, 540–552.
  * [Zhang and Pavone 2014] Zhang, R., and Pavone, M.  2014\.  Control of robotic mobility-on-demand systems: a queueing-theoretical perspective.  In Robotics: Science and Systems X, University of California, Berkeley, USA, July 12-16, 2014.
  * [Zhuo and Kambhampati 2013] Zhuo, H. H., and Kambhampati, S.  2013\.  Action-model acquisition from noisy plan traces.  In IJCAI, 2444–2450.
  * [Zhuo and Kambhampati 2017] Zhuo, H. H., and Kambhampati, S.  2017\.  Model-lite planning: Case-based vs. model-based approaches.  Artif. Intell. 246:1–21.
  * [Zhuo and Yang 2014] Zhuo, H. H., and Yang, Q.  2014\.  Action-model acquisition for planning via transfer learning.  Artif. Intell. 212:80–103.
  * [Zhuo et al. 2010] Zhuo, H. H.; Yang, Q.; Hu, D. H.; and Li, L.  2010\.  Learning complex action models with quantifiers and logical implications.  Artif. Intell. 174(18):1540–1569.
  * [Zhuo, Nguyen, and Kambhampati 2013] Zhuo, H. H.; Nguyen, T. A.; and Kambhampati, S.  2013\.  Refining incomplete planning domain models through plan traces.  In IJCAI, 2451–2458.
  * [Zhuo 2015] Zhuo, H. H.  2015\.  Crowdsourced action-model acquisition for planning.  In AAAI, 3439–3446.