The shared-taxi problem: Formulation and solution methods

• This paper presents a mixed integer programming formulation for the shared taxi problem which is a common mode of transportation in several cities.
• The contributions are mainly methodological in addition to the newly proposed problem formulation.
• A Lagrangian decomposition approach and an incremental cost heuristic are proposed.
• The running times and the solution quality of the proposed approaches are compared to CPLEX.

With the rising fuel costs, ride sharing is becoming a common mode of transportation. Sharing taxis which has been prominent in several developing countries is also becoming common in several cities around the world. Sharing taxis presents several advantages as it minimizes vacant seats in cars thus reducing costs on taxi operators which results in significantly lower taxi fares for passengers. Besides the economical advantages, taxi sharing is highly important for reducing congestion on the roads and for minimizing the impact of transportation on the environment. In this paper, we formulate the problem of assigning passengers to taxis and computing the optimal routes of taxis as a mixed integer program. To solve the proposed model, we present a Lagrangian decomposition approach which exploits the structure of the problem leading to smaller problems that are solved separately. Furthermore, we propose two heuristics that are used to obtain good quality feasible solutions. The Lagrangian approach along with the heuristics are implemented and compared to solving the full problem using CPLEX. The computational results indicate the efficiency of the methodology in providing tighter bounds than CPLEX in shorter computational time.