Strategy for Exploring Feasible and Infeasible Solution Spaces to Solve a Multiple-Vehicle Bike Sharing System Routing Problem
In bicycle sharing systems, many vehicles restore bicycles to ports. To construct the shortest tour of these vehicles, in a previous work, we formulated the multiple-vehicle bike sharing system routing problem (mBSSRP) and demonstrated that an optimal solution can be obtained for small-sized instanc...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-08-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/11/16/7749 |
| _version_ | 1797524691354648576 |
|---|---|
| author | Honami Tsushima Takafumi Matsuura Tohru Ikeguchi |
| author_facet | Honami Tsushima Takafumi Matsuura Tohru Ikeguchi |
| author_sort | Honami Tsushima |
| collection | DOAJ |
| description | In bicycle sharing systems, many vehicles restore bicycles to ports. To construct the shortest tour of these vehicles, in a previous work, we formulated the multiple-vehicle bike sharing system routing problem (mBSSRP) and demonstrated that an optimal solution can be obtained for small-sized instances through a general-purpose mixed-integer linear programming solver. However, for large-sized instances, the optimal solution could not be found in a reasonable time frame. Therefore, to find near-optimal solutions for the mBSSRPs in a short time, in this study, we develop a method with a searching strategy, which explores both the feasible and infeasible solution spaces. To investigate the performance of the proposed method, we solve benchmark problems of mBSSRP. In addition, we compare the proposed method with the method exploring only the feasible solution space, in terms of performance. The results of the numerical experiments demonstrate that the proposed method can reach optimal solutions for almost all small-sized mBSSRP instances and that searching both the feasible and infeasible solution spaces yields good feasible solutions both for small-sized and large-sized instances. |
| first_indexed | 2024-03-10T09:01:20Z |
| format | Article |
| id | doaj.art-61bdf5780d084c04aeaf5ca695a708b7 |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-10T09:01:20Z |
| publishDate | 2021-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-61bdf5780d084c04aeaf5ca695a708b72023-11-22T06:46:18ZengMDPI AGApplied Sciences2076-34172021-08-011116774910.3390/app11167749Strategy for Exploring Feasible and Infeasible Solution Spaces to Solve a Multiple-Vehicle Bike Sharing System Routing ProblemHonami Tsushima0Takafumi Matsuura1Tohru Ikeguchi2Department of Information and Computer Technology, Graduate School of Engineering, Tokyo University of Science, 6-3-1 Niijuku, Katsushika-ku, Tokyo 125-8585, JapanGraduate School of Electronics, Information and Media Engineering Major, Nippon Institute of Technology, 4-1 Gakuendai, Miyashiro-machi, Minamisaitama-gun, Saitama 345-8501, JapanDepartment of Information and Computer Technology, Graduate School of Engineering, Tokyo University of Science, 6-3-1 Niijuku, Katsushika-ku, Tokyo 125-8585, JapanIn bicycle sharing systems, many vehicles restore bicycles to ports. To construct the shortest tour of these vehicles, in a previous work, we formulated the multiple-vehicle bike sharing system routing problem (mBSSRP) and demonstrated that an optimal solution can be obtained for small-sized instances through a general-purpose mixed-integer linear programming solver. However, for large-sized instances, the optimal solution could not be found in a reasonable time frame. Therefore, to find near-optimal solutions for the mBSSRPs in a short time, in this study, we develop a method with a searching strategy, which explores both the feasible and infeasible solution spaces. To investigate the performance of the proposed method, we solve benchmark problems of mBSSRP. In addition, we compare the proposed method with the method exploring only the feasible solution space, in terms of performance. The results of the numerical experiments demonstrate that the proposed method can reach optimal solutions for almost all small-sized mBSSRP instances and that searching both the feasible and infeasible solution spaces yields good feasible solutions both for small-sized and large-sized instances.https://www.mdpi.com/2076-3417/11/16/7749bicycle sharing systemheuristic methodtabu searchfeasible and infeasible solution |
| spellingShingle | Honami Tsushima Takafumi Matsuura Tohru Ikeguchi Strategy for Exploring Feasible and Infeasible Solution Spaces to Solve a Multiple-Vehicle Bike Sharing System Routing Problem Applied Sciences bicycle sharing system heuristic method tabu search feasible and infeasible solution |
| title | Strategy for Exploring Feasible and Infeasible Solution Spaces to Solve a Multiple-Vehicle Bike Sharing System Routing Problem |
| title_full | Strategy for Exploring Feasible and Infeasible Solution Spaces to Solve a Multiple-Vehicle Bike Sharing System Routing Problem |
| title_fullStr | Strategy for Exploring Feasible and Infeasible Solution Spaces to Solve a Multiple-Vehicle Bike Sharing System Routing Problem |
| title_full_unstemmed | Strategy for Exploring Feasible and Infeasible Solution Spaces to Solve a Multiple-Vehicle Bike Sharing System Routing Problem |
| title_short | Strategy for Exploring Feasible and Infeasible Solution Spaces to Solve a Multiple-Vehicle Bike Sharing System Routing Problem |
| title_sort | strategy for exploring feasible and infeasible solution spaces to solve a multiple vehicle bike sharing system routing problem |
| topic | bicycle sharing system heuristic method tabu search feasible and infeasible solution |
| url | https://www.mdpi.com/2076-3417/11/16/7749 |
| work_keys_str_mv | AT honamitsushima strategyforexploringfeasibleandinfeasiblesolutionspacestosolveamultiplevehiclebikesharingsystemroutingproblem AT takafumimatsuura strategyforexploringfeasibleandinfeasiblesolutionspacestosolveamultiplevehiclebikesharingsystemroutingproblem AT tohruikeguchi strategyforexploringfeasibleandinfeasiblesolutionspacestosolveamultiplevehiclebikesharingsystemroutingproblem |