adding gas station to the VRP problem

[issacch...@gmail.com]

I want to plan the gas stations into the vehicle routing problem. 

1: Vehicle has a variable called fuelLevel that decreases linearly as distance travelled 

2: The fuelLevel will go back go full level after visiting a gas station.

3: Vehicles should visit a gas station before it goes down to zero.

4: A gas station can be visited by all vehicles for many times in a day. 

1 and 2 can be implemented with the help of shadow variable but 3 and 4 are not that straightforward. Could you give me some clues of how to build this domain model? 

Thanks,

Isaac

[Geoffrey De Smet]

With kind regards,
Geoffrey De Smet

On 11-02-15 08:36, issacch...@gmail.com wrote:

I want to plan the gas stations into the vehicle routing problem.

I presume you already have time windows.

1: Vehicle has a variable called fuelLevel that decreases linearly as distance travelled

You might be able to improve that estimate: city distance at 30km/h uses more fuel than country-side distance at 120km/h, per km.
I know GraphHopper provides distance and time for point-to-point route, maybe it can estimate fuel consumption too.

2: The fuelLevel will go back go full level after visiting a gas station.

3: Vehicles should visit a gas station before it goes down to zero.

Presuming you can somehow estimate the drainage of a gas station:
- for every standstill at a gas station, check if the time between this refueling and the last one wasn't too long.
- for every gas station at the end of the planning window, check if the time from the last refueling and the window end wasn't too long.

4: A gas station can be visited by all vehicles for many times in a day.

Time windows are needed of course.

So the issue: how many entities to make per gas station...
You could do a ceiled (= pessimistic) estimate, but then you'd force 4 stops as a gas station that might be doable with 3 stops.
To fix that, you 'd like to use nullable=true, but that isn't supported yet work with chained variables.
The typical workaround for that is a "dummy vehicle" to collect entities which should have the variable as null
in combination with score rules that are smart enough not to apply on the dummy vehicle (such as distance traveled cost).

1 and 2 can be implemented with the help of shadow variable but 3 and 4 are not that straightforward. Could you give me some clues of how to build this domain model? 

Thanks,

Isaac

--
You received this message because you are subscribed to the Google Groups "OptaPlanner development" group.
To unsubscribe from this group and stop receiving emails from it, send an email to optaplanner-d...@googlegroups.com.
To post to this group, send email to optapla...@googlegroups.com.
Visit this group at http://groups.google.com/group/optaplanner-dev.
For more options, visit https://groups.google.com/d/optout.

[issacch...@gmail.com]

Hi Geoffrey,

There could a score trap in your advices on my question 4: To use dummy vehicles to collect those gas stations. 

To allow vehicles travel more distance (so as to pick up more customers, and consider there is a cost of using an extra vehicle, which favors less vehicles used), a vehicle has to pass a gas station to fuel up. But that may require a composite (coarse-grained) move here that

1st: move a gas station entity to a chain (say begins with vehicle V1)

2: move more customers to V1 if these moves are acceptable considerting and distance, time and other costs like using one less vehicle.

But the 1st move can not be accepted due to increased distance cost because gas stations were ignore in distance calculation when they are assigned to a dummy vehicle.

I think we can create some composite move factories to provide that kinds of moves, but this approach can be time-consuming. Worst of all, it does not sound elegant to me :). Maybe implement some smart score rules to get out of this trap?

Would really appreciate if you could enlighten me more on this issue. 

Thanks,

Isaac

[Geoffrey De Smet]

Sounds like a subchain move or a tailChange move (which included in tailSwap moves).

Suppose you have these 2 chains:
  Vehicle1 - A - B - C - GasStation - D - E - GasStation - F - G - H
  Vehicle2 - X - Y - Z
Then a tailSwapMoveSelector (new in 6.2.0.Final - refactoring of the 2 opt experiment in the CR's)
can move the "GasStation - F - G - H" chain at the end of Vehicle2, in 1 move:
  Vehicle1 - A - B - C - GasStation - D - E
  Vehicle2 - X - Y - Z - GasStation - F - G - H

A subchain change move can even move the "GasStation - D - E" part.
Now this sounds better because every tailSwap is also a possible subchain move.
But don't presume you need to have every special move to get out of local optima,
otherwise you might as well be using Hill Climbing instead of Late Acceptance or Tabu Search.
My VRP use case benchmarks show that tailSwapMoves (which are faster) out pace subchainChange/Swap moves in best score when scaling up.
In your use case, run the benchmarker to see which move selector works best.

PS: Also try NearbySelection (which regretably doesn't work on subchain moves yet in 6.2).
  http://www.optaplanner.org/blog/2015/01/27/ScalingVehicleRoutingAndTSPWithNearbySelection.html

With kind regards,
Geoffrey De Smet

[issacch...@gmail.com]

Thank you for your reply. Maybe I was not clear on the descriptions of my problem. The problem is the solver has no incentive to move gasstation from the chain A (dummy vehicle) to the targeted chain C as the first step, then the seconds step, which moves the tail of chain B to Chain C, can not be performed due the the gas level constraints.

I have built a moveIteratorFactory to perform both steps in a single move to solve this problem (it seems to be solved, still examinating the results). 

[eshv...@gmail.com]

Hey Isaac,

Any chance you can post your custom move factory or at least describe how you implemented it? I have a similar problem and want to avoid completely reinventing the wheel!

Thanks