1 Search Results for "Pereira, Vinicius N. G."

Document

DOI: 10.4230/LIPIcs.SEA.2018.26

The Steiner Multi Cycle Problem with Applications to a Collaborative Truckload Problem

Authors: Vinicius N. G. Pereira, Mário César San Felice, Pedro Henrique D. B. Hokama, and Eduardo C. Xavier

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

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 less-than-truckload 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 NP-Hard, 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.

Cite as

Vinicius N. G. Pereira, Mário César San Felice, Pedro Henrique D. B. Hokama, and Eduardo C. Xavier. The Steiner Multi Cycle Problem with Applications to a Collaborative Truckload Problem. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 26:1-26:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{pereira_et_al:LIPIcs.SEA.2018.26,
  author =	{Pereira, Vinicius N. G. and San Felice, M\'{a}rio C\'{e}sar and Hokama, Pedro Henrique D. B. and Xavier, Eduardo C.},
  title =	{{The Steiner Multi Cycle Problem with Applications to a Collaborative Truckload Problem}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{26:1--26:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.26},
  URN =		{urn:nbn:de:0030-drops-89617},
  doi =		{10.4230/LIPIcs.SEA.2018.26},
  annote =	{Keywords: Steiner Cycle, Routing, Pickup-and-Delivery, Less-than-Truckload}
}

Refine by Author
1 Hokama, Pedro Henrique D. B.
1 Pereira, Vinicius N. G.
1 San Felice, Mário César
1 Xavier, Eduardo C.

Refine by Classification
1 Applied computing → Transportation
1 Theory of computation → Graph algorithms analysis
1 Theory of computation → Routing and network design problems

Refine by Keyword
1 Less-than-Truckload
1 Pickup-and-Delivery
1 Routing
1 Steiner Cycle

Refine by Type
1 document

Refine by Publication Year
1 2018

1 Search Results for "Pereira, Vinicius N. G."

The Steiner Multi Cycle Problem with Applications to a Collaborative Truckload Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message