Solving dial-a-ride problem using ant colony optimisation

• Main Author: Kolumam Anantharamakrishnan Krishnamurthy
• Other Authors: Justin Dauwels
• Format: Theses and Dissertations
• Language: English
• Published: 2018
• Subjects: DRNTU::Engineering::Electrical and electronic engineering
• Online Access: http://hdl.handle.net/10356/73136
• Institution: Nanyang Technological University

Dial-a-ride problem refers to the problem of designing scheduled vehicle routes to serve passenger requests in the form of pick-ups and deliveries. It is also called as ‘demand responsive transport’ wherein the customer demands/requests are specified as pick-up and drop-off locations and time windows. In this work, a static multivehicle case of DARP is considered where routes of multiple vehicles are designed to serve customer requests which are known a priori. The DARP necessitates the need of high quality algorithm to provide optimal feasible solutions. The Ant Colony Optimisation intends to achieve this, by leveraging real ant’s intelligence in the decision making process to select the routes efficiently. The work explores an ‘elitist ant’ based ACO algorithm to solve DARP. Additionally, tuning the values of the ant parameters play an important role in improving the solution. The results obtained by using the algorithm perform favourably when compared to existing algorithms. Furthermore, the theoretical results are also validated through simulations carried out in MATLAB.