PaperlayerView exact revision on arXiv

Source-linked AI summary

A heuristic algorithm for a single vehicle static bike sharing rebalancing problem

Fábio Cruz, Anand Subramanian, Bruno P. Bruck, Manuel Iori

arXiv:1605.00702v2cs.AI

TL;DR

The single-vehicle SBRP requires routing and load decisions that serve station demands while allowing split visits and temporary bike transfers. The paper proposes a hybrid iterated local search heuristic for the single-vehicle SBRP. ILSSBRP found 796 out of 823 known optimal solutions.

  • Problem

    The single-vehicle SBRP requires routing and load decisions that serve station demands while allowing split visits and temporary bike transfers.

    Source: §1 · p. 2

  • Method

    The paper proposes a hybrid iterated local search heuristic for the single-vehicle SBRP.

    Source: §1 · p. 3

  • Results

    ILSSBRP found 796 out of 823 known optimal solutions.

    Source: §5 · p. 17

  • Takeaways & Limitations

    The authors report that ILSSBRP is quite competitive with existing methods.

    Source: §1 · p. 3

    The AddUnbalanced repair procedure does not necessarily produce a feasible solution.

    Source: §3.2 · p. 6

Abstract

from arXiv · show

The static bike rebalancing problem (SBRP) concerns the task of repositioning bikes among stations in self-service bike-sharing systems. This problem can be seen as a variant of the one-commodity pickup and delivery vehicle routing problem, where multiple visits are allowed to be performed at each station, i.e., the demand of a station is allowed to be split. Moreover, a vehicle may temporarily drop its load at a station, leaving it in excess or, alternatively, collect more bikes from a station (even all of them), thus leaving it in default. Both cases require further visits in order to meet the actual demands of such station. This paper deals with a particular case of the SBRP, in which only a single vehicle is available and the objective is to find a least-cost route that meets the demand of all stations and does not violate the minimum (zero) and maximum (vehicle capacity) load limits along the tour. Therefore, the number of bikes to be collected or delivered at each station should be appropriately determined in order to respect such constraints. We propose an iterated local search (ILS) based heuristic to solve the problem. The ILS algorithm was tested on 980 benchmark instances from the literature and the results obtained are quite competitive when compared to other existing methods. Moreover, our heuristic was capable of finding most of the known optimal solutions and also of improving the results on a number of open instances.

1 Introduction

The introduction frames single-vehicle static bike rebalancing as an NP-hard routing problem with split station service and temporary bike transfers. It proposes a hybrid ILS heuristic and reports competitive results on 980 literature benchmark instances.

1 Introduction

  • Rebalancing addresses stations that may run out of bikes or free return slots by restoring inventories to desired levels.Source: §1 · p. 2
  • The single-vehicle SBRP is NP-hard because it includes TSP, and it allows station demands to be split across multiple visits.Source: §1 · p. 2
  • Stations may temporarily receive or yield bikes before later visits complete their demands, while visits to balanced stations are optional.Source: §1 · p. 2
  • The proposed hybrid ILS combines prior ingredients with problem-specific procedures to improve solution quality and check infeasibility.Source: §1 · p. 3
  • The experiments assess solution quality and CPU time across station counts and vehicle capacities.Source: §1 · p. 3
  • Across 980 literature benchmark instances, the heuristic is reported as quite competitive and yields a number of new best-known solutions.Source: §1 · p. 3

2 Problem description

The problem is to find a least-cost depot-to-depot route that serves stations with nonzero demand while respecting vehicle and station inventory constraints. Service quantities may be split across visits, and stations may temporarily hold or supply bikes for later service.

2 Problem description

  • The route starts and ends at the depot, visits each station with nonzero demand at least once, and meets all station demands.Source: §2 · p. 3
  • The vehicle load must remain between zero and capacity Q, so pickup and delivery quantities at each visit must be chosen accordingly.Source: §2 · p. 3
  • A station can temporarily hold excess bikes or supply more than its initial demand, with its actual demand completed on later visits.Source: §2 · p. 3
  • Figure 1 presents a graphical representation of an optimal solution valued at 5989 for benchmark instance n20q10D; positive and negative values next to nodes indicate numbers of bikes collected and delivered, respectively.Source: §2 · p. 3, Figure 1 · p. 4

3 Proposed heuristic

This section presents ILSSBRP, a multi-start iterated local search for the single-vehicle SBRP, combining randomized local search, perturbations, repair, and procedures to construct and improve solutions. It also describes the local-search neighborhoods and four randomly selected perturbations that modify routes by adding visits, rearranging subsequences, or suppressing a visit, potentially producing an infeasible sequence.

