Top

Published in:

2019 | OriginalPaper | Chapter

Applying NSGA-II to a Multiple Objective Dial a Ride Problem

Authors : Pedro M. M. Guerreiro, Pedro J. S. Cardoso, Hortênsio C. L. Fernandes

Published in: Computational Science – ICCS 2019

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

In Dial-a-Ride Problem (DARP) customers request from an operator a transportation service from a pick-up to a drop-off place. Depending on the formulation, the problem can address several constraints, being associated with problems such as door-to-door transportation for elderly/disabled people or occasional private drivers. This paper addresses the latter case where a private drivers company transports passengers in a heterogeneous fleet of saloons, estates, people carriers and minibuses. The problem is formulated as a multiple objective DARP which tries to minimize the total distances, the number of empty seats, and the wage differential between the drivers. To solve the problem a Non-dominated Sorting Genetic Algorithm-II is hybridized with a local search. Results for daily scheduling are shown.

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 Asymmetric Deep Cross-modal Hashing

next chapter Smart Campus Parking – Parking Made Easy

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

Berbeglia, G., Cordeau, J.F., Laporte, G.: A hybrid tabu search and constraint programming algorithm for the dynamic dial-a-ride problem. INFORMS J. Comput. 24(3), 343–355 (2012). https://doi.org/10.1287/ijoc.1110.0454MathSciNetCrossRefMATH

Chevrier, R., Liefooghe, A., Jourdan, L., Dhaenens, C.: Solving a dial-a-ride problem with a hybrid evolutionary multi-objective approach: Application to demand responsive transport. Appl. Soft Comput. 12(4), 1247–1258 (2012). https://doi.org/10.1016/j.asoc.2011.12.014CrossRef

Cordeau, J.F.: A branch-and-cut algorithm for the dial-a-ride problem. Oper. Res. 54(3), 573–586 (2006)MathSciNetCrossRef

Cordeau, J.F., Laporte, G.: The dial-a-ride problem: models and algorithms. Ann. Oper. Res. 153(1), 29–46 (2007)MathSciNetCrossRef

Cubillos, C., Rodriguez, N., Crawford, B.: A study on genetic algorithms for the DARP problem. In: Mira, J., Álvarez, J.R. (eds.) IWINAC 2007. LNCS, vol. 4527, pp. 498–507. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-73053-8_50CrossRef

Deb, K.: Multi-objective Optimization Using Evolutionary Algorithms. Wiley, Chichester (2001)MATH

Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002)CrossRef

Gendreau, M., Potvin, J.Y.: Handbook of Metaheuristics, vol. 2. Springer, Boston (2010). https://doi.org/10.1007/978-1-4419-1665-5CrossRefMATH

10.

Haddadene, S.A., Labadie, N., Prodhon, C.: NSGA-II enhanced with a local search for the vehicle routing problem with time windows and synchronization constraints. IFAC-PapersOnLine 49(12), 1198–1203 (2016)CrossRef

11.

Hadka, D.: Platypus - Multiobjective Optimization in Python (2015). https://platypus.readthedocs.io. Accessed 08 Feb 2019

12.

Ho, S.C., Szeto, W., Kuo, Y.H., Leung, J.M., Petering, M., Tou, T.W.: A survey of dial-a-ride problems: literature review and recent developments. Trans. Res. Part B Methodol. 111, 395–421 (2018). https://doi.org/10.1016/j.trb.2018.02.001CrossRef

13.

Holland, J.: Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor (1975)

14.

Issaoui, B., Khelifi, L., Zidi, I., Zidi, K., Ghédira, K.: A contribution to the resolution of stochastic dynamic dial a ride problem with NSGA-II. In: 13th International Conference on Hybrid Intelligent Systems (HIS 2013), pp. 54–59 (2013)

15.

Lai, M., Tong, X.: A metaheuristic method for vehicle routing problem based on improved ant colony optimization and tabu search. J. Ind. Manage. Optim. 8(2), 469–484 (2012). https://doi.org/10.3934/jimo.2012.8.469MathSciNetCrossRefMATH

