Publication Type

Journal Article

Version

acceptedVersion

Publication Date

7-2022

Abstract

This paper addresses the time dependent orienteering problem with time windows and service time dependent profits (TDOPTW-STP). In the TDOPTW-STP, each vertex is assigned a minimum and a maximum service time and the profit collected at each vertex increases linearly with the service time. The goal is to maximize the total collected profit by determining a subset of vertices to be visited and assigning appropriate service time to each vertex, considering a given time budget and time windows. Moreover, travel times are dependent of the departure times. To solve this problem, a mixed integer linear model is formulated and a metaheuristic algorithm based on variable neighborhood search (VNS) is developed. This algorithm uses three specifically designed neighborhood structures able to deal with the variable service times and profits of vertices. Extensive computational experiments are conducted on test instances adapted from the TDOPTW benchmarks, to validate the performance of our solution approach. Furthermore, a real instance for the city of Shiraz (Iran) is generated. Experimental results demonstrate the suitability of the TDOPTW-STP in practice, and demonstrate that the proposed algorithm is able to obtain high-quality solutions in real-time. Sensitivity analyses clearly show the significant impact of the service time dependent profits on the route plan, especially in the presence of travel time dependency and time windows.

Keywords

Real data set, Service time dependent profits, Time dependent orienteering problem, Tourist trip planning, Variable neighborhood search

Discipline

Computer Sciences | Operations Research, Systems Engineering and Industrial Engineering | Transportation

Research Areas

Intelligent Systems and Optimization

Publication

Computers and Operations Research

Volume

143

First Page

1

Last Page

18

ISSN

0305-0548

Identifier

10.1016/j.cor.2022.105794

Publisher

Elsevier

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1016/j.cor.2022.105794

Download

Share

COinS