A parallel memetic algorithm for solving complex transportation problems
A parallel memetic algorithm for solving complex transportation problems project is supported by the National Science Centre under research grant no. UMO-2013/09/N/ST6/03461 (years 2014-2017). It encompasses the following tasks:
- Design of the parallel algorithm for solving the PDPTW.
- Verification of correctness of the parallel algorithm, proving its safety and liveness.
- Theoretical analysis of characteristic measures of the parallel algorithm, i.e. its time and space complexity, speedup, parallel cost and efficiency.
- Implementation of the parallel algorithm for solving the PDPTW.
- Experimental analysis of characteristic measures of the parallel algorithm, i.e. its speedup, parallel cost and efficiency.
- Design and implementation of new, efficient co-operation schemes in the parallel memetic algorithm.
- Study of the influence of the co-operation frequency of parallel processes on the quality of final solutions.
- Study of the influence of a memetic algorithm parameters, including the initial population size, probability of crossover, pre- and post- selection schemes and number of child solutions for each pair of parents, on the quality of final solutions.
- Performing full Li and Lim benchmark tests.
- Gathering the experimental results and analyzing them statistically.
Publications (updated on April 26, 2017):
-
M. Błocho and J. Nalepa: LCS-Based Selective Route Exchange Crossover for the Pickup and Delivery Problem with Time Windows, In: Hu B., López-Ibáñez M. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2017. Lecture Notes in Computer Science, vol 10197, pages 124-140, Springer, Cham, 2017. (Nominated to the best paper award at the EvoCOP 2017 Conference, part of EvoStar 2017, Amsterdam, The Netherlands)
-
M. Błocho and J. Nalepa: Complexity Analysis of the Parallel Algorithm for Minimizing the Fleet Size in the Pickup and Delivery Problem with Time Windows, Proc. of the 25th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP 2017), Companion Material (Work in Progress Session), pages 1-2, 2017. (https://arxiv.org/abs/1704.06724)
-
J. Nalepa and M. Błocho.: Adaptive guided ejection search for pickup and delivery with time windows, Journal of Intelligent and Fuzzy Systems 32(2), pages 1547-1559, IOS Press, 2017. (JCR, IF=1.004)
-
J. Nalepa and M. Błocho.: Temporally adaptive co-operation schemes, Advances on P2P, Parallel, Grid, Cloud and Internet Computing (Proc. 3PGCIC 2016),
Vol. 1 of the series Lecture Notes on Data Engineering and Communications Technologies, pages 145-156, DOI: 10.1007/978-3-319-49109-7_14, Springer International Publishing, 2016. (Best paper of the 11th International Conference on P2P, Parallel, Grid, Cloud and Internet Computing (3PGCIC–2016, Asan, Korea) award)
-
J. Nalepa and M. Błocho.: Is your parallel algorithm correct?, Position Papers of the Federated Conference on Computer
Science and Information Systems, ACSIS, Vol. 9, pages 87–93, DOI: 10.15439/2016F554, 2016.
-
J. Nalepa: Genetic and memetic algorithms for selection of training sets for support vector machines, Ph.D. Thesis, Silesian University of Technology, Gliwice, 2016.
-
J. Nalepa and M. Błocho.: Intelligent Information and
Database Systems: Proc. 8th Asian Conference, ACIIDS 2016,
chapter Enhanced Guided Ejection Search for the Pickup
and Delivery Problem with Time Windows, pages 388–398.
Springer, Heidelberg, 2016.
-
J. Nalepa and M. Błocho.: Adaptive memetic algorithm for minimizing
distance in the vehicle routing problem with time windows. Soft
Computing, 20(6):2309–2327, 2016. (JCR, IF=1.630)
-
J. Nalepa and M. Błocho.: A parallel algorithm with
the search space partition for the pickup and delivery
with time windows. In Proc. 3PGCIC, pages
92-99, 2015.
-
M. Błocho and J. Nalepa.: A parallel algorithm for
minimizing the
fleet size in the pickup and delivery
problem with time windows. In Proc. EuroMPI, pages
15:1-15:2, New York, USA, 2015. ACM.
-
M. Błocho and J. Nalepa.: Impact of parallel memetic algorithm parameters on
its efficacy. In S. Kozielski, D. Mrozek, P. Kasprowski, B. Małysiak-Mrozek, and
D. Kostrzewa, editors, Beyond Databases, Architectures and Structures, volume 521
of Communications in Computer and Information Science, pages 299–308. Springer
International Publishing, 2015.
-
J. Nalepa and M. Błocho.: Co-operation in the parallel memetic algorithm. International
Journal of Parallel Programming, 43(5):812–839, 2015. (JCR, IF=0.680)
-
M. Kawulok and J. Nalepa.: Dynamically adaptive genetic algorithm to select
training data for SVMs. In A. L. Bazzan and K. Pichara, editors, Advances in
Artificial Intelligence – IBERAMIA 2014, Lecture Notes in Computer Science,
pages 242–254. Springer International Publishing, 2014.
Related webpages: