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.