Large neighborhood search for the bike request scheduling problem

This paper introduces an efficient algorithm for the bike request scheduling problem (BRSP). The BRSP is built around the concept of request, defined as the pickup or dropoff of a number of identical items (bikes) at a specific station, within a certain time window, and with a certain priority. The aim of the BRSP is to sequence requests on (and hence determine the routes of) a set of vehicles, in such a way that the sum of the priorities of the executed requests is maximized, all time windows are respected, and the capacity of the vehicles is not exceeded. The generation of the set of requests is explicitly not a part of the problem definition of the BRSP. The primary application of the BRSP, from which it derives its name, is to determine the routes of a set of repositioning vehicles in a bike sharing system, although other applications exist. The algorithm introduced in this paper is based on a set of related greedy randomized adaptive search procedure followed by variable neighborhood descent (GRASP + VND) operators embedded in a large neighborhood search (LNS) framework. Since this paper presents the first heuristic for the BRSP, a computational comparison to existing approaches is not possible. We therefore compare the solutions found by our LNS heuristic to those found by an exact solver (Gurobi). These experiments confirm that the proposed algorithm scales to realistic dimensions and is able to find near‐optimal solutions in seconds.