Public Transportation Advertisement Scheduling: Algorithms and a Case Study in Taiwan

Authors

Yun-Hsin Kuo, National Taiwan UniversityFollow
Fa-Xuan Xiao, National Taiwan UniversityFollow
Cheng-Wei Lu, National Taiwan UniversityFollow
Chia-Hua Chang, National Taiwan UniversityFollow
Ling-Chieh Kung, National Taiwan UniversityFollow

Abstract

We consider a real-world advertisement scheduling problem on public transportation. With modern technology of face recognition, the number of effective exposures of each advertisement display may be estimated more accurately than before. The objective of this work is thus to maximize the minimum effective exposure among advertisers to preserve fairness, one common operating issue faced by media agencies. We propose an algorithm consisting of two parts and aim to handle both efficiency and efficacy. The first part is a heuristic modified from the famous longest processing time (LPT) rule. The second part is a branch-and-bound algorithm by adjusting optimality gap over runtime to obtain the best possible schedule within the time limit. We run numerical experiments to evaluate the performances of the algorithm. Collaboration with a Taiwanese media agency on bus routes demonstrates the applicability of our algorithm in practice.

Recommended Citation

Kuo, Yun-Hsin; Xiao, Fa-Xuan; Lu, Cheng-Wei; Chang, Chia-Hua; and Kung, Ling-Chieh, "Public Transportation Advertisement Scheduling: Algorithms and a Case Study in Taiwan" (2019). PACIS 2019 Proceedings. 134.
https://aisel.aisnet.org/pacis2019/134