3 Proposed heuristic

  • ILSSBRP uses randomized variable-neighborhood descent and temporarily accepts infeasible solutions after perturbations, a modification described as crucial to its favorable performance on this SBRP.It applies local search, perturbation, and repair across multiple restarts, then returns the best solution found.Source: §3 · p. 4

3.1 Solution representation

  • The solution representation stores the depot-to-depot visit sequence, bike deliveries or collections, and vehicle loads; a flow network checks displacement and capacity feasibility in polynomial time.Loads are derived in linear time from bike displacements, while a station-visit map tracks how often each station appears.Source: §3.1 · p. 6

3.2 Repairing infeasible solutions

  • AddUnbalanced attempts to repair infeasible solutions by inserting visits between the most excessive and default stations, and experiments found it often succeeds but cannot guarantee feasibility.If repair is incomplete and local search finds no move to feasibility, the solution is discarded.Source: §3 · p. 5, §3.2 · p. 6

3.3 Constructive Procedure

  • The greedy randomized constructor randomizes candidate-station order, inserts fully serviceable stations first, then splits service by maximizing bikes moved, with nearest insertion breaking ties.It repeats insertion until all open vertices are served.Source: §3.3 · pp. 6–7

3.4 Local search

  • RVND systematically examines different neighborhood types randomly, implements six neighborhood structures, and ends when all neighborhoods fail to refine the current solution; only feasible solutions are considered.Source: §3.4 · p. 7
  • Local search uses five well-known TSP neighborhood structures and a final problem-specific neighborhood to modify solutions.The passage illustrates a 2-opt move applied to a previous solution.Source: §3.4 · p. 8

3.5 Perturbation mechanisms

  • The four perturbations are AddBuffer, AddStations, Double-Bridge, and Suppression, with one selected at random whenever the algorithm enters perturbation.Suppression may produce an infeasible modified sequence.Source: §3.5 · pp. 8–10
  • AddBuffer inserts an extra station visit by cheapest insertion, while AddStations adds visits to up to three random stations toward the route’s end.Unrouted stations are inserted twice; AddStations considers stations visited at most once and forbids adjacent visits to the same station.Source: §3.5 · p. 9
  • Double-Bridge permutes two subsequences, removing and adding four arcs; Martin et al. (1991) introduced it for the TSP.Suppression applies a random suppression move, and its resulting sequence may be infeasible.Source: §3.5 · pp. 9–10

4 Computational experiments

The computational experiments evaluate ILSSBRP on benchmark instances, compare it with prior heuristics and an exact method, and tune perturbation and iteration settings for solution quality and CPU time. They report better solution quality and CPU time on 100-station instances, and that ILSSBRP found most known optima and improved many open instances with up to 60 stations.

4.1 Instances

  • Benchmark instances span 20–500 stations and vehicle capacities 10–1000; ILSSBRP was tested on instances considered by either comparison study, using α=1 and 3.For each problem-size and capacity pair, the benchmark includes 10 instances.Source: §4.1 · pp. 10–11

4.2 Impact of the perturbation mechanisms

  • The combination P(2) + P(3) + P(4) offered a compromise with average gap below 1% and CPU time, so the authors adopted it.The tested mechanisms were AddBuffer, AddStations, Double-Bridge, and Suppression.Source: §4.2 · p. 11, Table 1 · p. 11

4.3 Parameter tuning

  • Testing Imin values from 100 to 180 suggested 160 as a quality–time compromise, yielding the setting IILS = max{160, 4 × n}.The tuning runs used 20- and 30-station instances, with 10 runs for each Imin value.Source: §4.3 · p. 12

4.4 Comparison with the literature

  • Each instance was run 10 times with a 1-hour limit; Chemla et al. (2013a) runtimes were scaled by 2.43, while Erdoğan et al. (2015) runtimes were unadjusted.The paper treats the latter machine as roughly equivalent to, or slightly faster than, its own.Source: §4.4 · p. 12

4.4.1 Results for instances with up to 60 stations

  • ILSSBRP and Erdoğan et al. (2015) produced visibly better solutions than Chemla et al. (2013a)’s tabu searches, especially TS1, with the advantage more pronounced at α=3.Table 2 reports results for α=1; the text notes that the superiority is even more prominent at α=3.Source: §4.4.1 · pp. 13–14, Table 2 · p. 13
  • With demands fixed, smaller vehicle capacities increased relative visits and tour size, affecting local-search operations and potentially the number of ILS iterations.More moves were required as visit counts increased.Source: §4.4.1 · p. 14
  • For ILSSBRP, average gaps tended to be larger at very small Q, while average CPU time decreased as Q increased for both α=1 and α=3.Chemla et al.’s heuristic showed a similar CPU-time pattern.Source: §4.4.1 · p. 14
  • For n ≤ 60, solution quality was equivalent to Erdo˘gan et al. (2015), except ILSSBRP clearly outperformed it at n = 60, α = 3.Source: §4.4.1 · p. 14
  • For n > 40, CPU time increased considerably for literature methods but more moderately for ILSSBRP; Erdo˘gan et al. (2015) and Chemla et al. (2013a) tend to grow exponentially with n.Source: §4.4.1 · pp. 14–15
  • ILSSBRP found 419 of 424 known optima and improved 17 of 26 open instances at α = 1; at α = 3, it found 377 of 399 proven optima and improved 44 of 51 best-known solutions.Source: Table 4 · p. 16, §4.4.1 · p. 16

