Creating a bus route

Question

What is a good algorithm or class of algorithms that can be used to create a bus route?

I was thinking something along the lines of algorithms that are used to solve Traveling Salesman tasks or Hamiltonian paths, but, in truth, the question of how to move between two stops is not really considered.

I would like the algorithm to have at least the following characteristics:

• creates a relatively optimized path (I understand the problem is probably completed by NP, so a good heuristic is fine)
• It can handle parts of the path that have different weights (for example, time to move along this part of the path).
• It can be forced to use a given start and end point (I don't think this problem will be like this)

Code that can do this, or something like this will be appreciated (especially in C #), but a good algorithm by itself will be fine.

Note. . Although there are many algorithms that can find the shortest path between two points, I do not know the order in which I want to stop. Thus, if I do not use a combination of two algorithms (which I doubt is true), these algorithms do not do what I want (if you think that they do, explain).

Edit: Suppose I know all the stops that need to be made.

Answer 1

It seems like a way to do this involves using the Floyd-Warsall algorithm, and then using the algorithm that is used to solve the traveling salesman problem.

This solves the problem of all “optional” vertices (intersections) and uses the traveling salesman algorithm to determine the order in which stops should be removed.

Answer 2

You can probably use the traveling salesman algorithm with a slight modification / assumption here to refer to point 2 (part of the path with different weights).

Suppose that the path from point “A” to point “B” has 2 weights (say, traffic at some point in time)

Despite the fact that this is the only way, we can simplify the task by assuming a “virtual vertex”, a point “C”, which is located between “A” and “B”, which will have fixed weights in each of the edges.

A ------- Weight = 10 ------ C ------ Weight = 15 ------ B

In this new chart, run the Salesing salesman algorithm.

Answer 3

I used the Jikstra algorithm: http://en.wikipedia.org/wiki/Dijkstras_algorithm

The cost of moving around the edge is not only the distance, but also related to the time until the "next" bus is separated from this node. Note. You may already be on the bus when it stops at node.

Answer 4

Bus routes are created by people, not computers. Only people know who needs to travel, where and how often. You need at least that kind of data to think about finding a set of routes that is optimal for people's needs. Regarding this, I believe that your question is not defined.