Max-Min Ant System (MMAS) for Vehicle Routing Problem with Time Windows

Abstract

This paper introduces a modified Max-Min Ant System (MMAS) algorithm to solve the Vehicle Routing Problem
with Time Windows (VRPTW). The VRPTW can be described as the problem of designing least cost routes
from one depot to a set of geographically scattered points. The routes must be designed in such a way that
each point is visited only once by exactly one vehicle within a given time interval, all routes start and end at the
depot, and the total demands of all points on one particular route must not exceed the capacity of the vehicle.
Many meta-heuristic approaches like Simulated Annealing (SA), Genetic Algorithm (GA), Tabu Search (TS), a
hybrid Ant System algorithm for VRP (HAS-VRP), a multiple Ant Colony System to vehicle routing problem with
time windows (MACS-VRPTW) and a hybrid Ant System algorithm and Simulated Annealing (IACS-SA). In this
research, we proposed a MMAS-VRPTW algorithm with local search approaches. Experiments on various
aspects of Solomon’s 56 benchmark problems are other meta-heuristic and show that our results are
competitive.