Journal of the Operational Research Society (2017)

ª

2017 The Operational Research Society. All rights reserved. 0160-5682/17 www.palgrave.com/journals

The Traveling Backpacker Problem: a computational comparison of two formulations Ka´tia Y. Nakamura1, Leandro C. Coelho2,3, Jacques Renaud2,3 and Maria´ C. V. Nascimento1* 1

Institute of Science and Technology, Federal University of Sa˜o Paulo, Sa˜o Jose´ dos Campos, Sa˜o Paulo, Brazil; Faculte´ des sciences de l’administration, Universite´ Laval, Que´bec City, Canada; and 3 Centre interuniversitaire de recherche sur les re´seaux d’entreprises, la logistique et le transport (CIRRELT), Que´bec City, Canada 2

The rise of low-cost airlines has influenced the tourism industry, particularly in trips known as backpacking. This form of traveling is mostly adopted by people on a tight budget, intending to visit a large number of touristic attractions. In the Traveling Backpacker Problem (TBP), the objective is to find the best sequence of visits, so as to minimize the total travel cost. This problem was first modeled as a routing problem. Nevertheless, for smallsized instances, an exact solver could not find any feasible solutions. In this paper, we propose a new formulation for the TBP, which is based on a network flow representation of the problem. We tested both models using a state-of-the-art MIP solver on instances generated from real data obtained from low-cost airlines. Computational experiments indicate that the network flow-based formulation outperforms the routing-based formulation and can yield high-quality solutions for instances of realistic size. Journal of the Operational Research Society (2017). doi:10.1057/s41274-017-0205-8; Keywords: low-cost airlines; backpacking; exact method; traveling salesman problem; graph theory

1. Introduction Air transportation has drawn the attention of many travelers around the world. The amount of users of this mode of transport has steadily increased over the years, and it is expected that the number of air travelers reaches a peak of 3.91 billions per year in 2017 (IATA, 2014). According to the United Nations World Tourism Organization (U.N.W.T.O.), most travels involve air transportation and the majority is intended for leisure (U.N.W.T.O., 2013). Consequently, planning routes in consonance with the preferences of travelers arises as motivation for a number of research topics. In particular, in the tourism industry, backpacking is a way of travel common for tourists with low budget. This term, coined in the 1990s (Pearce, 1990), describes the activities engaged by some tourists who aim at visiting several cities in a multiple destination trip and can be flexible in terms of timing and accommodation (Zhou et al, 2014). Backpacking is a recognized trend among youngsters, notably while visiting Europe (Majstorovic et al, 2013). The costs of transportation is considered one of the most important economical factors for backpackers. As these travelers look for the lowest transportation budget, Low-Cost Airlines (LCA) are a good alternative of transport for long *Correspondence: Maria´ C. V. Nascimento, Institute of Science and Technology, Federal University of Sa˜o Paulo, Sa˜o Jose´ dos Campos, Sa˜o Paulo, Brazil. E-mail: [email protected]

distances (Zhou et al, 2014). LCAs are companies that eliminate conventional services to provide cheap fares. Zhou et al (2014) design a backpacking service considering the LCAs to detect the best fare between an origin and a destination, whereas most backpackers intend to visit several destinations. Therefore, the visiting order among the places is not relevant, as long as the cost can be reduced and all target destinations are visited. Moreover, due to the peculiarities of tourist attractions, the periods of stay may vary among the different places of interest, and the timing of visits becomes of main interest, since air ticket prices change over time. Bearing this motivation in mind, we formally introduce two formulations for the Traveling Backpacker Problem (TBP). The TBP consists in identifying a route for a round multidestination trip in which it is possible to provide the minimum stay length at each destination. The objective is to minimize the trip cost considering the evolution of the prices of the air tickets. The first formulation is based on a generalization of the well-known Traveling Salesman Problem (TSP) (Applegate et al, 2007). The second is based on a k-partite graph. An industry partner has provided us with a large database of available airline tickets fares. Thus, we are able to evaluate the two formulations for the TBP in a real-life scenario, simulating trips involving six to twenty-two destinations. The remainder of this paper is organized as follows. In Section 2, we present motivation and material of some works related to this study. In Section 3 we propose two mathematical formulations for the problem. In Section 4 we present the

Journal of the Operational Research Society

results of our extensive computational experiments with the two formulations. The conclusions follow in Section 5.

