The vehicle routing problem of intercity ride-sharing between two cities

Jiaqi Guo, Jiancheng Long, Xiaoming Xu, Miao Yu and Kai Yuan

Transportation Research Part B: Methodological, 2022, vol. 158, issue C, 113-139

Abstract: In this paper, we consider that a private company has developed a platform to provide intercity ride-sharing (IRS) services for riders between two cities. The riders between the two cities need to provide their travel information to the platform hours in advance. The company adopts commercial vehicles to pick up riders from one city and deliver them to the other city. The vehicle routing problem of IRS (VRP-IRS) is one of the core problems in the platform's decision making process. Due to the private nature of IRS platform, it is assumed that the platform aims to maximize the total profit of the IRS system by optimizing vehicle routing. As the IRS is long-distance travel, in order to ensure driving safety, each driver has to take a break after completing a long-distance trip. In this paper, the VRP-IRS is defined on a directed graph and formulated as a mixed integer linear programming problem. As the VRP-IRS is NP-hard, we propose a variable neighborhood search algorithm to solve the VRP-IRS. According to the characteristics of the feasible solutions to the VRP-IRS, a greedy sequential route construction method is developed to generate the initial solutions. Four trip-based neighborhood operators and four rider-based local search operators are proposed to shake the current solution to a new neighborhood and find better solutions based on the new neighborhood, respectively. Finally, numerical examples are provided to illustrate the performance of the proposed algorithm and the properties of the proposed model.

Keywords: Intercity ride-sharing; Vehicle routing problem; Variable neighborhood search; Neighborhood operator; Local search (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261522000327
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:158:y:2022:i:c:p:113-139

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.2022.02.013

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 ().