Benchmark Problems for

H. Kim, B. Kim, and D.Noh ¡°The Multi-profit Orienteering Problem,¡± Computers and Industrial Engineering, 2020. https://doi.org/10.1016/j.cie.2020.106808.

1.       Introduction

The orienteering problem (OP) has recently drawn the attention of many researchers. It is also known as the selective traveling salesman problem (STSP), in which a vehicle maximises the profits collected from customers within some threshold (Gendreau et al., 1998; Laporte and Martello, 1990). In this study, we introduce the multi-profit orienteering problem (MPOP), which is another variant of the OP.

In the MPOP, every customer vertex has multiple profits, and the profit is determined when the vehicle visits a customer vertex. We assume that there are multiple pre-defined time slots for each vertex and that the profits are assigned to these time slots. Hence, the vertices to visit, the visiting times of the chosen vertices, and the routing order of these vertices must be determined to maximise the collected profits of the MPOP.

The MPOP is motivated by the concert promotion problem. A manager who wants to advertise a performer¡¯s concert has to determine the schedule for visiting some sites and promote the concert to people near that site. Because the moving population of a given region varies during the day, the promotion efficiency depends on the visiting time. Election campaigns can be an application area of the MPOP. The times and resources for campaigning are usually limited; thus, a campaign manager has to delicately determine the visiting priorities of the candidate regions. It is very important to plan campaign routes considering the floating population.

This paper presents a mathematical model for the problem. For a solution procedure, a hybrid heuristic algorithm consisting of a vertex sequence setting algorithm and an optimal visiting-time setting algorithm for a given sequence. A simulated annealing (SA) algorithm is used for the first part, and a visiting-time optimisation algorithm (VTOA) is used for the second part. Computational results on 98 benchmark problem instances show the effectiveness of the proposed solution.

 

2.       Benchmark Problems

To the best of our knowledge, no available benchmark data for MPOP exist. Thus, 98 benchmark instances were developed based on OP benchmark instances and VRP benchmark instances. Table 1 shows the summary of data sets.

To generate benchmark instances, we used the well-known benchmark data of the OP. The data were generated by Chao et al. (1996b) and Tsiligirides (1984) and can be downloaded from http://www.mech.kuleuven.be/en/cib/op. Chao et al. (1996b) provided two sets of data. The first set (Set 64) is composed of 14 benchmark instances with different time limits Tmax, each of which has 64 vertices including starting and ending vertices. The second set (Set 66) consists of 26 instances with 66 vertices. Tsiligirides (1984) created three datasets with 18, 11, and 20 benchmark instances (Tsiligirides 1, Tsiligirides 2, and Tsiligirides 3). The numbers of vertices in these datasets are 32, 21, and 33, respectively. We converted these datasets into MPOP data. In addition, to generate more large-sized instances, we used Solomon¡¯s VRP instances C101, R101, and RC101, each of which has 101 vertices, including depot vertex. These VRP benchmark data can be downloaded from http://web.cba.neu.edu/~msolomon/problems.htm. By converting the demands into profit, the VRP benchmark instances can be converted into OP instances. 

To convert OP data into MPOP data, Qi (the number of time slots for vertex i) should be determined. We set Qi to 3 for all i because a day is naturally divided by morning, afternoon, and evening. For the profit value, we first take the profit value S of a vertex from an OP instance and generate three profits [0.7S, S, 1.3S]. These profits are randomly allocated to the time slots of the same vertex in the MPOP instance. Thus, many combinations of profits such as {Pi1 = S, Pi2 = 0.7S, Pi3 = 1.3S}, {Pi1 = S, Pi2 = 1.3S, Pi3 = 0.7S}, {Pi1 = 0.7S, Pi2 = 1.3S, Pi3 = S}, {Pi1 = 1.3S, Pi2 = 0.7S, Pi3 = S} are possible. The same procedure for all of the vertices in each instance is performed. 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.

 

Table 1. Benchmark data summary

Name

# of
Vertices

# of
Instances

T1

32

18

T2

21

11

T3

33

20

S64

64

14

S66

66

26

VRP

100

9

 

The 98 benchmark data sets can be downloaded by click here.

Required data can be calculated or retrieved as follows:

ü  Travel time from vertex i to vertex j (tij) = Euclidean distance between the coordinates of the vertices, rounded to the first decimal

ü        Each vertex has 3 time slots :  where each boundary time is rounded to the first decimal (in OptionFile)

 

The algorithm exe and CPLEX code files can be downloaded below:

ü  MPOP_CODE files

 

The solution files obtained from the algorithm ¡°DP + SA + ng-route + update incumbent¡± can be downloaded      
  below:

ü  Solution_files_from_the_MPOP_Exact_algorithm_DP + SA + ng-route + update incumbent

ü  ¡°Hybrid Dynamic Programming with Bounding Algorithm for the Multi-profit Orienteering Problem,¡± working paper.

 

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. (1996b). 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]      Gendreau, M., Laporte, G., & Semet, F. (1998). A tabu search heuristic for the undirected selective traveling salesman problem. European Journal of Operational Research, 106, 539-545. https://doi.org/10.1016/S0377-2217(97)00289-0.

[3]      Laporte, G., & Martello, S. (1990). The selective traveling salesman problem. Discrete Applied Mathematics, 26, 193-207. https://doi.org/10.1016/0166-218X(90)90100-Q.

[4]      Tsiligirides, T. (1984). Heuristic Methods Applied to Orienteering. Journal of the Operational Research Society, 35, 797-809. https://doi.org/0.2307/2582629.