On Solving Constrained Routing Problems
by
Haldun Süral
Middle East Technical University
In this talk,
we focus on the routing problems based on the Traveling Salesman Problem (TSP),
and show a problem hierarchy that describes relationships between TSP and these
problems. In these problems, there are “delivery customers” demanding goods
from depot and “pickup customers” sending goods to depot. Different approaches
may exist for incorporating pickups with deliveries. The objective is to
minimize the cost of the tour that visits the customers. We first briefly
examine the solution methods that have been motivated by the conventional TSP
solution approaches and then consider the evolutionary algorithms (EA) in order
to analyze the adaptability of an EA, originally designed for TSP, to the
constrained routing problems. This effort includes commenting on the importance
of feasibility with respect to side constraints. Computational results are
provided.