Download Implementing a Time Optimal Task Sequence For Robot

Certain algorithms exist that can help the search not to get stuck in local optima, rather
they guide the search out of the local neighbourhood in different ways. These algorithms are called meta-heuristics. Two interesting meta heuristics are tabu search [7]
and simulated annealing [9] which have both been used on VRPs with good results.
Constraint-based local search [27] is a concept of combining the speed and power of
local search with the ease of modelling in constraint programming, see Section 3.5.4
below. Constraint-based local search has been applied to the vehicle routing problem
with good outcome [11, 20].
3.5.4
Constraint Programming
Constraint programming is a paradigm that is further described in Section 4. Constraint programming has proven to be a helpful tool in solving VRPs because of the
number of real-world side constraints that appear when working with real problems.
The strength of constraint programming in this case is the ability to with relative ease
incorporate side constraints into a model and the checking of these constraints ensures
that a solution is feasible [15].
Constraint programming performs a systematic search and is normally required to explore each possible solution in a predefined order. The search process and checking
of constraints sometimes make constraint programming a slower approach than nonsystematic approaches, unless it is hybridised with other methods, as in Section 3.5.5
below. This is a matter of trade-off that has to be made when selecting constraint
programming as a tool to solve the vehicle routing problem.
However when dealing with rich VRPs constraint programming has been shown to be
efficient in reducing the number of candidate solutions to evaluate since it guarantees
that the solutions returned all satisfy the constraints of the problem [20].
3.5.5
Large Neighbourhood Search and Other Hybrid Methods
A common way to solve the VRP is by hybrid methods, combining techniques to find
better solutions. In this way all the strengths of the techniques can be utilised to find a
near-optimal solution fast and with reasonable certainty that it will be feasible.
Similar to the local search approach, Large Neighbourhood Search (LNS) is a technique that uses meta-heuristics to improve a current solution. Instead of using smaller
moves like those in local search, the LNS approach is aimed at gradually improving
a solution by alternately destroying (removing variable assignments) parts of the current solution and repairing it (assigning new values) using the systematic search of
constraint programming. The heuristics used in LNS are such that they guide the algorithm in these two steps by telling how the current solution is to be destroyed and how
to rebuild the next solution [20].
The principle behind LNS is that searching a larger neighbourhood around any current solution will result in local optima that are of high quality; however the searching
of a larger neighbourhood is often more time consuming than the smaller neighbourhoods defined by the local search operators since increasing the neighbourhood size
also increases the possible ways a new solution can be constructed [20].
18