The one-station bike repositioning problem E. Angelelli1 A. Mor2 M.G. Speranza1 1Department of Economics and Management

2025-05-06 0 0 1004.56KB 45 页 10玖币

侵权投诉

The one-station bike repositioning problem

E. Angelelli1, A. Mor2, M.G. Speranza1

1Department of Economics and Management

University of Brescia, Italy

{enrico.angelelli, grazia.speranza}@unibs.it

2Department of Management, Economics and Industrial Engineering

Politecnico di Milano, Italy

andrea.mor@polimi.it

Accepted for publication in Discrete Applied Mathematics

Abstract

In bike sharing systems the quality of the service to the users strongly depends on the

strategy adopted to reposition the bikes. The bike repositioning problem is in general very

complex as it involves diﬀerent interrelated decisions: the routing of the repositioning vehi-

cles, the scheduling of their visits to the stations, the number of bikes to load or unload for

each station and for each vehicle that visits the station. In this paper we study the problem

of optimally loading/unloading vehicles that visit the same station at given time instants of

a ﬁnite time horizon. The goal is to minimize the total lost demand of bikes and free stands

in the station. We model the problem as a mixed integer linear programming problem and

present an optimal algorithm that runs in linear time in the size of the time horizon.

Keywords: Bike Repositioning Problem; One station; Linear complexity; Optimal algo-

rithm

1 Introduction

In a Bike Sharing System (BSS) one of the most important decisions at the operational level is

the adoption of a bike repositioning strategy to mitigate the imbalances caused by user demand

over time and space. These strategies can be divided in user-based and vehicle-based. In the

former, reward systems are put in place to encourage a use of the system that counteracts the

imbalance. In the latter, one or more vehicles are deployed to move bike to and from stations to

rebalance the bike inventory. In this paper we consider the latter and focus on the operations of

a ﬂeet of vehicles in a single station.

Vehicle-based bike repositioning strategies can be further classiﬁed as static or dynamic.

When a static bike repositioning strategy is adopted, the bike repositioning operations are per-

formed when the user demand is low compared to the rest of the day, typically at night. In this

arXiv:2210.14002v3 [math.OC] 14 Jun 2024

case, real-time user demand is disregarded. Dynamic bike repositioning is performed during the

day, accounting for the real-time status of the system and the behavior of the users, as well as

its forecast. Typically, the dynamic problem is tackled by solving a static time-dependent sub-

problem at the beginning of the operating day based on the current state and a forecast of the

demand during the day. Decisions are then periodically re-evaluated at later times with updated

information.

Various objectives have been considered in the literature to evaluate the quality of the relo-

cation solution. The most common one is the maximization of the quality of service, typically

measured as the number of lost withdraws (due to the lack of bikes) and/or returns (due to the

lack of stands). The former causes discomfort as the user has to either wait for a bike to be

returned at the desired departure station, move to another station where bikes are available, or

resort to another means of transportation. In the latter case, the user has to cycle to a diﬀerent

station with free stands or, if available, resort to alternative ways to return the bike (e.g., with

a lock issued by the BSS operator).

Decisions to be taken in a repositioning strategy include those about the amount of bikes to

be loaded or unloaded in each station, the routing of the vehicles, and, in the dynamic setting,

the timing of the visits of the vehicles at each station. We collect the models that approach

these decisions under the name of bike repositioning problems (BRPs). These decisions are

interrelated. The routing determines the sequence of the stations visited by the vehicles and

therefore constrains their arrival time at each station. The number of bikes present at each

station depends on the arrival time.

The decisions taken for the operations of a vehicle in a station inﬂuence (interact with) not

only the actions of the same vehicle in the following stations along its route but also the actions of

other vehicles that could be scheduled to visit the same station. In fact, the interaction between

the operations of multiple vehicles is one of the main challenges when solving a problem in the

class of BRPs. The need of multiple visits, by the same vehicle or diﬀerent vehicles, to the same

station is a consequence of the limited capacity of the repositioning vehicles, and of the dynamic

nature of the user demand. Both loading and unloading operations need to be performed across

the stations and across time at the same station.

When multiple visits to a station are considered, the interaction among the vehicles should be

taken into account when planning the loading/unloading operations of each vehicle. Any decision

taken for a vehicle has an impact on the operations that the following vehicles can perform along

their routes. For example, if a vehicle loads bikes to tackle a shortage of stands, and the next

