A Learning-Enhanced Metaheuristic Algorithm for Multi-Zone Orienteering Problem with Time Windows

Inspired by real-world logistics scenarios, in this paper, we introduce a new variant of the Orienteering Problem known as the Multi-zone Orienteering Problem with Time Windows (MzOPTW). In the MzOPTW, customers are situated in distinct zones, each with multiple entrances and exits. Each customer has specific time window requirements; access to them will generate certain profits. This problem is to simultaneously determine which zones and customers to visit, select the zonal entrances and exits, and generate the routes for visiting each zone and its customers, all while maximizing total profits within a limited time frame. To tackle the MzOPTW, this paper develops an integer programming model. There are significant computational challenges in the strong interdependencies among zone selection, customer selection within zones, entrance and exit selection for each zone, the sequence of visits to zones and customers, and arrival and stay times. To address these challenges, this paper proposes a learning-enhanced metaheuristic algorithm called the Hybrid Ant Colony Optimization (HACO) algorithm, which incorporates Pointer Network learning. The HACO algorithm combines the global search capabilities of a population-based algorithm with the parallel decision-making abilities of the Pointer Network learning model. Additionally, a method to optimize zonal stay time limits is proposed to further enhance the solution. Experimental results demonstrate that the HACO algorithm outperforms comparative algorithms, achieving better solutions in 73% of the instances within the same time frame. Furthermore, the proposed optimization method for zonal stay time limits results in improvements in 78% of instances.