Skip to main content
Kent Academic Repository

Formulation and a two-phase matheuristic for the roaming salesman problem: Application to election logistics

Shahmanzari, Masoud, Aksen, Deniz, Salhi, Said (2020) Formulation and a two-phase matheuristic for the roaming salesman problem: Application to election logistics. European Journal of Operational Research, 280 (2). pp. 656-670. ISSN 0377-2217. (doi:10.1016/j.ejor.2019.07.035) (KAR id:76359)

Abstract

In this paper we investigate a novel logistical problem. The goal is to determine daily tours for a traveling salesperson who collects rewards from activities in cities during a fixed campaign period. We refer to this problem as the Roaming Salesman Problem (RSP) motivated by real-world applications including election logistics, touristic trip planning and marketing campaigns. RSP can be characterized as a combination of the traditional Periodic TSP and the Prize-Collecting TSP with static arc costs and time-dependent node rewards. Commercial solvers are capable of solving small-size instances of the RSP to near optimality in a reasonable time. To tackle large-size instances we propose a two-phase matheuristic where the first phase deals with city selection while the second phase focuses on route generation. The latter capitalizes on an integer program to construct an optimal route among selected cities on a given day. The proposed matheuristic decomposes the RSP into as many subproblems as the number of campaign days. Computational results show that our approach provides near-optimal solutions in significantly shorter times compared to commercial solvers.

Item Type: Article
DOI/Identification number: 10.1016/j.ejor.2019.07.035
Uncontrolled keywords: Routing, Roaming salesman problem, Election logistics, Matheuristic, Campaign planning
Subjects: H Social Sciences > H Social Sciences (General)
Divisions: Divisions > Kent Business School - Division > Department of Analytics, Operations and Systems
Depositing User: Said Salhi
Date Deposited: 11 Sep 2019 14:52 UTC
Last Modified: 19 Sep 2023 15:03 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/76359 (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.