Review of the Literature on Heuristic Algorithms for Solving Routing Problems

by

Review of the Literature on Heuristic Algorithms for Solving Routing Problems

S.no

Title

Authors/year

Constraints

Objectives

Method

Instances

Size and results

1

Heuristic Algorithms for Solving the Generalized Vehicle Routing

Problem

P.C. Pop, C. Pop Sitar, I. Zelina, V. Lupse, C. Chira

2011

Combinatorial optimization problems can be generalized in a natural way by considering a related problem relative to a given partition of the nodes of the graph into node sets, while the feasibility constraints are expressed in terms of the clusters. In this way, it is introduced the class of generalized combinatorial optimization problems. In the literature one finds generalized problems such as the generalized minimum spanning tree problem [15], the generalized traveling salesman problem, the generalized vehicle routing problem, the generalized (subset) assignment problem, etc.

Perhaps the most natural heuristic for the GVRP is the famous Nearest Neighbour algorithm

(NN). In this algorithm the rule is always to go next to the nearest as-yet-unvisited customer

subject to the following restrictions: we start from the depot, from each cluster is visited exactly

one vertex (customer) and the sum of all the demands of the current tour (route) does not exceed

the capacity of the vehicle Q. If the sum of all the demands of a current tour (route) exceeds the

capacity of the vehicle then we start again from the depot and visit next the nearest customer

from an unvisited yet cluster. If all the clusters are visited, then the algorithm terminates.

A collection of routes traversing exactly one city from each cluster in the constructed order

represents the output of the algorithm.

Combinatorial optimization is a lively field of applied mathematics, combining techniques from combinatorics, linear programming, and the theory of algorithms, to solve optimization problems over discrete structures. The study of combinatorial optimization owes its existence to the advent of modern digital computer. Most currently accepted methods of solution to combinatorial optimization problems would hardly have been taking seriously 30 years ago, for the simple reason that no one could have carried out the computations involved. Moreover, the existence of digital computers has also created a multitude of technical problems of a combinatorial character.

Two fundamental goals in computer science are finding algorithms with provably good run

times and with provably good or optimal solution quality. A heuristic is an algorithm that

abandons one or both of these goals; for example, it usually finds pretty good solutions, but there

is no proof the solutions could not get arbitrarily bad; or it usually runs reasonably quickly, but

there is no argument that this will always be the case. Heuristics are typically used when there

is no known method to find an optimal solution, under the given constraints (of time, space etc.)

or at all.

Several families of heuristic algorithms have been proposed for the classical VRP, see for

example Laporte et al. [9]. These can be classified into two main classes: classical heuristics and

metaheuristics. Most standard construction and improvement procedures in use belong to the first class.

These methods performs a relatively limited exploration of the solution space and

generally produce good quality solutions in reasonable computational times

The Generalized Vehicle ...