MSGID: 1:317/3 6274a485   
   PID: hpt/lnx 1.9.0-cur 2019-01-08   
   TID: hpt/lnx 1.9.0-cur 2019-01-08   
    Newly proposed search strategies improve computational cost of the   
   bicycle-sharing problem    
      
     Date:   
         May 5, 2022   
     Source:   
         Tokyo University of Science   
     Summary:   
         Bicycle sharing is an attractive zero-carbon transportation   
         option for a world that is being increasingly disrupted by climate   
         change. But bikes need to be restored at bike ports every now and   
         then. Calculating the optimal way to restore bicycles is time   
         consuming and computationally expensive. Recently, researchers   
         have built upon their previous optimization algorithm to propose   
         two strategies to reduce computational costs while maintaining   
         the performance of the algorithm.   
      
      
      
   FULL STORY   
   ==========================================================================   
   Bicycle sharing systems (BSSs) are transport solutions wherein users   
   can rent a bicycle from a depot or 'port,' travel, and then return the   
   bike to the same port or different port. BSSs are growing in popularity   
   around the world because they are eco-friendly, reduce traffic congestion,   
   and offer added health benefits to users. But eventually, a port becomes   
   either full or empty in a BSS. This means that users are no longer able   
   to rent a bike (when empty) or return one (when full). To address this   
   issue, bikes need to be rebalanced among the ports in a BSS so that users   
   are always able to use them. This rebalancing must also be carried out   
   in a way that is beneficial to BSS companies so that they can reduce   
   labor costs, as well as carbon emissions from rebalancing vehicles.   
      
      
   ==========================================================================   
   There are several existing approaches to BSS rebalancing, however,   
   most solution algorithms are computationally expensive and take a lot   
   of time to find an 'exact' solution in cases where there are a large   
   number of ports. Even finding an approximate solution is computationally   
   expensive. Previously, a research team led by Prof. Tohru Ikeguchi from   
   Tokyo University of Science proposed a 'multiple-vehicle bike sharing   
   system routing problem with soft constraints' (mBSSRP-S) that can find   
   the shortest travel times for multiple bike rebalancing vehicles with the   
   caveat that the optimal solution can sometimes violate the real-world   
   limitations of the problem. Now, in a recent study published in MDPI's   
   Applied Sciences, the team has proposed two strategies to search for   
   approximate solutions to the mBSSRP-S that can reduce computational   
   costs without affecting performance. The research team also featured   
   PhD student Ms. Honami Tsushima of Tokyo University of Science and   
   Prof. Takafumi Matsuura of Nippon Institute of Technology.   
      
   Describing their research, Prof. Ikeguchi says, "Earlier, we had proposed   
   the mBSSRP-S and that offered improved performance as compared to our   
   original mBSSRP, which did not allow the violation of constraints. But   
   the mBSSRP-S also increased the overall computational cost of the problem   
   because it had to calculate both the feasible and infeasible solutions   
   of the mBSSRP. Therefore, we have now proposed two consecutive search   
   strategies to address this problem."  The proposed search strategies look   
   for feasible solutions in a much shorter period of time as compared to   
   the one originally proposed with mBSSRP-S. The first strategy focuses   
   on reducing the number of 'neighboring' solutions (solutions that are   
   numerically close to a solution to the optimization problem) before   
   finding a feasible solution. The strategy employs two well- known   
   algorithms called 'Or-opt' and 'CROSS-exchange,' to reduce the overall   
   time taken to compute a solution. The feasible solution here refers to   
   values that satisfy the constraints of mBSSRP.   
      
   The second strategy changes the problem to be solved based on the feasible   
   solution to either the mBSSRP problem or the mBSSRP-S problem and then   
   searches for good near-optimal solutions in a short time by either Or-opt   
   or CROSS- exchange.   
      
   The research team then performed numerical experiments to evaluate   
   the computational cost and performance of their algorithms. "With   
   the application of these two strategies, we have succeeded in   
   reducing computational time while maintaining performance," reveals   
   Prof. Ikeguchi. "We also found that once we calculated the feasible   
   solution, we could find short travel times for the rebalancing vehicles   
   quickly by solving the hard constraint problem, mBSSRP, instead of   
   mBSSRP-S."  The popularity of BSSs is only expected to grow in the   
   future. The new solution-search strategies proposed here will go a long   
   way towards realizing convenient and comfortable BSSs that benefit users,   
   companies, and the environment.   
      
      
   ==========================================================================   
   Story Source: Materials provided by Tokyo_University_of_Science. Note:   
   Content may be edited for style and length.   
      
      
   ==========================================================================   
   Journal Reference:   
      1. Honami Tsushima, Takafumi Matsuura, Tohru Ikeguchi. Searching   
      Strategies   
         with Low Computational Costs for Multiple-Vehicle Bike Sharing   
         System Routing Problem. Applied Sciences, 2022; 12 (5): 2675 DOI:   
         10.3390/ app12052675   
   ==========================================================================   
      
   Link to news story:   
   https://www.sciencedaily.com/releases/2022/05/220505114708.htm   
      
   --- up 9 weeks, 3 days, 10 hours, 50 minutes   
    * Origin: -=> Castle Rock BBS <=- Now Husky HPT Powered! (1:317/3)   
   SEEN-BY: 15/0 106/201 114/705 123/120 129/330 331 153/7715 218/700   
   SEEN-BY: 229/110 111 317 400 426 428 470 664 700 292/854 298/25 305/3   
   SEEN-BY: 317/3 320/219 396/45   
   PATH: 317/3 229/426