The Steiner Multi Cycle Problem with Applications to a Collaborative Truckload Problem
| Autor: | Pereira, Vinicius N. G., San Felice, Mário César, Hokama, Pedro Henrique D. B., Xavier, Eduardo C. |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
000 Computer science
knowledge general works 010201 computation theory & mathematics Computer Science 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing 0102 computer and information sciences 02 engineering and technology 01 natural sciences |
| DOI: | 10.4230/lipics.sea.2018.26 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|