关键词: 多重图, 共享单车, 调度优化, 混合整数规划, 禁忌搜索

Abstract: Nowadays, as a new form of the sharing economy, bike sharing systems (BSSs) have been widely recognized as an economical and low-carbon mode of transport, and they have effectively solved the problem of ‘the last mile’ in short-distance trips. One fundamental problem of bike sharing is that the numbers of bikes required at some stations are not enough to satisfy the bike user demand. Therefore, the operators need to deploy trucks to transport bikes from surplus stations to deficit ones to meet the bike user demand. This redistribution problem is currently called the bike repositioning problem (BRP).
Due to the practical importance and unique characteristics, BRP has attracted much attention in recent years. In the literature, BRP is modeled as static BRP (SBRP) and dynamic BRP (DBRP). A vast majority of BRP studies concern SBRP, partly as it is easier to model and the impact of repositioning may be more important at night. SBRP considers the operations within a period and neglects the station demand variations, while DBRP considers the real-time operations and takes station demand variations into account. SBRP considers the scenarios in which demand is low or the system is closed, implying that the change in demand can be negligible. DBRP considers the scenarios that take real-time system usage into account. Three different types of models are presented, including Arc-Indexed (AI) formulation, Time-Indexed (TI) formulation, and Sequence-Indexed (SI) formulation. In view of the characteristics of dynamic demand of DBRP, previous studies mainly analyzed the time-varying characteristics of demand and the stochastic characteristics of demand, and formulated two corresponding DBRP models.
However, all BRP studies are generally treated via the representation of the road network as a weighted complete graph, where arcs represent the shortest path between pairs of stations, and several attributes (e.g., travel time, travel cost) are defined for one arc. However, the shortest path implied by this arc is computed according to a single criterion. As a result, some alternative paths proposing a different compromise between these attributes are discarded.
In this paper, a bike repositioning problem on a multigraph (BRP-MG) is proposed to minimize the total cost (i.e., the total travelling costs and the total penalty costs for the deviating from the expected demands), where the alternative routes are considered. Ideally, the proposed BRP-MG would define one arc between two stations for each Pareto optimal road-path according to arc attributes in the bike sharing system. Any good road-path would then be captured in the graph.
In order to solve the proposed BRP-MG, this study may consider different solution methods used to solve BRP, including exact methods and heuristics. However, it is quite hard to adopt exact methods to solve realistic BRP because the problem is NP-hard. Exact methods only obtain optimal solutions in small BSS networks and are unsuitable for large BSS networks. As our ultimate aim is to develop an efficient solution method that can solve large BSS networks, this study prefers to develop a heuristic to solve BRP-MG. Tabu search is well-known to be quite efficient to solve routing problems. Particularly, the tabu search has been adopted in the multigraph-based vehicle routing problem (VRP) and BRP to obtain high-quality solutions in a short computing time with great success. Hence, the tabu search is chosen as the backbone of our solution method.
However, BRP-MG involves the loading/unloading quantities at each visited station and the arc selection between each two successive nodes in addition to the determination of the sequence of nodes. Therefore, the tabu search cannot be directly applied for routing problems to solve BRP-MG and some extra operations should be added to the tabu search.
For this purpose, several specific operators are developed (i.e., insertion operators, deletion operators, and exchange operators) to deal with the loading/unloading quantities at each visited station. In addition, decisions need to be made regarding which is to be selected between two successive nodes each. Therefore, an efficient arc selection heuristic is proposed to handle the arc selection for a fixed sequence of nodes.
To illustrate the accuracy and efficiency of our solution method, this study tests different sizes of instances and compares the results with ones obtained from the genetic algorithm, the classic tabu search, and the variable neighborhood search. In addition, in order to compare the advantages and disadvantages of repositioning in a complete graph and a multigraph, 10 groups of large instances are used to test the repositioning in a complete graph (retaining the parallel arc with the lowest transportation cost) and in a multigraph. Although the computing time based on the multigraph repositioning is slightly more than that in the complete graph, the quality of decision-making is significantly improved, which is shown by the effective reduction of total costs and a substantial increase in the demand for bike users.

Key words: multigraph, shared bike, repositioning problem, mixed integer programing, tabu search