0

I have the following CVRPTW problem and I'm trying to find a good solution with OptaPlanner. Time is in hh:mm:ss format.

My DRL file is like this. Moreover I defined also a hard contraint relative to the arrival before ready time. My solver configuration is like this, with the difference of the termination tag:

<termination>
    <terminationCompositionStyle>OR</terminationCompositionStyle>
    <maximumSecondsSpend>10</maximumSecondsSpend>
    <scoreAttained>0hard/-750000soft</scoreAttained>
</termination>

This is the problem statement:

PROBLEM STATEMENT:
CustID  ReadyTIME   DueTIME     ServiceDUR  DEMAND
1       20:38:18    20:44:18    00:05:00    2   
2       20:20:53    20:26:53    00:05:00    4   
3       20:51:39    20:57:39    00:05:00    3   
4       20:20:18    20:26:18    00:05:00    6   
5       20:34:15    20:40:15    00:05:00    5   
6       20:21:40    20:27:40    00:05:00    10

I have 2 vehicles with both a capacity of 10 items and 1 depot.

This is the solution (customers grouped by vehicle and sorted by arrival time):

Vehicle 1   Capacity 10 - from Depot [1]
[6]     D: 10   Ar.T: 20:21:40  Prev.D: 00:02:21    Next.D: --:--:--

Vehicle 2   Capacity 10 - from Depot [1]
[4]     D: 6    Ar.T: 20:20:18  Prev.D: 00:01:08    Next.D: 00:02:21
[2]     D: 4    Ar.T: 20:27:42  Prev.D: 00:02:24    Next.D: 00:03:38
[5]     D: 5    Ar.T: 20:36:03  Prev.D: 00:03:21    Next.D: 00:02:09
[1]     D: 2    Ar.T: 20:43:26  Prev.D: 00:02:23    Next.D: 00:07:23
[3]     D: 3    Ar.T: 20:55:40  Prev.D: 00:07:14    Next.D: --:--:--

(D = demand, Ar.T = arrival time, Prev.D = distance from previous location, Next.D distance from next location)

As you can see vehicle 2 have to transport 6+4+5+2+3=20 items, which is greater than the capacity. I don't understand why the solver suggest me this solution if there's a hard contraint relative to the capacity in the configuration.

Considering my rules, this is not an acceptable solution. Am I missing something? Isn't there a condition where the solver provides no solution? Is it contemplated a "solver failed" termination?

user2664655
  • 251
  • 1
  • 3
  • 9

1 Answers1

0

Correct if I am wrong, but you have:

  • a total demand of 30 (6+4+5+2+3+10)

  • a total capacity of 20 (2 vehicles with 10 each)

It's impossible to transport 30 items when your trucks can only transport 20 items. There is no feasible solution (so OptaPlanner delivers the best infeasible solution it finds).

Note: If the same vehicle can be used multiple times, add extra Vehicle instances and add a constraint to penalize the usage of multiple Vehicle instances with the same license plate.

Geoffrey De Smet
  • 26,223
  • 11
  • 73
  • 120
  • It's interesting to note that sometimes easy to prove infeasibility (such as in this dataset). But often it is not (and proving infeasibility is np-complete too). For example presume 3 demands (each of demand 6) with 2 vehicles (both of capacity 10). Even though `3 * 6 < 2 * 10`, it's not feasible: no vehicle can hold more then 1 item, but here is 1 item more than vehicles. – Geoffrey De Smet Oct 08 '13 at 18:02
  • I was assuming that OptaPlanner allows the usage of the same vehicle multiple times, so this is a wrong assumption. You suggest to add vehicle instances, but new instances have different IDs, right? So, in order to contemplate multiple-usage, should I model the problem as if I have more than 2 vehicles? – user2664655 Oct 08 '13 at 19:14
  • yes, the clean way would be to rename `Vehicle` to `VehicleTrip` and then add `Vehicle` again (and link every `VehicleTrip` to 1 `Vehicle. Then add a soft constraint to minimize the number trips per vehicle (squaring the count number of trips helps there). – Geoffrey De Smet Oct 08 '13 at 19:24
  • Your suggestion is helpful, but not so easy to understand. It would be interesting to have an example, maybe in the next release :) – user2664655 Oct 08 '13 at 19:39
  • Anyway I'm confused, because replace `Vehicle` with `VehicleTrip` does not guarantee that different trips of a single Vehicle are planned in separated time slots (not overlapping) – user2664655 Oct 08 '13 at 20:19
  • Good point - I forgot that you have Time Windows too. For the arrivalTime to work properly, you 'll need to keep 1 chain per Vehicle (even if it returns multiple times to the depot to reset it's capacity). Look at [this question](http://stackoverflow.com/questions/19080537/bicycle-messenger-tsppd-with-optaplanner) for inspiration on how to lower the capacity's constraint granularity to part of the chain (from a depot until the next time it returns to the depot). – Geoffrey De Smet Oct 09 '13 at 06:02
  • I read carefully the question you quoted, I'm sorry but I really didn't understand what to do. May you explain a bit more the solution you mentioned, please? I don't understand which are components to modify and how – user2664655 Oct 09 '13 at 11:39