Originally posted by: JorisK

I am trying to solve a vehicle routing problem though CP. Unfortunately, even for very small instances, no provable optimal solution can be found. I was wondering whether someone could give some feedback, e.g.:

• Is the model good, or would you rather model the problem differently
• Are there additional redundant constraints I should include?
• Alternative techniques I could try to speed up my CP model?

Problem description (vehicle routing problem):

• Assign service jobs to vehicles
• Sequence all service jobs assigned to a vehicle. The sequence must start and end with special dummy jobs (resp. 'startJob' and 'endJob'.
• Each service job has a resource demand. Vehicles have a finite capacity Q. Special resupplyJobs can be executed by a vehicle. The sum of demands of consecutive service jobs cannot exceed the vehicle's capacity; when a vehicle runs out of capacity, it must resupply before it can do more service jobs. So a vehicle schedule looks like: [startJob, serv1, serv2,..., resupply, serv14, serv15,..., endJob]. There are no limitations on how often a vehicle can resupply.
• Resupply jobs are associated with a location. At each of these locations, multiple resupply jobs are available.
• Between each pair of jobs, a setup time (>=0) is defined. Moreover, each service job can be executed in 2 modes. The mode does NOT affect the resource requirements, but does affect the setup time. That is, the setup time between a pair of jobs j1, j2 is dependent on the mode each of these jobs is executed.
• objective: minimize sum of setup times

Here is an outline of how I modeled this in CP optimizer 12.6.3, (java interface):

Variables:

1. Interval variables Job_i for every service job i.
2. Optional Interval (assignment) variables Job_i_Mode_j_Vehic_k, for every service job i, mode j in {1,2}, vehicle k.
3. Optional Interval variables ResupplyJob_l_loc_i, for the ith resupply job available at location l
4. Optional Interval (assignment) variables ResupplyJob_l_loc_i_vehic_k, for the ith resupply job available at location l, vehicle k.
5. Interval StartJob
6. Interval EndJob_k for every vehicle k.

All jobs have a fixed processing time, i.e. the length of all the intervals is fixed; there are no earliest start/latest end restrictions for the intervals. Consequently, a solution to this problem is obtained when:

1. the presence status of all variables if fixed.
2. all precedence relations between jobs assigned to the same vehicle have been determined.

Constraints (simplified notation):

//Each service job must be executed in exactly one mode and assigned to exactly 1 vehicle:
alternative(Job_i, Job_i_Mode_j_Vehic_k) for all i

//Each resupply job can be assigned to at most 1 vehicle:
alternative(ResupplyJob_l_loc_i, ResupplyJob_l_loc_i_Vehic_k) for all l, i

//Resupply jobs at a given location are identical, so we can enforce an ordering on them:
presenceOf(ResupplyJob_l_loc_(i+1)) implies presenceOf(ResupplyJob_l_loc_(i)) for all l, i=1,2,...

//Objective:
minimize sumOfSetupTimes

for every vehicle k:
  
  //Cumul function managing the vehicles resource (Q=capacity of vehicle, d_i=resource demand of job i):
  cumul_k=stepAtStart(startJob, Q) - stepAtStart(Job_i_Mode_j_Vehic_k, d_i) + stepAtStart(ResupplyJob_l_loc_i_vehic_k, 0, Q)
  //Enforce resource constraint:
  0 <= cumul_k <= Q

  //Sequencing:
  seq_k=SequenceVar(startJob, endjob_k, Job_i_Mode_j_Vehic_k, ResupplyJob_l_loc_i_vehic_k)
  noOverlap(seq_k, setupTimes_k)
  first(seq_k, startJob)
  last(seq_k, endJob_k)

  //Objective
  for every job j:
    sumOfSetupTimes += cp.element(setupTimes_k, typeOfNext(seq[k], j, LAST, ABSENT));

To strengthen the model, I have added the following constraints:

//A vehicle should never perform 2 resupply jobs consecutively, i.e. there must be at least one service job in between a pair of resupply jobs
for every vehicle k, resupply job j:
  cp.element(jobType_k, typeOfNext(seq[k], j, LAST, ABSENT)) != resupply_job_type

//Bounds can be computed on the total number of resupply jobs performed by all vehicles.
LB <= precenceOf(ResupplyJob_l_loc_i) <= UB

//Link start and end of interval variables (technically the actual start/end times of the variables are irrelevant as they do not affect the objective function or any of the constraints)
startOf(StartJob)=0
for every vehicle k, job j:
  startOf(j)=endOfPrevious(seq_k, j, LAST, ABSENT) + cp.element(setupTimes_k, typeOfPrevious(seq[k], j, LAST, ABSENT))

1. For an instance small instance with 9 service jobs, 9 optional resupply jobs, and 1 vehicle, CP optimizer does find a (known) optimal solution, but fails to prove optimality (I let it run for 2h).
2. For larger instances I obviously don't expect a proof of optimality, but I'm hoping to boost the quality of the solutions found by CP optimizer
3. I tried setting DefaultInferenceLevel or SequenceInferenceLevel to extended. With DefaultInferenceLevel=extended, the optimal solution could be found more quickly, but even my smallest instance could not be solved to optimality.
4. I tried to set a search phase on the sequence variables: IloSearchPhase searchPhase=cp.searchPhase(seq); This did not have a positive impact either.

Originally posted by: PhilippeLaborie

Hi Joris,

Given the objective function (it is a sum) and the production/consumption aspects of the problem (which do not results in a tight constraint propagation), I'm not too surprised that CPO cannot prove optimality, even for small instances. 

Now, finding good quality solutions is of course a different topic. What happens with your current model on larger problems? Does it have difficulties even finding a feasible solution? Or is it that a feasible solution is found quickly but it is of bad quality and then the search does not improve it fast enough? 

I'm also not surprised that the search phase on the sequence does not really help here because there are in general multiple vehicles (sequences) and the search phase will treat them one by one.

Could you show a search log for a reasonably large instance (without the search phase on the sequences and with Workers=1) ? 

Maybe one thing you could try on your model is to model the re-supplying activities slightly differently by considering them from the viewpoint of the vehicle rather than from the view point of the re-supplying location. For each vehicle, you would pre-define a set of optional re-supplying intervals no matter their location (used in the cumul function) and each of these interval would define an alternative with the set of re-supplying at a given location (used in the sequence like in your current model). That would allow factorizing the stepAtStart(ResupplyJob_l_loc_i_vehic_k, 0, Q) and may help. 

You could also try a search phase to first fix the visits and let the search insert the re-supplying activities when needed (assuming it propagates enough).

Also, if for a given vehicle you have much less re-supplying activities than the number of visits, maybe you can think of alternative models where you pre-define some sub-sequences of vehicle visits (separated by re-supplying activities).