In the TSP with time-dependent costs, the pairwise cost matrix that links two cities contains another layer to indicate the duration of the trip, being dependent on the time.

2. Related work Air tickets are mostly bought through the airline sites, and the variation in their prices is a result of the algorithms from these companies considering hidden variables, such as specific periods of the year or number of available seats in the aircraft (Etzioni et al, 2003). A whole branch of literature is dedicated to help companies to obtain the highest value for a ticket considering information from demand, supply, seat categories, competing companies and different transportation modes, among others (Anjos et al, 2004; Bilotkach et al, 2015). From the user perspective, being able to predict how the prices of airline tickets change in such a way that it is possible to minimize the cost of purchase remains a challenge (Etzioni et al, 2003). These authors use a multi-strategy data mining algorithm to estimate changes in values. Despite the difficulty in predicting the behavior of prices of air tickets, through a bank with the variation history of prices, the price data mining (price mining) proposed by the authors was able to efficiently predict the forthcoming fares. In Hung et al (2013), the authors underline the importance of low-cost airlines for the backpackers. In line with this aspect, the authors developed a backpacking search engine, focused on low-cost backpacking, able to find the lowest cost airfare as long as both points of origin and destination are provided. This search engine is convenient because it also considers flights with stopovers and layovers, in case the sum of the air ticket costs is minimal. To solve this problem, the authors used the well-known Dijkstra algorithm (Dijkstra, 1959), that from a graph and a starting vertex, finds the lowest cost route to reach other graph vertices. Notwithstanding, this service is restricted to choosing air tickets between two destinations at a time, generating multiple possibilities for routes to reach the final destination, through the connections between destinations. The TBP can be related to some variants of the TSP. Many extensions of the TSP consider time-dependent parameters. Recently, Tas¸ et al (2016) have proposed the case with timedependent service times. In this variant, the duration of the service (or visit) of a customer changes, depending on the arrival time. In the TBP, this duration is flexible and is directly linked to the total costs of the problem. Other variants of the TSP include those with time-dependent profits (or costs) (Lucena, 1990; Gouveia and Voß, 1995; Godinho et al, 2014). Since the timing of the visit at a destination has a direct influence on the costs and availability of inbound and outbound trips, the TBP has some structural similarities with both of these TSP variants. In the TSP with profits, the objective is to accumulate the highest profit by visiting selected destinations, each with a specific profit. In its timedependent variant, the profit depends on the timing of the visit.

3. Mathematical formulations for the Traveling Backpacker Problem In this section we present two mathematical formulations for the problem. The first one is based on flow variables similar to a traveling salesman problem. In Section 3.2 we propose a tighter graph-based formulation.

3.1. Flow-based formulation for the Traveling Backpacker Problem The TBP is defined over a set of nodes N ¼ f1; . . .; ng, where node 1 is the index of the origin of the trip, and node n represents the final destination of the trip, coinciding with the origin. For each node i, the traveler wants to stay ei time periods in that destination. A day is divided into p time periods, and after spending ei periods at destination i, the traveler must leave it within the next s periods, called slack periods. A trip from i to j starting in period t costs ctij , and fijt represents the duration of the trip from i to j starting in period t. For ease of notation, let gtij ¼ fijt þ ej be the total time from the moment the traveler departs from i to j in period t until the time s/he will be ready to depart from j. The objective of the problem is to visit all nodes starting at node 1 and finishing the trip at node n, respecting the duration of stay for all destinations, such that the total cost is minimized. In order to formulate this problem, let xtij be a binary variable equal to one if and only if the passenger leaves node i at time t heading to node j. Additionally, let di be an integer variable representing the departure time from node i. In what follows, T ¼ f1; . . .; Tg is the set of time periods, with T representing the period of the latest flight in the database, and M is a large number. In the implementation of the following model, variables xtij and related constraints are generated only if a flight leaves i for j in period t. XXX flow-based min ctij xtij ð1Þ i2N j2N t2T

subject to: N XX

xtij ¼ 1;

i 2 N nfng

xtij ¼ 1;

j 2 N nf1g

t2T j¼2 j6¼i n1 XX t2T i¼1 i6¼j

ð2Þ

ð3Þ

Ka´tia Y. Nakamura et al—The Traveling Backpacker Problem

XX

txtij ¼ di ;

i2N

ð4Þ

j2N t2T

dj  di þ gtij  ð1  xtij ÞM;

