A hybrid large neighborhood search for the static multi-vehicle bike-repositioning problem

Sin C. Ho and W.Y. Szeto

Transportation Research Part B: Methodological, 2017, vol. 95, issue C, 340-363

Abstract: This paper addresses the multi-vehicle bike-repositioning problem, a pick-up and delivery vehicle routing problem that arises in connection with bike-sharing systems. Bike-sharing is a green transportation mode that makes it possible for people to use shared bikes for travel. Bikes are retrieved and parked at any of the stations within the bike-sharing network. One major challenge is that the demand for and supply of bikes are not always matched. Hence, vehicles are used to pick up bikes from surplus stations and transport them to deficit stations to satisfy a particular service level. This operation is called a bike-repositioning problem. In this paper, we propose a hybrid large neighborhood search for solving the problem. Several removal and insertion operators are proposed to diversify and intensify the search. A simple tabu search is further applied to the most promising solutions. The heuristic is evaluated on three sets of instances with up to 518 stations and five vehicles. The results of computational experiments indicate that the heuristic outperforms both CPLEX and the math heuristic proposed by Forma et al. (2015) [Transportation Research Part B 71: 230–247]. The average improvement of our heuristic over the math heuristic is 1.06%, and it requires only a small fraction of the computation time.

Keywords: Bike-sharing; Bike-repositioning; Pick-up and delivery routing; Large neighborhood search; Tabu search (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (34)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261516302065
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:95:y:2017:i:c:p:340-363

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2016.11.003

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().