IBM Support

Improvement Heuristics

Question & Answer


Question

Improvement Heuristics

Answer

Improvement Heuristics

You can use the following improvement heuristics to refine theresults of your optimization run:
  • Neighborhoods which are refinement methods that modify the orderin which stops are performed.
  • Meta-heuristics which define the search framework used to refinethe first solutions.
    Note: If you choose one improvement heuristicyou must also choose the other heuristic.

When you use these improvement heuristics the optimization runusually takes longer to finish. You can test these heuristics anddecide whether the improved results justify the additional run time.

Neighborhoods

Neighborhoods define a setof solution changes representing alternative moves that can be takenduring optimization. Neighborhoods are classified into three groups:
  • Solution changes that modify only one route such as Or Opt orTwo Opt.
  • Solution changes that allow modifications between routes suchas Relocate or Cross.
  • Solution changes that control whether stops are performed or notsuch as Add/Drop or Performed Pair.
You can choose one or more of the following options. Select thecheck box for each heuristic you want the optimizer to use.
HeuristicDescription

Add/Drop

The optimizer removes an LTL shipment froma truckload to reduce the total distance of the route. The optimizermay be able to assign this LTL shipment to a different truckload.

Hereis an example of how the Add/Drop heuristic works:
  • The optimizer removes an LTL shipment from a truckload whichreduces the distance of the route.
  • The optimizer may be able to assign this LTL shipment to a differenttruckload.

Exchange

The optimizer swaps stops between two routes.This change reduces the total distance of the two routes.

Or Opt

The optimizer changes a single route by re-arrangingmore than two stops. These changes reduce the total distance of theroute.

Two Opt

The optimizer makes two changes to a singleroute. These changes reduce the total distance of the route.

Relocate

The optimizer moves an LTL shipment fromone route to another route. This change reduces the total distanceof the two routes.

Cross

The optimizer swaps the shipments at thebeginning or end of two routes. This change reduces the total distanceof the two routes.

Merge Relocate

The optimizer merges pickup and deliverypairs from multiple routes and relocates them into a single route.

FP Relocate

The optimizer moves LTL shipments from oneroute to a new position in another route reducing the total distanceof the two routes.

Performed Pair

The optimizer modifies a solution by addinga pair of "unperformed" stops to the route. For each vehicle routein which the pair is inserted the optimizer tries every combinationof positions for the two visits.

Meta-Heuristics

Meta-heuristics providean advanced search framework that the optimizer uses in conjunctionwith the selected neighborhoods to further analyze and improve yourtruckload routes. You can choose one of the following options:
Guided Local SearchDescription

Guided Local Search

Here is how this meta-heuristic works:
  1. The optimizer searches for truckload routes that can be improvedusing "penalty criteria" to judge the efficiency of each route.
  2. The optimizer re-arranges stops to improve the routes that aremost inefficient.

A Guided Local Search may increase the cost of a specifiedshipment but will lower the cost of the overall route.

Improve Local Minimum

The optimizer analyzes the truckload routesthat the run created. The optimizer looks for ways to change the routesand improve the projected truckload savings. Within the context ofthe selected Neighborhood Improvement Heuristics the optimizer considersany moves that will make the total solution less expensive.

Thisis the simplest meta-heuristic.

Guided Tabu Search

The optimizer searches for ways to improvethe truckload routes blending Guided Local Search and Tabu Searchtechniques. Using this meta-heuristic:
  • The tabu lists keep track of the routes that have already beenanalyzed and the route changes that the optimizer has already made.
  • The optimizer can avoid these routes as it searches for additionalroute improvements.
  • The optimizer uses "penalty criteria" to judge the efficiencyof each route and re-arranges stops to lower the overall cost ofthe solution.
Tip: The Guided Tabu Search meta-heuristiccan often produce high-quality solutions in fewer iterations thaneither a Guided Local Search or Tabu Search.

Tabu Search

The optimizer searches for ways to improvethe truckload routes. This search uses "tabu" (or taboo) lists thatare stored in the optimizer server memory:
  • The tabu lists keep track of the routes that have already beenanalyzed and the route changes that the optimizer has already made.
  • The optimizer can avoid these routes as it searches for additionalroute improvements.
Note: The Tabu Search heuristic works best if you choosetwo or three neighborhood heuristics. The search does not work asefficiently if you choose all the neighborhood heuristics.
Parent topic: Defining Optimization Heuristics
"

[{"Business Unit":{"code":"BU055","label":"Cognitive Applications"},"Product":{"code":"SS73G6","label":"Sterling Total Payments for Financial Services"},"Component":"","Platform":[{"code":"PF025","label":"Platform Independent"}],"Version":"All Versions","Edition":"","Line of Business":{"code":"","label":""}}]

Document Information

Modified date:
08 December 2018

UID

ibm10755605

Page Feedback