Skip to main content

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) (Access to this publication is currently restricted. You may be able to access a copy if URLs are provided) (KAR id:76359)

PDF Author's Accepted Manuscript
Language: English

Restricted to Repository staff only until 22 July 2021.

Creative Commons Licence
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Contact us about this Publication
[img]
Official URL
https://dx.doi.org/10.1016/j.ejor.2019.07.035

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: Faculties > Social Sciences > Kent Business School > Centre for Logistics and Heuristic Organisation (CLHO)
Depositing User: Said Salhi
Date Deposited: 11 Sep 2019 14:52 UTC
Last Modified: 18 Feb 2020 12:18 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/76359 (The current URI for this page, for reference purposes)
Salhi, Said: https://orcid.org/0000-0002-3384-5240
  • Depositors only (login required):

Downloads

Downloads per month over past year