01697835

Component

City bikes and bike sharing systems (BSSs) are one solution to reducing traffic-related CO₂ emissions. These systems feature a multitude of bike stations scattered around a city where users can borrow bikes from one station and return them to the same or a different station. However, this action may create an unbalanced system, namely, some stations will have excess bikes and other with a low number. In this paper, the authors propose a solution to address this issue and satisfy expected demand patterns. They unveil an algorithm that provides a delivery truck with a road to follow. The truck will go from one station to another and satisfy individual station demands. Achieving this objective in an optimal manner (i.e., finding the shortest Hamiltonian cycle) is an NP-hard problem. However, for small instances, an exact solution can be obtained. The heuristic algorithm presented can deliver optimal and/or near optimal solutions at substantially lower computational costs, eventhough the algorithm is not parallel and the different subtours are solved in a sequential manner. It has three steps. The first step consists of dividing a large BSS network into “p” subnetworks, where p is also the number of available trucks. Each truck will serve a subnetwork. Then the redistribution within each subnetwork is modeled as a cooperative game and the deferred acceptance algorithm is used to construct a good initial tours. Finally, an improvement to the tours is performed using the 2-opt algorithm. The proposed algorithm was tested using large benchmark instances. The results show promising performance in terms of solution quality and computational time. The proposed algorithm can be used for real-time BSS re-balancing given its computational efficiency.

This paper was sponsored by TRB committee ANF20 Standing Committee on Bicycle Transportation.

19-00239

English

16p

2019

Transportation Research Board 98th Annual Meeting

Digital/other

Figures; References; Tables

Algorithms; Bicycles; Delivery vehicles; Game theory; Heuristic methods; Optimization; Physical distribution; Routes; Vehicle sharing

Bicycle sharing stations; Inventory balancing

Freight Transportation; Operations and Traffic Management; Pedestrians and Bicyclists; Planning and Forecasting

Transportation Research Board Annual Meeting 2019 Paper #19-00239

TRIS, TRB, ATRI

Dec 7 2018 9:39AM