Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

4-2019

Abstract

This paper focuses on a recent variant of the Orienteering Problem (OP), namely the Capacitated Team OP (CTOP) which arises in the logistics industry. In this problem, each node is associated with a demand that needs to be satisfied and a score that need to be collected. Given a set of homogeneous fleet of vehicles, the objective is to find a path for each vehicle in order to maximize the total collected score, without violating the capacity and time budget. We propose an Iterated Local Search (ILS) algorithm for solving the CTOP. Two strategies, either accepting a new solution as long as it improves the quality of the solutions or accepting a new solution as long as there is no constraint violation, are implemented. For solving difficult instances, we simplify the move operator of local search in order to reduce the computational time. Instead of exploring all possible nodes in all paths to be moved, we only focus on nodes in the path with the least remaining amount of time. Computational experiments on benchmark instances illustrate that the algorithm can generate solutions within 1% and 4% from the current best known solution for small and large instances, respectively.

Keywords

Orienteering Problem, Iterated Local Search, Capacitated Team Orienteering Problem

Discipline

Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering | Theory and Algorithms

Research Areas

Intelligent Systems and Optimization

Publication

Proceedings of the 9th International Conference on Industrial Engineering and Operations ManagementBangkok, Thailand, March 5-7, 2019

First Page

1630

Last Page

1638

ISSN

2169-8767

ISBN

9781532359484

Publisher

IEOM Society

City or Country

Bangkok

Copyright Owner and License

Publisher

Additional URL

http://www.ieomsociety.org/ieom2019/papers/397.pdf

Download

Share

COinS