A Weighted and Epsilon-Constraint Biased-Randomized Algorithm for the Biobjective TOP with Prioritized Nodes

Abstract

This paper addresses a multiobjective version of the Team Orienteering Problem (TOP). The TOP focuses on selecting a subset of customers for maximum rewards while considering time and fleet size constraints. This study extends the TOP by considering two objectives: maximizing total rewards from customer visits and maximizing visits to prioritized nodes. The MultiObjective TOP (MO-TOP) is formulated mathematically to concurrently tackle these objectives. A multistart biased-randomized algorithm is proposed to solve MO-TOP, integrating exploration and exploitation techniques. The algorithm employs a constructive heuristic defining biefficiency to select edges for routing plans. Through iterative exploration from various starting points, the algorithm converges to high-quality solutions. The Pareto frontier for the MO-TOP is generated using the weighted method, epsilon-constraint method, and Epsilon-Modified Method. Computational experiments validate the proposed approach’s effectiveness, illustrating its ability to generate diverse and high-quality solutions on the Pareto frontier. The algorithms demonstrate the ability to optimize rewards and prioritize node visits, offering valuable insights for real-world decision making in team orienteering applications.

Keywords

• team orienteering problem
• heuristics
• biased-randomized algorithms
• multiobjective optimization
• Pareto frontier