16.

Luxen, D., Vetter, C.: Real-time routing with openstreetmap data. In: Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS 2011, pp. 513–516. ACM, New York (2011). https://doi.org/10.1145/2093973.2094062

17.

Männel, D., Bortfeldt, A.: A hybrid algorithm for the vehicle routing problem with pickup and delivery and three-dimensional loading constraints. Eur. J. Oper. Res. 254(3), 840–858 (2016)MathSciNetCrossRef

18.

Miettinen, K.: Nonlinear Multiobjective Optimization. Kluwer Academic Publishers, Boston (1999)MATH

19.

Morais, A.C., Torres, L., Dias, T.G., Cardoso, P.J.S., Fernandes, H.: A combined data mining and tabu search approach for single customer dial-a-ride problem. In: 7th International Conference on Metaheuristics and Nature Inspired Computing, Marrakech, Morocco, pp. 121–123, October 2018

20.

Murata, T., Itai, R.: Multi-objective vehicle routing problems using two-fold EMO algorithms to enhance solution similarity on non-dominated solutions. In: Coello Coello, C.A., Hernández Aguirre, A., Zitzler, E. (eds.) EMO 2005. LNCS, vol. 3410, pp. 885–896. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-31880-4_61CrossRefMATH

21.

OpenStreetMap contributors: Planet dump (2017). https://planet.osm.org. https://www.openstreetmap.org

22.

Parragh, S.N., Doerner, K.F., Hartl, R.F.: A survey on pickup and delivery problems. Journal für Betriebswirtschaft 58(1), 21–51 (2008)CrossRef

23.

Qu, Y., Bard, J.F.: A branch-and-price-and-cut algorithm for heterogeneous pickup and delivery problems with configurable vehicle capacity. Transp. Sci. 49(2), 254–270 (2014)CrossRef

24.

Riquelme, N., Lücken, C.V., Baran, B.: Performance metrics in multi-objective optimization. In: 2015 Latin American Computing Conference (CLEI), pp. 1–11, October 2015. https://doi.org/10.1109/CLEI.2015.7360024

25.

Ropke, S., Cordeau, J.F., Laporte, G.: Models and branch-and-cut algorithms for pickup and delivery problems with time windows. Networks Int. J. 49(4), 258–272 (2007)MathSciNetMATH

26.

Salhi, S., Imran, A., Wassan, N.A.: The multi-depot vehicle routing problem with heterogeneous vehicle fleet: formulation and a variable neighborhood search implementation. Comput. Oper. Res. 52, 315–325 (2014)MathSciNetCrossRef

27.

Subramanian, A., Drummond, L., Bentes, C., Ochi, L., Farias, R.: A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery. Comput. Oper. Res. 37(11), 1899–1911 (2010). https://doi.org/10.1016/j.cor.2009.10.011CrossRefMATH

28.

Toth, P., Vigo, D.: Vehicle Routing: Problems, Methods, and Applications. SIAM (2014)

29.

Tripathy, T., Nagavarapu, S.C., Azizian, K., Ramasamy Pandi, R., Dauwels, J.: Solving dial-a-ride problems using multiple ant colony system with fleet size minimisation. In: Chao, F., Schockaert, S., Zhang, Q. (eds.) UKCI 2017. AISC, vol. 650, pp. 325–336. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-66939-7_28CrossRef

30.

Zitzler, E., Thiele, L.: Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans. Evol. Comput. 3(4), 257–271 (1999)CrossRef

Title: Applying NSGA-II to a Multiple Objective Dial a Ride Problem
Authors: Pedro M. M. Guerreiro
Pedro J. S. Cardoso
Hortênsio C. L. Fernandes
Publisher: Springer International Publishing
Book: Computational Science – ICCS 2019
Print ISBN: 978-3-030-22749-4

Electronic ISBN: 978-3-030-22750-0

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-22750-0_5

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner