Fine-Tune Scheduler for Large Scale Problem Instance
- Go to Benchmarks tab.
- Double-click one problem instance, i.e. RC2_8_6 problem instance which has 800 customers.
- Go to Default Scheduler Library in Scheduler tab.
- Double-click one scheduler method, i.e. Clark & Wright Savings scheduler method.
- Take note of the caption title: VRPTW: Instances(RC2_8_6)(Clark & Wright Savings)
- Click Schedule button to run Clark & Wright Savings solution method on RC2_8_6 problem instance as shown in Figure.
As expected, Clark & Wright Savings solves the large scale problem instance almost in less than one second. However, the solution quality is 329853 in terms of total routing time which is inferior.
- Repeat step 3 to 6 to run SAM solution method on RC2_8_6 problem instance.
Based on the solution generated by SAM, it is found that SAM takes significantly more time although it can solve with much better solution. This is because large neighbourhood and computation required searching alternative solutions within such a neighbourhood. There are two ways to speed up SAM scheduler and other more powerful and complex schedulers.
First approach is to subclass VRPTWRoute class and implement near-const-time saving computation for making a move to alternative solution. However, this approach is not easy for programmer who does not have sufficient insight into saving computation in VRPTW.
Second approach is through parameter fine-tuning of SAM scheduler, which makes very little effort.
- Double-click SAM scheduler method in Scheduler tab.
- Algorithm View tab will be automatically activated.
- Configure properties of SAM scheduler in Property accordion of Algorithm Editor for large scale VRP as shown in Figure:
EnableMemesWithBestAcceptance = FALSE
Search Intensity Unit = 1
NeighbourhoodRelativeSize = 0.005 - Alternatively, Light Search Mode = TRUE instead of the above configuration.
- Click Schedule button to run SAM solution method on RC2_8_6 problem instance.
It is observed that the search is much faster on large scale problem instance after the initialization. However, solution improvement is slower. In Figure above, SAM runs 55 iterations in just 14 seconds and obtains the route solution with total route time of 260689 which is better than Clark & Wright Savings.
Light Search Mode is one extreme in which SAM uses very little local search power. However, it can be seen that solution quality is not as good. Therefore, one way to tune SAM or other powerful schedulers is to adjust EnableMemesWithBestAcceptance, Search Intensity Unit and NeighborhoodRelativeSize.
|
Algorithm Properties |
Description |
|
EnableMemesWithBestAcceptance |
It will make meme pool generate memes which search current neighbourhood but only accept the best alternative move which is expensive |
|
Search Intensity Unit |
Increment in terms of search iterations by a meme in the meme pool |
|
NeighborhoodRelativeSize |
It determines how big the neighbourhood is to search in a single iteration |
|
Value is between 1 and entire neighbourhood |