Design of diversified package tours for the digital travel industry : A branch-cut-and-price approach

Zhao, Yanlu; Alfandari, Laurent

Abstract

Motivated by the revolution brought by the internet and communication technology in daily life, this paper examines how the online travel agencies (OTA) can use these technologies to improve customer value. We consider the design of a fixed number of package tours offered to customers in the digital travel industry. This can be formulated as a Team Orienteering Problem (TOP) with restrictions on budget and time. Different from the classical TOP, our work is the first one to introduce controlled diversity between tours. This enables the OTA to offer tourists a diversified portfolio of tour packages for a given period of time, each potential customer choosing a single tour in the selected set, rather than multiple independent tours over several periods as in the classical TOP. Tuning the similarity parameter between tours enables to manage the trade-off between individual preferences in consumers’ choices and economies of scale in agencies’ bargaining power. We propose compact and extended formulations and solve the master problem by a branch-and-price method, and an alternative branch-cut-and-price method. The latter uses a delayed dominance rule in the shortest path pricing problem solved by dynamic programming. Our methods are tested over benchmark TOP instances of the literature, and a real dataset collected from a Chinese OTA. We explore the impact of tours diversity on all stakeholders, and assess the computational performance of various approaches.

Citation

Zhao, Y., & Alfandari, L. (2020). Design of diversified package tours for the digital travel industry : A branch-cut-and-price approach. European Journal of Operational Research, 285(3), 825-843. https://doi.org/10.1016/j.ejor.2020.02.020

• Journal Article Type: Article
• Acceptance Date: Feb 10, 2020
• Online Publication Date: Feb 14, 2020
• Publication Date: 2020-09
• Deposit Date: Sep 2, 2020
• Publicly Available Date: Feb 14, 2022
• Journal: European Journal of Operational Research
• Print ISSN: 0377-2217
• Electronic ISSN: 1872-6860
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 285
• Issue: 3
• Pages: 825-843
• DOI: https://doi.org/10.1016/j.ejor.2020.02.020
• Public URL: https://durham-repository.worktribe.com/output/1263065