A VNS-Based Matheuristic to Solve the Districting Problem in Bicycle-Sharing Systems
A matheuristic approach that combines a reduced variable neighbourhood search (rVNS) algorithm and a mathematical programming (MP) solver to solve a novel model for the districting problem in a public bicycle-sharing system is presented. The problem is modelled as an integer programming problem. Whi...
Main Authors: | , , , , |
---|---|
Format: | Article |
Language: | English |
Published: |
MDPI AG
2022-11-01
|
Series: | Mathematics |
Subjects: | |
Online Access: | https://www.mdpi.com/2227-7390/10/22/4175 |
_version_ | 1797464704062324736 |
---|---|
author | Guillermo Cabrera-Guerrero Aníbal Álvarez Joaquín Vásquez Pablo A. Maya Duque Lucas Villavicencio |
author_facet | Guillermo Cabrera-Guerrero Aníbal Álvarez Joaquín Vásquez Pablo A. Maya Duque Lucas Villavicencio |
author_sort | Guillermo Cabrera-Guerrero |
collection | DOAJ |
description | A matheuristic approach that combines a reduced variable neighbourhood search (rVNS) algorithm and a mathematical programming (MP) solver to solve a novel model for the districting problem in a public bicycle-sharing system is presented. The problem is modelled as an integer programming problem. While the rVNS algorithm aims to find a high-quality set of centres for the repositioning zones, the MP solver computes the optimal allocation network of the stations to the centres of the repositioning zones. We use a predefined grid to reduce the search space the rVNS needs to explore. The proposed approach obtains promising results for small and medium-sized instances, and is also able to handle large-sized models. |
first_indexed | 2024-03-09T18:10:57Z |
format | Article |
id | doaj.art-84aff65f6d8149fbb68216060bfd65b1 |
institution | Directory Open Access Journal |
issn | 2227-7390 |
language | English |
last_indexed | 2024-03-09T18:10:57Z |
publishDate | 2022-11-01 |
publisher | MDPI AG |
record_format | Article |
series | Mathematics |
spelling | doaj.art-84aff65f6d8149fbb68216060bfd65b12023-11-24T09:07:13ZengMDPI AGMathematics2227-73902022-11-011022417510.3390/math10224175A VNS-Based Matheuristic to Solve the Districting Problem in Bicycle-Sharing SystemsGuillermo Cabrera-Guerrero0Aníbal Álvarez1Joaquín Vásquez2Pablo A. Maya Duque3Lucas Villavicencio4Escuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362807, ChileEscuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362807, ChileEscuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362807, ChileResearch Group of Analytics for Decision Making (ALIADO), Industrial Engineering Department, Universidad de Antioquia, Calle 67 No. 53-108, Medellín 050010, ColombiaEscuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362807, ChileA matheuristic approach that combines a reduced variable neighbourhood search (rVNS) algorithm and a mathematical programming (MP) solver to solve a novel model for the districting problem in a public bicycle-sharing system is presented. The problem is modelled as an integer programming problem. While the rVNS algorithm aims to find a high-quality set of centres for the repositioning zones, the MP solver computes the optimal allocation network of the stations to the centres of the repositioning zones. We use a predefined grid to reduce the search space the rVNS needs to explore. The proposed approach obtains promising results for small and medium-sized instances, and is also able to handle large-sized models.https://www.mdpi.com/2227-7390/10/22/4175balancing strategyrepositioning zonedemand zonebicycle-sharing systemvariable neighbourhood searchmathematical programming |
spellingShingle | Guillermo Cabrera-Guerrero Aníbal Álvarez Joaquín Vásquez Pablo A. Maya Duque Lucas Villavicencio A VNS-Based Matheuristic to Solve the Districting Problem in Bicycle-Sharing Systems Mathematics balancing strategy repositioning zone demand zone bicycle-sharing system variable neighbourhood search mathematical programming |
title | A VNS-Based Matheuristic to Solve the Districting Problem in Bicycle-Sharing Systems |
title_full | A VNS-Based Matheuristic to Solve the Districting Problem in Bicycle-Sharing Systems |
title_fullStr | A VNS-Based Matheuristic to Solve the Districting Problem in Bicycle-Sharing Systems |
title_full_unstemmed | A VNS-Based Matheuristic to Solve the Districting Problem in Bicycle-Sharing Systems |
title_short | A VNS-Based Matheuristic to Solve the Districting Problem in Bicycle-Sharing Systems |
title_sort | vns based matheuristic to solve the districting problem in bicycle sharing systems |
topic | balancing strategy repositioning zone demand zone bicycle-sharing system variable neighbourhood search mathematical programming |
url | https://www.mdpi.com/2227-7390/10/22/4175 |
work_keys_str_mv | AT guillermocabreraguerrero avnsbasedmatheuristictosolvethedistrictingprobleminbicyclesharingsystems AT anibalalvarez avnsbasedmatheuristictosolvethedistrictingprobleminbicyclesharingsystems AT joaquinvasquez avnsbasedmatheuristictosolvethedistrictingprobleminbicyclesharingsystems AT pabloamayaduque avnsbasedmatheuristictosolvethedistrictingprobleminbicyclesharingsystems AT lucasvillavicencio avnsbasedmatheuristictosolvethedistrictingprobleminbicyclesharingsystems AT guillermocabreraguerrero vnsbasedmatheuristictosolvethedistrictingprobleminbicyclesharingsystems AT anibalalvarez vnsbasedmatheuristictosolvethedistrictingprobleminbicyclesharingsystems AT joaquinvasquez vnsbasedmatheuristictosolvethedistrictingprobleminbicyclesharingsystems AT pabloamayaduque vnsbasedmatheuristictosolvethedistrictingprobleminbicyclesharingsystems AT lucasvillavicencio vnsbasedmatheuristictosolvethedistrictingprobleminbicyclesharingsystems |