The Twin Robot Routing Problem
Oliver Thomasson  1, *@  , Maria Battarra  1@  , Gunes Erdogan  1@  , Gilbert Laporte  2@  
1 : University of Bath [Bath]  -  Website
Claverton Down, Bath, North East Somerset BA2 7AY -  United Kingdom
2 : HEC Montréal
3000 chemin de la Cote-Sainte-Catherine, Montreal H3T 2A7 -  Canada
* : Corresponding author

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.


Online user: 1 RSS Feed