Machine Learning and AI with Simple Python and Matlab Scripts

17GAs for Route Optimization

17.1 Introduction

In this chapter, we present another important application of GAs, namely the route optimization problem, where a set of nodes interconnected with segments with different cost values are to be covered with minimum cost. We can visualize this problem as follows: we are given a set of cities and we need to visit all of them such that the total length of the route is a minimum. If the cost is defined as the time to travel between cities, then the goal is to visit the cities in minimum time. This problem is known in computer science as the travelling salesman problem (TSP), where a salesman needs to visit each city only once, starting and returning to the same one [122]. Requirements that the salesman can visit each city only once and that the total length (or its equivalent cost) of the entire trip must be minimized make the travelling salesman class of problems a formidable challenge. Their solution complexity grows as the factorial of the number of cities and the connections between them.

Optimization problems for engineering tasks are often complex and frequently need to determine the most effective ordering of a sequence of actions to accomplish a given set of goals. Consider a delivery company that dispatches a fleet of hundreds of trucks to distribute packages to a set of locations every morning. Each truck starts at a base location, makes multiple stops during the day and returns to the base at the end of its shift. The goal ...