Benchmark Problems for

H. Kim, and B.-I. Kim “A branch-and-price approach for the multi-profit team orienteering problem,” working paper, 2021

1. Introduction

The orienteering problem (OP), which is a selective version of the traveling salesman problem(TSP), has recently attracted the attention of many researchers. The purpose of the OP is to maximize profits collected from customers in a limited time period, during which all customers cannot be visited. Many researchers study many variants of the OP. Among them, Kim et al. (2020) introduced the multi-profit orienteering problem (MPOP) in which every customer vertex v_i has D_i time slots and the profit P_id is allocated to dth time slot of vertex v_i. When the vehicle visits a vertex at the boundary of two time slots, it can collect the higher profit between the two time slots. This study introduces the multi-profit team orienteering problem (MPTOP), an extended variant of the MPOP, utilizing more than one vehicle. The goal is to determine routes of multiple vehicles and maximize the total profit collected from these vehicles within a specific travel time limit.

This study presents a mathematical model for the problem. For solution approaches, branch-and-price (BP)-based algorithms are proposed. Computational results on 147 benchmark problem instances show the effectiveness of the proposed algorithms.

2. Benchmark Problems

To the best of our knowledge, no available benchmark data for the MPTOP exist. Thus, 147 benchmark instances were generated based on TOP benchmark instances. The TOP benchmark instances were generated by Chao et al. (1996) and can be downloaded from https://www.mech.kuleuven.be/en/cib/op.

There are three sets of TOP benchmark instances. These three sets have 33, 54, and 60 benchmark instances. The first set (Set 21) is composed of 33 benchmark instances with different travel time limits T_max from 3.8 to 22.5-time units, each of which has 21 vertices, including starting and ending vertices. The second set (Set 32) consists of 54 instances with 32 vertices. In this set, the travel time limits T_max has a value between 1.2 and 42.5-time units. The third set (Set 33) has 60 instances with 33 vertices. The travel time limits T_max has a value within the range of 3.8 and 55-time units. The number of vehicles in all benchmark sets is one of 2, 3, and 4.

We converted these TOP datasets into the MPTOP data. To convert the TOP data into the MPTOP data, Di (the number of time slots for vertex vi) should be determined. As in making the MPOP benchmark data, we set Di to 3 for all vi because a day is naturally divided by morning, afternoon, and evening. In three time slots, each profit value s is generated as follows: First, the profit value S of a vertex from a TOP instance is obtained, and three profits [0.7S, S, 1.3S] are generated. These profits are randomly allocated to the time slots of each vertex in the MPTOP instance. For the starting and ending vertices, zero profits are allocated. The travel distances are calculated as the Euclidean distance and rounded to the first decimal.

The 147 benchmark instances can be downloaded by click here.

There are two input files for each case.

ü “p#_MPTOPData.csv” - a set of nodes (vertices) s given with the following characteristics: Node, NodeIndex, X coordinate, Y coordinate, NodeType (0:start 1:end 2:intermediate), Timeslot 1 Score, Timeslot 2 Score, and Timeslot 3 Score.

Ø NodeType è 0: starting vertex, 1: ending vertex, 2: customer vertex

ü “p#_OptionFile.csv” - a set of parameters used in the experiments: Time Limit, Num of Route, Velocity, Morning, Afternoon, and Evening.

Ø Morning è Timeslot 1

Ø Afternoon è Timeslot 2

Ø Evening è Timeslot 3

Required data can be calculated or retrieved as follows:

ü Travel time from vertex v_i to vertex v_j (t_ij) = Euclidean distance between the coordinates of the vertices, rounded to the first decimal

ü Each vertex has 3 time slots: [0, T_max/3], [T_max/3, 2*T_max/3], [2*T_max/3, T_max] where each boundary time is rounded to the first decimal (in OptionFile)

If you have any questions, please contact us via the email below.

ü e-mail: dnwjd2355@postech.ac.kr

3. References

[1] Chao, I., Golden, B. L., & Wasil, E. A. (1996). A fast and effective heuristic for the orienteering problem. European Journal of Operational Research, 88, 475-489. https://doi.org/10.1016/0377-2217(95)00035-6.

[2] Kim, H., Kim, B.-I., & Noh, D. (2020). The multi-profit orienteering problem. Computers & Industrial Engineering, 106808. https://doi:10.1016/j.cie.2020.106808.