Applying Particle Swarm Optimization for Solving Team Orienteering Problem with Time Windows
:
https://doi.org/10.9744/jti.16.1.9-16
Keywords:
Particle Swarm Optimization, Team Orienteering Problem, Time Windows, Metaheuristics, Solution Methodology.Abstract
The Team Orienteering Problem With Time Windows (TOPTW) is a transportation problem case that have a set of vertices with a score, service time, and the time windows, start and final at a depot location. A number of paths are constructed to maximize the total collected score by the vertices which is visited. Each vertice can be visited only once and the visit can only start during the time window of vertices. This paper proposes a Particle Swarm Optimization algorithm for solving the TOPTW, by defining a specific particle for representing the solution of TOPTW within the PSO algorithm and two alternatives, called PSO_TOPTW1 and PSO_TOPTW2, for translating the particle position to form the routes of the path. The performance of the proposed PSO algorithm is evaluated through some benchmark data problem available in the literature. The computational results show that the proposed PSO is able to produce sufficiently good TOPTW solutions that are comparable with corresponding solutions from other existing methods for solving the TOPTW.References
Ai, T. J., and Kachitvichyanukul, V., A Particle Swarm Optimisation for Vehicle Routing Problem with Time Windows, International Journal of Operational Research, 6(4), 2009, pp. 519-537.
Ai, T. J., and Kachitvichyanukul, V., A Particle Swarm Optimization for the Vehicle Routing Problem with Simultaneous Pickup and Delivery, Computers & Operations Research, 36(5), 2009, pp. 1693-1702.
Ai, T. J., and Kachitvichyanukul, V., Particle Swarm Optimization and Two Solution Representations for Solving the Capacitated Vehicle Routing Problem, Computers & Industrial Engineering, 56(1), 2009, pp. 380-387.
Ai, T. J., Pribadi, J.S., and Ariyono, V., Solving the Team Orienteering Problem with Particle Swarm Optimization. Industrial Engineering & Management Systems, 12(3), September 2013, pp.198-206.
Clerc, M., Particle Swarm Optimization, London: ISTE, 2006.
Cordeau, J. F., Gendreau, M., and Laporte, G., A Tabu Search Heuristic for Periodic and Multi-Depot Vehicle Routing Problems, Networks, 30(2), 1997, pp. 105-119.
Dang, D. C., Guibadj, R. N., and Moukrim, A, An Effective PSO-Inspired Algorithm for the Team Orienteering Problem, European Journal of Operational Research, 229(2), 2013, pp. 332-344.
Goksal, F. P., Karaoglan, I., and Altiparmak, F., A Hybrid Discrete Particle Swarm Optimization for Vehicle Routing Problem with Simultaneous Pickup and Delivery, Computers & Industrial Engineering, 65(1), 2013, pp. 39-53.
Golden, B. L., Levy, L., and Vohra, R., The Orienteering Problem, Naval Research Logistics, 34(3), 1987, pp. 307-318.
Govindan, K. , Jafarian, A. , Khodaverdi, R., and Devika, K., Two-Echelon Multiple-Vehicle Location–Routing Problem with Time Windows for Optimization of Sustainable Supply Chain Network of Perishable Food, International Journal of Production Economics, 152, 2013,pp.9-28.
Kantor, M. G., and Rosenwein, M. B., The Orienteering Problem with Time Windows, Journal of the Operational Research Society, 43(6), 1992, pp. 629-635.
Kennedy, J. and Eberhart, R. C., Swarm Intelligence, San Francisco: Morgan Kaufmann Publishers, 2001.
Kuo, R. J., Zulvia, F. E., and Suryadi, K., Hybrid Particle Swarm Optimization with Genetic Algorithm for Solving Capacitated Vehicle Routing Problem with Fuzzy Demand – A Case Study on Garbage Collection System. Applied Mathematics and Computation, 219(5), 2012, pp. 2574-2588.
Labadie, N., Melechovský, J., and Calvo, R. W., Hybridized Evolutionary Local Search Algorithm for the Team Orienteering Problem with Time Windows, Journal of Heuristics, 17(6), 2011, pp. 729-753.
Labadie, N., Mansini, R., Melechovský, J., and Wolfler Calvo, R., The Team Orienteering Problem with Time Windows: An lp-Based Granular Variable Neighborhood Search, European Journal of Operational Research, 220(1), 2012, pp. 15-27.
Lin, S. W., and Yu, V. F., A Simulated Annealing Heuristic for the Team Orienteering Problem with Time Windows, European Journal of Operational Research, 217(1), 2012, pp. 94-107.
Montemanni, R., and Gambardella, L. M., An Ant Colony System for Team Orienteering Problems with Time Windows, Foundations of Computing and Decision Sciences, 34, 2009, pp. 287-306.
Nguyen, S., Ai, T. J., and Kachitvichyanukul, V., Object Library for Evolutionary Techniques ETLib: User’s Guide, High Performance Computing Group, Asian Institute of Technology, Thailand, 2010.
Righini, G., and Salani, M., Decremental State Space Relaxation Strategies and Initialization Heuristics for Solving the Orienteering Problem with Time Windows with Dynamic Programming. Computers & Operations Research, 36(4), 2009, pp. 1191-1203.
Solomon, M.M., Algorithms for the Vehicle Routing and Scheduling Problems with Window Constraints, Operations Research, 35(2), 1987, pp. 254-265.
Tlili, T., Faiz, S., and Krichen, S., A Hybrid Metaheuristic for the Distance-Constrained Capacitated Vehicle Routing Problem, Procedia - Social and Behavioral Sciences, 109, 2014, pp. 779-783.
Vansteenwegen, P., Souffriau, W., van den Berghe, G., and van Oudheusden, D., Iterated Local Search for the Team Orienteering Problem with Time Windows, Computers & Operations Research, 36(12), 2009, pp. 3281-3290.
Vansteenwegen, P., Souffriau, W., Berghe, G. V., and van Oudheusden, D. V., The Orienteering Problem: A Survey, European Journal of Operation Research, 209(1), 2011, pp. 1-10.
Xu, J., Yan, F., and Li, S., Vehicle Routing Optimization with Soft Time Windows in a Fuzzy Random Environment, Transportation Research Part E: Logistics and Transportation Review, 47(6), 2011, pp. 1075-1091.
Downloads
Published
How to Cite
Issue
Section
License
Articles published in the Jurnal Teknik Industri: Jurnal Keilmuan dan Aplikasi Teknik Industri will be Open-Access articles distributed under the terms and conditions of the Creative Commons Attribution License (CC BY).
This work is licensed under a Creative Commons Attribution License (CC BY).
