Branch-and-Price-and-Cut for the Heterogeneous Fleet and Multi-Depot Static Bike Rebalancing Problem with Split Load

Ye Ding, Jiantong Zhang and Jiaqing Sun ()
Additional contact information
Ye Ding: School of Economic and Management, Tongji University, Shanghai 200092, China
Jiantong Zhang: School of Economic and Management, Tongji University, Shanghai 200092, China
Jiaqing Sun: School of Economic and Management, Tongji University, Shanghai 200092, China

Sustainability, 2022, vol. 14, issue 17, 1-24

Abstract: Heterogeneous Fleet and Multi-Depot Static Bike Rebalancing Problem with Split Load (HFMDSBRP-SD) is an extension of the Static Bike Rebalancing Problem, considering heterogeneous fleet multiple depots, allowing split load. It consists of finding a set of least-cost repositioning vehicle routes and determining each station’s pickup or delivery quantity to satisfy the demand of each station. We develop a branch-and-price-and-cut (BPC) where a tabu search column generator and a heuristic label-setting algorithm are introduced to accelerate the column generation procedure, the subset-row (SR) inequalities, the strong minimum number of vehicles (SMV) inequalities, and the enhanced elementary inequalities are extended fitting this problem and applied to speed up the global convergence rate. Computational results demonstrate the effectiveness of the BPC algorithm. Among 360 instances with a maximum size of 30, there are 298 instances capable of achieving optimality within two hour time limitation.

Keywords: bike sharing; split load; heterogeneous fleet; multi-depot; branch-and-price-and-cut; subset-row inequalities; elementary inequalities (search for similar items in EconPapers)
JEL-codes: O13 Q Q0 Q2 Q3 Q5 Q56 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2071-1050/14/17/10861/pdf (application/pdf)
https://www.mdpi.com/2071-1050/14/17/10861/ (text/html)

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:gam:jsusta:v:14:y:2022:i:17:p:10861-:d:902850

Access Statistics for this article

Sustainability is currently edited by Ms. Alexandra Wu

More articles in Sustainability from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().