Applying Particle Swarm Optimization for Solving Team Orienteering Problem with Time Windows
Keywords:Particle Swarm Optimization, Team Orienteering Problem, Time Windows, Metaheuristics, Solution Methodology.
AbstractThe 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.
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.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).