Two-level particle swarm optimization for the multi-modal team orienteering problem with time windows

• Published in: Applied soft computing 2017-12, Vol.61, p.1022-1040
• Main Authors: Yu, Vincent F., Jewpanya, Parida, Ting, Ching-Jung, Redi, A.A.N. Perwira
• Format: Article
• Language: English
• Subjects: Multiple transportation modes; Particle swarm optimization; Team orienteering problem; Time window; Tourist trip design problem
• ISSN: 1568-4946; 1872-9681
• DOI: 10.1016/j.asoc.2017.09.004

[Display omitted] •We study the multi-modal team orienteering problem with time windows (MM-TOPTW).•We propose a two-level particle swarm optimization with multiple social learning terms (2L-GLNPSO) for solving MM-TOPTW.•2L-GLNPSO incorporates a local search procedure to improve the performance on solving MM-TOPTW.•Using the local search procedure in 2L-GLNPSO is promising for solving MM-TOPTW. This study presents a new variant of the team orienteering problem with time windows (TOPTW), called the multi-modal team orienteering problem with time windows (MM-TOPTW). The problem is motivated by the development of a tourist trip design application when there are several transportation modes available for tourists to choose during their trip. We develop a mixed integer programming model for MM-TOPTW based on the standard TOPTW model with additional considerations of transportation mode choices, including transportation cost and transportation time. Because MM-TOPTW is NP-hard, we design a two-level particle swarm optimization with multiple social learning terms (2L-GLNPSO) to solve the problem. To demonstrate the applicability and effectiveness of the proposed model and algorithm, we employ the proposed 2L-GLNPSO to solve 56 MM-TOPTW instances that are generated based on VRPTW benchmark instances. The computational results demonstrate that the proposed 2L-GLNPSO can obtain optimal solutions to small and medium-scale instances. For large-scale instances, 2L-GLNPSO is capable of producing high-quality solutions. Moreover, we test the proposed algorithm on standard TOPTW benchmark instances and obtains competitive results with the state-of-art algorithms.