This paper deals with searching for a "best" circular service route passing through a given road network represented by an undirected graph. Each edge is characterized by a generalized cost, e.g. the length or travel time, and by a benefit associated to the importance of serving that edge. All these parameters are positive. The service route should meet a cost limit constraint and maximize the route benefit. The route does not need to be elementary, since edges can be traversed multiple times. However, the benefit associated to each traversal of an edge decreases as the number of traversals increases. The total benefit of a service route is defined as the sum of the benefits provided by each individual traversal of each edge of the route.

Partial Service Routes with Multiple Visits to Edges

NONATO, Maddalena
Ultimo
2014

Abstract

This paper deals with searching for a "best" circular service route passing through a given road network represented by an undirected graph. Each edge is characterized by a generalized cost, e.g. the length or travel time, and by a benefit associated to the importance of serving that edge. All these parameters are positive. The service route should meet a cost limit constraint and maximize the route benefit. The route does not need to be elementary, since edges can be traversed multiple times. However, the benefit associated to each traversal of an edge decreases as the number of traversals increases. The total benefit of a service route is defined as the sum of the benefits provided by each individual traversal of each edge of the route.
2014
978-80-225-3868-8
circular service route, multiple edge traversals, optimization, depth-first-search
File in questo prodotto:
File Dimensione Formato  
PriCeCeNo Partial service routes.pdf

solo gestori archivio

Descrizione: Pre-print
Tipologia: Pre-print
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 456.73 kB
Formato Adobe PDF
456.73 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Zbornik2014 (1).pdf

accesso aperto

Descrizione: Full text editoriale
Tipologia: Full text (versione editoriale)
Licenza: PUBBLICO - Pubblico con Copyright
Dimensione 587.89 kB
Formato Adobe PDF
587.89 kB Adobe PDF Visualizza/Apri

I documenti in SFERA 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/11392/2342007
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 0
social impact