i; j 2 N ;

t2T

ð5Þ

dj  di þ gtij þ s þ ð1  xtij ÞT;

i; j 2 N ;

t2T

ð6Þ

di  T  gi ;

i2N

ð7Þ

d1  s xtij 2 f0; 1g;

i; j 2 N ;

di 2 N;

ð8Þ t2T

i 2 N:

ð9Þ ð10Þ

The objective function (1) aims at finding the solution with the minimum total travel cost. Constraints (2) and (3) determine that one flight must depart from i and j, respectively. Constraints (4) link and synchronize variables x and d. Constraints (5) ensure that the departure time from each destination must be larger than or equal to the next period of the arrival time from its predecessor in the route, plus its duration of stay, while constraints (6) impose an upper bound on the latest departure period. Constraints (7) limit the departure time from i to the maximum period that each one can reach in the timeline. Here, we set gi ¼ mint gtin which corresponds to the minimum time required for returning to the destination of the trip (n) from the actual node i. Thus, constraints (7) restrict the departure time from i. Constraint (8) forces d1 to be lesser than the imposed s slack periods for departing from the origin. Finally, constraints (9) and (10) establish the domain of variables xtij and di , which are, respectively, binaries and natural values.

3.2. Graph-based formulation for the Traveling Backpacker Problem We now propose a novel formulation for modeling the TBP. We illustrate in Figure 1 an example of a small instance and solution to depict our new graph-based formulation, in which each column represents one destination, and each row represents a time period in the timeline. For each destination, there exists a set of nodes representing the time horizon. The label of nodes are denoted by (t, n), where t is the period in the timeline and n is the index of the destination. For each destination, i.e., each column, there must be exactly one incoming and one outgoing arc selected in a solution. This representation limits to one the number of visits to each destination. The proposed graph is similar to that used in fleet assignment models, namely those employed in the assignment of aircraft to legs of flights (Hane et al, 1995; Sherali et al, 2006; Gabteni and Gro¨nkvist, 2009).

In Figure 1, an arc between two nodes indicates a feasible travel, i.e., there exists a flight leaving the origin node in period t going to the destination node. In this representation, the length of an arc includes the flight time and the visiting time at the destination, i.e., gtij . Note that there is no arc between nodes representing a same destination. If a destination (t, j) is selected, one should leave j before t þ s. However, it is also possible to have a node (t, j) with only incoming arcs which means that there is no flight leaving j in period t. Thus, the departure time must be delayed, and selected from within the interval t þ s. The opposite is also possible: a node (t, j) may only contain outgoing arcs which means that no flight arrives at j in period ðt  ej Þ. Finally, nodes with no incoming and no outgoing arcs are simply omitted (i.e., this means that it is impossible to arrive or to leave this destination in that particular period). In the example provided at Figure 1, we consider three destinations and a planning horizon of 29 periods. All possible trips are shown as dashed arcs, and a solution is highlighted in solid arcs. The node labeled (5, 1) represents destination 1, which is left in period 5. Observe that no flight leaves destination 1 in period 1 to other destinations, thus no arc exists from (1, 1) which is then removed from the problem. The selected arc leaving (5, 1) arrives at destination 3, six periods later, i.e., (11, 3), which means that the duration of the trip from i ¼ 1 to j ¼ 3 plus the duration of the stay in j, e3 ¼ 3, equals six periods. The passenger was then ready to leave destination 3 in period 12, but chooses to do so in period 14, heading to destination 2, which s/he is ready to leave at the beginning of period 21. Finally, in period 23 the passenger leaves destination 2 and arrives back at destination 1, ending the trip and providing a feasible solution for the problem. In order to model the problem under this logic, we make use 0

of binary variables xjtit equal to one if and only if the traveler leaves node i in period t and is ready to depart from j in period t0 , i.e., t0 equals t, plus the traveling time, plus the duration of the stay at j. Again, in the implementation of the following 0

