Abstract

This paper introduces the Twin Robot Routing Problem (TRRP) in which two robots must be scheduled and routed to pick up, and deliver products at specified locations along a rail. The robots are initially located at the opposite ends of the rail and must preserve a minimum safe distance from one another (i.e., a non-crossing restraint must be respected). The objective is to minimise the makespan, defined as the time required to complete all operations and for both robots to return to their starting positions. The paper presents a proof of NP-Hardness of the TRRP, as well as two mixed integer linear programming models. A genetic algorithm is then developed, in which a linear-time heuristic and a dynamic algorithm are proposed to evaluate the quality of solutions. Extensive computational results demonstrate the limits of the mathematical models, the effectiveness of the genetic algorithm, and the savings obtained by using twin robots instead of a single one.
LanguageEnglish
Pages162
Number of pages1
StatusPublished - 11 Jul 2017
EventVeRoLog 2017 - Vrije Univiersiteit, Amsterdam, Netherlands
Duration: 10 Jul 201712 Jul 2017

Conference

ConferenceVeRoLog 2017
CountryNetherlands
CityAmsterdam
Period10/07/1712/07/17

Fingerprint

Robots
Rails
Genetic algorithms
Linear programming
Hardness
Mathematical models

Cite this

Thomasson, O., Battarra, M., Erdoğan, G., & Laporte, G. (2017). The Twin-Robot Routing Problem. 162. Abstract from VeRoLog 2017, Amsterdam, Netherlands.

The Twin-Robot Routing Problem. / Thomasson, Oliver; Battarra, Maria; Erdoğan, Güneş; Laporte, Gilbert.

2017. 162 Abstract from VeRoLog 2017, Amsterdam, Netherlands.

Research output: Contribution to conferenceAbstract

Thomasson, O, Battarra, M, Erdoğan, G & Laporte, G 2017, 'The Twin-Robot Routing Problem' VeRoLog 2017, Amsterdam, Netherlands, 10/07/17 - 12/07/17, pp. 162.
Thomasson O, Battarra M, Erdoğan G, Laporte G. The Twin-Robot Routing Problem. 2017. Abstract from VeRoLog 2017, Amsterdam, Netherlands.
Thomasson, Oliver ; Battarra, Maria ; Erdoğan, Güneş ; Laporte, Gilbert. / The Twin-Robot Routing Problem. Abstract from VeRoLog 2017, Amsterdam, Netherlands.1 p.
@conference{ae2726a97caa4438b92fcfc66590c129,
title = "The Twin-Robot Routing Problem",
abstract = "This paper introduces the Twin Robot Routing Problem (TRRP) in which two robots must be scheduled and routed to pick up, and deliver products at specified locations along a rail. The robots are initially located at the opposite ends of the rail and must preserve a minimum safe distance from one another (i.e., a non-crossing restraint must be respected). The objective is to minimise the makespan, defined as the time required to complete all operations and for both robots to return to their starting positions. The paper presents a proof of NP-Hardness of the TRRP, as well as two mixed integer linear programming models. A genetic algorithm is then developed, in which a linear-time heuristic and a dynamic algorithm are proposed to evaluate the quality of solutions. Extensive computational results demonstrate the limits of the mathematical models, the effectiveness of the genetic algorithm, and the savings obtained by using twin robots instead of a single one.",
author = "Oliver Thomasson and Maria Battarra and G{\"u}neş Erdoğan and Gilbert Laporte",
year = "2017",
month = "7",
day = "11",
language = "English",
pages = "162",
note = "VeRoLog 2017 ; Conference date: 10-07-2017 Through 12-07-2017",

}

TY - CONF

T1 - The Twin-Robot Routing Problem

AU - Thomasson, Oliver

AU - Battarra, Maria

AU - Erdoğan, Güneş

AU - Laporte, Gilbert

PY - 2017/7/11

Y1 - 2017/7/11

N2 - This paper introduces the Twin Robot Routing Problem (TRRP) in which two robots must be scheduled and routed to pick up, and deliver products at specified locations along a rail. The robots are initially located at the opposite ends of the rail and must preserve a minimum safe distance from one another (i.e., a non-crossing restraint must be respected). The objective is to minimise the makespan, defined as the time required to complete all operations and for both robots to return to their starting positions. The paper presents a proof of NP-Hardness of the TRRP, as well as two mixed integer linear programming models. A genetic algorithm is then developed, in which a linear-time heuristic and a dynamic algorithm are proposed to evaluate the quality of solutions. Extensive computational results demonstrate the limits of the mathematical models, the effectiveness of the genetic algorithm, and the savings obtained by using twin robots instead of a single one.

AB - This paper introduces the Twin Robot Routing Problem (TRRP) in which two robots must be scheduled and routed to pick up, and deliver products at specified locations along a rail. The robots are initially located at the opposite ends of the rail and must preserve a minimum safe distance from one another (i.e., a non-crossing restraint must be respected). The objective is to minimise the makespan, defined as the time required to complete all operations and for both robots to return to their starting positions. The paper presents a proof of NP-Hardness of the TRRP, as well as two mixed integer linear programming models. A genetic algorithm is then developed, in which a linear-time heuristic and a dynamic algorithm are proposed to evaluate the quality of solutions. Extensive computational results demonstrate the limits of the mathematical models, the effectiveness of the genetic algorithm, and the savings obtained by using twin robots instead of a single one.

M3 - Abstract

SP - 162

ER -