SOLVING THE DIAL-A-RIDE PROBLEM USING AGENT- BASED SIMULATION

Authors

  • Ian Campbell University of the Witwatersrand
  • Montaz M Ali
  • M L Fienberg

DOI:

https://doi.org/10.7166/27-3-1649

Abstract

The ‘dial-a-ride problem’ (DARP) requires a set of customers to be transported by a limited fleet of vehicles between unique origins and destinations under several service constraints, including within defined time windows. The problem is considered NP-hard, and has typically been solved using metaheuristic methods. An agent-based simulation (ABS) model was developed, where each vehicle bids to service customers based on a weighted objective function that considers the cost to service the customer and the time quality of the service that would be achieved. The approach applied a pre- processing technique to reduce the search space, given the service time window constraints. Tests of the model showed significantly better customer transit and waiting times than the benchmark datasets. The ABS was able to obtain solutions for much larger problem sizes than the benchmark solutions, with this work being the first known application of ABS to the DARP. 

Downloads

Published

2016-11-11

How to Cite

Campbell, I., Ali, M. M., & Fienberg, M. L. (2016). SOLVING THE DIAL-A-RIDE PROBLEM USING AGENT- BASED SIMULATION. The South African Journal of Industrial Engineering, 27(3), 143–157. https://doi.org/10.7166/27-3-1649

Issue

Vol. 27 No. 3 (2016)

Section

General Articles

License

Authors who publish in the Journal agree to the following terms:
  1. Authors retain copyright and grant the Journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this Journal.
  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the Journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this Journal.