Skip to main content

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
0 answers
110 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 ...
James Drain's user avatar
3 votes
0 answers
2k 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)$ ...
Thomas Bosman's user avatar
2 votes
0 answers
136 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. ...
zcahfg2's user avatar
  • 121
2 votes
0 answers
52 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 ...
Paul Accisano's user avatar
2 votes
1 answer
142 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 ...
janicebaratheon's user avatar
2 votes
0 answers
62 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 ...
SrvSsG's user avatar
  • 21
2 votes
0 answers
485 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 ...
zavg's user avatar
  • 131
1 vote
0 answers
47 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 ...
Mike's user avatar
  • 51
1 vote
0 answers
28 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 ...
Brian Lee's user avatar
1 vote
2 answers
158 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{...
JJJJJJJJJJJJJJJJ's user avatar
1 vote
0 answers
33 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 ...
Olivier Bégassat's user avatar
1 vote
0 answers
45 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 ...
S.D's user avatar
  • 152
1 vote
0 answers
110 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.
Anthony O's user avatar
  • 177
1 vote
1 answer
88 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....
foobar's user avatar
  • 19
1 vote
0 answers
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 ...
Sulistyo Chandrianto's user avatar
1 vote
0 answers
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 ...
user3570728's user avatar
0 votes
0 answers
14 views

Collaborative Multi Agent Path planning on directional and non-planar graph

I am trying to implement a multi-agent path planning algorithm that works on non-planar graphs and large agents (that is, collisions may at the intersection of two edges and at points where the edges ...
CubeArrow's user avatar
0 votes
0 answers
93 views

Finding the optimal trading route with output amount based on previous trades

I am trying to solve the following problem: Suppose there are traders who can exchange one good for another. Each trader $i$ defines two functions $y = f_{i1}(x)$ and $x = f_{i2}(y)$, with which we ...
Alex D.'s user avatar
0 votes
0 answers
138 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 ...
shivam's user avatar
  • 1
0 votes
0 answers
32 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 ...
Shoaib Manzoor's user avatar
0 votes
0 answers
132 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 ...
Thomas's user avatar
  • 1
0 votes
0 answers
98 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–...
giannisl9's user avatar
0 votes
1 answer
276 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 ...
Luigi Logrippo's user avatar
0 votes
0 answers
77 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 ...
spam's user avatar
  • 101
0 votes
0 answers
39 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 ...
José Henrique Davino's user avatar
0 votes
0 answers
105 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 ...
user3306097's user avatar