The intermittent travelling salesman problem

• Date: 01 January 2020
• DOI: http://doi.org/10.1111/itor.12609
• Author: Pieter Leyman,Tu‐San Pham,Patrick De Causmaecker
• Published date: 01 January 2020

Intl. Trans. in Op. Res. 27 (2020) 525–548

DOI: 10.1111/itor.12609

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

The intermittent travelling salesman problem

Tu-San Pham, Pieter Leyman and Patrick De Causmaecker

Department of Computer Science, KU Leuven, KULAK, CODeS, Etienne Sabbelaan 53, 8500 Kortrijk, Belgium

E-mail: san.pham@kuleuven.be [Pham]; pieter.leyman@kuleuven.be [Leyman];

patrick.decausmaecker@kuleuven.be [De Causmaecker]

Received 31 October 2017; receivedin revised form 6 October 2018; accepted 9 October 2018

Abstract

In this paper,we introduce a new variant of the travellingsalesman problem, namely the intermittent travelling

salesman problem (ITSP), which is inspired by real-world drilling/texturing applications. In this problem,

each vertex can be visited more than once and there is a temperatureconstraint enforcing a time lapse between

two consecutive visits. A branch-and-bound approach is proposed to solve small instances to optimality. We

furthermore develop fourvariable neighbourhood search metaheuristics which produce high-quality solutions

for large instances. An instance library is built and made publicly available.

Keywords:inter mittent travelling salesman problem; branchand bound; variable neighbourhood search

1. Introduction

In this paper, we study a new variant of the travelling salesman problem (TSP). The problem is

inspired by industrial drilling or texturing applications where the temperature of the workpiece is

taken into account. The processing causes the workpiece to locally heat up until it eventually melts

the workpiece down. Therefore, the processing must be divided over time intervals, with time lapses

for cooling down of the workpiecein between. This gives rise to an optimisation problem of finding

the best schedule to process the whole workpiece in the shortest time while respecting temperature

constraints. In this paper, we study a simplified version of the problem where we assume linearity

with identical and constant cooling and heating speeds. We model the problem as a variant of

the TSP in which some vertices are visited multiple times and there is a time lapse between two

consecutive visits of a vertex, which is caused by the maximum temperature constraint, hence the

name intermittent travelling salesman problem (ITSP).

The TSP is a well-studied problem in the field of combinatorialoptimization with several variants.

Extended reviewsof the TSP can be found in, for example Laporte (1992) and Johnsonand McGeoch

(1997). To the best of our knowledge, the ITSP is the first variant with intermittent constraints. The

ITSP bears similarities to the vehicle routing problem (VRP) family. The following problems share

similarities with the ITSP. We point out the important differences.

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

526 T.-S.Pham et al. / Intl. Trans. in Op. Res. 27 (2020) 525–548

rThe TSP with multiple visits (TSPM) (Gutin and Punnen, 2006): In the TSPM, a vertex must be

visited a number of times. However, unlike the ITSP, each visit is not associated with a processing

time and there is no time constraint between visits.

rThe TSP with time windows (TSPTW) (Dumas et al., 1995): The TSPTW has time constraints

associated with each vertex in the form of a time window. In contrast to the ITSP, the TSPTW

does not consider multiple visits and the time constraints apply only for individual vertices.

rThe inventory routing problem (IRP) (Campbell et al., 1998): Each vertex (retailer) has a period-

ical (e.g. daily) requirement and an inventory capacity that should not be exceeded. The problem

consists of finding the best shipping policy to deliver a product froma common supplier to several

retailers, subject to the vehicle capacity constraints, product requirements and inventory capaci-

ties of the retailers. The inventory constraints are similar to the temperature constraints, be it that

in the IRP, vehicle travelling routes are within one discrete period (e.g. a day). Therefore, route

scheduling does not affect retailer inventorylevels, in contrast with the ITSP where travellingtime

directly affects vertex temperature.

In this paper, we provide a detailed description of the ITSP and analyse its properties. We study a

decomposition model, a branch-and-bound (BNB) approach and a metaheuristic. A decomposition

model is proposed including a mixed integer programming (MIP) and a linear programming (LP)

formulation for the subproblems. These are integrated in a BNB approach shown to solve small

instances to optimality. We then develop a metaheuristic approach for the larger instances. Two

constructive heuristics are proposed. Those two heuristics and two perturbation strategies are inte-

grated in a variable neighbourhood search (VNS) framework resulting in four VNS metaheuristics.

We analyse problem difficulty and create a problem library as a foundation for further research.

The structure of the paper is as follows. Section 2 describes the ITSP in detail and analyses

its difficulty. Section 3 introduces the building blocks of the BNB approach, namely a lemma,

two subproblems and two corresponding mathematical models. Section 4 is devoted to the VNS

approach. Experimental results are given in Section 5 and finally a conclusion and future work

follow in Section 6.

2. Problem description

We consider the problem of visiting a number of vertices v∈Vwith a given distance matrix cvu ≥0

defined for every pair of vertices (v,u)∈V×Vwith cvv =0. We assume the triangle inequality

holds. Each vertex v∈Vneeds to be processed for a certain time dv.Lett,tsand tebe the current

time, the beginning and the end of the current contiguous period of processing, respectively. While

being processed, the temperature of a vertexrises linearly, Tv(t)=Tv(ts)+(t−ts). While not being

processed, the temperature cools linearly, Tv(t)=max(Tv(te)−t,0)with a minimum of 0, below

which no cooling occurs. The maximum temperature of a vertex is B, beyond which no processing

is allowed. We assume that at the beginning of the processing, the temperature of each vertex is 0.

The ITSP asks for the processing schedule of shortest total completion time.

We introduce some terminologies used throughout the paper:

rA processing step is a processing interval without interruption at a vertex.

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies