Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Integrating Association Rules Mined from Health-Care Data with Ontological Information for Automated Knowledge Generation Read chapter Read first chapter

2018 | Supplement | Chapter

Solving Dial-A-Ride Problems Using Multiple Ant Colony System with Fleet Size Minimisation

Authors : Twinkle Tripathy, Sarat Chandra Nagavarapu, Kaveh Azizian, Ramesh Ramasamy Pandi, Justin Dauwels

Published in: Advances in Computational Intelligence Systems

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This paper proposes an ant colony optimization (ACO) based algorithm to minimise the fleet size required to solve dial-a-ride problem (DARP). In this work, a static multi-vehicle case of DARP is considered where routes of multiple vehicles are designed to serve customer requests which are known a priori. DARP necessitates the need of high quality algorithm to provide optimal feasible solutions. We employ an improved ACO algorithm called ant colony system (ACS) to solve DARP. The fleet minimisation is also achieved by using ACS. In summary, multiple ACS are employed to minimise the fleet size while generating feasible solutions for DARP. Furthermore, the theoretical results are also validated through simulations.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Fuzzy Bi-objective Chance-Constrained Programming Model for Timetable Optimization of a Bus Route
next chapter Bus Scheduling Timetable Optimization Based on Hybrid Bus Sizes
Literature
1.
Wilson, N.H., Sussman, J.M., Wong, H.K., Higonnet, T.: Scheduling algorithms for a dial-a-ride system. Massachusetts Institute of Technology, Urban Systems Laboratory (1971)
2.
Psaraftis, H.N.: An exact algorithm for the single vehicle many-to-many dial-a-ride problem with time windows. Transp. Sci. 17(3), 351–357 (1983)CrossRef
3.
Healy, P., Moll, R.: A new extension of local search applied to the dial-a-ride problem. Eur. J. Oper. Res. 83(1), 83–104 (1995)CrossRefMATH
4.
5.
Cordeau, J.-F., Laporte, G.: A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transp. Res. Part B: Methodol. 37(6), 579–594 (2003)CrossRef
6.
Attanasio, A., Cordeau, J.-F., Ghiani, G., Laporte, G.: Parallel tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem. Parallel Comput. 30(3), 377–387 (2004)CrossRef
7.
Cordeau, J.-F., Laporte, G.: The dial-a-ride problem (DARP): variants, modeling issues and algorithms. 4OR: A Q. J. Oper. Res. 1(2), 89–101 (2003)MathSciNetCrossRefMATH
8.
Rekiek, B., Delchambre, A., Saleh, H.A.: Handicapped person transportation: an application of the grouping genetic algorithm. Eng. Appl. Artif. Intell. 19(5), 511–520 (2006)CrossRef
9.
10.
Dorigo, M., Stutzle, T.: Ant Colony Optimization. The MIT Press (2004)
11.
Dorigo, M.: Optimization, learning and natural algorithms, Ph.D. thesis, Politecnico di Milano, Italy (1992)
12.
Dorigo, M., Gambardella, L.M.: Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans. Evol. Comput. 1(1), 53–66 (1997)CrossRef
13.
Gambardella, L.M., Taillard, E., Agazzi, G.: MACS-VRPTW: a multiple ant colony system for vehicle routing problems with time windows. Istituto Dalle Molle Di Studi Sull Intelligenza Artificiale (1999)
14.
Paquette, J., Cordeau, J.-F., Laporte, G., Pascoal, M.M.B.: Combining multicriteria analysis and tabu search for dial-a-ride problems. Transp. Res. Part B: Methodol. 52, 1–16 (2013)CrossRef
15.
Blum, C.: Ant colony optimization: introduction and recent trends. Phys. Life Rev. 2(4), 353–373 (2005)CrossRef
16.
Tan, W.F., Lee, L.S., Majid, Z.A., Seow, H.V.: Ant colony optimization for capacitated vehicle routing problem. J. Comput. Sci. 8(6), 846–852 (2012)CrossRef
17.
Bullnheimer, B., Hartl, R.F., Strauss, C.: Applying the ant system to the vehicle routing problem. In: Meta-heuristics: Advances and Trends in Local Search Paradigms for Optimization, pp. 285–296. Kluwer Academic Publishers, Dordrecht (1999)
18.
Metadata
Title
Solving Dial-A-Ride Problems Using Multiple Ant Colony System with Fleet Size Minimisation
Authors
Twinkle Tripathy
Sarat Chandra Nagavarapu
Kaveh Azizian
Ramesh Ramasamy Pandi
Justin Dauwels
Copyright Year
2018
Book
Advances in Computational Intelligence Systems

Print ISBN: 978-3-319-66938-0

Electronic ISBN: 978-3-319-66939-7

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-319-66939-7_28

Premium Partner

    Image Credits