A modified artificial bee colony algorithm for dynamic ride-hailing sharing problems

Abstract

Ride-hailing sharing involves grouping ride-hailing customers with similar trips and time schedules to share the same ride-hailing vehicle to reduce their total travel cost. Although there have been some studies on the ride-hailing/taxi sharing problem, the following research gaps exist. First, the travel cost and travel time of the passengers were not considered in the objective function and constraints of the ride-hailing sharing problem simultaneously in previous studies while those two factors are important due to sharing. Meanwhile, there was no efficient solution method to solve the ride-hailing sharing problem when considering the travel cost and travel time in both objective function and constraints. Second, there were rarely studies on the dynamic electric ride-hailing sharing problem integrating a dynamic electric ride-hailing matching problem (with sharing) and a dynamic ride-hailing electric vehicle (REV) charging problem. No existing studies of the charging problem of REVs consider the charging burden of charging stations and the effect of charging schedule on future request-REV matches. Third, multiple vehicle types which include express ride-hailing vehicles (ERHVs) and premier ride-hailing vehicles (PRHVs) as well as multiple user classes were not considered in the ride-hailing sharing problem. Substitution of an ERHV with a PRHV which means that a PRHV can be temporarily used as an ERHV to serve the customers who order ERHVs was also not studied in the literature. To fill the research gaps above, some studies of the ride-hailing sharing problem are conducted. First, a dynamic ride-hailing sharing problem that simultaneously maximizes the number of served customers, minimizes the travel cost and travel time ratios, and considers the capacity, time window, and travel cost constraints is formulated. The travel cost ratio is the ratio of actual passengers’ fare to the passengers’ fare without ride-hailing sharing, whereas the travel time ratio is defined as the actual travel time (including waiting time) over the maximum allowable travel time. To solve the dynamic ride-hailing sharing problem, it is divided into many small and continuous static subproblems with an equal time interval. Each subproblem is solved by a modified artificial bee colony (MABC) algorithm with path relinking, while the contraction hierarchies and vantage point tree are used to determine the shortest path and accelerate the algorithm, respectively. Second, a simulation-optimization framework for the dynamic electric ride-hailing sharing problem is developed which integrates a dynamic electric ride-hailing matching problem (with sharing) and a dynamic REV charging problem. REV charging problem incorporates a novel charging strategy to determine the charging schedules of REVs by considering the information of requests, REVs, and charging stations. Lastly, a dynamic ride-hailing sharing problem with multiple vehicle types, user classes, and substitution of ERHVs with PRHVs is proposed, in which a lexicographic multi-objective function with three-level objectives is adopted. Meanwhile, a new solution method based on the MABC algorithm is developed to solve the problem.