Large neighborhood search for the bike request scheduling problem

• DOI: http://doi.org/10.1111/itor.12688
• Author: Nicholas Vergeylen,Pieter Vansteenwegen,Kenneth Sörensen
• Published date: 01 November 2020
• Date: 01 November 2020

Intl. Trans. in Op. Res. 27 (2020) 2695–2714

DOI: 10.1111/itor.12688

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Large neighborhood search for the bike request

scheduling problem

Nicholas Vergeylena, Kenneth S¨

orensena,∗and Pieter Vansteenwegenb

aDepartment of Engineering Management, University of Antwerp,Prinsstraat 13, 2000 Antwerp, Belgium

bLeuven Mobility Research Center – CIB, University of Leuven, 3000 Leuven, Belgium

E-mail: nicholas.vergeylen@uantwerpen.be [Vergeylen]; kenneth.sorensen@uantwerpen.be [S¨

orensen];

pieter.vansteenwegen@kuleuven.be [Vansteenwegen]

Received 17 July2018; received in revised form 4 May 2019; accepted 9 May 2019

Abstract

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 whichit 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.

Keywords: city bike; repositioning; large neighborhood search; greedy randomized adaptive search procedure; variable

neighborhood descent

1. Introduction

Like other forms of shared mobility systems (Laporteet al., 2018), bicycle sharing systems (BSSs) are

popping up in cities all over the world. Most of these initiatives allow a bike to be rented from an

automated rental station, use it fora short period of time, and return it to any other rental station in

the city. In 2014, the global Institute for Transportation and Development Policy (ITDP) reported

∗Corresponding author.

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

2696 N. Vergeylen et al. / Intl. Trans. in Op. Res. 27 (2020) 2695–2714

over 600 implemented BSSs, and this number is still increasing every year. In November 2017, The

Bike Sharing World Map (2017) puts the number of bike rental systems at slightly less than 1,500.

For a historical perspectiveon BSSs, as well as some future trends, we refer to the survey of DeMaio

(2009) and OBIS (2011). Clearly, bike sharing has evolvedfrom an interesting experiment to a viable

addition to the modal mix of public passenger transport.

A major challenge in almost all bike sharing systems is that stations tend to fill up or deplete over

time, preventingusers from returning or collecting bikes.This might happen according to predictable

patterns (e.g., in cities with topographical differences, stations at the top of a hill tend to deplete

whereas those at the bottom tend to fill up), or randomly.Since the ability to collect and return bikes

determines to a large extent the usability of the system, empty or full stations should be avoided

as much as possible. To maintain a minimum number of bikes and free slots in each station, BSSs

therefore use a fleet of vehicles to transfer bikes between stations. This is referred to as rebalancing

the system. The vehicles are in constant contact with the dispatching station, where the current

inventory of each station is monitored, and from where the repositioning activities are directed.

In many bike sharing systems, a monitoring system is at work that generates warnings when a

station is about to become full or empty. These warnings give rise to what we will call “requests.” A

request is a demand to pick up or drop off a specified number of bikes at a certain station within a

certain time window. It is very similar to, and performs the same function as, a “demand” in other

vehicle routing problems. Additionally, requests may have a priority, indicating their importance.

For example, requests that takeplace at busy stations (e.g., near an important public transport hub)

may have a higher priority than those at unimportant peripheral stations. The “Velo Antwerpen”

system in the city of Antwerp, Belgium, with which the authors of this paper maintain an intensive

collaboration, uses a proprietary mapping application in which full/empty warnings (which could

easily be transformed into requests) are generated based on the current status of each station, but

also based on prior knowledge about the expected net flowof bikes to or from a given station, given

the time of day. For example, some stations near buildings of the city administration tend to fill

up in the morning when public servants come to work, and deplete in the evening when the same

people return home.

Requests are not theoretical constructs intended to simplify the underlying vehicle routing prob-

lem. On the contrary, a large number of bike sharing system operators are currently using a request-

based system in practice. Requestsin such a system are generated by a system that warns the operator

if stations are expected to deplete or fill up in the near future. The resulting vehicle routing problem,

that is, the process of scheduling these requests on a set of repositioning vehicles, however, is now

typically solved manually in practice. The aim of this paper is to develop an algorithm to automate

this scheduling process.

Requests provide an intuitive and flexible way to plan the repositioning vehicles by assigning a

subset of all requests in a certain order to a vehicle, the vehicle’s route is fully determined. Since—in

general—more requests are generated than can be executed, the aim is to minimize the (priority-

weighted) number of requests that cannot be executed by the vehicles. The action of assigning and

sequencing the requests with the aim to minimize the total priority of unscheduled requests gives

rise to an optimization problem that we have called the bike request scheduling problem (BRSP) in

S¨

orensen and Vergeylen (2015). For a more formal introduction, we refer to Section 3.

Figure 1 illustrates the BRSP. In this figure, seven stations are defined (black circles), each having

zero or more requests. Requests show the time window, the priority, and the number of bikes

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation ofOperational Research Societies