Application of Large Neighborhood Search method in solving a dynamic dial-a-ride problem with money as an incentive
Open Access
- 1 May 2019
- conference paper
- Published by IOP Publishing in Journal of Physics: Conference Series
- Vol. 1218 (1) , 012008
Abstract
A Dynamic Dial-a-Ride Problem with Money as an Incentive (DARP-M) is a problem of finding optimal route to serve requests demand which uses taxi-sharing system with cost constraint. Taxi-sharing is a system where individual customer share vehicle with other customers, who has the same or similar origin, destination, and travel time. The optimal solution is the solution that can minimize the cost of each trip request. This study discusses DARP-M to optimize the use of taxi-sharing. The search for the DARP-M solution in this research uses the insertion heuristic method for construction of initial solution and the large neighborhood search method for the optimal solution determination. Then, the experiment uses three times periods, from which the experiment result shows the large neighborhood search method can minimize customers travel cost up to 27.40 % less than the cost of private rides.Keywords
This publication has 8 references indexed in Scilit:
- Taxi and Ride Sharing: A Dynamic Dial-a-Ride Problem with Money as an IncentiveExpert Systems with Applications, 2015
- Optimization for dynamic ride-sharing: A reviewEuropean Journal of Operational Research, 2012
- Large Neighborhood Search2010
- The dial-a-ride problem: models and algorithmsAnnals of Operations Research, 2007
- A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time WindowsTransportation Science, 2004
- Heuristic Algorithms for the Handicapped Persons Transportation ProblemTransportation Science, 1997
- Algorithms for the Vehicle Routing and Scheduling Problems with Time Window ConstraintsOperations Research, 1987
- An Analysis of Several Heuristics for the Traveling Salesman ProblemSIAM Journal on Computing, 1977