Euler vs. Hamiltonian path or circuit for a bus route

Question

Let's say that we have to pick up and drop off children at different stops along a bus route. Would a Euler path and circuit be more practical, or a Hamiltonian path or circuit for a mapping algorithm?

Answer 1

The reason for finding an Euler Circuit is to cross every every edge once. I don't think the driver is interested in driving down every street if he or she doesn't have to.

The reason for finding a Hamiltonian path is to get to every location exactly once. That seems to fit better. But I'm not convinced that passing by a bus stop more than once needs to be forbidden.

I think the driver and the passengers would really like to minimize the time they have to spend on the bus, or maybe the amount of fuel used for the ride. if it means the ride is quicker or cheaper, then it seems ok to pass by one of the stops more than once.

So I would model this as a problem of finding the circuit (a bus trip that ends where it starts) that hits every stop at least once and minimizes the total cost of the trip, where :"cost" is the total time of the trip, or the total over all students of the time they spent on the bus, or the total fuel cost. I think that would be called a "Minimum Cost Spanning Circuit".

Clearly the vertices in this graph would be the bus stops and the bus's garage or parking lot. What exactly are the edges in this graph?