Questions tagged [routing]
The routing tag has no usage guidance.
1
vote
1answer
50 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
26 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.
1
vote
1answer
71 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
49 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
0answers
427 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
177 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
43 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
151 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 ...
3
votes
1answer
83 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
985 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
97 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
67 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
72 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
35 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
37 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 ...
4
votes
1answer
327 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
51 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
208 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
76 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 ...
0
votes
1answer
382 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
135 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
150 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
571 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
441 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
95 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
66 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
6k 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-...
3
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
563 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
...
