Questions tagged [routing]

The tag has no usage guidance.

26 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4
votes
0answers
108 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 ...
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)$ ...
2
votes
0answers
27 views

Algorithm for stacked orders in food delivery (Pick up and deliveries)

I am trying to implement stacking orders While the most optimal solution would be to consider picking up orders from nearby restaurants that have similar food prep time AND nearby delivery locations. ...
2
votes
0answers
34 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 ...
2
votes
1answer
101 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{...
2
votes
1answer
70 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
68 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
59 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
471 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
1answer
36 views

Trying to understand a Router's Forwarding Table

I am trying to understand how a router's forward table works. As such, I am working on the following problem. Problem: A router’s forwarding table has the following entries. \begin{array} {|r|r|}\...
1
vote
0answers
42 views

Delivery problem, unsure which exact problem it is

I'm looking for guidance on how to reduce the following problem to a known problem or a suggestion for solving it altogether. Optimal / heuristic solutions or any other suggestions are greatly ...
1
vote
0answers
25 views

An algorithm to find differences between routing paths

I need to come up with an algorithm that finds differences in the sequence of each product's routing (or sequence of processes). There are several processes aligned together and each process's been ...
1
vote
0answers
32 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
0answers
99 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
2k 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
79 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
15 views

The size of a router's forwarding table

Consider a home network. Say three computers, a network printer and an internet connection. The three computers and the network printer will use the router to communicate with each other. I am ...
0
votes
0answers
32 views

Routing with constraints

The following is the statement of the problem: There are 40 packets to be delivered in a day. Each packet needs to be delivered to a particular location. Apart from this, there are constraints also ...
0
votes
0answers
17 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 ...
0
votes
0answers
112 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
83 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
205 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
72 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
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
88 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 ...