• Newly proposed search strategies improve

    From ScienceDaily@1:317/3 to All on Thu May 5 22:30:38 2022
    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)