Searching

[DumRat]

I've asked this Q couple of times before but didn't get an answer (Or I didn't get it.). Here goes again. Glad if anyone can help me out.

Well, there are these bunch of school children who want to go to school. They are in different groups, in different places, in different numbers. (i.e one place has 3 children, another 2, another 5, etc.). There is this school bus, which has to drop each and every one of these children at the school. The only trouble is that the fuel consumption of the bus is proportional to the number of children onboard. Come up with the most fuel-efficient way of doing this. For ease we can assume that the bus can only drop children at the school and not anywhere else. Can anyone tell me a way to solve this? Thank you.

[weaknessforcats]

I can provide help with a specific problem but I do not provide solutions.

Read the posting guildelines before making a post.

This forum for C/C++ questions only.

I will move this to the Games and Puzzles forum.

[DumRat]

Yep, I understand that. But I don't want solutions, I only want to find out how to approach the problem so I can make the algorithm myself. A few keywords may even help - I can google them. I'd be really glad if anyone can help. Thanks.

[bartonc]

Yep, I understand that. But I don't want solutions, I only want to find out how to approach the problem so I can make the algorithm myself. A few keywords may even help - I can google them. I'd be really glad if anyone can help. Thanks.

How 'bout "Genetic Algorithm Tutorial" or some such search keywords?

[JosAH]

I've asked this Q couple of times before but didn't get an answer (Or I didn't get it.). Here goes again. Glad if anyone can help me out.

Well, there are these bunch of school children who want to go to school. They are in different groups, in different places, in different numbers. (i.e one place has 3 children, another 2, another 5, etc.). There is this school bus, which has to drop each and every one of these children at the school. The only trouble is that the fuel consumption of the bus is proportional to the number of children onboard. Come up with the most fuel-efficient way of doing this. For ease we can assume that the bus can only drop children at the school and not anywhere else. Can anyone tell me a way to solve this? Thank you.

This is a VRP (Vehicle Routing Problem) which is more difficult that a TSP
(Traveling Saleman Problem). If there are not many pick-up locations and not
may delivery locations (schools) the problem boils down to:

1) let p_ij be the pick-up locations for i in [1, n]
2) let d_j be the delivery locations for j in [1,m]

Select the cheapest permutation of of the two sets above such that p_ij < d_j,
i.e. kids are picked up from location p_ij before destination location d_j is
reached. A complete enumeration over all the permutations will find the cheapest
route. Especially the constraint mentioned above will cut deeply into the problem
size. A recursive backtracking algorithm will do if n and m are quite small.

If the capacity of the bus is also limited (which it probably is), that constraint
will even cut more into the size of the problem. If you pick up all or none of the
kids for a certain delivery location you have another cut point.

kind regards,

Jos

[Motoma]

Great analysis Jos, but with a couple of assumptions (based on how the problem was posed in this thread) it can be greatly simplified.

If we assume that the bus only makes one trip to pick up all students, and that there is ample room on the bus, we can turn the problem into a variation on the Dijkstra's Shortest Path. By running the problem in reverse (starting out with a full bus), and determining the weight of each node by considering the number of students on the bus, you can come to a quicker (albeit less general) solution.

[JosAH]

Great analysis Jos, but with a couple of assumptions (based on how the problem was posed in this thread) it can be greatly simplified.

If we assume that the bus only makes one trip to pick up all students, and that there is ample room on the bus, we can turn the problem into a variation on the Dijkstra's Shortest Path. By running the problem in reverse (starting out with a full bus), and determining the weight of each node by considering the number of students on the bus, you can come to a quicker (albeit less general) solution.

No you can never reduce it to a simple Dijkstra algorithm with a cost function
that is both depending on the distance traveled plus the number of students on
the bus. (fuel consumption depends on the 'pay' load). And would it be reasonbable
to pick up all the payload first and then deliver everything? I guess not (depending
on the loations of the delivery points).

kind regards,

Jos

[Motoma]

No you can never reduce it to a simple Dijkstra algorithm with a cost function
that is both depending on the distance traveled plus the number of students on
the bus. (fuel consumption depends on the 'pay' load). And would it be reasonbable
to pick up all the payload first and then deliver everything? I guess not (depending
on the loations of the delivery points).

kind regards,

Jos

I'm going to whip up some code tonight and see if I can work something out :)
Been great discussing this with you Jos, hopefully I will be able to back up my assertions tomorrow :P

[JosAH]

I'm going to whip up some code tonight and see if I can work something out :)

That's the spirit; I'll keep on nitpicking then just to preserve the 'balance' ok? ;-)

Been great discussing this with you Jos, hopefully I will be able to back up my assertions tomorrow :P

Nice and complicated problems always induce nice and more complicated
discussions. Especially when I'm involved ;-) I wish there were more of those
discussions around.

kind regards,

Jos

[Motoma]

That's the spirit; I'll keep on nitpicking then just to preserve the 'balance' ok? ;-)



Nice and complicated problems always induce nice and more complicated
discussions. Especially when I'm involved ;-) I wish there were more of those
discussions around.

kind regards,

Jos

Sorry to have questioned you Jos, the restrictions I have placed on this reduce the problem to a Traveling Salesman problem with a weight function. I guess I wasn't thinking it through earlier today.

For some reason I was thinking that by starting at the end of the trip, we could devise a greedy algorithm to assess the depth of the node. I neglected to acknowledge that simply touching each node was not enough; you need to travel through each one to reach the end.

[JosAH]

Sorry to have questioned you Jos, the restrictions I have placed on this reduce the problem to a Traveling Salesman problem with a weight function. I guess I wasn't thinking it through earlier today.

For some reason I was thinking that by starting at the end of the trip, we could devise a greedy algorithm to assess the depth of the node. I neglected to acknowledge that simply touching each node was not enough; you need to travel through each one to reach the end.

No need to apologize; those VRPs are nasty and tricky. They're indeed similar
to TSPs with a lot of irregular, incoherent constraints. In case of school buses
(or UPS parcel services etc.) there are capacity constraints w.r.t. to the bus or
truck itself (1000 students in a bus?), the order of the p_ij and d_j (a bus won't
drive (in)directly to school d_j when not at least one student p_ij is on the bus).

Additional constraints could be road capacity constraints (a 40 tons truck won't
go well on a dusty or wet dirtroad etc.) My bet for this particular problem would
be to apply a "3-Opt". Start with the following route:

G p_11 p_21 ... p_nm d_1 d_2 ... d_m G

i.e. pick up all the students p_ij and deliver them to the schools d_j. G is the
garage where the bus starts and ends it (circular) trip. Given this circle with
all the nodes; select three edges in the trip and name the trip parts A, B and C.

The entire current trip is ABC, now rearrange it as ACB, (note that the other
four permutations are circular identical to one of the permutations ABC or ACB).

If ACB is a better route, and it is feasible, keep it and try again for all possible
triples of edges. If no better route can be found, stop. Usually this produces
fairly nice routes (read: near optimal) and it's quite fast.

kind regards,

Jos