vehicle unloads bikes to prevent a later shortage of bikes, the number of bikes loaded by the ﬁrst

vehicle may have an impact on the size of the subsequent bike shortage. In other words, loading

an exceedingly large number of bikes on the ﬁrst vehicle may cause a worsening of the shortage

of bikes at a later time that the second vehicle may be unable to cope with.

Contribution. Drawing from the experience gained in a collaboration with Brescia Mobilità

SpA, operating the station-based BSSs in Brescia, Italy (see Angelelli et al. [2022]), in this paper

we study the problem of optimally loading/unloading vehicles that visit the same station at given

time instants of a discrete and ﬁnite time horizon. The net users demand at the station is known

(provided by the forecast) at each time instant of the time horizon. The goal is to minimize the

total lost demand of bikes and free stands. The station is characterized by an initial inventory

stock and a known capacity. Likewise, each vehicle is characterized by a capacity and an initial

load of bikes. We model the optimization problem, that accounts for the interaction of the

operations of the vehicles, as a mixed integer linear programming problem whose linear relaxation

is shown to always have an integer solution. We then present a solution algorithm that runs in

linear time in the size of the time horizon. Given the forecast of net users demand on each instant

(epoch) of the time horizon, the algorithm ﬁnds the type of operation (loading/unloading) and

the number of bikes (to be loaded/unloaded) for each vehicle that visits the station to minimize

the number of unsatisﬁed requests, taking into account the limits imposed by the capacity and

the load at the time of the visit. It also ﬁnds the number of requests that remain unsatisﬁed

regardless of the load and capacity of the vehicles. Therefore, the algorithm could be also used to

calibrate the load of the vehicles upon their arrival at a station and to evaluate the eﬀectiveness

of certain visiting times at a station. The problem addressed can be seen as a subproblem to be

solved in a solution approach to a more general repositioning problem. The availability of a very

eﬃcient optimal algorithm for the solution of the subproblem will contribute to the eﬃciency of

the approach. In this sense our work provides a contribution to the design of solution approaches

to more general models in the class of BRPs.

Literature Review. The design and management of a BSS involve many issues that have

been tackled by the optimization literature (see Laporte et al. [2018], Shui and Szeto [2020],

Vallez et al. [2021]). Among these problems, those regarding the mitigation of spatio-temporal

imbalances in the demand and oﬀer of bikes by the users have received a considerable attention.

Many works consider a static setting, where bike relocation is assumed to take place at night,

when user demand is negligible (see Benchimol et al. [2011], Chemla et al. [2013], Dell’Amico

et al. [2014], Erdoğan et al. [2014]). In this context, the decisions can be decomposed in those

regarding the inventory of the station and those about the routing of the relocating vehicles.

Considering the nighttime-only relocation of bikes can be a limitation in systems experiencing

high ﬂuctuations in user demand. This limitation is overcome in the dynamic setting where the

relocation takes place during the day and therefore decisions can be revised multiple times. In

this setting, the decisions to be taken include the inventory of each station, and the scheduling

and routing of the vehicles performing the relocation must be taken. These decisions have been

tackled both separately (e.g., Regue and Recker [2014]) and in an integrated way (e.g., Zhang

et al. [2017], Ghosh et al. [2017], Zheng et al. [2021]). It must be noted that the dynamic

setting requires to accurately forecast user behavior. This requirement is considered in various

contributions (e.g., Regue and Recker [2014], Alvarez-Valdes et al. [2016], Yoshida et al. [2019],

Lee et al. [2020]).

As noted above, in this paper we aim at tackling the problem of coordinating the operations

of multiple vehicles visiting a single station over time. A summary of the literature for this class

of BRPs that is relevant for our contribution is presented in Table I. For each reference, the table

classiﬁes the papers according to: the time setting of the problem (static or dynamic), the number

of vehicles for the repositioning of bikes, whether stations are allowed to be visited multiple times,

and whether vehicle interaction is considered or not. Considering the real-time evolution of the

system and the forecast of users behavior makes the bike repositioning a very diﬃcult problem

to solve. It is therefore not surprising that early contributions generally considered the static

setting. Furthermore, a considerable portion of the literature examined considers the case of a

single vehicle or does not allow for multiple visits or vehicle interaction. To further highlight the

diﬃculty of the task, it is also worth noting that, in many of the papers, the fact that stations

might be visited multiple times is not the result of a repositioning plan that explicitly considers

this possibility and the consequent vehicle interactions. In these papers this is the result of either

