Solving vehicle routing problems using multipleant colonies and deterministic approaches

In the vehicle routing problem with time windows VRPTW, there arc two main objectives. The primary objective is to reduce the number of vehicles, the secondary one is to minimise the total distance travelled by all vehicles. This thesis describes some experiments with multiple ant colony and deterministic approaches. For that, it starts explaining how a double ant colony system called DACS 01 with two colonies has the advantage of using the pheromone trails and the XCHNG local search and the ability of tackling multiple objectives problems like VRPTW. Also, it shows how such DACS system lacks vital components that make the performance as comparable and competitive with that of the well-known VRPTW algorithms. Therefore, the inclusions of components, like a triple move local search, a push-forward and pushbackward strategy PFPBS, a hybrid local search HLS and a variant of a 2-0pt move, improve the results very significantly, compared to not using them. Furthermore, it draws the attention to an interesting discovery, which suggests that if a DACS system uses ants that arc more deterministic, then that system has the ability to bring performance that is better than that of another DACS system with pheromone ants. Consequently, the interesting discovery has motivated the author to investigate a number of SI1- Like deterministic approaches, which most of them depend on capturing under-constrained tours and removing them using a removing heuristic that uses the hybrid local search HLS. Some of these SI1-Like approaches show signs of the ability of improving the average, best and worst case performances of DACS systems on some problem set cases, if they are merged with such systems. Of course, this casts some doubt on whether the usc of pheromone trails, which is a distinctive feature of multiple ant-colony systems in the research literature, is really so advantageous as is sometimes claimed. Experiments are conducted on the 176 problem instances with 100, 200 and 400 customers of Solomon [1], Ghering and Homberger [2] and [3]. The results shown in this thesis are comparable and competitive to those obtained by other state-of-the-art approaches