hyperpaths

README

Hyperpath routing in Golang

Just implementation of Spiess, H. and Florian, M. (1989) "Optimal strategies: A new assignment model for transit networks" in Golang

Algorithm

Here is copy of algorithm in MathJax (for the LaTeX see spiess_floarian.tex):

Part 1: Find optimal strategy

1. Initialization

   • Set $u_r = 0$ for destination node
   • Set $u_i = \infty$ for all other nodes
   • Set $f_i = 0$ for all nodes
   • Initialize empty attractive set $\overline{A}$

2. Label Setting

   • For each link $a = (i,j)$ with minimum $u_j + c_a$
   • If $u_i \geq u_j + c_a$:
     • Update node label: $$u_i = \frac{f_i \cdot u_i + f_a \cdot (u_j + c_a)}{f_i + f_a}$$
     • Update frequency: $$f_i = f_i + f_a$$
     • Add to attractive set: $$\overline{A} = \overline{A} \cup {a}$$

Part 2: Assign demand according to optimal strategy

1. Initialization

   • Set $V_i = g_i$ for all nodes

2. Loading

   • Process links in decreasing order of $u_j + c_a$
   • For attractive links $a \in \overline{A}$:
     • Calculate volume: $$v_a = \frac{f_a}{f_i}V_i$$
     • Update node volume: $$V_j = V_j + v_a$$

How to use

• Get the package:

  go get github.com/lddl/go-hyperpaths
  

• Code (you can find it in examples/paper)

  package main
  
  import (
     "fmt"
  
     "github.com/lddl/go-hyperpaths"
  )
  
  func main() {
     allNodes := map[string]struct{}{
        "A": {},
        "X": {}, "X2": {},
        "Y": {}, "Y3": {},
        "B": {},
     }
     allLinks := []*hyperpaths.Link{
        {"A", "B", "Line 1", 25, 6},
        {"A", "X2", "Line 2", 7, 6},
        {"X2", "X", "Line 2", 0, 0},
        {"X", "X2", "Line 2", 0, 6},
        {"X2", "Y", "Line 2", 6, 0},
        {"Y3", "Y", "Line 3", 0, 15},
        {"Y", "B", "Line 4", 10, 3},
        {"X", "Y3", "Line 3", 4, 15},
        {"Y", "Y3", "Line 3", 0, 15},
        {"Y3", "B", "Line 3", 4, 0},
     }
     destinationNode := "B"
     odMatrix := map[string]map[string]float32{
        "A": {
           "B": 1,
        },
     }
     res := hyperpaths.ComputeSF(allLinks, allNodes, destinationNode, odMatrix)
     fmt.Println("Optimal strategy:")
     fmt.Println("\tNode labels:")
     for nodeID, nodeLabel := range res.Strategy.Labels {
        fmt.Printf("\t\tu_{i} = %s: %f\n", nodeID, nodeLabel)
     }
     fmt.Println("\tNodes probablities:")
     for nodeID, freq := range res.Strategy.Freqs {
        fmt.Printf("\t\tf_{i} = %s: %f\n", nodeID, freq)
     }
     fmt.Println("\tAttractive links set:")
     for _, link := range res.Strategy.ASet {
        fmt.Printf("\t\t a = (i, j) = (%s, %s)\n", link.FromNode, link.ToNode)
     }
     fmt.Println("Volumes:")
     fmt.Println("\tLinks volumes:")
     for fromNode := range res.Volumes.Links {
        for toNode, volume := range res.Volumes.Links[fromNode] {
           fmt.Printf("\t\tv_{i, j} = (%s, %s): %f\n", fromNode, toNode, volume)
        }
     }
     fmt.Println("\tNodes volumes:")
     for nodeID, volume := range res.Volumes.Nodes {
        fmt.Printf("\t\tv_{i} = %s: %f\n", nodeID, volume)
     }
  }
  

References

Spiess, H. and Florian, M. (1989) "Optimal strategies: A new assignment model for transit networks". Transportation Research Part B: Methodological, 23(2), 83-102. Available in: https://doi.org/10.1016/0191-2615(89)90034-9

Documentation

Index

• Constants
• Variables
• type Link
• type PriorityQueue
  • func (pq PriorityQueue) Len() int
  • func (pq PriorityQueue) Less(i, j int) bool
  • func (pq *PriorityQueue) Pop() interface{}
  • func (pq *PriorityQueue) Push(x interface{})
  • func (pq PriorityQueue) Swap(i, j int)
• type SFResult
  • func ComputeSF(allLinks []*Link, allStops map[string]struct{}, destination string, ...) *SFResult
• type Strategy
  • func FindOptimalStrategy(allLinks []*Link, allStops map[string]struct{}, destination string) *Strategy
• type Volumes
  • func AssignDemand(allLinks []*Link, allStops map[string]struct{}, optimalStrategy *Strategy, ...) *Volumes

Constants

const (
	ALPHA = float32(1.0)
)

Variables

var (
	Verbose = false
)

Types

type Link

type Link struct {
	// Source node of the link
	FromNode string
	// Target node of the link
	ToNode string
	// Corresponding route
	RouteID string
	// In most cases this should trave time along the link
	TravelCost float32
	// Interval of public transport
	// Headway could have only dwell (on-board) links
	Headway float32
}

Link is just an edge in graph

type PriorityQueue

type PriorityQueue []*pqEntry

func (PriorityQueue) Len

func (pq PriorityQueue) Len() int

func (PriorityQueue) Less

func (pq PriorityQueue) Less(i, j int) bool

func (*PriorityQueue) Pop

func (pq *PriorityQueue) Pop() interface{}

func (*PriorityQueue) Push

func (pq *PriorityQueue) Push(x interface{})

func (PriorityQueue) Swap

func (pq PriorityQueue) Swap(i, j int)

type SFResult

type SFResult struct {
	// Optimal strategy
	Strategy *Strategy
	// Assigned demand
	Volumes *Volumes
}

SFResult is the result of running through the Spiess-Florian algorithm

func ComputeSF

func ComputeSF(allLinks []*Link, allStops map[string]struct{}, destination string, odMatrix map[string]map[string]float32) *SFResult

ComputeSF computes the Spiess-Florian algorithm

type Strategy

type Strategy struct {
	// u_{i} - expected time to destination
	Labels map[string]float32
	// f_{i} - combined frequency at node
	Freqs map[string]float32
	// \overline{A} - attractive links in hyperpath
	ASet []*Link
}

Strategy is optimal strategy as it defined in Spiess-Florian algorithm

func FindOptimalStrategy

func FindOptimalStrategy(allLinks []*Link, allStops map[string]struct{}, destination string) *Strategy

type Volumes

type Volumes struct {
	// Volumes for links
	Links map[string]map[string]float32
	// Volumes for nodes
	Nodes map[string]float32
}

Volumes is assignment demand according to optimal strategy

func AssignDemand

func AssignDemand(allLinks []*Link, allStops map[string]struct{}, optimalStrategy *Strategy, trips map[string]map[string]float32, destination string) *Volumes