TY - GEN
T1 - Multiobjective orienteering problem with time windows
T2 - Conference on Technologies and Applications of Artificial Intelligence, TAAI 2015
AU - Chen, Yu Han
AU - Sun, Wei Ju
AU - Chiang, Tsung Che
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2016/2/12
Y1 - 2016/2/12
N2 - The orienteering problem with time windows (OPTW) deals with the problem about selecting a set of points of interest and then determining the route to visit them under the time window constraints. In the classical OPTW each candidate point of interest is associated with a profit value, and the objective is to maximize the total profit. In this study, we extend the problem and allow each point to have multiple profit values, which could reflect different aspects of consideration. We propose an ant colony optimization (ACO) algorithm to solve the multiobjective OPTW (MOOPTW) with the goal of finding the set of Pareto optimal solutions. To our best knowledge, this is the first study to address the MOOPTW with comprehensive numerical experiments. Our algorithm is a decomposition-based one, which decomposes the multiobjective optimization problem into single-objective sub-problems. Pheromone matrices are associated with sub-problems. We also incorporate path-relinking and propose several strategies. We apply our algorithm to solve 76 public benchmark instances and offer the list of non-dominated solutions to facilitate performance comparison in future researches.
AB - The orienteering problem with time windows (OPTW) deals with the problem about selecting a set of points of interest and then determining the route to visit them under the time window constraints. In the classical OPTW each candidate point of interest is associated with a profit value, and the objective is to maximize the total profit. In this study, we extend the problem and allow each point to have multiple profit values, which could reflect different aspects of consideration. We propose an ant colony optimization (ACO) algorithm to solve the multiobjective OPTW (MOOPTW) with the goal of finding the set of Pareto optimal solutions. To our best knowledge, this is the first study to address the MOOPTW with comprehensive numerical experiments. Our algorithm is a decomposition-based one, which decomposes the multiobjective optimization problem into single-objective sub-problems. Pheromone matrices are associated with sub-problems. We also incorporate path-relinking and propose several strategies. We apply our algorithm to solve 76 public benchmark instances and offer the list of non-dominated solutions to facilitate performance comparison in future researches.
KW - Pareto optimal
KW - ant colony optimization
KW - multiobjective
KW - orienteering problem
KW - time window
UR - http://www.scopus.com/inward/record.url?scp=84964308717&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84964308717&partnerID=8YFLogxK
U2 - 10.1109/TAAI.2015.7407130
DO - 10.1109/TAAI.2015.7407130
M3 - Conference contribution
AN - SCOPUS:84964308717
T3 - TAAI 2015 - 2015 Conference on Technologies and Applications of Artificial Intelligence
SP - 128
EP - 135
BT - TAAI 2015 - 2015 Conference on Technologies and Applications of Artificial Intelligence
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 20 November 2015 through 22 November 2015
ER -