Urban transportation has been a significant contributor to environmental challenges, including traffic congestion and greenhouse gas emissions, exacerbating climate change. In contrast, public transportation, especially in rural areas, often struggles to meet mobility needs effectively. Ridesharing systems have emerged as a response to these pressing issues. By facilitating the sharing of rides among individuals heading in the same direction, ridesharing optimizes vehicle use. This not only offers economic benefits but also addresses environmental concerns. This study addresses the critical challenge of dynamic matching in ridesharing systems, where the objective is to optimize the allocation of drivers to multiple passengers. Recognizing the multifaceted nature of this problem, our approach leverages the Firefly algorithm, a metaheuristic known for its efficacy in tackling complex optimization tasks. In our model, we account for a range of constraints including spatiotemporal limitations, capacity consideration and passenger waiting time restrictions. The primary goal is to minimize both the waiting time for passengers and the total distance traveled. To rigorously evaluate our method, we conducted experiments utilizing real-world data from a geographic area in the city of Guelma, Algeria. The results obtained through our experiments have demonstrated the effectiveness and performance of our system based on the Firefly algorithm. Indeed, our approach enhances the experience of passengers via a notable reduction in waiting times and it contributes to the overall efficiency of the ridesharing system by minimizing the total distance traveled.
In our modern society, mobility has transitioned from a convenience to an absolute necessity. However, this surge in mobility comes hand-in-hand with a numerous environmental and logistical challenges. While new means of transportation continue to develop, public transportation, especially in rural areas, often struggles to meet mobility needs competitively. At the same time, the intensive use of private cars has detrimental consequences on the environment, such as traffic congestion and greenhouse gas emissions, contributing to global warning.
In response to these challenges, the concept of ridesharing [
Over time, ridesharing has evolved into a more flexible and adaptable form known as
dynamic ridesharing [
In this work, we are interested in this critical challenge of dynamically matching drivers and
passengers, a problematic that is extensively studied in the literature exploring various
techniques ranging from exact methods [
Our goal is to optimize matches between drivers and passengers taking into account spatiotemporal constraints, vehicle capacity limitations, and passengers’ waiting times. This is done with respect to two distinct objectives. At a local level, the matches’ solutions proposed will optimize the pick-up and drop-off of passengers within each vehicle which involves finding the best temporal distribution to minimize passengers’ waiting time. At a global level, the goal is to optimally allocating passengers among the available vehicles in order to minimize the total distance traveled by both drivers and passengers.
Because of the nature of the problem: dynamicity, non-deterministic, multi-objective; metaheuristic algorithms are aptly suited to solve it. Indeed, their ability to traverse a wide solution space, coupled with their adaptability to dynamic environments, positions them as powerful tools for finding near-optimal solutions in real-time ride-matching scenarios. In this study, we propose to solve the considered problem using the firefly algorithm [13]. Our selection is driven by the renowned effectiveness of the Firefly algorithm in addressing intricate and dynamic optimization problems. Indeed, the firefly algorithm is known for its: (1) automatic population partitioning, dividing individuals (drivers and passengers) into subgroups to streamline solution searches; (2) innovative attraction mechanism which accelerates convergence, crucial in swiftly finding optimal matches between drivers and passengers; (3) adaptability to different optimization problems, demonstrated in dynamic ridesharing [9], [14], [15], allows for tailored solutions, offering flexibility to meet specific constraints and enabling the pursuit of optimal outcomes.
The remainder of the paper is organized as follows. We discuss in section 2 related articles to this work. The problem statement and formulation are presented in section 3. In section 4, we detail our proposed modeling and the solution proposed. The performance of our proposed approach is evaluated in section 5. Section 6, concludes and summarizes our work with future research directions.
Heuristic and metaheuristic approaches have seen extensive use within the dynamic ridesharing domain. Authors of [16] developed a new metaheuristic based on tabu search, integrated into the Dynamic Carpooling Optimization System (DyCOS). DyCOS is a system that supports the process of automatic and optimal placement of passengers in a very short time or even during the journey. Jadivi et al. [17] proposed an algorithm using Biogeography-Based Optimization (BBO) to solve a multi-objective optimization problem for online ridesharing. Zhan et al. [18] introduced a modified Artificial Bee Colony algorithm (MABC) with "path relinking" to address the real-time ridesharing problem. The objective is to maximize the number of participants, minimize cost and travel time, and consider capacity, time window, and travel cost constraints. The work of [19] proposed the Multi-agent, Multi-objective Preferencebased ridesharing model (MaMoP). They integrated evolutionary algorithms to find an optimized solution that maximizes benefits, reduces travel time, and minimizes costs. Gao et al. [20] suggested a Voting-based Matching (VOMA) mechanism to compute near-optimal matching solutions for drivers and passengers while respecting their privacy. Although the Firefly algorithm is less widely used than other optimization methods, it has been successfully applied in [9]. The authors integrated a hybrid metaheuristic algorithm called Firefly Algorithm and Differential Evolution (Firefly-DE). However, their focus was on optimizing cost sharing rather than addressing the broader dynamic ridesharing problem. Therefore, it is essential to further explore the use of the Firefly algorithm in other aspects of dynamic ridesharing, which is the objective of this work.
The main objective of this study is to solve the dynamic ridesharing problem by optimizing the matching between passengers’ requests and drivers’ offers using the Firefly algorithm. Specifically, we focus on scenarios where a driver can accommodate multiple passengers, while adhering to spatiotemporal constraints, capacity constraints, and passenger waiting time, all while optimizing two objectives: passengers’ waiting times and total distance traveled.
Dynamic ridesharing involves an automated process where a service provider connects drivers and passengers with similar routes and timetables, allowing them to share a ride in a private vehicle at a moment's notice. The defining characteristic of ridesharing systems is their dynamic nature, necessitating quick and efficient matching. The challenge lies in connecting individuals who have varying constraints, such as spatiotemporal limitations, seat availability, and user preferences. These constraints must be communicated beforehand by both drivers and passengers, prior to embarking on the intended trip.
The ridesharing system we aim to establish comprises several integral components, including a set of ride offers and requests, a matching mechanism, and a set of objectives for optimization. In this dynamic system, both drivers and passengers have the flexibility to submit their ride offers or requests shortly before their desired departure time. For drivers, this involves specifying details such as their departure point, destination, preferred departure and arrival times, along with the number of available seats in their vehicle. Passengers, on the other hand, provide information on their departure point, destination, preferred departure and arrival times, and the maximum waiting time they can tolerate.
The core of our service lies in the execution of a regular matching mechanism, ensuring adherence to various constraints. These constraints include temporal considerations, where matches are based on the desired departure and arrival times of both drivers and passengers. Additionally, spatial constraints are incorporated by considering the starting and destination points to optimize routes and ensure geographic proximity. The seat constraint further refines the matching process, prioritizing trips with a single driver and multiple passengers to maximize the efficient utilization of resources. As the system orchestrates these matches, it takes into account specific criteria for optimization. The primary objective is to minimize the overall distance traveled by drivers and passengers, accomplished by finding matches that lead to efficient routes. Simultaneously, a focus is placed on reducing passenger waiting time, achieved by promptly pairing them with compatible drivers who offer routes aligning with their preferences. In the following, we give the formulation of this problem. 3.1. Offer Let be a set of drivers submitting their ride offers. An offer ( ) of driver ( ∈ {1,2, … , }, with is the number of drivers) is defined as : ( ) = ( , , , , , ), where: - , is the driver’s identifier, - , is the departure point of the driver, - , is the arrival point of the driver, - , indicates the latest departure time of the driver, - , indicates the latest arrival time of the driver, - , represents the number of available seats.
with ( ,
Let be a set of passengers requesting rides. A request ( ) of passenger ( ∈ {1,2, … , } is the number of passengers) is defined as: ( ) = , , , ,
), where: - , is the passenger’s identifier, - , is the passenger’s departure point, - , is the passenger’s arrival point, - , represents the latest departure time of the passenger, - , represents the latest arrival time of the passenger, -
, is the passenger’s maximum waiting time.
Based on the travel offers and requests submitted by drivers and passengers, the final solution is a list of matches between drivers and passengers that adhere to the matching constraints, which are: •
Temporal constraints: The departure time of the passenger matched with the driver must not be before the departure time of the driver, and the actual arrival time of a driver at their destination after dropping off a passenger must not exceed their latest • • arrival time. Furthermore, the maximum waiting time for a passenger, must be greater than or equal to its current waiting time, denoted as of the passenger must be included in the driver’s itinerary. In this work, we, only, consider the case of inclusive itineraries, i.e., [ , ] ⊂ [ , ] .
Capacity constraint: Drivers must respect the maximum capacity of their vehicles during the matching process.
We propose to model and solve the considered problem using metaheuristic, specifically the firefly algorithm [13]. This algorithm is renowned for its ability to handle multi-objective optimization aligns seamlessly with the multifaceted nature of the problem, which involves minimizing the total distance traveled by vehicles and the waiting time for passengers while respecting spatial, temporal, and capacity constraints. In the next section, we present, in detail, the problem modeling approach.
The Firefly algorithm is a metaheuristic optimization technique inspired by the behavior of fireflies in nature. Developed by Xin-She Yang in 2009, it aims to solve optimization problems by mimicking the blinking patterns and attraction behavior of fireflies [13]. The flashing lights of fireflies serve a dual purpose: attracting individuals for mating and warning potential predators. This algorithm relies on three ideal rules that the Firefly algorithm adheres to regarding flashing lights and their intensity:
Fireflies are unisex, so a firefly will be attracted to others regardless of their gender. Attraction is proportional to brightness, and both decrease as distance increases. Thus, for two flashing fireflies, the less bright one will move toward the brighter one. If no firefly is brighter than a given firefly, it will move randomly.
The standard Firefly algorithm was initially developed for solving continuous optimization problems, rendering it unsuitable for discrete optimization issues like dynamic ridesharing. To apply it to a discrete ridesharing context, adaptation becomes essential by modifying each step and characteristic of the algorithm to account for discrete spaces, where solutions are based on discrete pairings between drivers and passengers.
Figure 2 illustrates the various steps of our proposed modeling of the problem using the Firefly algorithm.
The ridesharing problem involves matching drivers with passengers, where the solution can be expressed as the assignment of passengers to drivers. In our approach, each solution is represented by a firefly, and each firefly is characterized by a binary vector. A value of 1 indicates that the driver will take the corresponding passenger, while a value of 0 indicates that the passenger will not be taken by the driver.
We generated a population of fireflies in parallel and randomly for each driver. We consider three constraints during the population generation:
The passenger's itinerary is included in the driver's itinerary, The passenger's departure time must not be before the driver's departure time, The driver cannot take more passengers than the number of available seats.
Each firefly is evaluated to determine its objective function, which is associated with the brightness of the corresponding firefly. In the context of this study, the goal is to minimize both the distance and the waiting time of passengers. To achieve this, we propose an objective function that assesses the ratio between the distance among passengers and drivers and the maximum waiting time relative to the current waiting time of passengers. This objective function is defined as follows: min ( ) = ∑
∑ √( − ) =1 =1 2
2 + ( − ) + ( − ) × Where: √( − ) 2
2 + ( − ) indicates the Euclidean distance between the departure and arrival points of the driver's itinerary and the passenger's itinerary, ( −
) indicates the difference between the maximum waiting time of a passenger and his current waiting time, noted , - , is the decision variable, which is equal to 1 if the passenger is accepted and 0 otherwise.
The evaluation and analysis of the proposed objective function have led to a crucial observation in our problem:
If the value of the objective function is negative, it indicates that the current waiting time exceeds the maximum waiting time, and consequently, the request is automatically rejected. Indeed, since the distance is always positive, this suggests an excessively long delay for the passenger.
On the other hand, if the value of the objective function is greater than zero, it means that the solution is accepted. Finally, when the objective function has a zero value, two scenarios must be considered: if the passenger's route is identical to that of the driver, the request is accepted; otherwise, it is rejected: - ( ) > 0; the request is accepted, - ( ) < 0; the request is rejected, - ( ) = 0; In this case, we consider two situations: o The request is accepted if the passenger's route is the same as the driver's; i.e., the passenger has the same starting and ending points as the driver. o The request is rejected if the passenger's route is different from that of the driver.
In the Firefly algorithm, the movement of fireflies is based on the light intensity and the comparison between two fireflies. The attractiveness of a firefly is determined by its brightness, which is associated with the coded objective function. Thus, in the case of a minimization problem, a brighter firefly will move towards a less bright firefly. The process of updating solutions is carried out in the following steps:
A) Distance: To calculate the distance between fireflies, we propose using the Hamming distance. The Hamming distance between two solutions corresponds to the number of elements that differ in the sequence.
B) Attractiveness: To calculate attractiveness, we adjusted the attractiveness equation used in the continuous Firefly algorithm, replacing Cartesian distance with Hamming distance to meet the requirements of our ridesharing problem. The equation is defined as follows:
= 0 − 2 Where, 0 is the light intensity at the source, is a predefined light absorption coefficient and is the hamming distance between two fireflies.
In our work, we consider the parameter as a probability that guides the modification of the value of a variable in a firefly. The value of a variable in a less-performing firefly will be replaced by the corresponding value in a more-performing firefly. We referred to the work of [21] in making this choice. Thus, the higher the value of , the more likely the less-performing solution is to adopt the variable values of the best solution.
C) Local movement: The movement from a solution to another in a discrete problem
space can be achieved by following these steps:
- Identify the variables that share the same value in the solutions. These values will
remain unchanged in a less bright firefly.
- Generate a random number in the interval [
D) Global movement: To avoid the pitfalls of local optima in metaheuristics, we adopted a global exploration approach. During this step, we tested various mutation methods, including random reset mutation, inversion mutation, and swap mutation [21], [22]. After these tests, we chose the swap mutation method. This operator randomly selects two values in the firefly and exchanges their positions.
In this section, a series of numerical experiments are conducted to authenticate the proposed models by employing metrics that are significant to the problem of ridesharing. A simulator is devised to facilitate comprehension of the performance of our models under various circumstances, thereby offering valuable knowledge regarding their efficacy and flexibility within an online matching system.
To demonstrate the effectiveness and performance of our method, we present 3 scenarios where we vary the number of vehicles (drivers) and the number of passengers. The goal is to test the behavior and performance of our approach and evaluate its scalability.
We run our ridesharing simulation from 7:30 AM to 12:00 PM, imposing tight time windows to efficiently cater to passenger demands. The scenarios details and the matching results are given in Table 1.
In the first scenario, we fixed the number of drivers at 5 and the number of passengers at 15, while only 12 seats were available. In this scenario, we adjusted the number of iterations to evaluate its impact on the results. Initially, setting the maximum number of iterations to 10, we found that 11 passengers were satisfied while 4 were not, with an execution time of 372.588s. By increasing the number of iterations to 50, we observed a deterioration, with 10 satisfied passengers and 5 dissatisfied, with an execution time of 905.317s. In the second scenario, we fixed the number of drivers at 10 and the number of passengers at 25, with 23 seats available. We found that 19 passengers were satisfied and 6 were dissatisfied, with an execution time of 412.8s. And, in scenario 3, with 15 drivers and 35 passengers, along with 33 available seats, we achieved satisfaction for 29 passengers and dissatisfaction for 8, with an execution time of 579.59s.
The results of our study have demonstrated that the Firefly algorithm is capable of providing efficient matches, leading to increased passenger satisfaction. By optimizing routes and balancing demand and supply, we observed a significant reduction in passenger waiting times. This implies that passengers are less constrained by long waiting periods and can enjoy a more pleasant and convenient travel experience.
Dynamic ridesharing emerges as a modern and flexible solution to meet the transportation needs in our contemporary societies. Adapting to spatiotemporal constraints, it provides users with a convenient and swift way to find shared rides, thereby enhancing the overall efficiency of travel.
In this study, we explored the use of the Firefly metaheuristic algorithm to address the dynamic matching problem in ridesharing. Our objective was to minimize the distance traveled and passenger waiting time, taking into account capacity constraints, spatiotemporal constraints, and passenger waiting time constraints.
The results obtained through our experiments demonstrated the effectiveness and performance of our system based on the Firefly algorithm. We observed a significant improvement in the number of satisfied passengers, thanks to a notable reduction in waiting times. Furthermore, we successfully minimized the total distance traveled, contributing to a more efficient utilization of transportation resources. These promising results underscore the importance of metaheuristic algorithms in solving complex problems related to dynamic ridesharing. The Firefly algorithm has proven to be an effective tool for optimizing matches between drivers and passengers, providing an advantageous solution for users.
This work can benefit from many different extensions. One potential is the optimization of algorithm parameters where it is possible to conduct in-depth studies to determine the best optimization parameters for the Firefly algorithm. A second direction can be handling more complex constraints, such as detour constraints, cost-sharing constraints, environmental constraints, etc. Exploring the incorporation of these additional constraints can provide a more comprehensive solution for dynamic ridesharing systems.
During the preparation of this work, the authors used ChatGPT for grammar checks and to improve the clarity of certain paragraphs.
The authors affirm full responsibility for the accuracy, originality, and integrity of the final manuscript. [8] M. A. Masmoudi, M. Hosny, E. Demir, and E. Pesch, Hybrid adaptive large neighborhood search algorithm for the mixed fleet heterogeneous dial-a-ride problem, Journal of Heuristics, 26(2020), pp. 83-118. [9] F. S. Hsieh, A Hybrid Firefly-DE algorithm for Ridesharing Systems with Cost Savings
Allocation Schemes, in: IEEE World AI IoT Congress (AIIoT), 2022. [10] Z. T. Qin, H. Zhu, and J. Ye, Reinforcement learning for ridesharing: An extended survey,
Transportation Research Part C: Emerging Technologies, 144 (2022). [11] N. D. Kullman, M. Cousineau, J. C. Goodson, and J. E. Mendoza, Dynamic ride-hailing with electric vehicles, Transportation Science, 56 (2022), no. 3, pp. 775-794. [12] H. Abdelmoumène, C. Bencheriet, H. Belleili, I. Touati and C. Zemouli, Dynamic Matching Optimization in Ridesharing System Based on Reinforcement Learning, IEEE Access 12 (2024): 29525-29535. [13] X. S. Yang, Firefly algorithms for multimodal optimization, in: International symposium on stochastic algorithms. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. [14] F. S. Hsieh, A comparative study of several metaheuristic algorithms to optimize monetary incentive in ridesharing systems, ISPRS International Journal of Geo-Information 9.10 (2020): 590. [15] F.S. Hsieh, Trust-based recommendation for shared mobility systems based on a discrete self-adaptive neighborhood search differential evolution algorithm, Electronics 11.5 (2022): 776. [16] S. Ben Cheikh-Graiet, D. Mariagrazia, and S. Hammadi. A Tabu Search based metaheuristic for dynamic carpooling optimization, Computers & Industrial Engineering 140 (2020): 106217. [17] H. Javidi, D. Simon, L. Zhu and Y. Wang, A multi-objective optimization framework for online ridesharing systems, in: 2021 IEEE International Conference on Big Data and Smart Computing (BigComp). [18] X. Zhan, W. Y. Szeto, C. S. Chui, and X. M. Che, A modified artificial bee colony algorithm for the dynamic ride-hailing sharing problem, Transportation Research Part E: Logistics and Transportation Review 150 (2021): 102124. [19] V. R. de Carvalho, and F. Golpayegani, Satisfying user preferences in optimised ridesharing services: A multi-agent multi-objective optimisation approach, Applied Intelligence 52.10 (2022): 11257-11272. [20] J. Gao, Jie, T. Wong, B. Selim, and C. Wang, VOMA: A privacy-preserving matching mechanism design for community ride-sharing, IEEE Transactions on Intelligent Transportation Systems 23.12 (2022): 23963-23975. [21] M. Bidar, M. Mouhoub, and S. Sadaoui. Discrete firefly algorithm: A new metaheuristic approach for solving constraint satisfaction problems, in: 2018 IEEE Congress on Evolutionary Computation (CEC). [22] D. Srivatsa, T. K. Teja, I. Prathyusha and G. Jeyakumar, An empirical analysis of genetic algorithm with different mutation and crossover operators for solving Sudoku, in: Pattern Recognition and Machine Intelligence: 8th International Conference, PReMI 2019, Tezpur, India, December 17-20, 2019, Proceedings, Part I. Springer International Publishing, 2019.