## 2 Problem Formulation
### Multiple-Vehicle Bike Sharing System Routing Problem  
In this section, an integer linear programming formulation of mBSSRP is described. The mBSSRP consists of a depot and many ports where rental bicycles are parked. The ports are classified into two sets: (i) a set of delivery ports with a shortage of rental bicycles and (ii) a set of pickup ports. From the pickup ports, some bicycles are transported to the delivery ports because of inadequate bicycle parking space. In mBSSRP, multiple vehicles transport the bicycles from the pickup port to the delivery port. All vehicles start from the depot, load and unload bicycles at the corresponding ports and return to the depot. The vehicles can leave the depot loaded with bicycles because there are many bicycles at the depot. The tour of the vehicles must satisfy the following constraints:  
* Time limit constraint All vehicles must start at the depot and return to the depot within a limited time. * Capacity constraint The number of bicycles loaded onto the vehicle cannot exceed its capacity throughout the tour. * Visiting constraint Each port must be visited exactly once by a vehicle. * Loading and supplying constraint The vehicle must load all excess bicycles and supply the required bicycles in one visit. Under the above constraints, the goal of the mBSSRP is to find tours that minimize the total travel time of all vehicles. Let \(G=(V,E)\) be a graph, where \(V=\{0,1,\ldots,n\}\) is a set of nodes representing a depot \(\{0\}\) and ports \(\{1,\ldots,n\}\), and \(E\) is a set of edges. Let \(t_{ij}\) be the travel time from port \(i\) to port \(j\) (\(t_{ij}=t_{ji}\)). Let \(b_{i}\) be the number of excess or shortage bicycles at port \(i\). If \(b_{i}>0\), \(b_{i}\) bicycles are in excess at port \(i\). In this case, \(b_{i}\) bicycles at port \(i\) are transported to the delivery ports. If \(b_{i}<0\), the vehicle must supply \(b_{i}\) bicycles to port \(i\). In mBSSRP, the excess bicycles are delivered to the delivery ports by multiple vehicles. The set of capacitated vehicles is \(K=\{1,\ldots,m\}\). The vehicles cannot carry more than \(q\) bicycles. The capacity \(q\) is max \(|b_{i}|\leq q\), because the vehicle can visit each port only once. It takes \(\tau\) minutes to load/unload one bicycle onto/from the vehicle. The vehicle leaving the depot must restore the bicycles and return to the depot within \(T\) minutes. We introduce four decision variables (Table 2), \(y_{ik}\), \(x_{ijk}\), \(z_{ijk}\) and \(f_{ijk}\). The first variable \(y_{ik}\) is a 0-1 variable and denotes whether vehicle \(k\) visits port \(i\) (\(y_{ik}=1\)) or not (\(y_{ik}=0\)). The second variable \(x_{ijk}\) is also a 0-1 variable and denotes whether vehicle \(k\) moves from port \(i\) to port \(j\) directly (\(x_{ijk}=1\)) or not (\(x_{ijk}=0\)). The third variable \(z_{ijk}\) is a non-negative variable that represents the number of bicycles loaded onto vehicle \(k\) when vehicle \(k\) moves from port \(i\) to port \(j\). This third variable \(z_{ijk}\) is essential: in the static rebalancing problem, the direction of the vehicle is very important, because the number of bicycles on the vehicle depends on the direction. Let us suppose that five bicycles must be supplied at port 1; two bicycles must be picked up at port 2; and the vehicle is loaded with three bicycles. In this case, the vehicle can travel from port 2 to port 1, but not from port 1 to port 2. This is because, if the vehicle picks up the two bicycles at port 2 before visiting port 1, it cannot supply five bicycles at port 1. Thus, if the decision variable \(z_{ijk}\) is not defined, vehicle \(k\) cannot determine if it can move from port \(i\) to port \(j\). To eliminate sub-tours, the fourth non-negative variable \(f_{ijk}\) is used, which represents the number of ports visited by vehicle \(k\) before it reaches port \(j\) from port \(i\).