z-logo
Premium
Large neighborhood search for the bike request scheduling problem
Author(s) -
Vergeylen Nicholas,
Sörensen Kenneth,
Vansteenwegen Pieter
Publication year - 2020
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12688
Subject(s) - computer science , solver , grasp , greedy randomized adaptive search procedure , set (abstract data type) , scheduling (production processes) , mathematical optimization , heuristic , greedy algorithm , variable neighborhood search , algorithm , metaheuristic , mathematics , artificial intelligence , programming language
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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here