The shared-taxi problem: Formulation and solution methods

Hadi Hosni, Joe Naoum-Sawaya and Hassan Artail

Transportation Research Part B: Methodological, 2014, vol. 70, issue C, 303-318

Abstract: 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.

Keywords: Shared taxi; Lagrangian relaxation; Integer programming (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (48)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261514001659
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:70:y:2014:i:c:p:303-318

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2014.09.011

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().