Energy-constrained orienteering problem for green tourist trip design: Mathematical formulation and heuristic solution approaches

作     者：Karabas, Tolga Tural, Mustafa Kemal 

作者机构：Middle East Tech Univ Dept Ind Engn Ankara Turkiye 

出 版 物：《COMPUTERS & INDUSTRIAL ENGINEERING》 (Comput Ind Eng)

年 卷 期：2025年第200卷

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Scientific and Techno-logical Research Council of Turkiye (TUBIdot TAK) [2211-A] 

主　　题：Conic programming Green logistics Iterated local search Orienteering problem Speed optimization Tourist trip planning 

摘      要：Planning a touristic itinerary is a challenging task that requires personalized tour generation for tourists interested in visiting available points of interest (POIs). The negative externalities of using vehicles (e.g., emissions) can be reduced by considering such aspects in itinerary planning. To address this need, we propose the Energy-Constrained Tourist Trip Design Problem to plan environmentally friendly touristic itineraries. We model this problem as an Energy-Constrained Orienteering Problem (ECOP), where we consider continuous vehicle speed, speed-dependent travel time, and fuel consumption -accordingly emissions- which have not been considered in the scope of the OP before. First, the ECOP is formulated as a mixed-integer second-order cone programming (MISOCP) model which is able to solve only small-size instances to optimality within a reasonable time. Second, for large-size instances, we develop two heuristic methods, namely Greedy Insertion (GI) and Iterated Local Search (ILS) algorithms. In the latter, several improvement heuristics are coupled with an SOCP-based speed optimization procedure. Based on our computational experiments, the GI heuristic is the fastest among the proposed methods, while generally yielding suboptimal solutions compared to the ILS algorithm, but for larger instances, these solutions are better than the ones obtained via the exact method. The ILS algorithm outperforms the exact method by reaching good-quality solutions in a relatively short computing time. The ECOP has prospective applications on selective routing problems involving other transportation modes (e.g., cruise, aerial) and has a significant potential on reducing transportation-related GHG emissions.