Questions tagged [routing]
The routing tag has no usage guidance.
45
questions
0
votes
0answers
12 views
How to select “best” journey in McRaptor?
What are the good, well-known strategies to select the "best" journey in multi-criteria raptor by calculating its score? I came up with the solution like this:
journeyScore = (j.arrivalTime ...
0
votes
0answers
15 views
Lowest cost path(s) between source and destination that collects required items
I have an undirected graph where each vertex is given some items from a set of items. My goal is to find the lowest cost path from my source vertex to destination vertex while collecting all such ...
2
votes
1answer
25 views
Raptor algorithm: find next best paths
I'm reading Microsoft's white paper "Round-Based Public Transit Routing" (the RAPTOR algorithm). What are the ways to find next best paths (path is a sequence of trips and transfers from source to ...
2
votes
0answers
27 views
Finding multiple paths through a grid such that every grid square is equally used
Setup
Here’s the setup: I have an $N$ x $N$ grid of tiles, and a list of $M$ agents that need to move across the grid. Each agent has its own start tile $S(a)$, end tile $E(a)$, and an exact number ...
1
vote
1answer
35 views
Multi-Path Length Minimization
I've been thinking about path planning and am trying to make good heuristics for cases with multiple agents.
Suppose there are sets $S_i$ of coordinates in $\mathbb R^2$ or $\mathbb R^3$, each of the ...
2
votes
1answer
91 views
Mutli-Path Collision Avoidance
I need an algorithm which can do the following:
Given some finite number of particles (circles) each with the same radius, and a list of prescribed points for each particle, find paths in $\mathbb{...
1
vote
1answer
25 views
Finding stages in routing algorithm
I have an undirected graph where I need to find routes of minimum cost in a point to multi-point, but where cost can be reduced by creating intermediate "packs" of routing terminals. I am currently ...
2
votes
2answers
3k views
How do web browsers find out the MAC address?
While reading through my textbook, I discovered that if you want to access a particular web page, your web browser will find out the IP address of the web server that hosts the web page and try and ...
1
vote
1answer
233 views
Finding path with specific length in weighted graph
Given a weighted, cyclic, directed graph and two nodes I am looking for a connecting path which total weight comes as near as possible to a specific value which is greater than the shortest path.
...
0
votes
1answer
64 views
In “multi hop” network, is computer => computer 0 hop or 1 hop?
Would this here, a computer sending information directly to another computer, count as 0 hops or 1 hop?
0
votes
0answers
96 views
Shortest path for vehicle routing problem with alternative locations
I'm currently developing an algorithm that solves the vehicle routing problem with time windows and the possibility for clients to be delivered to multiple locations.
Right now, I'm trying to find ...
2
votes
0answers
40 views
How to solve cubing, batching, and routing problem together?
I am working on an order picking project, which requires to cube the items into several totes in a trolley, then batching the totes, followed by parallel aisle picking/routing.
The input data has ...
0
votes
0answers
72 views
Intuition for the convergence of the distance vector routing protocols
What is an intuitive way to think about the convergence of the distance vector routing algorithm?
According to Wikipedia:
Distance-vector routing protocols use the Bellman–Ford algorithm and Ford–...
1
vote
0answers
31 views
Routing a DAG through 5 consecutive butterfly networks
I have two questions concerning the paper Nearly linear-size holographic proofs. In the second paragraph of section 6, A Graph Coloring Problem, it is claimed that
Using standard packet-routing ...
1
vote
0answers
43 views
Delivering to two or more locations in one go while respecting deadlines?
Assume that I have a business where people can place product orders. Each order must be delivered within a time limit, say $x$ minutes.
I need 15 minutes to make each product. However, multiple ...
1
vote
1answer
72 views
Combinatorial Optimization: Shortest distance given sets of drivers and riders
Problem:
I have 2 sets, one of drivers and one of riders. All my participants need to reach one common destination. I wish to calculate the shortest combined distance in order for all participant to ...
1
vote
0answers
72 views
How do distributed algorithms for shortest path finding handle negative cycles?
I am searching the web for an answer to this question, but I have only found answers for non-distributed algorithms. I am interested in this for its application to Distance Vector routing.
3
votes
1answer
1k views
Distance Vector Routing Example
Consider a network with five nodes, N1 to N5, as shown as below.
The network uses a Distance Vector Routing protocol. Once the routes have been stabilized, the distance vectors at different nodes are ...
0
votes
1answer
64 views
Seek to infer “correct” route from sequence of stops
Let us consider school buses. Let a 'Bus Route' be a sequence of bus stops travelled by a single school bus (day after day). Let a 'Bus Stop' be a combination of Latitude (Lat), Longitude (Lon) and ...
1
vote
1answer
889 views
Routing algorithm for train network
I am trying to analyse a weighted multi-graph which represents a snapshot of a rail network for a particular day. As such, the vertices of the graph can be considered stations and the weighted edges ...
1
vote
1answer
245 views
Shortest Path using at most k colors
I have an edge-colored network, in which edges also have a length, and I am considering the problem of determining the shortest Path between a pair of nodes, with the additional constraint that the ...
2
votes
1answer
58 views
Question regarding terminology used to describe Benes networks
I'm studying a routing problem on a cyclic butterfly network. The paper I am reading states that two properties of the cyclic butterfly network make it efficient for the routing algorithm it describes....
0
votes
1answer
184 views
A path modification problem in directed graphs
We start with a given finite directed graph. It could represent transitive relations such as:
data transfer paths in social networks,
transportation connections, etc.
Let us use the notation
A->B ...
2
votes
1answer
105 views
route and/or packing optimization algorithm
What type of problem would this question fall under, are there known algorithms/heuristics for it, what would be good resources to learn more about solving it?
Given:
a list of items each with a ...
1
vote
0answers
1k views
How to use Clarke and Wright saving algorithm to afford heterogeneous fleet?
I want to solve Heterogeneous fleet in vehicle routing problem using the Clarke and Wright saving algorithm. After reading many literature I found two options:
Explicit and early assignment for the ...
4
votes
0answers
106 views
Parallel bubble sorting on arbitrary graphs
Are there bubblesort-esque algorithms for sorting on arbitrary graphs?
I'm working on a problem in which $k$ robots are placed randomly on a graph and have to reach their respective goals as quickly ...
0
votes
0answers
70 views
Planning interviews
This is real-world problem, but I need to model it with algorithm as I am going to implement it (probably with PostGIS and Google Maps).
Problem is:
Everyday I am receiving job offers, and I have to ...
1
vote
1answer
74 views
How can simulated annealing be related to the vehicle routing problem?
I have been searching through internet how could simulated annealing to solve the vehicle routing problem, but didn't find anything that made it clear to me. Most of what I found are research papers ...
0
votes
0answers
38 views
Looking for algorithms context-aware to solve a Bicycle Routing Problem
I am conducting a study has the general objective to build a route recommendation system for bicycle users, able to suggest viable alternatives to dislocation in urban environments, with reference to ...
0
votes
0answers
73 views
How to avoid looping of packets while implementing k-shortest paths algorithm in Network Simulator-3?
I am trying to implement k-shortest paths algorithm in NS-3 for IPv4GlobalRoutingProtocol. I am concerned about how to avoid looping of packets. My implementation calculates k-shortest paths from ...
3
votes
1answer
416 views
Shortest path problem where edge weight depends on path taken
I am attempting to find the most efficient route to get from a source to a destination in a bus network. Each stop is a vertex in a graph, and each edge between vertices represents a route between ...
2
votes
2answers
1k views
Raptor Algorithm: Differences between trip and route
I'm reading Microsoft's white paper "Round-Based Public Transit Routing" (the RAPTOR algorithm). In this algorithm, there are some definitions that I don't understand:
About trip:
trip represents ...
2
votes
0answers
58 views
How to know for sure that a router is congested?
Suppose a router X is dropping packets. Another router A will investigate whether X is dropping packets due to congestion. What are the procedures that A should follow?
A already knows X's buffer ...
2
votes
1answer
219 views
Route planning for a car driver picking up people using public transport
We just had an interesting though for a routing algorithm for people carpooling. Imagine the following situation:
Person 1 is driving with his car from the south of city A to city B far in the north. ...
1
vote
0answers
78 views
Best route around confirmed appts - Traveling Salesman Problem
First, I am not a programmer, but an end user. We are trying to come up with a solution to a TSP issue that is causing us SIGNIFICANT time being wasted "manually" routing.
Here is the issue. We ...
1
vote
2answers
436 views
Algorithm for finding the best “route” of tasks
I have the following problem: Let's say I'm in a city with some friend we have a bunch of tasks to do. All persons start on a different position, for example (0/0), (10/5), (-20/0), ... , and every ...
0
votes
2answers
159 views
Listing all possible train routes [closed]
I'm interested whether there is the standard solution to the following problem.
Some number of train routes is given:
Route1: First City -> Next City -> ... -> Last City
Route2: ...
...
We need to ...
3
votes
1answer
174 views
Unsplittable flow in capacitated networks
I have an undirected network with capacitated links/edges. Between some nodes unsplittable traffic has to be routed. All demands and capacities are known, but it is uncertain if all flows can be ...
0
votes
2answers
720 views
Bellman–Ford negative path meaning
In the Bellman–Ford algorithm, what is the practical meaning of
having a negative path between routers?
I have tried searching the net but didn't find any data
thanks
Eli
2
votes
0answers
470 views
Optimal vehicle routing on map
Currently I am developing a piece of software that solves the vehicle routing problem.
The task is the following:
I have several vehicles along the town
I have lots of destination points along the ...
0
votes
1answer
127 views
How can one come up with reasonable IP subnet allocations?
An ISP has following chunk of CIDR-based IP addresses available with it: 245.248.128.0/20
The ISP wants to give half of this chunk addresses to Organization A,
and ...
1
vote
0answers
69 views
Buffering packets vs. low latency routing [closed]
I am considering strategies to compare the performance of routers with buffers vs. their lower latency counterparts in a simple network setting (N clients communicating with each other randomly ...
3
votes
1answer
8k views
Destination-based vs source-based routing
I understand that destination-based routing builds the "route" from the destination backwards to the source (e.g. if using a spanning tree, then the tree is routed at the destination). With source-...
4
votes
0answers
1k views
Time complexity 2-opt method
I'm doing a practice test for a course on routing problems. There's a question asking to infere the time complexity of the 2-opt method.
I can see that the complexity per iteration is in $O(n^2)$ ...
1
vote
1answer
684 views
Simple routing table question
I'm having difficulties understanding the solution to the following question:
Consider the following description of a LAN:
The main Internet connection is connected to our gateway router. This
...
