期刊
EXPERT SYSTEMS WITH APPLICATIONS
卷 42, 期 19, 页码 6728-6737出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.eswa.2015.04.060
关键词
Taxi-sharing; Ride-sharing; Dial-a-Ride; Heuristics; GRASP
类别
资金
- CNPq
- FAPESP
This paper deals with a combinatorial optimization problem that models situations of both dynamic ride-sharing and taxi-sharing. Passengers who want to share a taxi or a ride, use an app to specify their current location, destination and further information such as the earliest departure time, the latest arrival time and the maximum cost they are willing to pay for the ride. Car owners also specify their origin, destination, the leaving time and the maximum accepted delay. Taxi drivers report their location and the time they will start and end the service. All drivers need to define a price per kilometer. The problem is to compute routes, matching requests to vehicles in such a way that ride-sharing is allowed as long as some restrictions are satisfied, such as: the capacity of the vehicle, maximum trip cost of each passenger and maximum delay. The problem is dynamic since new requests arrive on-line and routes can be modified in order to attend them. To solve this dynamic problem, the day is divided in time periods. For each period, an instance of a static problem is created and solved by a greedy randomized adaptive search procedure (GRASP). Experiments with instances based on real data were made to evaluate the heuristics and the proposed method. In our simulations with taxis, passengers paid, on average, almost 30% less than they would pay on private rides. (C) 2015 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据