Questions tagged [routing]

The tag has no usage guidance.

21 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4
votes
0answers
103 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 ...
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)$ ...
2
votes
0answers
36 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 ...
2
votes
1answer
52 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....
2
votes
0answers
55 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
0answers
467 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 ...
1
vote
0answers
16 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
79 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
0answers
30 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
42 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
0answers
61 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
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 ...
1
vote
0answers
77 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
0answers
27 views

What kind of routing does the telephone system of Europe use?

I am reading Computer Networks 5th edition by Andrew S. Tanenbaum and on page 141 it is stated that "The U.S. telephone system used hierarchical routing to find a path, going to higher ...
0
votes
1answer
50 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
90 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 ...
0
votes
0answers
68 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–...
0
votes
1answer
175 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 ...
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 ...
0
votes
0answers
37 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
58 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 ...