COLUMN GENERATION MODELS FOR OPTIMAL PACKAGE TOUR COMPOSITION

Our work aims to introduce a combinatorial optimization problem orbiting in Revenue Management, called Package Tour Composition (PTC) and to discuss its resolution with a mathematical programming method called column generation method. The classic Network Revenue Management problem considers a set of resources of finite capacity to be allocated to a set of products characterized by a given price and a given demand. The models of Network Revenue Management are applied by airline companies in order to decide how many seats to allocate on each flight leg (resource) to each fare (product) that is characterized by origin, destination and fare class. The model we propose aims to deal with a similar problem in which the demand is not expressed towards a set of products but towards a set of resources. This problem arises, for instance, in the composition of package tours where customer preferences towards events that compose a package tour are more relevant, and easier to be traced, than customer preferences for the whole package. In the PTC problem customers buy products that are bundles of resources in combinations under various terms and conditions. However demand is linked to resources not to products. The resource composition of each product is a decision variable. As a consequence product price is not known but is the sum of reservation prices of each resource in the bundle. The resource set is partitioned into several subsets corresponding to different resource types. A parameter states how many resources of each type characterize each product type. We refer to resources as 'events' and to products as 'package tours' or simply 'packages'. The resulting Package Tour Composition problem is a non-linear problem with integer variables that represent the number of tourists assigned to each package tour and binary variables that represent which events are assigned to each package tour. Each event is characterized by a reservation price, a demand and a capacity. Each package tour belongs to a package tour type that is characterized by its event type composition parameter. The number of tourists assigned to each event cannot exceed its actual capacity, which is defined as the minimuml value between the event capacity and the event demand. We also impose that the binary variables respect the composition constraint for every package tour according to its type. The objective function to be maximized is the total revenue, that is the number of packages to be sold times their price. We propose a column generation model to solve the linear relaxation of the Package Tour Composition problem. The Column Generation technique splits the problem in two sub-problems: the pricing problem and the master problem. The pricing problem dynamically generates, for every package type, several columns containing an event combination according to the package type composition parameter. The master problem chooses which event combinations to use and in which quantity, imposing that event actual capacity is respected, in order to maximize revenue. Chapter 1 concerns the motivation of our research. At first we analyze the previous literature on the theory of Revenue Management focusing our attention on the most important mathematical models that tackle two main Revenue Management problems: Single Resource Capacity Control and Network Capacity Control. We analyze the assumptions of these models to find improvement directions. After that, we present the state-of-the-art of mathematical models applied to tourist operators industry, in particular in the composition of tour itineraries. We propose a taxonomy to classify several possible Package Tour Composition problem formulations. In Chapter 2 the Package Tour Composition Model is formally defined and we propose the application of Column Generation method and a Column generation heuristics method to determine an optimal solution to the linear relaxation problem and a rounded solution to the integer problem. Two formulations are compared: the integer master formulation and the binary master formulation. Thereafter we present the dataset description and we display the results of integer and binary master formulations. In Chapter 3 we illustrate several extensions of the basic models. The extensions take into account market segmentation, inconvenience costs, tourist groups and stochastic demand. For each extension we present computational results obtained with the state-of-the-art mathematical programming solver CPLEX. Finally Chapter 4 presents some conclusions and possible future research directions.