Heuristic Approaches to Solve E-Scooter Assignment Problem

Abstract

Nowadays, rapid urbanization causes a wide-range of congestion and pollution in megacities worldwide, which bears an urgent need for micromobility solutions such as electric scooters (e-scooter). Many e-scooter firms use freelancers to charge the scooter where they compete to collect and charge the e-scooters at their homes. This competition leads the chargers to travel long distances to collect e-scooters. In this paper, we developed a mixed-integer linear programming (MILP) model for a real-world e-scooter -Chargers Allocation (ESCA) problem. The proposed model allocates the e-scooters to the chargers with an emphasis on minimizing the chargers’ average travelled distance to collect the e-scooters. The MILP returns optimal solutions in most cases; however, the ESCA is identified as a generalized assignment problem which classifies as an NP-complete combinatorial optimization problem. Moreover, we modelled the charging problem as a game between two sets of disjoint players, namely e-scooters and chargers. Then we adapted the college admission algorithm (ACA) to solve the ESCA problem. For the sake of comparison, we applied the black hole optimizer (BHO) algorithm to solve this problem using small and medium cases. The experimental results show that the ACA solutions are close to the optimal solutions obtained by the MILP. Furthermore, the BHO solutions are not as good as the ACA solutions, but the ACA solution consumes more time to solve large-scale real cases. Based on the obtained results, we recommend applying the ACA1 to find the near-optimal solution for large-scale instances, as the MILP is inapplicable to find the exact solution in comparison.