4.4.2 Results for instances with 100 stations

  • On 100-station instances, ILSSBRP outperformed literature methods in both solution quality and CPU time, significantly improving the best-known solution for every instance.Source: §4.4.2 · p. 17
  • For α = 1, ILSSBRP averaged at most 8 seconds; for Q ≥ 30 it took fractions of a second, while α = 3 generally took longer, mostly for Q = 10.These times were for finding or improving Chemla et al. (2013a)’s best results.Source: §4.4.2 · p. 17

5 Concluding Remarks

The hybrid ILS heuristic was evaluated on literature instances from 20 to 100 stations and produced strong results against existing methods. The authors identify feasibility checking as the main computational bottleneck and suggest improving it or exploring other hybridizations.

5 Concluding Remarks

  • The proposed method is a hybrid iterated local search designed for the single-vehicle SBRP and tested on 980 literature instances ranging from 20 to 100 stations.The comparison included results reported by Chemla et al. (2013a) and Erdo˘gan et al. (2015).Source: §5 · p. 17
  • ILSSBRP found 796 of 823 known optimal solutions (97%) and improved 61 of 77 open instances (79%), and failed to be at least equal to the best-known solution in 27 instances (3%).Source: §5 · p. 17
  • For the 80 instances with 100 stations, ILSSBRP outperformed the best available heuristics; overall, the authors report better solution quality and CPU time than literature methods.The conclusion also says the heuristic considerably improved the best-known solution for all instances.Source: §5 · p. 17
  • The authors propose exploring other hybridizations, such as combining efficient exact algorithms with their heuristic.They also identify development of an enhanced feasibility-verification procedure as future work.Source: §5 · p. 17
  • Feasibility verification is the algorithm's most time-consuming part and uses a relatively costly max-flow procedure.The authors suggest that improving this procedure could improve CPU time.Source: §5 · p. 17

Appendix A Checking feasibility

For a candidate station sequence, the feasibility check builds a directed flow network and computes a maximum flow to determine bike displacements. Network arcs encode station targets, vehicle capacity, and bikes remaining between repeat visits.

Appendix A Checking feasibility

  • Source arcs for each station's first occurrence use capacity p_i, while sink arcs for its last occurrence use capacity p'_i.These arcs encode the station targets at the sequence's first and last visits.Source: Appendix A · p. 23
  • Arcs between consecutive sequence vertices have capacity Q, and arcs between repeat visits to a station have capacity q_i.The latter arcs represent bikes remaining at that station between visits.Source: Appendix A · p. 23
  • A maximum-flow computation on the network finds optimal bike displacements along the candidate sequence.The sequence is a list of vertices that starts and ends at the depot.Source: Appendix A · p. 23
  • The resulting flow on arcs u_i and w_i gives the station's displacement values, while other arcs track bike transfers and bikes left between visits.The paper illustrates the network with the sequence 0, 1, 4, 2, 3, 5, 2, 4, 1, 0.Source: Appendix A · p. 23, Figure 10 · p. 23
  • A sequence is feasible when the computed displacement matches p_i for each station in the sequence; stations absent from it have zero displacement.The passage also specifies equality of the corresponding prime-marked displacement values for absent stations.Source: Appendix A · p. 23

Appendix B Detailed results

Appendix B presents detailed comparisons with the exact algorithm for instances up to 60 stations. Its tables cover two parameter settings, and a footnote flags a one-unit discrepancy that may reflect rounding.

Appendix B Detailed results

  • The appendix reports detailed ILSSBRB and exact-algorithm results for instances with up to 60 stations.The exact results are attributed to Erdo˘gan et al. (2015).Source: Appendix B · p. 23
  • Table 7 covers n ∈ {20, 30, 40, 50, 60} at α = 1, while Table 8 covers the same station counts at α = 3.The captions identify the scope of each table, not its cell values.Source: Table 7 · p. 24, Table 8 · p. 30
  • A footnote says one best feasible solution costs one unit less than the reported optimum, possibly because of rounding issues.The footnote attributes the reported optimal solution to Erdo˘gan et al. (2015).Source: Appendix B · p. 37
Loading 1605.00702v2…