We address the problem of orienting the edges of an undirected graph so as to minimize the sum of the distances between a given set of origin-destination pairs in the resulting directed graph. The problem originates from the design of Personal Rapid Transit (PRT) networks. We consider an Integer Linear Programming (ILP) formulation with variables associated with the orientation of the arcs, and variables associated with the arcs in the paths in the directed graph between origin-destination pairs. Given that the direct solution of this natural formulation is impractical even for small instances, we propose a branch-and-cut approach based on Benders decomposition, reporting preliminary experimental results on arising from PRT networks.

An Application of Network Design with Orientation Constraints

CAPRARA, ALBERTO;TRAVERSI, EMILIANO;SCHWEIZER, JOERG
2008

Abstract

We address the problem of orienting the edges of an undirected graph so as to minimize the sum of the distances between a given set of origin-destination pairs in the resulting directed graph. The problem originates from the design of Personal Rapid Transit (PRT) networks. We consider an Integer Linear Programming (ILP) formulation with variables associated with the orientation of the arcs, and variables associated with the arcs in the paths in the directed graph between origin-destination pairs. Given that the direct solution of this natural formulation is impractical even for small instances, we propose a branch-and-cut approach based on Benders decomposition, reporting preliminary experimental results on arising from PRT networks.
Proceedings of the 7th Cologne-Twente Workshop on Graphs and Combinational Optimization
16
21
A. Caprara; E.Traversi; J. Schweizer
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/61151
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact