Solving a collective version of the vehicle routing problem

user_10816937 0
Viewed 150

I'm having troubles with finding an algorithm for the following problem:

In an undirected weighted graph with weights w there needs to be one package delivered from s to t. All nodes of the graph count as station. Each station has a specific type of vehicles with a given speed v and a traveling distance d. The vehicles need to work collective to deliver the package. So if a vehicle of current traveling distance 10 travels along an edge of weight 4, the traveling distance will be shortened to 6. Vehicles have to stop at a station, if they can't travel along a whole edge. The package can be handed over at any station.

I have to find the fastest possible path (by optimizing distance / speed)to deliver the package from s to t .

I've been looking through a lot of scientific papers with many versions of the vehicle routing problem, but it can't find one that deals with my problem.

I tried solving this with a modified version of djikstra by using edgeweights of w/v, but I don't know, when to mark a node as visited. I would be happy if someone has an idea for an algorithm how to solve the problem.

dijkstra graph-theory algorithm
1 Answers

I would codify a "state" as

  • node n with the package
  • time at which it arrived there
  • speed & range of car that you used to get there

The starting state is package at s, time 0, car from s with full range. To find successor states to a given state, you would follow this logic:

  • for each e, an outgoing edge from n; and only if the current car's range is sufficient, create 2 new successor states, n1 and n2, with
node[n1] = node[n2] = target[e]
time[n1] = time[n2] = time[n] + length[e] / car_speed[n]
car_speed[n1] = car_speed[n]
car_range[n1] = car_range[n] - length[e]
car_speed[n2] = target[e].car_speed
car_range[n2] = target[e].car_range

You then use A* on this, using time as cost and a suitable heuristic, and find the optimal route & time at the end. Since I am unsure of the best heuristic here (time is distance/speed, but speed varies by car...), you may use a null heuristic, which may expand more nodes than usual, but will never overestimate.

The idea is that there are two ways to proceed from each node that you reach: switch the car or keep the one you arrived on. Since you don't know what the best decision is, you test both and see which works out better.

Memory-wise, assuming that you are only interested in the minimum time to reach the goal, and that your chosen heuristic is either null or both admissible and consistent, you only need to keep at most 2*V open states for a graph with V nodes -- as already-visited nodes will never need to be visited again (mark them somewhere to avoid re-processing them if reached again), and old states can therefore be discarded with no ill effects.

[in the previous version, I was mixing up cost and heuristic; I have edited to clarify that I recommend a null heuristic and time-as-cost]

user_154720
Related