Abstract
We introduce a new problem called Steiner Multi Cycle Problem that extends the Steiner Cycle problem in the same way the Steiner Forest extends the Steiner Tree problem. In this problem we are given a complete weighted graph G=(V,E), which respects the triangle inequality, a collection of terminal sets {T_1,..., T_k}, where for each a in [k] we have a subset T_a of V and these terminal sets are pairwise disjoint. The problem is to find a set of disjoint cycles of minimum cost such that for each a in [k], all vertices of T_a belong to a same cycle. Our main interest is in a restricted case where T_a = 2, for each a in [k], which models a collaborative lessthantruckload problem with pickup and delivery. In this problem, we have a set of agents where each agent is associated with a set T_a containing a pair of pickup and delivery vertices. This problem arises in the scenario where a company has to periodically exchange goods between two different locations, and different companies can collaborate to create a route that visits all its pairs of locations sharing the total cost of the route. We show that even the restricted problem is NPHard, and present some heuristics to solve it. In particular, a constructive heuristic called Refinement Search, which uses geometric properties to determine if agents are close to each other. We performed computational experiments to compare this heuristic to a GRASP based heuristic. The Refinement Search obtained the best solutions in little computational time.
BibTeX  Entry
@InProceedings{pereira_et_al:LIPIcs:2018:8961,
author = {Vinicius N. G. Pereira and M{\'a}rio C{\'e}sar San Felice and Pedro Henrique D. B. Hokama and Eduardo C. Xavier},
title = {{The Steiner Multi Cycle Problem with Applications to a Collaborative Truckload Problem}},
booktitle = {17th International Symposium on Experimental Algorithms (SEA 2018)},
pages = {26:126:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770705},
ISSN = {18688969},
year = {2018},
volume = {103},
editor = {Gianlorenzo D'Angelo},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8961},
URN = {urn:nbn:de:0030drops89617},
doi = {10.4230/LIPIcs.SEA.2018.26},
annote = {Keywords: Steiner Cycle, Routing, PickupandDelivery, LessthanTruckload}
}
Keywords: 

Steiner Cycle, Routing, PickupandDelivery, LessthanTruckload 
Collection: 

17th International Symposium on Experimental Algorithms (SEA 2018) 
Issue Date: 

2018 
Date of publication: 

19.06.2018 