the problem being modeled as a Markov Decision Process where the set of actions includes the

visit to one among all the stations of the system, or the problem being solved by considering a

rolling horizon scheme where the reoptimization step considers a visit to all the stations, that

is, without removing from the set of candidate stops stations that have been visited at earlier

times.

We report that, to the best of our knowledge, the only work considering the problem on a

single station is Raviv and Kolka [2013]. The authors model the user requests to rent or return

a bike as stochastic processes and introduce a dissatisfaction function, establishing its convexity

and devising an accurate and eﬃcient approximation for its estimation.

The paper is organized as follows. First, in Section 2 the problem is deﬁned. Then, in Section

3 the optimization problem is discussed for speciﬁc subsets of the time horizon. The results are

then exploited in Section 4 to present a solution algorithm for the problem on the entire time

horizon.

Reference Time

setting # of vehicles Multiple

visits

Vehicles

interaction

Benchimol et al. [2011] Static Single - -

Chemla et al. [2013] Static Single - -

Erdoğan et al. [2014] Static Single - -

Ho and Szeto [2014] Static Single - -

Li et al. [2016] Static Single - -

Szeto et al. [2016] Static Single - -

Cruz et al. [2017] Static Single ✓-

Lin and Chou [2012] Static Multiple - -

Gaspero et al. [2013] Static Multiple - -

Forma et al. [2015] Static Multiple - -

Dell’Amico et al. [2016] Static Multiple - -

Szeto and Shui [2018] Static Multiple - -

Schuijbroek et al. [2017] Static Multiple1- -

Bulhões et al. [2018] Static Multiple ✓-

Rainer-Harbach et al. [2013] Static Multiple ✓ ✓

Raviv et al. [2013] Static Multiple ✓ ✓

Angeloudis et al. [2014] Static Multiple ✓ ✓

Alvarez-Valdes et al. [2016] Static Multiple ✓ ✓

Ho and Szeto [2017] Static Multiple ✓ ✓

Wang and Szeto [2018] Static Multiple ✓ ✓

Casazza et al. [2018] Static Multiple ✓ ✓4

Caggiani and Ottomanelli [2012] Dynamic Single - -

Shui and Szeto [2018] Dynamic Single ✓-

Brinkmann et al. [2019] Dynamic Single ✓2-

Kloimüllner et al. [2014] Dynamic Multiple - -

Huang et al. [2022] Dynamic Multiple1- -

Legros [2019] Dynamic Multiple1✓2-

Brinkmann et al. [2020] Dynamic Multiple ✓2-

Contardo et al. [2012] Dynamic Multiple ✓3-

Zhang et al. [2017] Dynamic Multiple ✓3-

Chiariotti et al. [2020] Dynamic Multiple ✓3-

Angelelli et al. [2022] Dynamic Multiple ✓3-

Ghosh et al. [2017] Dynamic Multiple ✓ ✓

Lowalekar et al. [2017] Dynamic Multiple ✓ ✓

Ghosh et al. [2019] Dynamic Multiple ✓ ✓

Zheng et al. [2021] Dynamic Multiple ✓ ✓

1Stations are clustered and each cluster is assigned to one vehicle.

2A Markov Decision Process is presented where routing decisions involve only one vehicle

visit per station. Further visits to a station are allowed only in subsequent stages.

3Each station can be served at most once by one vehicle within a repositioning time-

window. A rolling horizon scheme is presented, with multiple repositioning time-

windows, meaning that a station can be served in multiple time-windows during the

day.

4The vertices can be visited several times and by distinct vehicles, but temporary storage

is not allowed. This means that when inventory units are delivered to some vertices,

they cannot be picked up later again.

Table I: Literature contributions with respect to the characteristics relevant for this work.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Theone-stationbikerepositioningproblemE.Angelelli1,A.Mor2,M.G.Speranza11DepartmentofEconomicsandManagementUniversityofBrescia,Italy{enrico.angelelli,grazia.speranza}@unibs.it2DepartmentofManagement,EconomicsandIndustrialEngineeringPolitecnicodiMilano,Italyandrea.mor@polimi.itAcceptedforpublicationin...

展开>> 收起<<

The one-station bike repositioning problem E. Angelelli1 A. Mor2 M.G. Speranza1 1Department of Economics and Management.pdf

共45页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

The one-station bike repositioning problem E. Angelelli1 A. Mor2 M.G. Speranza1 1Department of Economics and Management

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: