Error message

  • Deprecated function: implode(): Passing glue string after array is deprecated. Swap the parameters in drupal_get_feeds() (line 394 of /home3/memec59d/public_html/lescas/includes/common.inc).
  • Deprecated function: The each() function is deprecated. This message will be suppressed on further calls in menu_set_active_trail() (line 2405 of /home3/memec59d/public_html/lescas/includes/menu.inc).

Fine-Tune Scheduler for Large Scale Problem Instance

  1. Go to Benchmarks tab.
  2. Double-click one problem instance, i.e. RC2_8_6 problem instance which has 800 customers.
  3. Go to Default Scheduler Library in Scheduler tab.
  4. Double-click one scheduler method, i.e. Clark & Wright Savings scheduler method.
  5. Take note of the caption title: VRPTW: Instances(RC2_8_6)(Clark & Wright Savings)
  6. Click Schedule button to run Clark & Wright Savings solution method on RC2_8_6 problem instance as shown in Figure.

Solution Generated by Clark & Wright Savings Solution Method on RC2_8_6 Problem Instance

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.

  1. 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.

  1. Double-click SAM scheduler method in Scheduler tab.
  2. Algorithm View tab will be automatically activated.
  3. 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
  4. Alternatively, Light Search Mode = TRUE instead of the above configuration.

Parameter Fine-Tuning of SAM Solution Method in Algorithm View

  1. Click Schedule button to run SAM solution method on RC2_8_6 problem instance.

Results of SAM Solution Method on RC2_8_6 Problem Instance after Parameter Fine-Tuning

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