model, only feasible variables xjtit and related constraints are generated. The problem can then be formulated as follows: XXX X 0 ctij xjtit graph-based min ð11Þ i2N t2T j2N t0 2T ;t0 [ t

subject to: X X X

0

xjtit ¼ 1;

i2N

ð12Þ

j2N

ð13Þ

t2T t0 2T ;t0  t j2N

X X X

0

xjtit ¼ 1;

t2T t0 2T ;t0  t i2N

X X i2N t2T ;t  t0

0 xjtit

¼

t0 þs X T X X k2N r¼t0 þ1 r 0 ¼r

0

xkr jr ;

j 2 N;

t0 2 T

ð14Þ

Journal of the Operational Research Society Destination 1

Destination 2

Destination 3

4. Computational experiments In this section we present the results of extensive computational experiments to compare the two formulations for the TBP. We have implemented the two formulations using IBM CPLEX version 12.7 in Java using six threads on machines equipped with an Intel i7-6700TM processor and 64 GB of RAM, with the Ubuntu 16.04.1 operating system. We imposed a time limit of 6 h per instance.

2, 1 3, 1 4, 1 5, 1 8, 1

8, 2

8, 3

9, 1

9, 3

10, 1

10, 2

11, 1

11, 2

11, 3

14, 1

14, 2

14, 3

15, 1

4.1. Instances generation

15, 3

16, 1

16, 2

17, 1

17, 2

17, 3

20, 1

20, 2

20, 3

21, 1

21, 3

22, 1

22, 2

23, 1

23, 2

23, 3

26, 1

26, 2

26, 3

27, 1

27, 2

27, 3

28, 1

28, 2

29, 1

29, 2

29, 3

Figure 1 An example of the graph containing nodes and trips for three destinations and 29 periods.

X XX

0

xjt1t ¼ 1

t2T ;t  s t0 2T j2N

X

X

X

t2T t0 2T ;t0  m i2N 0

xjtit 2 f0; 1g;

i; j 2 N ;

t2T;

ð15Þ

0

x1t it ¼ 1

ð16Þ

t0 2 T nf1; . . .; tg: ð17Þ

The objective function (11) minimizes the total cost of the selected trips. Constraints (12) and (13) limit, respectively, that destination i be the starting point to other destination only once, and destination j be the final point of a trip only once. Constraints (14) ensure that if the passenger is ready to leave destination j in period t0 , s/he must leave it within the next s periods, where s represents the number of slack periods. Constraint (15) ensures that for the first s periods in the timeline, an outgoing arc leaving the origin is selected. Constraint (16) ensures the trip back to the origin to take place after at least the sum of all periods of stay in all destinations, represented by period m, if we do not use any slack periods during the trip at all.

An industrial partner, Skypicker,1 provided us access to real data containing information about flights operated by LCAs from Europe. The database contains information from more than 7,000,000 flights from July 2014 to February 2015 operating in more than 300 airports. For each flight, we have the information of the origin and destination airports, the departure day and time, the flight duration, and its cost. From this large database, we created instances of different sizes as follows. Each generated instance is identified by two numbers: the number of destinations (n) and the slack time in days (s). We randomly selected the traveler starting date in the first week of the database, i.e., July 2014. For each destination we selected at random the duration of the stay in each destination, ei , within ½s þ 2; s þ 5. We then fixed the length of the planning horizon to the sum of all ei plus the maximum possible slack time at each destination. For each pair of destinations, we used all the direct flights covering the relevant time period. Note that corresponding flights can easily be taken into consideration by including possible intermediate stops between i and j and adjusting the cost and arrival time t0 at j accordingly. We have separated the instances in two sets. The first set includes medium-sized instances ranging from 6 to 12 destinations, with n ¼ f6; 8; 10; 12g. For each instance size, we have created five instances for each size of the slack period from the set s ¼ f1; 2; 3; 4g. The smallest instances, with n ¼ 6 and s ¼ 1, have more than 1500 flights, whereas the largest instances in the first set, with n ¼ 12 and s ¼ 4, contains up to 20,000 flights. Likewise, we have created a second set of larger and more challenging instances with n ¼ f14; 16; 18; 20; 22g and slack times s ¼ f1; 2; 3; 4g leading to instances having up to 100,000 flights. A total of 180 instances compose both sets. These are available for download with an explanation of their format from https://sites.google.com/site/ nascimentomcv/downloads/backpackerproblem.

4.2. Computational results We report in Tables 1 and 2 the results of the experiments for two sets of instances created, totaling 80 instances shown in 1

http://skypicker.com/.

Ka´tia Y. Nakamura et al—The Traveling Backpacker Problem

Table 1 Average solutions for the first set of instances for the flow-based formulation and the graph-based formulation Slack

Dest.

Flow-based 1h

1

Average 2

Average 3

Average 4

6 8 10 12 6 8 10 12 6 8 10 12 6 8 10 12

Average Total average

6h

Sol

Opt

Gap (%)

OptGap (%)

Sol

Opt

Gap (%)

OptGap (%)

5 5 5 1 4.00 5 5 5 5 5.00 5 5 5 0 3.75 5 5 5 1 4.00 4.19

5 5 5 0 3.75 5 5 1 0 2.75 5 5 0 0 2.50 5 5 1 0 2.75 2.94

0.00 0.00 0.00 0.29 0.07 0.00 0.00 0.24 0.54 0.20 0.00 0.00 0.23 – 0.08 0.00 0.00 0.25 0.59 0.21 0.14

0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.10 0.33 0.11 0.00 0.00 0.06 – 0.02 0.00 0.00 0.04 0.46 0.12 0.06

5 5 5 2 4.25 5 5 5 5 5.00 5 5 5 3 4.50 5 5 5 2 4.25 4.50

5 5 5 1 4.00 5 5 3 0 3.25 5 5 3 0 3.25 5 5 3 0 3.25 3.44

0.00 0.00 0.00 0.25 0.06 0.00 0.00 0.05 0.38 0.11 0.00 0.00 0.06 0.44 0.13 0.00 0.00 0.09 0.61 0.17 0.12

0.00 0.00 0.00 0.17 0.04 0.00 0.00 0.01 0.17 0.05 0.00 0.00 0.01 0.16 0.04 0.00 0.00 0.01 0.48 0.12 0.06

Slack

Average 2

Average 3

Average 4

Average Total average

0.87 43.04 639.82 18456.60 4785.08 3.35 345.93 14536.15 21600.12 9121.38 1.68 445.40 12692.61 21600.46 8685.04 6.51 417.75 14483.34 21602.19 9127.45 7929.74

Graph-based 1h

1

Time (s)

6h

Time (s)

Sol

Opt

Gap (%)

OptGap (%)

Sol

Opt

Gap (%)

OptGap (%)

5 5 5 5 5.00 5 5 5 5 5.00 5 5 5 5 5.00 5 5 5 5 5.00 5.00

5 5 5 5 5.00 5 5 5 3 4.50 5 5 5 2 4.25 5 5 5 0 3.75 4.38

0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.05 0.01 0.00 0.00 0.00 0.17 0.04 0.00 0.00 0.00 0.42 0.11 0.04

0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.05 0.01 0.00 0.00 0.00 0.35 0.09 0.02

5 5 5 5 5.00 5 5 5 5 5.00 5 5 5 5 5.00 5 5 5 5 5.00 5.00

5 5 5 5 5.00 5 5 5 5 5.00 5 5 5 4 4.75 5 5 5 0 3.75 4.63

0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.05 0.01 0.00 0.00 0.00 0.31 0.08 0.02

0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.05 0.01 0.00 0.00 0.00 0.31 0.08 0.02

Table 1 and 100 instances in Table 2. In all cases, column Sol indicates the number of instances for which the method was able to obtain a feasible solution. A value lower than five indicates that either CPLEX ran out of memory, or no integer solution was found within the allotted computing time. Column Opt indicates the number of optimal solutions found,

0.14 0.52 1.75 18.80 5.31 0.64 4.01 51.34 2477.55 633.38 0.44 3.67 70.88 10256.81 2582.95 0.86 6.56 795.50 21600.42 5600.84 2205.62

Gap (%) represents the average percentage gap with respect to the lower bound as reported by CPLEX, and column OptGap (%) indicates the gap with respect to the best lower bound yielded by any method (any formulation, running for 1 or 6 h). Finally, column Time(s) indicated to the total computing time in seconds for the instances that did not run out of memory.

Journal of the Operational Research Society

Table 2 Average solutions for the second set of instances for the flow-based formulation and the graph-based formulation Slack

Dest.

Flow-based 1h

1

Average 2

Average 3

Average 4

14 16 18 20 22 14 16 18 20 22 14 16 18 20 22 14 16 18 20 22

Average Average

6h

Sol

Opt

Gap (%)

OptGap (%)

Sol

Opt

Gap (%)

OptGap (%)

0 0 0 0 0 0.00 2 0 0 0 0 0.40 0 0 0 0 0 0.00 0 0 0 0 0 0.00 0.10

0 0 0 0 0 0.00 0 0 0 0 0 0.00 0 0 0 0 0 0.00 0 0 0 0 0 0.00 0.00

– – – – – – 0.38 – – – – 0.38 – – – – – – – – – – – – 0.38

– – – – – – 0.07 – – – – 0.07 – – – – – – – – – – – – 0.07

2 0 0 0 0 0.40 3 1 0 0 0 0.80 0 0 0 0 0 0.00 0 0 0 0 0 0.00 0.30

0 0 0 0 0 0.00 0 0 0 0 0 0.00 0 0 0 0 0 0.00 0 0 0 0 0 0.00 0.00

0.40 – – – – 0.40 0.37 0.56 – – – 0.47 – – – – – – – – – – – – 0.03

0.21 – – – – 0.21 0.10 0.48 – – – 0.29 – – – – – – – – – – – – 0.25

Slack

Average 2

Average 3

Average 4

Average Average

21600.46 21602.31 21605.59 21601.02 21601.56 21602.19 21600.11 21600.14 21600.13 21600.18 21600.23 21600.16 21600.71 21603.41 21620.23 21603.32 21600.92 21605.72 21600.65 21604.30 21627.59 21600.70 21601.44 21606.93 21603.75

Graph-based 1h

1

Time (s)

6h

Time (s)

Sol

Opt

Gap (%)

OptGap (%)

Sol

Opt

Gap (%)

OptGap (%)

5 5 5 5 5 5.00 5 5 5 4 3 4.40 5 5 5 4 4 4.60 5 5 5 5 5 5.00 4.75

4 4 0 0 0 1.60 3 0 0 0 0 0.60 1 0 0 0 0 0.20 0 0 0 0 0 0.00 0.60

0.00 0.02 0.21 0.41 0.50 0.23 0.04 0.39 0.42 0.56 0.47 0.37 0.33 0.52 0.42 0.41 0.41 0.42 0.35 0.45 0.34 0.37 0.50 0.40 0.36

0.00 0.00 0.08 0.36 0.48 0.18 0.01 0.34 0.37 0.54 0.47 0.35 0.28 0.50 0.41 0.40 0.40 0.40 0.30 0.43 0.33 0.36 0.50 0.38 0.33

5 5 5 5 5 5.00 5 5 5 4 3 4.40 5 5 5 4 5 4.80 5 5 5 5 5 5.00 4.80

4 5 5 0 0 2.80 5 0 1 0 0 1.20 1 0 0 0 0 0.20 1 0 0 0 0 0.20 1.10

0.00 0.00 0.00 0.25 0.46 0.14 0.00 0.31 0.34 0.47 0.44 0.31 0.26 0.46 0.39 0.37 0.37 0.37 0.29 0.39 0.25 0.29 0.33 0.31 0.28

0.00 0.00 0.00 0.25 0.46 0.14 0.00 0.31 0.34 0.47 0.44 0.31 0.26 0.46 0.39 0.37 0.37 0.37 0.29 0.39 0.25 0.29 0.33 0.31 0.28

469.08 1695.69 12928.31 21603.95 21604.14 11660.23 3197.56 21605.11 18998.02 21605.16 21607.95 17402.76 17709.26 21608.69 21614.00 21607.20 21608.06 20829.44 19255.38 21617.69 21609.49 21603.19 21605.19 21138.19 17757.66

Ka´tia Y. Nakamura et al—The Traveling Backpacker Problem

One can observe in Table 1 that both models are very sensitive to the slack time and to the number of destinations. Clearly, the graph-based formulation outperforms the flowbased one by solving all 80 instances to optimality, against 73 when employing flow-based formulation after 6 h of running time. Finally, the graph-based model led to much lower computing times than flow-based one. For the largest instances for which all five instances were solved to optimality by both models (line s ¼ 4 and n ¼ 10), the average computing times are 14,483 for the flow-based model and 795 s for the graphbased one. Table 2 presents the results for the set with the large-sized instances. The flow-based formulation did not find any optimal solution and failed to solve 94 instances. On the other hand, our graph-based formulation provides solutions for all but 4 instances, and proves 22 optimal solutions out of 100, and 12 within 1 h.

5. Conclusion In this paper we have described and modeled the Traveling Backpacker Problem using a graph-based formulation. We have also compared its performance with an already proposed flow-based formulation both being solved by branch-andbound by a MIP solver. We have generated instances based on real-world data provided by an industrial partner, and on two large sets of instances we have shown that our graph-based formulation clearly outperformed the flow-based formulation. The problem remains challenging and other methods are needed to find good solutions and to close the gap by improving the lower bounds yielded by our methods. Acknowledgements—The first and last authors acknowledge the financial support from the Fundac¸a˜o de Amparo a` Pesquisa do Estado de Sa˜o Paulo (FAPESP) under Grant 2015/21660-4, Conselho Nacional de Desenvolvimento Cientı´fico e Tecnolo´gico under Grants 308708/2015-6 and 448614/2014-6 and Coordenac¸a˜o de Aperfeic¸oamento de Pessoal de Nı´vel Superior (CAPES). The second and third authors gratefully acknowledge the financial support from the Canadian Natural Sciences and Engineering Research Council (NSERC) under Grants 0172633 and 2014-05764. We also thank Oliver Dlouhy and Jozef Ke´pesi for providing us the data for the experiments and Calcul Que´bec for enabling the use of high-performance computing facilities. We thank an associate editor and two anonymous referees for their valuable comments on an earlier version of this paper.

References Anjos MF, Cheng RCH and Currie CSM (2004). Maximizing revenue in the airline industry under one-way pricing. Journal of the Operational Research Society 55(5):535–541.

Applegate DL, Bixby RE, Chvatal V and Cook WJ (2007). The Traveling Salesman Problem: A Computational Study (Princeton Series in Applied Mathematics). Princeton University Press: Princeton, NJ. Bilotkach V, Gaggero AA and Piga CA (2015). Airline pricing under different market conditions: Evidence from european low-cost carriers. Tourism Management 47:152–163. Dijkstra E (1959). A note on two problems in connexion with graphs. Numerische Mathematik 1(1):269–271. Etzioni O, Tuchinda R, Knoblock CA and Yates A (2003). To buy or not to buy: Mining airfare data to minimize ticket purchase price. In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’03, New York, NY, USA, pp. 119–128. ACM. Gabteni S and Gro¨nkvist M (2009). Combining column generation and constraint programming to solve the tail assignment problem. Annals of Operations Research 171(1):61–76. Godinho MT, Gouveia L and Pesneau P (2014). Natural and extended formulations for the time-dependent traveling salesman problem. Discrete Applied Mathematics 164:138–153. Gouveia L and Voß S (1995). A classification of formulations for the (time-dependent) traveling salesman problem. European Journal of Operational Research 83(1):69–82. Hane CA, Barnhart C, Johnson EL, Marsten RE, Nemhauser GL and Sigismondi G (1995). The fleet assignment problem: Solving a largescale integer program. Mathematical Programming 70(1–3): 211–232. Hung JC, Zhou R, Hu J, Chen H, Zhou Q, Qi J and Yang L (2013). Cloud services aided e-tourism: In the case of low-cost airlines for backpacking. In: Parallel and Distributed Systems (ICPADS), 2013 International Conference on, pp. 468–473. IEEE. IATA (2014). Airlines expect 31% rise in passenger demand by 2017: 930-million more passengers compared with 2012. Northwestern University Transportation Library 41(12):55. Lucena A (1990). Time-dependent traveling salesman problem—The deliveryman case. Networks 20(6):753–763. Majstorovic V, Stankov U and Stojanov S (2013). The presence of backpacking tourism in Europe. Turizam 17:145–154. Pearce PL (1990). The Backpacker Phenomenon: Preliminary Answers to Basic Questions. James Cook University: Townville. Sherali HD, Bish EK and Zhu X (2006). Airline fleet assignment concepts, models, and algorithms. European Journal of Operational Research 172(1):1–30. Tas¸ D, Gendreau M, Jabali O and Laporte G (2016). The traveling salesman problem with time-dependent service times. European Journal of Operational Research 248(2):372–383. U.N.W.T.O. (2013). The world tourism organization: Tourism highlights 2013. Zhou Q, Hung JC, Hu J, Chen H, Zhou R, Qi J, Yang L and Wang X (2014). Cloud services aided e-tourism: In the case of low-cost airlines for backpacking. In: Park J, Zomaya A, Jeong HY, Obaidat M. (eds) Frontier and Innovation in Future Computing and Communications. Lecture Notes in Electrical Engineering, vol 301. Springer: Dordrecht.

Received 23 August 2016; accepted 15 February 2017