{
  "$type": "site.standard.document",
  "description": "Computing distance tables is important for many logistics problems like the vehicle routing problem (VRP). While shortest distances from all source nodes in S to all target nodes in T are time-independent, travel times are not. We propose a method of determining a time-dependent route parameter for…",
  "path": "/patents/1008714",
  "publishedAt": "2011-10-12T00:00:00.000Z",
  "site": "at://did:plc:oql6ds5vnff4ugar6rruliwd/site.standard.publication/3mn3ohu7oxx5w",
  "tags": [
    "G01C21/3446",
    "KARLSRUHER INST TECHNOLOGIE [DE]"
  ],
  "textContent": "Computing distance tables is important for many logistics problems like the vehicle routing problem (VRP). While shortest distances from all source nodes in S to all target nodes in T are time-independent, travel times are not. We propose a method of determining a time-dependent route parameter for a transportation network, for use in an automated routing system in connection with traffic, transportation, and logistics, said method comprising the steps: a) modelling the transportation network in the form of a graph (G) in the memory (2) of a computer system (1), said graph comprising a plurality of nodes (s, t, u, v, w), wherein said nodes correspond to starting-locations, target locations, and intermediate way-points in said transportation network, and a plurality of edges (E) interconnecting pairs of said nodes, wherein said edges indicate travel costs for travelling between respective nodes, wherein at least some of said travel costs are time-dependent quantities; b) for at least one arbitrary starting-node (s) of said plurality of nodes and for a first set of departure times (Ä), computing and storing first travel costs for respective first routes on said graph, said first routes leading from said one starting-node to a first plurality of intermediate way-point nodes (u, v, w) of said plurality of nodes; c) for at least one arbitrary target node (t) of said plurality of nodes and for a second set of departure times, computing and storing second travel costs for respective second routes on said graph, said second routes leading from a second plurality of intermediate way-point nodes (u, v, w) of said plurality of nodes to said one target node; d) for a plurality of target nodes and/or starting-nodes, determining a time-dependent travel cost for at least one route on said graph between said starting-node and said target node via at least one intermediate way-point node, which at least one intermediate way-point node is comprised in both of said first and second plurality of intermediate way-point nodes, from said first travel costs and said second travel costs, and e) for a third set of departure times (Ä), determining said time-dependent route parameter based on said time-dependent travel cost. We present the first efficient algorithms to compute time-dependent travel time tables in large time-dependent transportation networks.",
  "title": "Method and system for time-dependent routing"
}